【P5727】冰雹猜想

题目描述

给出一个正整数 $n$，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 $3$ 再加 $1$，否则除以 $2$。经过若干次循环后，最终都会回到 $1$。经过验证很大的数字（$7\times 10^{11}$）都可以按照这样的方式比变成 $1$，所以被称为“冰雹猜想”。例如当 $n$ 是 $20$，变化的过程是 $20\to 10\to 5\to 16\to 8\to 4\to 2\to 1$。

根据给定的数字，验证这个猜想，并从最后的 $1$ 开始，倒序输出整个变化序列。

输入格式

输入一个正整数 $n$。

输出格式

输出若干个由空格隔开的正整数，表示从最后的 $1$ 开始倒序的变化数列。

样例 #1

样例输入 #1

20

样例输出 #1

1 2 4 8 16 5 10 20

提示

数据保证，$1\le n\le 100$

先附上我的代码：

#include<iostream>
 using namespace std;
  int main()
 {
     int n;
     cin >> n;
     int a[10000]={0};
     a[0] = n;
     int t = 0;
     while (n!=1)
    {
        if (n % 2 == 0)
        {
            n /= 2;
            t++;
            a[t] = n;
        }
        else
        {
            n = 3 * n + 1;
            t++;
            a[t] = n;
        }
    }
        for (int i = 9999; i >=0; i--)
        {
            if (a[i] != 0)
                cout << a[i] << " ";
        }
        /*或者   for (int i = t; i >=0; i--)
           {
            if (a[i] != 0)
                cout << a[i] << " ";
        }
        */

   

    return 0;

}

首先是我的思路：
题目给出一个数字n,从n的奇偶性出发分别做出两种操作，周而复始直至n变化至1为止，最后题目要求我们将变化过程中，将n的值的变化过程以逆序的方式输出。
开始写程序时，第一步自然时将拿到的数字进行奇偶判断从而做出对应操作，做出第一步后，第一个问题来了，每一次操作后n变化成的数字不能直接输出，因为题目要求逆序，若直接输出则为顺序，所以这时候想到将每一步操作产生的值保存在数组中，但又有几个新问题随之而来，因为不知道有几个步骤，所以数组要多大的？怎么将数组的值输出？输出条件是什么？以下是我的解决方法：
考虑到n<101，奇数x3+1<1000,其很有可能进行偶数操作后再乘以3再减一，数字成正比增加，无法预估其会增长至多大，所以我用一个巧妙的方法解决了这个问题，
每进行一次偶数或者奇数操作，t的值加1，t在这里起到计数和标记的作用，用t来做数组的自变量，可以解决数组的长度问题（操作数不会太高，但以防万一我还是开到了10000，这样相当于开了一个上百万数量的数组）且每个
t值随操作数的增加而增加，a[t]便顺序存放了每次变化的值。而输出条件则十分简单，因为数组存放的是每次变化的值，所以一定不等于0，将数组初始化为0，则数组不为0的值便为n变化的值，所以我们数组输出的条件便是数组的值不为0(当然，因为我们每次操作都使t值加一，所以最后t的值对应的数组其实就是最后一个有效的改变后的n，即为1，所以我们数组从t开始输出，减到零为止也是可以的)本道题自然也就迎刃而解啦！