P6922

题目内题解

前置:基础语法

最低所需知识点:循环结构

题面没有明显的提到具体的 $i,j$ 输入多少次 但是模拟就可以过

普通的模拟

只给一点点的提示:

注意在 $Collatz Conjecture$ 猜想的序列长度包含最初的那个数以及最后的 $1$

下面给出一些相关优化:

记忆化:

一开始把数据范围想的太大了所以写的优化

我们发现不管初始数字是什么 只要某一步进入到了之前计算过的数字 那么后续的计算就和之前计算这个数字的步骤完全一样.

所以我们开一个数组存储一些数到 $1$ 的序列长度.后续在次计算到此数时直接读出该数据而不是重复计算.

对于这个数组的大小可以只开 $10010$ 个.(实验得出的 足以证明此题数据之水)

具体的实现细节:

使用递归回溯:

只要当前数据没有计算过(数组中为0)则往下计算.

特别的 初始化 $1$ 的长度为 $1$.

在递归的时候如果碰到了非 $0$ 的数(之前算过) 则直接返回这个数+1

回溯:

把当前的数的序列长度存储 然后范围当前数的序列长度+1,继续回溯.

此数组全局可用 所以建议开全局变量.