冰雹数

原题目链接

题目描述

任意给定一个正整数 N：

• 如果是偶数，执行：N / 2；
• 如果是奇数，执行：N × 3 + 1。

生成的新数字继续执行同样的动作，循环往复。

观察发现，这个数字会一会儿上升到很高，一会儿又降下来。就这样起起落落，但最终必定会落到 1。

这种过程形象地被称为小冰雹数列。

例如，当 N = 9 时，数列为：

9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

可以看到，小冰雹序列中最高冲到了 52。

---

输入描述

• 输入一个正整数 N（N < 10⁶）。

---

输出描述

• 输出一个正整数，表示 不大于 N 的所有数字，在冰雹数变换过程中，能达到的最大高度。

---

输入输出样例

示例

输入

10

输出

52

c++代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

unordered_map<ll, ll> mp;

ll n, ans = 0;

ll dfs(ll n) {
    if (mp.find(n) != mp.end()) return mp[n];
    ll res;
    if (n == 1) res = 1;
    else if (n % 2 == 0) res = max(n, dfs(n / 2));
    else res = max(n, dfs(3 * n + 1));
    mp[n] = res;
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) ans = max(ans, dfs(i));
    cout << ans;
    return 0;
}//by wqs

思路解析

要用map记录已经算出的值，不要算第二次，否则超时。