スポンサーサイト

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

F#雑記 3本を選んでできるだけ周長の長い三角形を作る

  
BLUEPIXYさんの記事について考えてみました。 
 
問題は「n本の棒があります。棒iの長さはaiです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。」というもので、棒の長さをリストで与えられたとして考えます。 
 
a<b<c<dとするとき、例えばa,c,dで三角形が成立するなら、b,c,dでも三角形が成立しa+c+d<b+c+dです。 
またb,c,dで三角形が成立しないのなら、a,c,dでも、a,b,dでも三角形は成立しません。 
ということで数を降順に並べておいて、連続する3項について、三角形が成立するかどうかを調べていき、 
最初に成立したものの和が最大の周長になります。また、もしも最後まで成立しないのならばどの3数をとっても三角形は成立しないことになります。 
 
ということでコードは以下の通りです。 
 
> let findTriPerMax (ori_list:list<int>) = 
    let rec ftpmSub lst = 
        match lst with 
        |a::b::c::tl when a<b+c -> a+b+c 
        |a::b::c::tl -> ftpmSub (b::c::tl) 
        |_ -> 0 
    ori_list 
    |>List.sort 
    |>List.rev 
    |>ftpmSub;; 
 
val findTriPerMax : int list -> int 
 
(実行例) 
 
> findTriPerMax [ 2; 3; 4; 5; 10];; 
val it : int = 12 
 
> findTriPerMax [ 4; 5; 10;20];; 
val it : int = 0 
スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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