スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 3n+1問題

みずぴーさんの記事にとりあげられていた問題をやってみます。 
数列の問題で初期値が与えられたとき次のルールで数列を作成します。(有限数列となることは証明されていないですが、3 × 2^53までは有限数列になることが確かめられているそうです)
 
もし現在の値が1なら、終了する 
もし現在の値が偶数なら、半分にする 
もし現在の値が奇数なら、3倍して1を足す 
という操作を与えられた数値に対して繰り返す。
 
問題は「自然数n,m(n<=m)が与えられたとき、n以上m以下であるすべての数に対して1になるまでの系列の長さを求め、その最大値を出力するプログラムを書けと」いうものです。
 
まずは初項を与えた時に数列を返す関数を定義します。
(このような帰納的定義から、数列を作るときには、Seq.unfoldが重宝します。)
(なお計算途中でintの範囲を超えることは想定していません。)
 
> let make3n1Seq init = Seq.unfold(fun x -> if x = 1 then None //最後の1は要素として付加されない
                                            elif x % 2 = 0 then Some(x,x/2)
                                            else Some(x,3*x + 1)) 
                                init
;;
 
val make3n1Seq : int -> seq<int>
 
ちょっと使ってみます。
 
> 10 |> make3n1Seq |> Seq.iter (fun x -> printf "%d  " x);;
10  5  16  8  4  2  val it : unit = ()
 
なお最後の項の1は付加されません。
 
次に「n,m(n<=m)が与えられたとき、n以上m以下であるすべての数に対して1になるまでの系列の長さを求め、その最大値とその時の数列を求めて表示する関数です。(複数の場合は複数の数列が表示されます。)
 
> let getMaxBetween (n1:int) (n2:int) =
    seq{n1 .. n2}
    |>Seq.map (fun i -> make3n1Seq i)  //Seq.map make3n1Seqでよい
    |>Seq.map (fun sq -> ((Seq.length  sq) + 1) ,sq)
    |>Seq.fold(fun (maxLen,maxSeqLst) (sql,sq) ->
                      if sql > maxLen then (sql,[sq])
                      elif sql = maxLen then (sql,sq::maxSeqLst)
                      else (maxLen,maxSeqLst))
               (0,[])
 
    |>(fun (len,sqLst) -> printfn "最大の長さ%d : " len
                          sqLst |> Seq.iter (fun sq -> sq |> Seq.iter(fun x ->printf "%d " x)
                                                       printfn "1 "));;
 
val getMaxBetween : int -> int -> unit
 
使用してみます。
 
> getMaxBetween 1 10;;
最大の長さ20 : 
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
val it : unit = ()
 
> getMaxBetween 100 200;;
 
最大の長さ125 : 
171 514 257 772 386 193 580 290 145 436 218 109 328 164 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 
val it : unit = ()
 
> getMaxBetween 201 210;;
 
最大の長さ89 : 
207 622 311 934 467 1402 701 2104 1052 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 
206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 
val it : unit = ()
 
> getMaxBetween 900 1000;;
 
最大の長さ174 : 
937 2812 1406 703 2110 1055 3166 1583 4750 2375 7126 3563 10690 5345 16036 8018 4009 12028 6014 3007 9022 4511 13534 6767 20302 10151 30454 15227 45682 22841 68524 34262 17131 51394 25697 77092 38546 19273 57820 28910 14455 43366 21683 65050 32525 97576 48788 24394 12197 36592 18296 9148 4574 2287 6862 3431 10294 5147 15442 7721 23164 11582 5791 17374 8687 26062 13031 39094 19547 58642 29321 87964 43982 21991 65974 32987 98962 49481 148444 74222 37111 111334 55667 167002 83501 250504 125252 62626 31313 93940 46970 23485 70456 35228 17614 8807 26422 13211 39634 19817 59452 29726 14863 44590 22295 66886 33443 100330 50165 150496 75248 37624 18812 9406 4703 14110 7055 21166 10583 31750 15875 47626 23813 71440 35720 17860 8930 4465 13396 6698 3349 10048 5024 2512 1256 628 314 157 472 236 118 59 178 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
val it : unit = ()
 
ちなみに 
> getMaxBetween 98 102;;
とすると
 
最大の長さ26 : 
102 51 154 77 232 116 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
99 298 149 448 224 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
val it : unit = ()
 
となりますので、98から102までは連続して系列の長さが26なのですね。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

3 × 2^253

3 × 2^53 では?

No title

指がすべってました。訂正しました。ご指摘ありがとうございました。

余計なお世話

(fun i -> make3n1Seq i)
は、
make3n1Seq
のように単に関数を渡せばいいかと思います。

No title

なんか、mapとか来ると、指が (fun   と動いてしまいます。
補足しました。
プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。