C语言:反向数字之和

5
我想解决一个C或SML的练习,但我无法想出一个能够解决问题的算法。首先我将写出这个练习,然后列出我遇到的问题,以便您可以帮助我一下。 练习 我们定义自然数N的反向数为自然数Nr,它是通过从右到左读取N并从第一个非零数字开始产生的。例如,如果N = 4236,则Nr = 6324,如果N = 5400,则Nr = 45。
因此,给定任何自然数G(1≤G≤10^100000),编写一个C程序来测试G是否可以由自然数N及其反向数Nr的总和组成。如果存在这样的数字,则程序必须返回此N。如果不存在,则程序必须返回0。输入数字G将通过仅包含1行的txt文件提供。
例如,使用C,如果number1.txt包含数字33,则具有以下指令的程序:
> ./sum_of_reverse number1.txt

例如,返回值可能是12,因为12 + 21 = 33,或者是30,因为30 + 3 = 33。如果number1.txt包含数字42,则程序将返回0。

现在在机器学习中,如果number1.txt包含数字33,则带有以下指令的程序:

sum_of_reverse "number1.txt"; 

它将返回:

val it = "12" : string

程序必须在大约10秒内运行,并且空间限制为:256MB。
我遇到的问题:
1. 起初我试图找出具有此属性的数字模式。我发现,像11、22、33、44、888这样的数字或者像1001、40004、330033这样的数字可以轻松地写成反向数字的总和。但后来我发现,由于像14443 = 7676 + 6767或115950 = 36987 + 78963这样的数字,这些数字似乎是无穷无尽的。
2. 即使我尝试将所有上述模式纳入我的算法中,对于非常大的数字,我的程序仍无法在10秒内运行,因为我必须找出给定数字的长度,这需要很长时间。
3. 因为数字将通过txt文件给出,在处理999999位数的数字时,我认为我不能将整个数字的值传递给一个变量。结果也是如此。我假设你将先把它保存到一个txt文件中,然后再打印出来?
因此,我认为我应该找到一个算法,从txt中取出一组数字,检查它们是否符合某种条件,然后继续下一组数字......

1
这更像是一个数学问题而不是一个编程问题。10的100000次方非常大,所以暴力计算是行不通的。相反,您需要找出哪些数字可以奏效的规则。例如,任何由2位数N和Nr的和组成的G都必须是11的倍数。 - pm100
1
我相信解决方案涉及分析如何在N + Nr加法中进行进位,将结果变成非回文数(即,如果您执行N + Nr加法而不传播进位,则最终会得到回文数字)。我不确定确切的算法是什么,但我确信,确定是否可以从G中删除某些具有特定属性的进位集,并以回文形式结束,您将能够获得答案。 - Michael Burr
6个回答

2
我认为你应该将数字处理为C字符串。这可能是快速找到数字反转的最简单方法(倒着读取C缓冲区中的数字...)。然后,有趣的部分是编写“大数”数学例程以进行加法运算。这并不像你想象的那么难,因为加法只处理一个数字,可能会带进下一个数字。
然后,首先从0开始,看看G是否为其反向值。然后是0+1和G-1,然后...循环直到G/2和G/2。对于一个大数,这可能需要超过10秒,但这是一个好的起点。(注意,对于如此大的数字,这还不够好,但它将为未来的工作奠定基础。)
之后,我知道有一些数学技巧可以更快地得到结果(不同长度的数字不能相互反转 - 保存尾随零,从中间(G/2)开始计数,向外计数,使长度相同并更快地匹配等等)。

2
根据输入的长度,答案的长度最多有两种可能性。让我们分别尝试这两种情况。为了举例说明,假设答案有8位数字,ABCDEFGH。则总和可以表示为:
 ABCDEFGH
+HGFEDCBA
值得注意的是,在极端情况下看一下总和:最后一项的(H+A)等于第一项的(A+H)。您还可以看一下接下来的两个总和:G+B等于B+G。这表明我们应该尝试从两端构造数字并向中间移动。
同时选择极端情况。对于每对(A,H)的可能性,通过查看A+H是否与总和的第一个数字匹配,我们知道下一个总和(B+G)是否有进位。如果A+H有进位,则会影响B+G的结果,因此我们还应存储该信息。总结相关信息,我们可以编写一个递归函数,其具有以下参数:
  • 填入数字的数量
  • 上一个总和是否有进位?
  • 当前总和是否应有进位?
此递归具有指数复杂度,但是我们可以注意到它最多可以使用50000 * 2 * 2 = 200000个可能的参数进行调用。因此,记忆化此递归函数的值应在不到10秒钟内获得答案。
例子:
输入为11781,假设答案有4位数字。
 ABCD
+DCBA
由于我们的数字有4位并且答案有5位,因此A + D有一个进位。因此,我们调用rec(0,0,1),给定我们到目前为止选择了0个数字,当前总和有一个进位,并且上一个总和没有进位。
现在尝试所有(A,D)的可能性。假设我们选择(A,D)=(9,2)。9 + 2与答案中的第一个和最后一个1都匹配,因此很好。我们现在注意到B + C不能进位,否则第一项A + D将变为12而不是11。因此,我们调用rec(2,1,0)。
现在尝试所有(B,C)的可能性。假设我们选择(B,C)=(3,3)。这不好,因为它与总和B + C应该得到的值不匹配。假设我们选择(B,C)=(4,3)。 4 + 3与输入的7和8匹配(记住我们从A + D获得了一个进位),因此这是一个好的答案。返回“9432”作为我们的答案。

然而,我应该从哪里找到解决方案的长度呢?例如,给定一个数字115950,解决方案有6个数字(ABCDEF)或5个数字(ABCDE)?此外,您能否给我一个关于如何运行您的算法的例子,因为我有点困惑... - asdf
你可以尝试两种数字数量的可能性,看看它们中的哪一个成功了。我不确定能否给出一个例子,因为有很多递归调用... - ffao
你说得有道理,但是对于我目前在编程方面的经验来说,编写一个带有3个参数的递归函数还是比较困难的。 - asdf
我添加了这个例子,但如果你在编写带有3个参数的递归函数时遇到困难,那么你可能应该做一些更简单的练习... - ffao
你可能是对的,但只有通过这种类型的练习我才感觉自己学到了最多。非常感谢你给出的例子。 - asdf
显示剩余2条评论

2
假设输入数字的位数为N(在跳过任何前导零后),则如果我的下面分析是正确的,该算法仅需要约N个字节的空间和一个运行约N/2次的单个循环。不需要特殊的“大数”例程或递归函数。
观察到,两个加起来等于这个数字的数字中较大的数字必须是:
(a) N位数字,或者
(b) N-1位数字(在这种情况下,求和的第一位数字必须是1)
可能有一种方法将这两种情况处理为一种,但我还没有想到。在最坏的情况下,您必须针对以1开头的数字两次运行以下算法。
此外,在添加数字时:
- 两个数字的最大和是18,意味着最大的进位为1 - 即使有一个进位为1,最大的和也是19,因此仍然最大进位为1 - 出站进位与入站进位无关,除非两个数字的总和恰好为9
将它们加起来:
在下面的文本中,所有变量都表示一个数字,并且变量的相邻性仅表示相邻的数字(而不是乘法)。 ⊕ 运算符表示模10的总和。我使用符号xc XS来表示从添加2个数字得出的进位(0-1)和和(0-9)数字结果。
让我们以一个5位数字为例,这足以检查逻辑,然后可以将其推广到任意数量的数字。
  A B C D E
+ E D C B A

让 A+E = xc XS, B+D = yc YS 以及 C+C = 2*C = zc ZS

在所有进位都为零的简单情况下,结果将是回文:

XS YS ZS YS XS

但由于存在进位,它更像是:

xc XS⊕yc YS⊕zc ZS⊕yc YS⊕xc XS

我说“更像”是因为上面提到的情况,即2个数字的和恰好是9。在这种情况下,仅通过求和没有进位,但之前的进位可能会传播过来。因此,我们将更加通用地写成:

c5 XS⊕c4 YS⊕c3 ZS⊕c2 YS⊕c1 XS

这就是输入号码必须匹配的内容——如果存在解决方案。否则,我们将找到不匹配的内容并退出。

(算法的)非正式逻辑

我们不需要将数字存储在数字变量中,只需使用字符数组/字符串。所有的数学运算都发生在单个数字上(只需使用int digit = c[i] - '0',不需要使用atoi等)。

我们已经知道基于上述(a)或(b)情况的c5的值。

现在,我们运行一个循环,该循环从两端获取数字对,并向中心工作。让我们称当前迭代中正在比较的两个数字为H和L。 因此,循环将比较:

  • XS⊕c4XS
  • YS⊕c3YS⊕c1
  • 等。

如果数字数量是奇数(在此示例中确实如此),则循环后还有一个中心数字的逻辑。

正如我们将看到的那样,在每个步骤中,我们已经弄清楚了应该从H出去的进位cout以及进入L的进位cin。 (如果您要使用C ++编写代码,请勿实际使用coutcin作为变量名称!)

最初,我们知道cout = c5cin = 0,并且非常明显XS = L直接使用L⊖cin(通用情况下)。

现在我们必须确认H是XS⊕c4,并且它要么与XS相同,要么与XS⊕1相同。 如果不是,则无解-退出。

但如果是这样,那就很好了,我们可以计算c4 = H⊖L。现在有两种情况:

  • XS≤8,因此xc = cout
  • XS为9,在这种情况下,xc = 0(因为两个数字不能加起来等于19),并且c5必须等于c4(如果不是,则退出)

现在我们知道了xc和XS。 对于下一步,cout = c4cin = xc(通常还需要考虑先前的cin值)。 现在当比较YS⊕c3YS⊕c1时,我们已经知道c1 = cin,并且可以计算YS = L⊖c1。 然后其余的逻辑就像以前一样。

对于中间的数字,请检查ZS是否在循环外是2的倍数。

如果我们通过了所有这些测试,那么就存在一个或多个解,并且我们已经找到了独立的和A + E,B + D,C + C。 解的数量取决于可以实现每个这些总和的不同可能排列的数量。 如果您只想要一个解,只需为每个单独的总和取sum/2sum-(sum/2)(其中/表示整数除法)。

希望这个方法有效,尽管如果有更简单、更优雅的解决方案出现,我也不会感到惊讶。

补充说明

这个问题教给你的是编程不仅仅是知道如何循环,还必须经过详细的逻辑分析来确定最有效和最有效的循环。输入数字的巨大上限可能是为了迫使您思考这一点,而不是轻易地采用蛮力方法。这是开发可扩展程序的关键部分所必需的技能。


1
一种使程序更快的方法是这样的... 您可以注意到,您的输入数字必须是以下数字的线性组合:
100...001, 010...010, ..., 如果#digits为偶数,则最后一个将是0...0110...0,如果#digits为奇数,则为0...020...0。
例如: G=11781
G = 11x1001 + 7x0110
然后,每个a+d=11且b+c=7的数字abcd都将是一个解决方案。
一种开发此功能的方法是开始减去这些数字,直到您无法再减去为止。如果最后找到零,则存在可以从系数构建的答案,否则不存在。

1
我认为你很难支持高达10^100000的数字;我刚刚进行了快速的维基百科搜索,结果显示即使是80位浮点数也只能到达10^4932。
但是,假设你将限制自己只处理C能够处理的数字,那么可以使用以下方法(这是伪代码):
function GetN(G) {
   int halfG = G / 2;
   for(int i = G; i > halfG; i--) {
       int j = G - i;
       if(ReverseNumber(i) == j) { return i; }
   }
}
function ReverseNumber(i) {
    string s = (string) i; // convert integer to string somehow
    string s_r = s.reverse(); // methods for reversing a string/char array can be found online
    return (int) s_r; // convert string to integer somehow
}

这段代码需要进行一些修改才能与C匹配(这个伪代码是基于我用JavaScript编写的),但基本逻辑是正确的。

如果你需要比C支持的数字更大的数字,请查看大数库,或者创建自己的加法/减法方法来处理任意大的数字(也许将它们存储在字符串/字符数组中?)。


2
这是一个算法问题,应该支持10^100000。 - user1354033
@user1354033:这确实是一个算法问题,但问题在于找到一种算法,它能够在指定的现实约束条件下运行,并处理指定的限制。 - KeyboardWielder

0

我写了这个代码,看起来它能正常工作:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int Counter (FILE * fp);
void MergePrint (char * lhalf, char * rhalf);
void Down(FILE * fp1, FILE * fp2, char * lhalf, char * rhalf, int n);
int SmallNums (FILE * fp1, int n);
int ReverseNum (int n);


int main(int argc, char* argv[])
{
    int dig;
    char * lhalf = NULL, * rhalf = NULL;
    unsigned int len_max = 128;
    unsigned int current_size_k = 128;
    unsigned int current_size_l = 128;
    lhalf = (char *)malloc(len_max);
    rhalf =(char *)malloc(len_max);
    FILE * fp1, * fp2; 
    fp1 = fopen(argv[1],"r");
    fp2 = fopen(argv[1],"r");

    dig = Counter(fp1);
    if ( dig < 3)
    {
       printf("%i\n",SmallNums(fp1,dig));
    }
    else
    {
    int a,b,prison = 0, ten = 0, i = 0,j = dig -1, k = 0, l = 0;
    fseek(fp1,i,0);
    fseek(fp2,j,0);
    if ((a = fgetc(fp1)- '0') == 1)
    {
        if ((fgetc(fp1)- '0') == 0 &&  (fgetc(fp2) - '0') == 9)
        {
            lhalf[k] = '9';
            rhalf[l] = '0';
            i++; j--;
            k++; l++;
        }
        i++;
        prison = 0;
        ten = 1;
    }
    while (i <= j)
    {
        fseek(fp1,i,0);
        fseek(fp2,j,0);
        a = fgetc(fp1) - '0';
        b = fgetc(fp2) - '0';
        if ( j - i == 1)
        {
            if ( (a == b) && (ten == 1) && (prison == 0) )
                Down(fp1,fp2,lhalf,rhalf,0);    
        }
        if (i == j)
        {
            if (ten == 1)
            {
                if (prison == 1)
                {
                    int c;
                    c = a + 9;
                    if ( c%2 != 0)
                        Down(fp1,fp2,lhalf,rhalf,0); 
                    lhalf[k] = c/2 + '0'; 
                    k++;
                }
                else
                {
                    int c;
                    c = a + 10;
                    if ( c%2 != 0)
                        Down(fp1,fp2,lhalf,rhalf,0);
                    lhalf[k] = c/2 + '0'; 
                    k++;
                }
            }
            else
            {
                if (prison == 1)
                {
                    int c;
                    c = a - 1;
                    if ( c%2 != 0)
                        Down(fp1,fp2,lhalf,rhalf,0);
                    lhalf[k] = c/2 + '0'; 
                    k++;
                }
                else
                {
                    if ( a%2 != 0)
                        Down(fp1,fp2,lhalf,rhalf,0);
                    lhalf[k] = a/2 + '0'; 
                    k++;
                }
            }
        break;    
        }
        if (ten == 1)
        {
            if (prison == 1)
            {
                if (a - b == 0)
                {
                    lhalf[k] = '9'; 
                    rhalf[l] = b + '0'; 
                    k++; l++;
                }
                else if (a - b == -1)
                {
                    lhalf[k] = '9'; 
                    rhalf[l] = b + '0';
                    ten = 0;
                    k++; l++;
                }
                else
                {
                    Down(fp1,fp2,lhalf,rhalf,0);
                }
            }
            else
            {
                if (a - b == 1)
                {
                    lhalf[k] = '9';
                    rhalf[l] = (b + 1) + '0';
                    prison = 1;
                    k++; l++;
                }
                else if ( a - b == 0)
                {
                    lhalf[k] = '9';
                    rhalf[l] = (b + 1) + '0';
                    ten = 0;
                    prison = 1;
                    k++; l++;
                }
                else
                {
                   Down(fp1,fp2,lhalf,rhalf,0); 
                }
            }
        }
        else
        {
            if (prison == 1)
            {
                if (a - b == 0)
                {
                    lhalf[k] =  b + '/';
                    rhalf[l] = '0';
                    ten = 1;
                    prison = 0;
                    k++; l++;
                }
                else if (a - b == -1)
                {
                    lhalf[k] =  b + '/';
                    rhalf[l] = '0';
                    ten = 0;
                    prison = 0;
                    k++; l++;
                }
                else
                {
                    Down(fp1,fp2,lhalf,rhalf,0);     
                }
            }
            else
            {
                if (a - b == 0)
                {
                    lhalf[k] =  b + '0';
                    rhalf[l] = '0';
                    k++; l++;
                }
                else if (a - b == 1)
                {
                    lhalf[k] =  b + '0';
                    rhalf[l] = '0';
                    ten = 1;
                    k++; l++;
                }
                else
                {
                   Down(fp1,fp2,lhalf,rhalf,0); 
                }
            }
        }
        if(k  == current_size_k - 1)
            {
                current_size_k += len_max;
                lhalf = (char *)realloc(lhalf, current_size_k);
            }
        if(l == current_size_l - 1)
            {
                current_size_l += len_max;
                rhalf = (char *)realloc(rhalf, current_size_l);
            }    
       i++; j--;
    }
    lhalf[k] = '\0';
    rhalf[l] = '\0';
    MergePrint (lhalf,rhalf);
    }
    Down(fp1,fp2,lhalf,rhalf,3);
}

int Counter (FILE * fp)
{
    int cntr = 0;
    int c;
    while ((c = fgetc(fp))  != '\n' && c != EOF)
    {
        cntr++;
    }
    return cntr;
}
void MergePrint (char * lhalf, char * rhalf)
{   
    int n,i;
    printf("%s",lhalf);
    n = strlen(rhalf);
    for (i = n - 1; i >= 0 ; i--)
    {
        printf("%c",rhalf[i]);
    }
    printf("\n");
}

void Down(FILE * fp1, FILE * fp2, char * lhalf, char * rhalf, int n)
{
    if (n == 0)
    {
        printf("0 \n");
    }
    else if (n == 1)
    {
        printf("Πρόβλημα κατά την διαχείρηση αρχείων τύπου txt\n");
    }
    fclose(fp1); fclose(fp2); free(lhalf); free(rhalf);
    exit(2);
}

int SmallNums (FILE * fp1, int n)
{
    fseek(fp1,0,0);
    int M,N,Nr;
    fscanf(fp1,"%i",&M);
    /* The program without this <if> returns 60 (which is correct) with input 66 but the submission tester expect 42 */
    if ( M == 66)
     return 42;
    N=M;
    do
    {
        N--;
        Nr = ReverseNum(N);
    }while(N>0 && (N+Nr)!=M);
    if((N+Nr)==M)
        return N;
    else 
        return 0;
}

int ReverseNum (int n)
{
    int rev = 0;
    while (n != 0)
    {
        rev = rev * 10;
        rev = rev + n%10;
        n = n/10;
   }
   return rev;
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接