C:倒数之和 [英] C : Sum of reverse numbers

问题描述

所以我想解决用C或SML进行的练习，但我只是无法提出一种能做到这一点的算法.首先，我将编写练习，然后编写我遇到的问题，以便您可以对我有所帮助.

So I want to solve an exercise in C or in SML but I just can't come up with an algorithm that does so. Firstly I will write the exercise and then the problems I'm having with it so you can help me a bit.

锻炼

我们将自然数N的反数定义为自然数Nr，它是通过从第一个非零数字开始从右到左读取N产生的.例如，如果N = 4236，则Nr = 6324；如果N = 5400，则Nr = 45.

We define the reverse number of a natural number N as the natural number Nr which is produced by reading N from right to left beginning by the first non-zero digit. For example if N = 4236 then Nr = 6324 and if N = 5400 then Nr = 45.

因此，给定任意自然数G(1≤G≤10^ 100000)，请在C中编写一个程序，以测试是否可以通过自然数N及其反数Nr的和来产生G.如果有这样一个数字，则程序必须返回此N.如果没有，那么程序必须返回0.输入数字G将通过仅由1行组成的txt文件给出.

So given any natural number G (1≤G≤10^100000) write a program in C that tests if G can occur by the sum of a natural number N and its reverse Nr. If there is such a number then the program must return this N. If there isn't then the program must return 0. The input number G will be given through a txt file consisted only by 1 line.

例如，使用C，如果number1.txt包含数字33，则程序的指令为:

For example, using C, if number1.txt contains the number 33 then the program with the instruction :

> ./sum_of_reverse number1.txt

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

could return for example 12, because 12+21 = 33 or 30 because 30 + 3 = 33. If number1.txt contains the number 42 then the program will return 0.

现在在ML中，如果number1.txt包含数字33，则该程序的指令为:

Now in ML if number1.txt contains the number 33 then the program with the instruction :

sum_of_reverse "number1.txt"; 

它将返回:

val it = "12" : string

程序必须在大约10秒内运行，其空间限制为256MB

The program must run in about 10 sec with a space limit : 256MB

我遇到的问题

1. 起初，我试图找到模式，即带有此属性的数字.我发现像11,22,33,44,888之类的数字或像1001、40004、330033之类的数字都可以很容易地写成反向数字的总和.但是后来我发现这些数字似乎无穷无尽，因为例如14443 = 7676 + 6767或115950 = 36987 + 78963.

1. At first I tried to find the patterns, that numbers with this property present. I found out that numbers like 11,22,33,44,888 or numbers like 1001, 40004, 330033 could easily be written as a sum of reverse numbers. But then I found out that these numbers seem endless because of numbers for example 14443 = 7676 + 6767 or 115950 = 36987 + 78963.

即使我尝试将上述所有模式都包含在算法中，对于很大的数字，我的程序也不会在10秒内运行，因为我将不得不找到给定数字的长度，这会花费很多时间

Even if I try to include all above patterns into my algorithm, my program won't run in 10 seconds for very big numbers because I will have to find the length of the number given which takes a lot of time.

因为该数字将通过txt给出，所以如果是一个具有999999位数字的数字，我想我只是不能将这个整数的值传递给变量.结果相同.我假设您要先将其保存到txt，然后再打印出来??

Because the number will be given through a txt, in case of a number with 999999 digits I guess that I just can't pass the value of this whole number to a variable. The same with the result. I assume that you are going to save it to a txt first and then print it??

所以我假设我应该找到一种算法，该算法从txt中获取一组数字，检查它们是否有问题，然后继续进行下一组数字...?

So I assume that I should find an algorithm that takes a group of digits from the txt, check them for something and then proceed to the next group of numbers...?

推荐答案

让输入中的数字位数为N(跳过任何前导零之后). 然后-如果我的下面的分析是正确的-该算法只需要≈ N个字节的空间和一个运行&rox;的循环N/2次. 不需要特殊的大数"例程或递归函数.

Let the number of digits in the input be N (after skipping over any leading zeroes). Then - if my analysis below is correct - the algorithm requires only ≈ N bytes of space and a single loop which runs ≈ N/2 times. No special "big number" routines or recursive functions are required.

与该数字相加的2个数字中较大的一个必须是:
(a)有N位数字，或者
(b)具有N-1个数字(在这种情况下，总和的第一位必须为1)

The larger of 2 numbers that add up to this number must either:
(a) have N digits, OR
(b) have N-1 digits (in which case the first digit in the sum must be 1)

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

There's probably a way to handle these two scenarios as one, but I haven't thought through that. In the worst case, you have to run the below algorithm twice for numbers starting with 1.

此外，在添加数字时:

• 仅2位数字的最大和为18，表示最大外出进位为1
• 即使进位进位为1，最大和为19，所以最大进位仍为1
• 外出进位与外来进位无关，除非两位数的总和恰好是9时

在下面的文本中，所有变量都表示一个数字，并且变量的相邻性仅表示相邻数字( not 乘法). ⊕运算符表示总和模10.我使用符号xc XS表示加2位所得的进位(0-1)和总和(0-9)位.

In the text below, all variables represent a single digit, and adjacency of variables simply means adjacent digits (not multiplication). The ⊕ operator denotes the sum modulo 10. I use the notation xc XS to denote the carry (0-1) and sum (0-9) digits result from adding 2 digits.

让我们举一个5位数字的例子，它足以检查逻辑，然后可以将其推广为任意数量的数字.

Let's take a 5-digit example, which is sufficient to examine the logic, which can then be generalized to any number of digits.

  A B C D E
+ E D C B A

让A + E = xc XS，B + D = yc YS和C + C = 2 * C = zc ZS

Let A+E = xc XS, B+D = yc YS and C+C = 2*C = zc ZS

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

In the simple case where all the carries are zero, the result would be the palindrome:

XS YS ZS YS XS

但是由于携带，它更像是:

But because of the carries, it is more like:

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

我之所以说喜欢"，是因为上面提到的情况，其中2位数字的和正好是9.在那种情况下，和本身没有进位，但是先前的进位可以通过它传播.因此，我们将更加通用并编写:

I say "like" because of the case mentioned above where the sum of 2 digits is exactly 9. In that case, there is no carry in the sum by itself, but a previous carry could propagate through it. So we'll be more generic and write:

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

这是输入数字必须与之匹配的-如果存在解决方案.如果没有，我们将找到不匹配的内容并退出.

This is what the input number must match up to - if a solution exists. If not, we'll find something that doesn't match and exit.

我们不需要将数字存储在数字变量中，只需使用字符数组/字符串即可.所有的数学运算都用一位数字表示(只需使用int digit = c[i] - '0'，不需要atoi& co.)

We don't need to store the number in a numeric variable, just use a character array / string. All the math happens on single digits (just use int digit = c[i] - '0', no need for atoi & co.)

根据上述情况(a)或(b)，我们已经知道c5的值.

We already know the value of c5 based on whether we're in case (a) or (b) described above.

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

Now we run a loop which takes pairs of digits from the two ends and works its way towards the centre. Let's call the two digits being compared in the current iteration H and L. So the loop will compare:

• XS⊕c4和XS
• YS⊕c3和YS⊕c1
• 等

• XS⊕c4 and XS
• YS⊕c3 and YS⊕c1
• etc.

如果数字的位数为奇数(如本例所示)，则循环后将有最后一位逻辑用于中心数字.

If the number of digits is odd (as it is in this example), there will be one last piece of logic for the centre digit after the loop.

正如我们将看到的，在每个步骤中，我们都已经弄清楚了需要从H移出的进位cout和进入L的进位cin. (如果要使用C ++编写代码，请不要实际使用cout和cin作为变量名！)

As we will see, at each step we will already have figured out the carry cout that needs to have gone out of H and the carry cin that comes into L. (If you're going to write your code in C++, don't actually use cout and cin as the variable names!)

最初，我们知道cout = c5和cin = 0，并且很显然直接是XS = L(通常使用L⊖cin).

Initially, we know that cout = c5 and cin = 0, and quite clearly XS = L directly (use L⊖cin in general).

现在，我们必须确认H为XS⊕c4是与XS或XS⊕1相同的数字. 如果没有，则没有解决方法-退出.

Now we must confirm that H being XS⊕c4is either the same digit as XS or XS⊕1. If not, there is no solution - exit.

但是如果是这样的话，到目前为止一切都很好，我们可以计算出c4 = H⊖L.现在有两种情况:-

But if it is, so far so good, and we can calculate c4 = H⊖L. Now there are 2 cases:-

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

• XS is <= 8 and hence xc = cout
• XS is 9, in which case xc = 0 (since 2 digits can't add up to 19), and c5 must be equal to c4 (if not, exit)

现在我们知道xc和XS. 对于下一步cout = c4和cin = xc(通常，您还需要考虑cin的先前值). 现在，在比较YS⊕c3和YS⊕c1时，我们已经知道c1 = cin并可以计算YS = L⊖c1. 然后，其余逻辑将像以前一样.

Now we know both xc and XS. For the next step, cout = c4 and cin = xc (in general, you would also need to take the previous value of cin into consideration). Now when comparing YS⊕c3 and YS⊕c1, we already know c1 = cin and can compute YS = L⊖c1. The rest of the logic then follows as before.

对于中心数字，请在循环外检查ZS是否为2的倍数.

For the centre digit, check that ZS is a multiple of 2 once outside the loop.

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

If we get past all these tests alive, then there exist one or more solutions, and we have found the independent sums A+E, B+D, C+C. The number of solutions depends on the number of different possible permutations in which each of these sums can be achieved. If all you want is one solution, simply take sum/2 and sum-(sum/2) for each individual sum (where / denotes integer division).

希望这是可行的，尽管如果发现有一个更简单，更优雅的解决方案，我不会感到惊讶.

Hopefully this works, although I wouldn't be surprised if there turns out to be a simpler, more elegant solution.

这个问题告诉您编程不仅是要知道如何旋转一个循环，还需要在进行详细的逻辑分析后找出最有效的旋转循环.输入数字的巨大上限可能会迫使您考虑这一点，而不是通过强力手段轻易逃脱.这是开发可伸缩程序关键部分的一项基本技能.

This problem teaches you that programming isn't just about knowing how to spin a loop, you also have to figure out the most efficient and effective loop(s) to spin after a detailed logical analysis. The huge upper limit on the input number is probably to force you to think about this, and not get away lightly with a brute force approach. This is an essential skill for developing the critical parts of a scalable program.

这篇关于C:倒数之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！