DouKaku?beta

challenge コラッツ・角谷の問題 

任意の数nを与えたときに
・nが偶数ならば2で割る　(n=n/2)
・nが奇数ならば3倍して1を足す （n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
（すべての数について成り立つかは不明）
参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

see: コラッツの問題の成り立つ範囲

post comment

Posted feedbacks - BASIC

十進BASIC Ver7.0.4の2進モードで。
実行環境は、pentiumM 1.3GHz、メモリ256MB、WindowsXPです。 

f( 837799 ) = 524 
 3.15000000000873 sec

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
!コラッツ・角谷の問題
LET  st = TIME
LET  n = 2^20
DIM  c(n)

FUNCTION f(k)
   IF k = 1 THEN
      LET  f = 0
   ELSEIF k <= n AND c(k) <> 0 THEN
      LET  f = c(k)
   ELSE
      IF  MOD(k,2) = 0  THEN
         LET  s = f(k / 2) + 1
      ELSE
         LET  s = f((3 *  k + 1) / 2) + 2
      END IF
      IF k <= n THEN  LET  c(k) = s 
      LET  f = s
   END IF
END FUNCTION 

LET  mx = f(n)
LET  no = n
FOR i = 3 TO n STEP 2
   LET  j = f(i)
   IF j > mx THEN 
      LET  mx = j
      LET  no = i
   END IF
NEXT I 
PRINT "f(";no;") =";mx
PRINT TIME - st;"sec"
END

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]