题目描述

冰雹猜想是指对于任意一个正整数，如果它是奇数，则对它乘3加1，如果是偶数，则除以2，最终会变成1，目前仍未找到反例。
例如数字6。按照上述规则可以变成3、10、5、16、8、4、2、1，经过8次变换。
现在给定数字n，求存在多少个数字变换n次得到1。

输入一个数字n(0≤n≤55)

输出一个数字表示答案。

样例

样例1
0

样例2
4

样例3
8

样例1
1

样例2
1

样例3
4

用dfs从1开始反向搜索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, ans;
void dfs(ll u, ll cnt)
{
    if (cnt == n)
    {
        ans++;
        return;
    }
    dfs(u * 2, cnt + 1);//先搜出乘2的 ，因为一直乘2的肯定存在
    if ((u - 1) % 3 == 0 && (u - 1) / 3 % 2 == 1) //整除且必须是奇数
    {
        if ((u - 1) / 3 == 1)
            return;
        dfs((u - 1) / 3, cnt + 1);
    }
}
int main()
{
    cin >> n;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}