侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-10 / 0 评论 / 0 点赞 / 30 阅读 / 510 字 / 正在检测是否收录...

题目

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

3155. 冰雹数


任意给定一个正整数 NN

如果是偶数,执行: N/2N / 2
如果是奇数,执行: N×3+1N \times 3 + 1

生成的新的数字再执行同样的动作,循环往复。

通过观察发现,这个数字会一会儿上升到很高,一会儿又降落下来。

就这样起起落落的,但最终必会落到 1“1”

这有点像小冰雹粒子在冰雹云中翻滚增长的样子。

比如 N=9N=9 时:

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

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

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

输入格式

一个正整数 NN

输出格式

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

数据范围

0<N<1060 < N < 10^6

示例 1:

输入:
10
输出:
52

示例 2:

输入:
100
输出:
9232

解题

方法一:模拟

思路

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

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

代码

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);
    }
}
0

评论区