趣味算法：冰雹猜想的递归解法

趣味算法：冰雹猜想的递归解法

引用

CSDN

1.

https://blog.csdn.net/markingyi/article/details/141270777

冰雹猜想，又称3n+1猜想，是一个著名的未解数学问题。本文将通过一个具体的编程实例，演示如何使用递归算法来验证这个猜想，并输出从任意正整数到1的变化序列。

题目描述

给出一个正整数 n，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 3 再加 1，否则除以 2。经过若干次循环后，最终都会回到 1。经过验证，很大的数字（7×10¹¹）都可以按照这样的方式变成 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);
}

总结

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