专栏首页程序员PAT(乙级)1001

PAT(乙级)1001

1001. 害死人不偿命的(3n+1)猜想

卡拉兹(Callatz)猜想:

对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想,传说当时耶鲁大学师生齐动员,拼命想证明这个貌似很傻很天真的命题,结果闹得学生们无心学业,一心只证(3n+1),以至于有人说这是一个阴谋,卡拉兹是在蓄意延缓美国数学界教学与科研的进展…… 我们今天的题目不是证明卡拉兹猜想,而是对给定的任一不超过1000的正整数n,简单地数一下,需要多少步(砍几下)才能得到n=1? 输入格式:每个测试输入包含1个测试用例,即给出自然数n的值。 输出格式:输出从n计算到1需要的步数。 输入样例: 3 输出样例

5

分析:由于这个题目很简单,直接就上代码了。

代码如下:

#include<stdio.h>

int i = 0;
int fun(int n);

int main()
{
  int n,sum;
  scanf("%d",&n);
  sum = fun(n);
  printf("%d",sum);
  
  return 0;
}
int fun(int n)		//递归版
{
  if(1 == n)
  {
    return 0;
  }
  else
  {
    if(0 == n%2)
    {
      n /= 2;
    }
    else
    {
      n = (3 * n + 1) / 2;
    }
    i++;
    fun(n);
    return i;
  }
}
#ifdef D		//非递归版
int fun(int n)
{
	if(1 == n)
	{
		return 0;
	}
	else
	{
		int i ;
		for(i = 0;1 != n;i++)
		{
			if(0 == n%2)
			{
				n /= 2;
			}
			else
			{
				n = (3 * n + 1) / 2;
			}	
		}
		return i;		
	}
}
#endif //D

由于这是一个数值计算,不建议采用递归来做,这样会导致不必要的内存开销。递归版本,大家看看就行了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NOI接水问题

    15:接水问题 总时间限制: 1000ms 内存限制: 65536kB 描述 学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟...

    zy010101
  • PAT(乙级)1013

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/z...

    zy010101
  • PAT(乙级)1005

    卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里,情况稍微有些复杂。

    zy010101
  • C++版 - 剑指offer面试题38:数字在已排序数组中出现的次数

    提交网址: http://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&...

    Enjoy233
  • HDU-1846-Brave Game

    ACM模版 描述 ? 题解 BASH 裸题,没啥可说的。 代码 #include <iostream> #include <cstdio> #define _...

    f_zyj
  • 第89场周赛

    题解:根据描述,第一想法是通过模拟,每经历一段时间,更新每辆车的位置,再判断各辆车的位置,对每辆车的速度进行更新,不太好些代码。

    用户1145562
  • 剑指OFFER之重建二叉树(九度OJ1385)

    题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

    用户1154259
  • 挑战程序竞赛系列(30):3.4矩阵的幂

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 2019 CCPC 重现赛 1006 基环树

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • 搜索(4)

    mathor

扫码关注云+社区

领取腾讯云代金券