スポンサーサイト

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

どう書く?org 分数の発見

お題は どう書く?orgの「分数の発見」です。
 
問題は次の通り
 
非負の実数aが一つ与えられたときに、次の3つの条件を満たす分数b/cをaに近い順に全て表示する手続きを考えてみてください。
1. 分数b/cよりaに近い分数d/cは存在しない 
2. 分数b/cは既約 
3. cは1桁の整数 
  
まず補助の関数を3つほど定義しておきます。
 
> //2数の最大公約数を求める
let rec hcf a b =       
    if a=0 then b
    elif a<b then hcf a (b-a)
    else hcf (a-b) b
 
//互いに素かどうかを判定
let isIrreducible a b =
    hcf a b = 1  
 
val hcf : int -> int -> int
val isIrreducible : int -> int -> bool 
 
分母がqの分数で、aに一番近い分数を求めて,それが既約であればSome("分子/分母",aとの距離)
既約でなければNoneを返す関数を定義します。
 
>let nearestIrreducibleFrac q (a:double)  =
    let n = (int)a
    let nearestFrac =
        [(q*n) .. (q*(n+1))]
        |>List.map (fun i -> (i,abs((double i) / (double q) - a),isIrreducible i q))
        |>List.sortBy (fun (_,d,_) -> d)
        |>List.head
    let (j,dis,isIre) = nearestFrac
    if isIre then
        Some(sprintf "%d/%d" j q,dis)
    else 
        None;;
 
val nearestIrreducibleFrac : int -> double -> (string * float) option
 
使ってみます。
 
> nearestIrreducibleFrac 7 1.732051;;
val it : (string * float) option = Some ("12/7", 0.01776528571)
 
> nearestIrreducibleFrac 4 1.732051;;
val it : (string * float) option = Some ("7/4", 0.017949)
 
> nearestIrreducibleFrac 6 1.732051;;
val it : (string * float) option = None
 
さて考える分母は1~9までなので、それぞれに対して、上の関数を適用して、リストにしてaとの距離が小さい順に並べて返す関数を定義します。
 
>let getResultList (a:double) =
    [1 .. 9]//分母は1から9まで
    |> List.map(fun i -> nearestIrreducibleFrac i a)
    |> List.filter(fun x -> x.IsSome)
    |> List.map (fun x -> x.Value)
    |> List.sortBy (fun (s,dis) -> dis)
    |> List.map (fun (s,_) -> s)
;;
 
val getResultList : double -> string list
 
では使用してみます。
 
> getResultList 1.732051;;
val it : string list = ["12/7"; "7/4"; "16/9"; "5/3"; "9/5"; "3/2"; "2/1"]
 
> getResultList 3.141593;;
val it : string list = ["22/7"; "25/8"; "19/6"; "28/9"; "16/5"; "13/4"; "3/1"]
 
> getResultList (1920.0/1080.0);;
val it : string list = ["16/9"; "9/5"; "7/4"; "11/6"; "12/7"; "5/3"; "2/1"]
 
なお近いといっても、doubleの誤差の範囲内で考えてますので、答えは数学的に厳密なものではありません。
 
ついでに、分母を1から9までとせずに、1からmまでと指定できるようにしておきます。(1か所変更するだけです。)
 
> let getResultList m (a:double) =
    [1 .. m]//分母は1からmまで
    |> List.map(fun i -> nearestIrreducibleFrac i a)
    |> List.filter(fun x -> x.IsSome)
    |> List.map (fun x -> x.Value)
    |> List.sortBy (fun (s,dis) -> dis)
    |> List.map (fun (s,_) -> s);;
 
val getResultList : int -> double -> string list
 
使用例
 
> getResultList 100 3.141593;;
val it : string list =
  ["311/99"; "289/92"; "267/85"; "245/78"; "223/71"; "201/64"; "179/57";
   "22/7"; "157/50"; "292/93"; "135/43"; "248/79"; "113/36"; "305/97";
   "283/90"; "261/83"; "204/65"; "239/76"; "295/94"; "217/69"; "195/62";
   "91/29"; "173/55"; "251/80"; "151/48"; "160/51"; "280/89"; "229/73";
   "129/41"; "298/95"; "236/75"; "69/22"; "107/34"; "254/81"; "192/61";
   "185/59"; "116/37"; "85/27"; "163/52"; "210/67"; "148/47"; "47/15"; "63/20";
   "167/53"; "104/33"; "119/38"; "145/46"; "72/23"; "41/13"; "97/31"; "101/32";
   "60/19"; "25/8"; "79/25"; "53/17"; "19/6"; "28/9"; "35/11"; "31/10"; "16/5";
   "13/4"; "3/1"]
   
 > getResultList 1000 3.141593;;
val it : string list =
  ["355/113"; "2862/911"; "2818/897"; "2507/798"; "2463/784"; "2152/685";
   "2108/671"; "1797/572"; "1753/558"; "1442/459"; "1398/445"; "2529/805";
   "2441/777"; "1087/346"; "1043/332"; "2906/925"; "2774/883"; "1819/579";
   "1731/551"; "2551/812"; "2419/770"; "3107/989"; "732/233"; "688/219";
   "2573/819"; "3085/982"; "1841/586"; "2397/763"; "2950/939"; "1709/544";
   "1109/353"; "2730/869"; "2595/826"; "1021/325"; "1486/473"; "2375/756";
   "1863/593"; "1354/431"; "2240/713"; "2617/833"; "3041/968"; "2994/953";
   "1687/537"; "2020/643"; "2353/749"; "2686/855"; "377/120"; "3019/961";
   "3038/967"; "2661/847"; "333/106"; "2284/727"; "1907/607"; "1530/487";
   "2683/854"; "2975/947"; "2642/841"; "1153/367"; "2309/735"; "1976/629";
   "3082/981"; "1929/614"; "1643/523"; "2705/861"; "2953/940"; "1310/417";
   "776/247"; "2287/728"; "2727/868"; "977/311"; "1951/621"; "3126/995";
   "2598/827"; "1175/374"; "1621/516"; "2749/875"; "2265/721"; "1574/501";
   "2909/926"; "1973/628"; "2372/755"; "644/205"; "2771/882"; "2887/919";
   "2243/714"; "1599/509"; "399/127"; "2554/813"; "955/304"; "2815/896";
   "2416/769"; "2221/707"; "2017/642"; "1266/403"; "1618/515"; "2843/905";
   "2837/903"; "1577/502"; "1219/388"; "1888/601"; ...]  
   
 
ちなみに
> 355.0/113.0;;
val it : float = 3.14159292
 
> 2862.0/911.0;;
val it : float = 3.141602634
スポンサーサイト

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

コメントの投稿

非公開コメント

absD

abs がそのまま使えます。

No title

そうでした!訂正しました。ありがとうございます。

流儀?

キャスト(変換)する場合、カッコはかならずしも必要ではないですよ。

No title

c#言語での手癖ですね。訂正しました。ありがとうございます。
プロフィール

T GYOUTEN

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

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

この人とブロともになる

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