使用递归将特定进制的数字转换为十进制数

Question

我的任务是创建一个递归方法makeDecimal，当传入一个由字符串表示的数字和它的进制时，将该数字转换为十进制。您需要使用方法 Integer.parseInt(str)。(提示：使用子字符串.) 此方法接受一个 String 并返回它的整数形式。

例如，Integer.parseInt("21"); 将返回 int 类型的 21。

以下是 makeDecimal 的一些示例：

makeDecimal("11", 2) 将返回 3。

makeDecimal("100", 4) 将返回 16。

这是我尝试写的代码：

public static double makeDecimal(String number, int base){
    int len = number.length();
    double f = 0;

    if(len <= 0)
        return 0;
    else{
        makeDecimal(number,base);

        double temp = Integer.parseInt(number.substring(len - 1, len + 1));
        f = f + temp * Math.pow(3, len-1);
    }

    len--;
    return f;
}

然而，我遇到了“溢出错误”，我不知道它是否被正确编写。

- Maria

---

makeDecimal(number,base); - 这将使用与之前完全相同的参数进行递归调用，没有任何更改。这意味着它永远不会结束，因为它总是以相同状态进入方法。您需要确保在进行调用时传递不同的值。 - resueman

Answer 1

您正在使用完全相同的参数进行递归。结果，调用将重复进行递归，直到堆栈溢出。这不是递归应该工作的方式。相反，您需要找出如何在当前调用中完成问题的一部分，然后递归执行一个更小的问题。

在您的代码中，甚至不清楚您正在使用什么逻辑。（计算3^len-1的目的是什么？）请尝试以下方法：

- 如果输入字符串的长度为0，则答案为0（您已经做对了这一部分） - 否则，取最后一个数字并在当前基础上解析它。然后，答案就是该值加上base乘以除输入的最后一个数字外的所有值的价值。（提示：这是使用递归的好地方。） - 您应该能够将该描述转换为适当的方法调用和使用substring()。

哦，还有一件事：在这里使用double值没有理由。只需始终使用int变量即可。您将不需要Math.pow()。

- Ted Hopp

---

如果基数是16，会怎样？ - nbro

@nbro - 然后您解析最后一位数字，基数为16。关键是最后一位数字是一个字符串，并且您已经给出了要使用的基数来解析它。想法是始终使用Integer.parseInt()的两个参数版本，并使用您所给定的任何基数。 - Ted Hopp

Answer 2

这里是使用递归、substring和Integer.parseInt的最简单解决方案：

public int makeDecimal(String value, int base) {
    // exit from recursion
    if (value.length() < 1) 
        return 0;

    //parsing last character of string
    int charValue = Integer.parseInt(value.substring(value.length() - 1), base);

    //calling recursion for string without last character
    return makeDecimal(value.substring(0, value.length() - 1), base) * base + charValue;
} 

- Andrey Tretyak

---

这是一个不错的解决方案，因为你不需要创建表格，例如我所创建的，因为我没有意识到（或者没有想到）你可以使用 parseInt 方法。无论如何，你不需要 result，可以简单地返回 0。事实上，在任何地方都没有修改它：唯一使用它的地方是如果长度小于 1，即它为 0（在这种情况下无论如何都不可能是其他情况）。 - nbro

@nbro 这是最简单的解决方案，但如果您手动解析它（使用创建的表或不使用），您将获得更多控制，并且可以使用其他字符来解析例如基数大于36的内容。 - Andrey Tretyak

是的，那也是真的。 - nbro

@nbro 是的，你说得对，结果完全没有用，它是从之前的变量中留下来的，感谢你指出这个问题。 - Andrey Tretyak

Answer 3

编辑： 起初，我忽略了递归对于这个解决方案的必要性，所以我的原始答案没有它可能会比下面的方法多四个字符。

以下是使用递归且不使用 substring 和 Math.pow 的解决方案：

public double makeDecimal(String value, int base) {
    makeDecimal(value, base, value.length() - 1);
}

public double makeDecimal(String value, int base, int index) {
    double result = 0;

    if (index < 0)
        return result;

    double charValue = 0;
    char currentChar =  values.get(Character.toUpperCase(value.charAt(index));
    if (currentChar >= 0 && currentChar <= '9') {
       charValue = currentChar - '0';
    } else if (currentChar >= 'A' && currentChar <= 'Z') {
        charValue = currentChar - 'A';
    } else {
        throw new InvalidValueException("Unsupported character '" + currentChar + "'.");
    }

    if (charValue >= base) {
        throw new InvalidValueException("Wrong character '" + currentChar + "' for base '" base + "'.");
    }

    return makeDecimal(value, base, index - 1)) * base + charValue;
} 

原始回答： 对于任何从2到36的进制，类似这样的代码都应该可以使用：

private Map<Character, Integer> getCharValues(int base)
{
    Map<Character, Integer> values = new HashMap<Character, Integer>();
    for (int i = 0; i < base; i++){
        if (i < 10) {
            values.put('0' + i, i);
        } else if (i < 36) {
            values.put('A' + i - 10, i);
        } else {
            throw new InvalidValueException("Base '" + base + "' not supported");
        }
    }
    return values;
}

public double makeDecimal(String value, int base)
{
    Map<Character, Integer> charValues = getCharValues(base);
    double result = 0;
    for (int i = 0; i < value.length(); i++){
        result = result * base + charValues.get(Character.toUpperCase(Character.toUpperCase(value.charAt(i))));
    }
    return result;
}

如果您需要使用超过36个字符的基数，可以在方法getCharValues中扩展字符集。此外，最好不要每次创建HasMap，而只需将其存储到最大基数中，并在字符值超出给定基数时抛出异常。

- Andrey Tretyak

---

如果你想让它处理小写十六进制数字的话，你需要再加些工作。（顺便说一下，我不是那个给你点踩的人。） - Ted Hopp

这不使用递归！我是提到原因的投票者。 - nbro

@nbro 感谢指出，我完全忽略了递归是强制性的。 - Andrey Tretyak

Answer 4

这是我在Python中编写原型后的解决方案（如果您感兴趣，我也可以包含Python源代码）：

import java.util.HashMap;
import java.util.Map;

public class MakeDecimal {

    public static final Map<Character, Integer> alphabet = buildAlphabetTable();

    public static void main(String[] args) {

        // System.out.println(alphabet);
        System.out.println(makeDecimal("af10bb1", 16));
    }

    // pos refers to the position of the character in the string.
    // For example, if you have the following binary string 100
    // then 1 at the left is at position 2, 
    // the 0 in the middle is at position 1,
    // and the right most 0 is at position 0 
    // (you start counting from the right side).
    // In general, you would convert that string in the following way:
    // 2^2 * 1 + 2^1 * 0 + 2^0 * 0 = 4

    // If the base was n, then you would have
    // first * n^{pos + "length of string - 1"} + ... + penultimate * n^{pos + 1} + last * n^{pos}
    // Note that pos starts from 0.
    private static int makeDecimal(String s, int base, int pos) {
        if (s.length() == 0) {
            return 0;
        } else {
            int last = (int) Math.pow(base, pos) * alphabet.get(s.charAt(s.length() - 1));
            return makeDecimal(s.substring(0, s.length() - 1), base, pos + 1) + last;
        }
    }

    public static int makeDecimal(String s, int base) {
        if (s.length() == 0) {
            return 0;
        }

        if (base < 2 || base > 36) {
            throw new IllegalArgumentException("not base >= 2 and base <= 36");
        }

        return makeDecimal(s.toLowerCase(), base, 0);
    }


    // Creates a table that maps characters to their decimal value
    // the characters can be also '0' or '2' (or any other character number)
    // or they can be a character of the English alphabet
    private static Map<Character, Integer> buildAlphabetTable() {
        Map<Character, Integer> a = new HashMap<>(36);

        int i = 0;

        for (char c = '0'; c <= '9'; c++, i++) {
            a.put(c, i);
        }

        for (char c = 'a'; c <= 'z'; c++, i++) {
            a.put(c, i);
        }

        return a;
    }

}

我的解决方案基于以下帖子，你一定要阅读它来更新有关如何在不同进制之间进行转换的想法。

http://www.purplemath.com/modules/numbbase.htm

它不接受小于2或大于36的基数。它还处理当您传递大写英文字符时。

- nbro