C:反向数的和

Question

所以我想解决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.

现在在ML中如果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中获取一组数字的算法,检查它们的某些内容然后继续下一组数字...？

Answer 1

令输入中的位数为 N（跳过任何前导零后）。然后 - 如果我下面的分析是正确的 - 该算法仅需要 ≈ N 字节的空间和运行 ≈ N/2 次的单个循环。不需要特殊的“大数”例程或递归函数。

观察结果

2 个数字中较大的一个数字之和必须是：
(a)有 N 位数字，或者
(b)有 N-1 位数字（在这种情况下，总和中的第一个数字必须是 1）

可能有一种方法可以将这两种情况作为一个处理，但我还没有考虑过。在最坏的情况下，对于以 1 开头的数字，您必须运行以下算法两次。

另外，在添加数字时：

• 单独 2 位数字的最大和为 18，这意味着最大传出进位为 1
• 即使传入进位为 1，最大和为 19，因此最大进位仍为 1
• 传出进位与传入进位无关，除非 2 位数字之和恰好为 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& co.）

根据我们是在上述情况 (a) 还是 (b) 中，我们已经知道 c5 的值。

现在我们运行一个循环，从两端获取数字对并向中心移动。我们将当前迭代中比较的两个数字称为 H 和 L。因此循环将进行比较：

• XS⊕c4和XS
• YS⊕c3和YS⊕c1
• ETC。

如果位数是奇数（如本例所示），则循环后将有最后一段逻辑用于中心数字。

正如我们将看到的，在每一步中，我们都已经计算出cout需要从 H 发出的进位以及cin进入 L 的进位。（如果您打算用 C++ 编写代码，实际上不要使用cout并cin作为变量名！）

最初，我们直接清楚地知道cout = c5和cin = 0，并且XS = L（L⊖cin一般使用）。

现在我们必须确认 H 与或XS⊕c4是同一个数字。如果不是，则没有解决方案 - 退出。XSXS⊕1

但如果是的话，到目前为止一切都很好，我们可以计算c4 = H⊖L。现在有2种情况：-

• XS <= 8，因此xc = cout
• XS 是 9，在这种情况下xc = 0（因为 2 位数字加起来不能等于 19），并且 c5 必须等于 c4（如果不等于，则退出）

现在我们知道了xc和XS。对于下一步，cout = c4and cin = xc（一般来说，您还需要考虑 cin 的先前值）。现在当比较YS⊕c3和时YS⊕c1，我们已经知道c1 = cin和 可以计算了YS = L⊖c1。其余逻辑如前所述。

对于中心数字，在循环外检查一次 ZS 是否是 2 的倍数。

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

希望这能奏效，尽管如果有一个更简单、更优雅的解决方案，我也不会感到惊讶。

附录

这个问题告诉你，编程不仅仅是知道如何旋转循环，你还必须在详细的逻辑分析后找出最高效和最有效的循环。输入数量的巨大上限可能会迫使你思考这一点，而不是轻易通过暴力方法逃脱。这是开发可扩展程序的关键部分的一项基本技能。