2004/12/29

うけてたちます。

hisashim: [Programming][Fun] コンピュータで解く簡単な問題::
http://www.livejournal.com/users/hisashim/85886.html

任意の自然数nについて、偶数なら2で割り、奇数なら3をかけて1を足して得られる数列に関し、(1)n = 7 のときに1に収束するまでのステップ数を求めよ。(2)n∈[2, 100]のなかでもっとも1までの収束に時間がかかるのは何ステップか求めよ。という問題。
元ネタはhttp://www.t-base.ne.jp/~tj/d/?date=20041214#p03らしい。

#! /usr/local/bin/python

def numeric(n):
count = 0
while n > 1:
if n & 1:
count = count + 2
n = (3 * n + 1) >> 1
else:
count = count + 1
n = n >> 1
return count

print "7 needs", numeric(7), "steps"

i = 0
basej = 0

for j in range(2, 101):
if i < numeric(j):
i = numeric(j)
basej = j
print "most steps in [2,100] is", i, "at n =", basej

実行結果

7 needs 16 steps
most steps in [2,100] is 118 at n = 97


ポイントは、奇数を3倍して1を足すと必ず偶数になることですかね(つまり、偶数の場合は偶奇判定が必須だけど、奇数の場合は次の偶奇判定を省略できる)。

No comments :