AtCoder ABC 116 B – Collatz Problem Python解説
Collatz Problem
今回の問題は「Collatz Problem」。コラッツの問題は未解決問題のひとつで、nが偶数の場合nを2で割り、nが奇数の場合nに3を掛けて1を足すことを繰り返すと、どうなるのかという問題です。
この問題では初項sが与えられ、先述したように、nが偶数の場合nを2で割り、nが奇数の場合nに3を掛けて1を足していった結果、最初に要素の重複が起こるのは第何項なのかを求めていきます。
s = int(input())
a = []
i = 1
while True:
if s not in a:
a.append(s)
i += 1
if s % 2 == 0:
s //= 2
else:
s = 3 * s + 1
else:
print(i)
break
要素の重複が起こるまで続くのでwhile文で書きました。要素が配列aになければ要素を追加し、次の要素は偶数か奇数かを見て計算を変えています。要素の重複が起きたら重複が起きた項数を出力して完了です。