【模拟】冰雹数【蓝桥杯】

题目

试题 历届真题 冰雹数【第七届】【省赛】【C组】

3155. 冰雹数

---

任意给定一个正整数 $N$，

如果是偶数，执行： $N / 2$
如果是奇数，执行： $N \times 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

可以看到，$N=9$ 的时候，这个“小冰雹”最高冲到了 $52$ 这个高度。

给定数字 $N$，请你求出不大于 $N$ 的数字，经过冰雹数变换过程中，最高冲到了多少。

输入格式

一个正整数 $N$。

输出格式

一个正整数，表示不大于 $N$ 的数字，经过冰雹数变换过程中，最高冲到了多少。

数据范围

$0 < N < 10^6$

示例 1：

输入：
10
输出：
52

示例 2：

输入：
100
输出：
9232

解题

方法一：模拟

思路

按照题目模拟，维护一个最大值即可。

注意：求出不大于 $N$ 的数字，经过冰雹数变换过程中最高冲到了多少，而不仅仅是等于 $N$ 的数字。

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int N = (int) in.nval;
        long max = N;
        for (int i = 3; i <= N; ++i) {
            long n = i;
            while (n != 1) {
                if ((n & 1) == 0) n /= 2;
                else n = n * 3 + 1;
                max = Math.max(max, n);
            }
        }
        System.out.println(max);
    }
}