9

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

问题：

您必须通过将 ID 号插入校验和来验证 ID 号。需要将 ID 转换为 base-10，然后才能将其插入算法。ID 号以字母开头：

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

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

第2部分：

获得 base-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) =

f(n1, n2)

g(n) =

g(n)

操作员 X：

操作员 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*'s 是我应该得到 0 的地方，但我得到了不同的值。我的校验和算法在哪里搞砸了？

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

4

2 回答 2

7

错误 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运算中。正如您在问题的注释中看到的那样，他们说：

请注意，-4 mod 5 = 1。

所以复制粘贴 hte 运算符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 的答案。

于 2013-09-07T22:47:57.087 回答
3

你的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;
于 2013-09-07T23:19:40.310 回答