スポンサーサイト

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

F# 雑記 昇順になる部分列の長さの最大

 BLUEPIXYさんのブログでとりあげられた問題を、自分でもやってみました。  
 
問題は数列の部分列(条件:昇順になっていること)のうち、最大の長さをもつものの長さを求めよというものです。 
 
F#でリストを使ってやってみます。 
 
一つ目は最大の長さをもつものの内の一つを返す関数を定義します。 
 
> //最長のリストの長さを求める関数 
let getLongestLst lstlst = 
    if  List.length lstlst = 0 then 
        [] 
    else 
        List.reduce (fun ele1 ele2 -> if List.length ele1 > List.length ele2 then ele1 else ele2) lstlst 
 
//nを付け足せるもののうち最長のリストにnを付け足した形で返す関数。 
let getlongestNhead n lstlst = 
    let underNheadLsts = List.filter (fun lst -> List.head lst < n) lstlst     
    let longest= getLongestLst underNheadLsts 
    n :: longest 
 
//最長の増加部分列のうち一つを返す関数 
let rec getAns rem res = 
    match rem with 
    |hd::tl -> getAns tl ((getlongestNhead hd res)::res) 
    |[]     -> getLongestLst res |> List.rev ;; 
 
val getLongestLst : 'a list list -> 'a list 
val getlongestNhead : 'a -> 'a list list -> 'a list when 'a : comparison 
val getAns : 'a list -> 'a list list -> 'a list when 'a : comparison 
 
使ってみます。 
 
> getAns [33;1;22;3;34;6;54;9;19] [];; 
val it : int list = [1; 3; 6; 9; 19] 
 
もう一つは、最長のものの長さだけ返します。 
 
> let rec search cnt lastAddedNum rem = 
    match rem with 
    |[]                            -> cnt 
    |hd::tl when hd > lastAddedNum -> max (search cnt lastAddedNum tl) (search (cnt+1) hd tl) 
    |hd::tl                        -> (search cnt lastAddedNum tl);; 
 
val search : int -> 'a -> 'a list -> int when 'a : comparison 
 
使ってみます。 
 
> search 0 System.Int32.MinValue [33;1;22;3;34;6;54;9;19];; 
val it : int = 5
スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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