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

Question

我正在为比赛做一些练习题，我一整天都在研究这个算法。如果您想阅读整个问题 here是的，但我会给你一个简短的解释，因为这是一个很长的问题。

问题:

您必须通过将 ID 号插入校验和来验证 ID 号。在将 ID 插入算法之前，需要将 ID 转换为 base-10。 ID 号以字母开头:

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

我没有遇到从这些字母到 base-10 的转换问题，我的转换代码很好，所以我将向您展示问题的下一部分:

第 2 部分:

获得以 10 为基数的 ID 号码后，您需要将其插入以下算法:

注意:每个 ID 号码的长度必须为 8 位数字，0 将位于至少 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) =

运算符(operator) X:

我假设 mod 与我代码中的 % 相同，我不确定是否还有另一个 mod 操作我不是熟悉。

我的结构

这就是我决定要解决问题的方式:

1. 将 10 进制数转换为 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 的地方，但我得到的是不同的值。我的校验和算法哪里出了问题？

阅读所有这些内容后，请随时要求对我的代码的任何部分进行说明。

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)

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

要解决这个问题，您只需反转十进制值的 int 数组表示即可。

错误2

第二个错误是在模 5 运算中。正如您在问题注释中看到的那样，他们说:

Note that -4 mod 5 = 1.

所以复制粘贴 hte operator 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;
}

你会得到预期的结果。

这是修复了两个错误的结果:

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 的回答。