我的校验和算法有什么问题？

Question

我正在做一些比赛的练习题，我已经花费了一整天的时间在这个算法上。如果您想要阅读整个问题，请单击此处查看完整问题，但是因为这个问题有点长，所以我将给您一个简短的解释。

问题：

您需要通过将ID号码插入校验和来验证ID号码。在将其插入算法之前，需要将ID转换为10进制。 ID号码最初以字母开头：

Z = 0，Y = 1，X = 2，W = 3，V = 4

我不会从这些字母到10进制的转换中出现问题，我的转换代码很好，所以我将向您展示问题的下一部分：

第二部分：

在拥有您的10进制ID号码之后，您需要将其插入以下算法：

注意：每个ID号码必须为8位数字，如果不足8位，则在数字前加零。

checksum = F(0, d0) X F(1, d1) X F(2, d2) ...

所以简单来说：

checksum = F(n, dn) X F(n+1, dn) ...
where n is the index of the digit

在这里最重要的是，X并不是操作*（乘法）。X是它自己的操作，在后面定义。

注意：最显著的数字似乎是d7，但我不确定，问题对此并没有非常明确的说明。

---

以下是f(n1，n2)，g(n)和运算符X的定义：

f(n1，n2) =

g(n) =

运算符X:

我假设mod在我的代码中等同于%。如果还有其他我不熟悉的mod操作，请告知。

我的结构

这是我希望解决该问题的方法：

1. 将十进制数转换为int [8]
2. 将int [8]的每个数字通过f（n，dn）
3. 使用X运算符将它们合并在一起。

我的代码

以下是我的算法函数。如果它们有什么困惑的地方，我可以加上注释，但它们确实完全按照上述算法执行。

/*
 * This will return the checksum of the id.
 * Formula: F(0, d0) X F(1, d1) ...
 * 
 * F(n, dn) where n is the current index.
 * X != * (multiply)!! X is a defined operator
 */
public static int getChecksum(int[] id)
{
    int result = 0;

    for(int x = 0;x < id.length;x++)
    {
        if(x == 0)
            result = fOfxd(x, id[x]);
        else{
            result = opX(result, fOfxd(x, id[x]));
        }
    }

    return result;
}

public static int gOfx(int x)
{
    return GOFX[x];
}

public static int fOfxd(int x, int d)
{
    switch(x)
    {
        case 0:
            return d;
        case 1:
            return gOfx(d);
        default:
            return fOfxd(x - 1, gOfx(d));
    }
}

public static int opX(int num1, int num2)
{
    if(num1 < 5 && num2 < 5)
        return (num1 + num2) % 5;
    if(num1 < 5 && num2 >= 5)
        return (num1 + (num2 - 5)) % 5 + 5;
    if(num1 >= 5 && num2 < 5)
        return ((num1 - 5) - num2) % 5 + 5;
    return (num1 - num2) % 5;
}

public static final int[] GOFX = {1, 5, 7, 6, 2, 8, 3, 0, 9, 4};

现在，这是我的main(String args[])代码：

注意：你可以假设parseBase10和toArray函数已经正常工作。我已经用问题中的输入/输出示例进行了检查。

public static void main(String args[])
{
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    while(true)
    {
        int ids = 0; // how many ids are we checking?
        try
        {
            ids = Integer.parseInt(reader.readLine()); // get user input

            String[] list = new String[ids]; // will hold all of the ids

            for(int x = 0;x < list.length;x++)
                list[x] = reader.readLine(); // reads all of the ids we will be checking

            for(int x = 0;x < list.length;x++) // lets check the ids individually now
            {
                String stringID = list[x]; // the string representation of the id
                int base10 = parseBase10(stringID);
                int[] id = toArray(base10);
                int checksum = getChecksum(id);

                System.out.println(stringID);
                System.out.println(base10);
                System.out.println(Arrays.toString(id));
                System.out.println(checksum);

            }
        }catch(Exception e){e.printStackTrace();}
        break;
    }
}

想要自己编译吗？

这里是我完整的（未编辑过的）代码：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main 
{
    public static void main(String args[])
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        while(true)
        {
            int ids = 0; // how many ids are we checking?
            try
            {
                ids = Integer.parseInt(reader.readLine()); // get user input

                String[] list = new String[ids]; // will hold all of the ids

                for(int x = 0;x < list.length;x++)
                    list[x] = reader.readLine(); // reads all of the ids we will be checking

                for(int x = 0;x < list.length;x++) // lets check the ids individually now
                {
                    String stringID = list[x]; // the string representation of the id
                    int base10 = parseBase10(stringID);
                    int[] id = toArray(base10);
                    int checksum = getChecksum(id);

                    System.out.println(stringID);
                    System.out.println(base10);
                    System.out.println(Arrays.toString(id));
                    System.out.println(checksum);

                }
            }catch(Exception e){e.printStackTrace();}
            break;
        }
    }

    /*
     * This will return the checksum of the id.
     * Formula: F(0, d0) X F(1, d1) ...
     * 
     * F(n, dn) where n is the current index.
     * X != * (multiply)!! X is a defined operator
     */
    public static int getChecksum(int[] id)
    {
        int result = 0;

        for(int x = 0;x < id.length;x++)
        {
            if(x == 0)
                result = fOfxd(x, id[x]);
            else{
                result = opX(result, fOfxd(x, id[x]));
            }
        }

        return result;
    }

    public static int gOfx(int x)
    {
        return GOFX[x];
    }

    public static int fOfxd(int x, int d)
    {
        switch(x)
        {
            case 0:
                return d;
            case 1:
                return gOfx(d);
            default:
                return fOfxd(x - 1, gOfx(d));
        }
    }

    public static int opX(int num1, int num2)
    {
        if(num1 < 5 && num2 < 5)
            return (num1 + num2) % 5;
        if(num1 < 5 && num2 >= 5)
            return (num1 + (num2 - 5)) % 5 + 5;
        if(num1 >= 5 && num2 < 5)
            return ((num1 - 5) - num2) % 5 + 5;
        return (num1 - num2) % 5;
    }

    /*
     * This will convert a number to an array equivalent of that number
     * The result will be 8 digites long with leading 0's if possible.
     * 
     * EX:
     * 12345 = {0, 0, 1, 2, 3, 4, 5, 6}
     */
    public static int[] toArray(int value)
    {
        int result[] = new int[8];

        for(int x = result.length - 1;x >= 0;x--)
        {
            result[x] = value % 10;
            value /= 10;
        }

        return result;
    }

    /*
     * converts a String sequence and converts it to a base 10 equivalent.
     * Z = 0, Y = 1, X = 2, W = 3, V = 4
     * 
     * EX:
     * YY = 11(base-5) = 6(base-10)
     */
    public static int parseBase10(String string) throws Exception
    {
        int multiplier = 1;
        int result = 0; // in base 10

        for(int x = string.length() - 1;x >= 0;x--)
        {
            char letter = string.charAt(x); // the letter we are parsing
            int value = -1; // initial value, set to -1 to check for parsing error

            for(int y = 0;y < VALUES.length;y++)
                if(letter == VALUES[y])
                    value = y; // letter found in VALUES[]

            if(value == -1)
                throw new Exception("Could not parse: " + letter); // the specified letter was not found

            result += (multiplier * value);
            /* ^^ this moves the value to the correct digit place by using a multiplier:
             * EX:
             * 
             * current result: 45 (base-10)
             * new value to parse: 2 (base-5)
             * 45(base-10) + (2(base-5) * 25(base-10)) = 245 <-- correct output
             */

            multiplier *= 5; // sets up multiplier for next value
        }

        return result;
    }

    public static final char[] VALUES = {'Z', 'Y', 'X', 'W', 'V'};
    public static final int[] GOFX = {1, 5, 7, 6, 2, 8, 3, 0, 9, 4};
}

---

这是我输入的问题：

6
WYYXWVZXX
YWYWYYXWVZYY
YWYWYYXWVZYX
YYZWYYXWVZYX
YXXWYYXWVZXW
XYXWYYXWXYY

这是我的输出结果：

WYYXWVZXX
1274262
[0, 1, 2, 7, 4, 2, 6, 2]
2  *0*
YWYWYYXWVZYY
81352381
[8, 1, 3, 5, 2, 3, 8, 1]
0
YWYWYYXWVZYX
81352382
[8, 1, 3, 5, 2, 3, 8, 2]
4
YYZWYYXWVZYX
59868007
[5, 9, 8, 6, 8, 0, 0, 7]
0
YXXWYYXWVZXW
73539888
[7, 3, 5, 3, 9, 8, 8, 8]
5  *0*
XYXWYYXWXYY
22520431
[2, 2, 5, 2, 0, 4, 3, 1]
3  *0*

当你看到*0*时，我应该得到0，但我得到了不同的值。我的校验和算法出了什么问题？

阅读所有内容后，如果需要任何代码方面的澄清，请随时提问。

- John

---

这段代码太长了，可能不会引起太多关注（除非您发布赏金）。请缩小您的程序范围，并找到算法中未产生您期望的转换的具体步骤（例如，名称->数字部分是否有效？F(n, dn)？）。 - chrylis -cautiouslyoptimistic-

我认为一个好的建议是将其分解为单个步骤，并使用测试用例覆盖每个步骤。即，使用示例数据调用单个步骤并检查它们是否产生预期结果。 - Janis F

@John：欢迎来到调试复杂代码的世界。 - chrylis -cautiouslyoptimistic-

@chrylis 嗯，我已经尝试过了，这就是为什么我在寻求帮助 =) - John

取一个短的输入字符串W，手动计算期望值，与您代码的结果进行比较，如果不匹配，则需要检查更少的点，如果匹配，则只需添加另一个字母并重复。使用IDE调试器还可以在每个指令执行后“观察”变量的值，以便检查中间计算。我知道这不是对您提出问题所付出的努力的非常具体的答案，但论坛不能替代适当的调试（+1）。 - SJuan76

Answer 1

错误 1

这个错误很微妙。首先，在问题中数字的描述是：d7 d6 ... d1 d0，这意味着d0是十进制数的个位数。

然后，他们说F是左结合的，并描述该过程为：

F(0,d0) x F(1,d1) x F(2,d2) x ... x F(6,d6) x F(7,d7)

这意味着，您必须先将 d0 应用于运算符 F。但是，在创建 int 数组时，索引为 0 的元素是 d7，由于在这种情况下顺序很重要，因此会得到错误的结果。

要解决问题，您只需反转小数值的 int 数组表示。

第二个错误在模 5 运算中。正如您可以在问题的注释中读到的那样：

请注意，-4 mod 5 = 1。

因此，复制粘贴运算符 x 是一个错误。请将其更改为：

public static int opX(int num1, int num2)
{
    if(num1 < 5 && num2 < 5)
        return (num1 + num2) % 5;
    if(num1 < 5 && num2 >= 5)
        return (num1 + (num2 - 5)+5) % 5 + 5;
    if(num1 >= 5 && num2 < 5)
        return ((num1 - 5) - num2+20) % 5 + 5;
    return (num1 - num2 +10) % 5;
}

当你修复这两个bug后，你将得到预期的结果。

以下是修复了两个bug后的结果：

1274262
[2, 6, 2, 4, 7, 2, 1, 0]
0
YWYWYYXWVZYY
81352381
[1, 8, 3, 2, 5, 3, 1, 8]
0
YWYWYYXWVZYX
81352382
[2, 8, 3, 2, 5, 3, 1, 8]
1
YYZWYYXWVZYX
59868007
[7, 0, 0, 8, 6, 8, 9, 5]
0
YXXWYYXWVZXW
73539888
[8, 8, 8, 9, 3, 5, 3, 7]
0
XYXWYYXWXYY
22520431
[1, 3, 4, 0, 2, 5, 2, 2]
0

编辑

如果您需要更一般的BUG 2解决方案，请查看Martijn Courteaux的答案。

- Save

---

那么d0是算法中最重要的值吗？ - John

你也发现了mod的错误，但仍未修复它。在所有地方都加上20也不能解决问题。 - Martijn Courteaux

@MartijnCourteaux 在这种特定情况下是这样的，因为数字受模数限制。我会重新计算一下确保20足够 :) 我承认这不是一个优雅的解决方案。 - Save

取第一个案例：if(num1 < 5 && num2 < 5) return (num1 + num2) % 5; 带入 num1 = -100 和 num2 = -100。 - Martijn Courteaux

是的，我明白了。你说得对。得出这个结论需要一些思考和分析。（不过，当你发布错误1时，你已经得到了我的+1 :D） - Martijn Courteaux

Answer 2

您的mod逻辑有问题。该网站上写道：

请注意，-4％5 = 1。

在Java中，这是不正确的：(-4)％5 == -4。因此，请实现自己的mod（int a，int b）方法：

public static int mod(int a, int b)
{
    while (a < 0) a += b;
    while (a >= b) a -= b;
    return a;
}

< p > 或者像 @durron597 建议的那样，使用更高效的实现方式：< /p>

public static int mod(int a, int b)
{
    a %= b;
    return a < 0 ? a + b : a;
}

这非常重要，因为你可能会得到负数值
（例如：假设num1 = 5和num2 = 4）：

if(num1 >= 5 && num2 < 5)
    return ((num1 - 5) - num2) % 5 + 5;

- Martijn Courteaux

---

嗯，这很慢。为什么不使用 int temp = a % b; if(temp < 0) temp += b; return temp; 呢？尤其是如果 OP 想要具有竞争力的话！ - durron597

哈哈，我从来没有想过编辑输入参数。我写的所有代码都可以将每个方法参数设置为final :) - durron597

是的，我更喜欢这种方式，因为你可以避免不必要的堆栈推入/弹出。 - Martijn Courteaux