目录
题目描述:
给出一个正整数 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);
}
总结:
设计该递归函数时,要找出递归退出条件,打印函数的位置,根据数值的类型决定下一级递归的数值。
标签:猜想,递归,int,void,冰雹,fun,解题,------,倒序 From: https://blog.csdn.net/markingyi/article/details/141270777