H 数字游戏

题目链接：

题目描述

奶牛们又在玩一种无聊的数字游戏。输得很郁闷的贝茜想请你写个程序来帮她在开局时预测结果。在游戏的开始，每头牛都会得到一个数N(1<=N<=1,000,000)。此时奶牛们的分数均为0。如果N是奇数，那么奶牛就会把它乘以3后再加1。如果N是偶数，那么这个数就会被除以2。数字每变动一次，这头奶牛就得到1分。当N的值等于1时，游戏结束，此时的分数就是这头奶牛在这局游戏中的最终得分。

以下是N=5时，一局游戏的完整过程：

N   操作后所得数 注释   总分

5        16          3*5+1       1

16         8           16/2       2

8         4            8/2       3

4         2            4/2       4

2         1            2/2       5

输入描述:

第1行: 一个正整数，N

输出描述:

第1行: 输出一个正整数N，即奶牛在这局游戏中的最终得分

示例1

输入

112

输出

20

思路： 运用快速幂，只要操作到2的幂次方，就可不必再逐一操作，减少复杂度：运用快速幂，只要操作到2的幂次方，就可不必再逐一操作，减少复杂度

#include
          
           typedef long long ll;using namespace std;const int maxn=2e5+7;int quick(int y,int x){    int result=1;    while(x)    {        if(x&1)        {            result*=y;        }        x>>=1;        y=y*y;     }    return result;}int main(){     int n;    while(cin>>n)    {        int dept = 0;        int book = 0;        for (int i = 0; i < 500; i++) {            if (n % 2 == 0) {                n /= 2;                dept++;                bool flag = true;                for (int i = 0; i < 500; i++) {                    if (quick(2, i) == n) {                        book = i;                        flag = false;                        break;                    }                }                if (!flag)                    break;            } else {                n = 3 * n + 1;                dept++;                bool flag1 = true;                for (int i = 0; i < 500; i++) {                    if (quick(2, i) == n) {                        book = i;                        flag1 = false;                        break;                    }                }                if (!flag1)                    break;            }        }        cout << dept + book  << endl;    }    return 0;}