スポンサーサイト

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

どう書く?org '('と')'の対応

 
お題は「'('と')'の対応」です。  
  
問題は次の通り  
 
入力の'('と')'の対応をとってください。  
ただし、コード中に'('と')'を含まないでください。 
 
コード中に'('と')'を含まないという制約をいかに実現するかという問題です。 
 
チェックする文字列を引数にして対応がとれているかどうかを返す関数checkを定義します。 
 
> let check inp = 
    let inpAsStr = string inp 
    let endIndex = inpAsStr.Length 
    let rec checkSub dif cur_index = 
        if dif < 0 then false 
        else 
            if cur_index = endIndex   then 
                if dif = 0 then 
                    true 
                else  
                    false 
            else  
                let cur_char =inpAsStr.Chars cur_index 
                let newDif = if cur_char = '\x28' then 
                                    dif + 1  
                             elif cur_char = '\x29' then 
                                    dif - 1 
                             else  
                                    dif 
                let newIndex = cur_index + 1 
                checkSub newDif newIndex 
    checkSub 0 0;; 
 
val check : obj -> bool 
 
> check "(()))";; 
val it : bool = false 
> check ")(";; 
val it : bool = false 
> check "(()())";; 
val it : bool = true 
 
では全コードです。 
 
let check inp = 
    let inpAsStr = string inp 
    let endIndex = inpAsStr.Length 
    let rec checkSub dif cur_index = 
        if dif < 0 then false 
        else 
            if cur_index = endIndex   then 
                if dif = 0 then 
                    true 
                else  
                    false 
            else  
                let cur_char =inpAsStr.Chars cur_index 
                let newDif = if cur_char = '\x28' then 
                                    dif + 1  
                             elif cur_char = '\x29' then 
                                    dif - 1 
                             else  
                                    dif 
                let newIndex = cur_index + 1 
                checkSub newDif newIndex 
    checkSub 0 0                        
 
[<EntryPoint>] 
let main args = 
   let result = check args.[0] 
   System.Console.Write result 
   0 
スポンサーサイト

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

どう書く?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

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

どう書く?org F# 逆転したビット列

 GushwellさんBLUEPIXYさん がやっておられた「逆転したビット列」を私もやってみました。
 もとのお題は「どう書く?org」の「逆転したビット列」http://ja.doukaku.org/61/です。 
 Gushwellさんのコメント欄に投稿したものを少し改良しました。
 
 手癖なのか自分のコードはlet rec ...........res = の形が多いようです。
 
 コードはこちら。(なおint32型でなくuint32型を使用しています。)
 
 > let inline getLowestBit (n: uint32)= 
   if ((n >>> 1) <<< 1) <> n then 1u
   else 0u
 
let GetReverseNum num width = 
    let rec GetRNumSub curWidth limitWidth rNum res =
       if curWidth = limitWidth then res
       else
         GetRNumSub (curWidth + 1) limitWidth (rNum >>> 1) ((res <<< 1) ||| (getLowestBit rNum))
    GetRNumSub 0 width num 0u
 
let pow2MaxMinus1 (m: int32) =
    let rec subPow curM res =
        if curM = m then res
        else subPow (curM+1) (res <<< 1 ||| 1u)
    subPow 1 1u
 
let makeReversedNumSeq n =
    seq{ for i in  0u .. (pow2MaxMinus1 n) -> (GetReverseNum i n) }
 
let disp n =
    (makeReversedNumSeq n) |> Seq.iter (fun x -> printfn "%A" x) ;;
 
val inline getLowestBit : uint32 -> uint32
val GetReverseNum : uint32 -> int -> uint32
val pow2MaxMinus1 : int32 -> uint32
val makeReversedNumSeq : int32 -> seq<uint32>
val disp : int32 -> unit
 
(実行例)
 
> disp 4;;
0u
8u
4u
12u
2u
10u
6u
14u
1u
9u
5u
13u
3u
11u
7u
15u
val it : unit = ()
>  

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

どう書く?org F# 数字混じり文字列ソート

「どう書く?org」http://ja.doukaku.org/に挑戦です。   
さて今回の問題はこちら「数字混じり文字列ソート」http://ja.doukaku.org/295/ 
 
次のようなソードをおこなうソートを作れというものです。
 
辞書順ソート: 1.txt, 10.txt, 100.txt, 2.txt, 20.txt 
 
数字混じり文字列ソート: 1.txt, 2.txt, 10.txt, 20.txt, 100.txt 
 
例2: 
 
辞書順ソート: x12, x13, x1A, x1B, xAB 
 
数字混じり文字列ソート: x1A, x1B, x12, x13, xAB 
 
例3: 
 
辞書順ソート: A10B1, A10B10, A10B2, A1B1, A1B10, A1B2, A2B1, A2B10, A2B2 
 
数字混じり文字列ソート: A1B1, A1B2, A1B10, A2B1, A2B2, A2B10, A10B1, A10B2, A10B10
 
正規表現を利用して、愚直に実装してみました。(コードが堅い!)
速度も望めません。
 
> open System
open System.Text.RegularExpressions
 
let numRemRegex = new Regex("(?<topNum>(^([\\d]+)))(?<topNumRem>(.*))")
let strRemRegex = new Regex("(?<topStr>(^([^\\d]+)))(?<topStrRem>(.*))")
 
let rec compStrIncNum (st_L:string) (st_R:string) =
    let topNum_L = numRemRegex.Match(st_L).Groups.["topNum"]
    let topNum_R = numRemRegex.Match(st_R).Groups.["topNum"]
    let topStr_L = strRemRegex.Match(st_L).Groups.["topStr"]
    let topStr_R = strRemRegex.Match(st_R).Groups.["topStr"]
    if (topNum_L.Success && topNum_R.Success) then
       let intCompVal = compare (Int64.Parse(topNum_L.Value)) (Int64.Parse(topNum_R.Value)) 
       if intCompVal = 0 then
            let TopNumRem_L = numRemRegex.Match(st_L).Groups.["topNumRem"]
            let TopNumRem_R = numRemRegex.Match(st_R).Groups.["topNumRem"]
            compStrIncNum TopNumRem_L.Value TopNumRem_R.Value 
       else
            intCompVal
    elif (topStr_L.Success && topStr_R.Success) then
        let strCompVal = compare topStr_L.Value topStr_R.Value
        if strCompVal = 0 then
            let TopStrRem_L = strRemRegex.Match(st_L).Groups.["topStrRem"]
            let TopStrRem_R = strRemRegex.Match(st_R).Groups.["topStrRem"]
            compStrIncNum TopStrRem_L.Value TopStrRem_R.Value
        else 
            compare st_L st_R
    else
        compare st_L st_R;;
 
val numRemRegex : System.Text.RegularExpressions.Regex =
  (?<topNum>(^([\d]+)))(?<topNumRem>(.*))
val strRemRegex : System.Text.RegularExpressions.Regex =
  (?<topStr>(^([^\d]+)))(?<topStrRem>(.*))
val compStrIncNum : string -> string -> int
 
実行例
 
> List.sortWith compStrIncNum  ["100.txt"; "1.txt"; "20.txt"; "2.txt"; "10.txt"];;
val it : string list = ["1.txt"; "2.txt"; "10.txt"; "20.txt"; "100.txt"]
 
> List.sortWith compStrIncNum ["x13"; "x1B"; "xAB"; "x12"; "x1A"];;
val it : string list = ["x1A"; "x1B"; "x12"; "x13"; "xAB"]
 
> List.sortWith compStrIncNum ["A10B1";"A10B10";"A10B2";"A1B1";"A1B10";"A1B2";"A2B1";"A2B10";"A2B2"];;
val it : string list =
  ["A1B1"; "A1B2"; "A1B10"; "A2B1"; "A2B2"; "A2B10"; "A10B1"; "A10B2";"A10B10"]
 
> List.sortWith compStrIncNum ["う54う"; "い23い"; "い1い"; "あ9あ"; "う100う"; "あ88あ"];;
val it : string list = ["あ9あ"; "あ88あ"; "い1い"; "い23い"; "う54う"; "う100う"]
 
ただこれだとA006BとA6Bが等しいものとしてソートされるので、なにか規則を付け加えた方がよいかもしれません。

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

どう書く?org F# 文字列で+を表示する

今回の問題はこちら 
 
与えられた文字列で+のかたちを表示するプログラムをかいてください。
サンプル入力:
doukaku
 
サンプル出力:(表示がくずれるので、ブランク部分に_をいれてあります。)
_______doukakud
_______u______o
_______k______u
_______a______k
_______k______a
_______u______k
_______o______u
doukakud______doukakud
u____________________o
k____________________u
a____________________k
k____________________a
u____________________k
o____________________u
dukakuod______dukakuod
_______u______o
_______k______u
_______a______k
_______k______a
_______u______k
_______o______u
_______dukakuod
 
今回はLEGO風に書いてみました。
コードは以下の通り
 
type NextTurnDirection =
    |Right
    |Left
let cdr (dx,dy) = ((-1)*dy,dx) //cdrはchangeDirectionRightの略
let cdl (dx,dy) = (dy,(-1)*dx) //cdlはchangeDirectionLeftの略
 
let doWork (s:string) =
    let len = s.Length
    let canvasArr = Array2D.create (3*len + 1) (3*len + 1) ' ' 
    let startPos = (len,0)
    let getNextTrunDirection turnN = 
        if turnN % 3 = 1 then Left else Right //3回に1回左折
    let rec drawCanvas stepNum turnNum (x,y) (dx,dy) cbfvosp =
       // cbfvospはcanBeFirstVisitOnStartPointの略
       if (x,y) = startPos && cbfvosp = false then
            ()
       else
          canvasArr.[x,y] <- s.[stepNum] 
          match (stepNum,turnNum) with
          |(sn,tn)  when sn = len - 1 && (getNextTrunDirection tn) = Right
                ->  drawCanvas 0 (tn + 1) (x+dx,y+dy) (cdr (dx,dy)) false
          |(sn,tn)  when sn = len - 1 && (getNextTrunDirection tn) = Left
                ->  drawCanvas 0 (tn + 1) (x+dx,y+dy) (cdl (dx,dy)) false   
          |(sn,tn)
                ->  drawCanvas (stepNum+1) tn (x+dx,y+dy) (dx,dy) false
    
    drawCanvas 0 0  startPos (1,0) true  
    
    for i in 0 .. 3*len do
        printfn ""
        for j in 0 .. 3*len do
            printf "%c" canvasArr.[j,i]
 
open System
 
[<STAThread()>] 
[<EntryPoint>] 
let main(args) = 
    if (args.Length = 0 || args.[0].Length <2) then
        printf "引数が不正です。"
    else
        doWork args.[0]
    0
 

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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