PAT乙级（Basic）题库---1001

题目

1001-害死人不偿命的（3n+1）猜想

解题思路

这里的数不大，不用考虑溢出超时什么的，直接运用递归的思想，f(n)为数n砍到1时的步数，则 f(n)=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪f(n2）+1,f(3n+12)+1,0,如果 n 是偶数如果 n 是不为1的奇数如果 n 为1 f ( n ) = { f ( n 2 ） + 1 , 如果  n  是偶数 f ( 3 n + 1 2 ) + 1 , 如果  n  是不为1的奇数 0 , 如果  n  为1

代码

虽然使用递归的思想，但是同样可以使用循环来实现，这里将两种方法均贴出。

递归

#include<iostream> #include<math.h> using namespace std; //数num砍到1的步数 int step(int num) { //num为1 if(num==1) { return 0; } //num是不为1的奇数 else if(num%2) { int temp=3*num+1; return step(temp/2)+1; } //num是偶数 else { return step(num/2)+1; } } int main() { int num; while(cin>>num) { cout<<step(num)<<"\n"; } return 0; }

循环

#include<iostream> #include<math.h> using namespace std; int main() { //sum记录数num砍到1的步数 int num,sum; while(cin>>num) { sum=0; //num为1时退出循环 while(num!=1) { //num是不为1的奇数 if(num%2) { num=(3*num+1)/2; } //num是偶数 else { num/=2; } sum++; } cout<<sum<<"\n"; } return 0; }