[开发测试]PAT1001题解

1001

卡拉兹(Callatz)猜想

输入格式：

每个测试输入包含 1 个测试用例，即给出正整数 n 的值。

输出格式：

输出从 n 计算到 1 需要的步数。

输入样例：

3

输出样例：

5

解法一：（循环）

#include<iostream>
using namespace std;
int main()
{
 ? ?int n;
 ? ?int i = 0;
 ? ?cin >> n;
 ? ?while (n != 1) {
 ? ? ? ?if (n % 2 == 0)
 ? ? ?  {
 ? ? ? ? ? ?n /= 2;
 ? ? ? ? ? ?i++;
 ? ? ?  }
?
 ? ? ? ?else {
 ? ? ? ? ? ?n = (3 * n + 1) / 2;
 ? ? ? ? ? ?i++;
 ? ? ?  }
 ?  }
?
 ? ?cout << i;
 ? ?return 0;
}

解法二：（递归）

#include<iostream>
using namespace std;
int countstep(int n, int i) {
    if (n == 1)
        return i;
    if (n % 2 == 0)
        return countstep(n / 2, i + 1);//偶数
    if (n % 2 == 1)
        return countstep((3 * n + 1) / 2, i + 1);//奇数
}
?
int main()
{
    int n, i;
    cin >> n;
    i = 0;
    cout << countstep(n, i);
?
}

总结：

注意题目的时间和代码长度限制，将奇数和偶数采用分支结构。