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

Question

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

问题：

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

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

从这些字母到基-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) =

​

​

操作员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

您的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;
}

或@durron597建议的更有表现力的实现。

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;