神奇的利克瑞尔数：196 【大数加法】【回文数】

微信搜索：编程笔记本
微信搜索：编程笔记本
微信搜索：编程笔记本

点击上方蓝字关注我，我们一起学编程
欢迎小伙伴们分享、转载、私信、赞赏

今天要跟小伙伴们分享神奇的数字：196。
在介绍这个神奇的数字之前，我们先来回顾一下回文数。

回文数：正读与倒读为同一个数字。 譬如，12321 就是一个回文数。

这个神奇的数字就与回文数有关。有人发现，**几乎所有的自然数，将其自身与自身的倒序数相加，再对得到的和重复这一过程，最终总会得到一个回文数。**不同的数字所需要的循环次数不同。

12 只需 1 步即可得到相应的回文数：12 + 21 = 33
156 需要 3 步才能得到相应的回文数：156 + 651 = 807，807 + 708 = 1515，1515 + 5151 = 6666

到目前为止，人类计算能力所能发现的需要最多循环次数的数为 1186060307891929990 ，它需要循环操作 261 次才能得到回文数。

下面该 196 登场了！

就是这么一个不起眼的数字，似乎打破了上面所描述的近乎完美的数字规律。曾经，有人将其运算了将近 7 万步，仍未能活得到其回文数。后来，有人修改了算法，更是算到了 2.89 亿步，仍然没能找到回文数。这就是一个著名的利克瑞尔数。

利克瑞尔数（Lychrel Number）指的是将该数与将该数各数位逆序翻转后形成的新数相加、并将此过程反复迭代后，结果永远无法是一个回文数的自然数。

利克瑞尔数的介绍到底就结束了，不知道各位小伙伴们有没有一种意犹未尽的感觉呢？是不是少了点什么？
对嘛，写个程序跑一下嘛！

微信搜索：编程笔记本
微信搜索：编程笔记本
微信搜索：编程笔记本

首先，我们需要一个获取逆序数的子程序。

int reverse(int positive)
{int last_digit;int reverse_num = 0;while (positive) {last_digit = positive % 10;reverse_num *= 10;reverse_num += last_digit;positive /= 10;}return reverse_num;
}

有了这个子程序后，我们就能很轻松地对一些数字进行验证了，

#include <stdio.h>int main()
{int num;int step = 0;printf("Please input the number: ");scanf("%d", &num);while (num != reverse(num)) {num += reverse(num);++step;}printf("Find palindrome %d with %d step(s)\n", num, step);return 0;
}

我们用 156 来测试一下：

➜  Lychrel gcc -o test test.c 
➜  Lychrel ./test 
Please input the number: 156
Find palindrome 6666 with 3 step(s)

可以看到，跟我们上面计算的结果一致。我们接着来测试一下 1186060307891929990 。

Please input the number: 1186060307891929990
Find palindrome -914565419 with 2 step(s)

微信搜索：编程笔记本
微信搜索：编程笔记本
微信搜索：编程笔记本

怎么肥四？？？这明显不对啊！

原来，由于 int 型数据的表示范围有限，导致程序不能正确处理数据及其和，最终导致错误的结果。

于是我准备将 int 换成 unsigned long long ，仔细一想这样也是不够的，整型数据类型总是只能表示有限的数据，所以我们需要一个表示无限数据的类型：字符串。

因此，我们需要重新定义字符串整数的加法运算。

void add(char **str1, char **str2)
{char *num1 = *str1;char *num2 = *str2;int len1 = strlen(num1);int len2 = strlen(num2);int carry = 0;int sum;if (len2 > len1) {swap(&num1, &num2);swap(&len1, &len2);}for (int i = 0; i < len2; ++i) {sum = (num1[len1 - i - 1] - '0') + (num2[len2 - i - 1] - '0') + carry;if (sum >= 10) {carry = 1;num1[len1 - i - 1] = sum - 10 + '0';} else {carry = 0;num1[len1 - i - 1] = sum + '0';}}if (carry == 1) {for (int i = 0; i < len1 - len2; ++i) {sum = num1[len1 - len2 - i - 1] - '0' + carry;if (sum >= 10) {carry = 1;num1[len1 - len2 - i - 1] = sum - 10 + '0';} else {carry = 0;num1[len1 - len2 - i - 1] = sum + '0';}if (carry == 0) {break;}}if (carry == 1) {char *num = (char *)malloc((len1 + 1 + 1) * sizeof(char));memcpy(num + 1, num1, len1 + 1);num[0] = '1';free(num1);*str1 = num;}}
}

同样地，我们也需要一个字符串逆序子程序，并且对于逆序后开头为 0 的数要将 0 去除。

char *reverse(const char* positive)
{int len;char *reverse_num;/* trim the zero(s) on the tail */for (int i = strlen(positive); i > 0; --i ) {if (positive[i - 1] != '0') {len = i;break;}}reverse_num = (char *)malloc((len + 1) * sizeof(char));reverse_num[len] = '\0';for (int i = 0; i < len; ++i) {reverse_num[i] = positive[len - i - 1];}return reverse_num;
}

主程序逻辑类似：

int main()
{char *num;char *reverse_num;int step = 0;num = (char *)malloc(1024 * sizeof(char));printf("Please input the number: ");gets(num);reverse_num = reverse(num);while (0 != strcmp(num, reverse_num)) {add(&num, &reverse_num);++step;free(reverse_num);reverse_num = reverse(num);}free(reverse_num);printf("Find palindrome %s with %d step(s)\n", num, step);return 0;
}

这样我们就能测试任意大数了。

➜  Lychrel gcc -o test test.c
➜  Lychrel ./test
Please input the number: 1186060307891929990
Find palindrome 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 with 261 step(s)
➜  Lychrel

可以看到，程序运行符合预期。