趣味算法——冰雹猜想（递归解题）

大家好，欢迎来到IT知识分享网。

目录

题目描述：

思路解析：

 冰雹猜想简介

构造递归函数：

具体代码：

总结：

题目描述：

给出一个正整数 n，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 3 再加 1，否则除以 2。经过若干次循环后，最终都会回到 1。经过验证，很大的数字（7×10 
11
 ）都可以按照这样的方式比变成 1，所以被称为“冰雹猜想”。

根据给定的数字，验证这个猜想，并从最后的 1 开始，倒序输出整个变化序列。

输入输出格式
输入格式
输入一个正整数 n。

输出格式
输出若干个由空格隔开的正整数，表示从最后的 1 开始倒序的变化数列。

输入输出样例
输入
40

输出
1 2 4 8 16 5 10 20 40

思路解析：

 冰雹猜想简介

冰雹猜想，也称为3n+1猜想或Collatz猜想，是由德国数学家洛塔尔·哥拉茨（Lothar Collatz）在1937年提出的一个关于自然数的数学问题。该猜想的内容是：对于任意给定的一个正整数，如果它是偶数，则将其除以2；如果它是奇数，则将其乘以3再加1。按照这样的操作反复进行，最终总会达到数1。尽管这个猜想在大量的数值试验中被验证为正确，但至今尚未得到严格的数学证明. 

构造递归函数：

        因为我们需要倒序打印结果，所以我们可以尝试构造递归函数。

        首先我们先定义一个函数，该函数不带有返回值，仅仅需要传入一个形参。

void fun(int n) { }

        然后判断这个数是奇数还是偶数，这样才知道对应的操作。

void fun(int n) { if (n % 2) fun(3 * n + 1); else fun(n / 2); }

        之前我们讲过，递归要有停止条件，否则会一直执行下去。虽然现在冰雹猜想并没有得到严格验证，但是在这道题的数值范围内，冰雹猜想都能成立，所以结束条件就是 n == 1。

void fun(int n) { if (n != 1) { if (n % 2) fun(3 * n + 1); else fun(n / 2); } }

        现在我们需要打印每一级函数内的数字，因为是倒序输出，所以递归最底层的函数内的数字n先输出。

void fun(int n) { if (n != 1) { if (n % 2) fun(3 * n + 1); else fun(n / 2); } printf("%d ", n); }

        自此，核心代码完成。

具体代码：

#include<stdio.h> void fun(int n) { if (n != 1) { if (n % 2) fun(3 * n + 1); else fun(n / 2); } printf("%d ", n); } int main(void) { int n; scanf("%d", &n); fun(n); }

总结：

        设计该递归函数时，要找出递归退出条件，打印函数的位置，根据数值的类型决定下一级递归的数值。