角谷猜想

题意

正整数为奇数时变为 $3n+1$ ，偶数时变为 $n/2$ ，逐行输出过程直到得到 1，最后输出 End。

思路

循环条件是 number != 1。每次先按奇偶计算 next_number 并按题面格式输出，再将当前数更新为它；输入本身为 1 时循环不执行，直接输出 End。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12number = int(input())

while number != 1:
    if number % 2:
        next_number = number * 3 + 1
        print(f"{number}*3+1={next_number}")
    else:
        next_number = number // 2
        print(f"{number}/2={next_number}")
    number = next_number

print("End")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#include <cstdio>

int  main(){
	long long n;
	scanf("%lld",&n);
	while( n != 1) {
		long long  ans;
		if( n % 2 == 1){
			ans = n*3+1;
			printf("%lld*3+1=%lld\n",n,ans);
		}
		else {
			ans =n /2;
			printf("%lld/2=%lld\n",n,ans);
		}
		n = ans;
	}
	printf("End");
	return 0;
}

复杂度

设变换次数为 $t$ ，时间复杂度为 $O(t)$ ，额外空间复杂度为 $O(1)$ 。

总结

过程输出题要区分“计算前的当前状态”和“计算后的下一状态”，输出后再更新状态。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结