冰雹猜想——洛谷(P5727 【深基5.例3】)

目录

题目描述

样例

参考题解

解法1：

解法2：

解法3

题目链接

给出一个正整数再加  ，否则除以  。经过若干次循环后，最终都会回到  。经过验证很大的数字  都可以按照这样的方式比变成  ，所以被称为“冰雹猜想”。例如当  是 ，变化的过程是  。 根据给定的数字，验证这个猜想，并从最后的  开始，倒序输出整个变化序。

样例

样例输入：

20

样例输出：

1 2 4 8 16 5 10 20

参考题解

解法1：

分析：

• 需要足够长度的数组存储中间结果

• 利用while(1)循环，实现得到中间计算结果和输出

代码实现：

# include "bits/stdc++.h"

using namespace std;
int main()
{
    int a = 0, b = 0;
    int sto[1000] = { 0 };
    cin >> a;
    b = a;

    int  i = 0;
    while (a-1)
    {
        a = (a % 2 == 0) ? a / 2 : (3*a + 1);
        sto[i] = a;
        ++i;
    }

    --i;  // 倒序输出
    while (i + 1)
    {
        cout << sto[i] << " ";
        --i;
    }
    cout << b << " ";  // 小补丁

    return 0;

}

解法2：

分析：

• 递归实现逆序输出，不使用数组存储中间结果

• 位运算

代码实现：

# include "bits/stdc++.h"

void write(int n);

using namespace std;
int main(){
    int n;
    cin >> n;

    write(n);

    return 0;

}

void write(int n)
{
    if(n==1)
    {
        cout << "1 ";
        return;
    }

    n&1 ? write(3*n + 1) : write(n >> 1);
    cout << n << " ";

}

解法3

分析：

• 题目要求逆序输出，可以利用“栈”的 LIFO 特点

代码实现：

# include "bits/stdc++.h"

# include "stack"

using namespace std;
int main()
{
    stack  s;
    int n;
    cin >> n;

    while (n!=1)
    {
        s.push(n);
        n = (n % 2 == 0) ? n/2 : n*3 + 1;
    }

    s.push(1);

    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
        return 0;

}

题目链接

P5727 【深基5.例3】冰雹猜想 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P5727