スポンサーサイト

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

F#雑記 falling number

anarchy golfに次のような問題があります。
 
「数字がどんどん小さくなっていくような自然数のうち、桁数がn桁からm桁のものを求めよ。(m>=n >=2)」
(原題は2ケタから4ケタです。)
 
例えば2ケタから4ケタの場合は10,20,21,30,31,32,40,.............,9873,9874,9875,9876
となります。
 
考え方は単純で先に数字を降順で並べておいてそれにマスクをかけます。
 
9876543210
0000000011
->10
 
9876543210
0000000101
->20
 
9876543210
0000000110
->21
 
マスクはuint32の下から10ビットを使うことにして、立っているビット数を数えるために前回定義した bitCountUint32関数を使用することにします。
 
マスクから数字を得る関数を定義します。
 
> let inline isLowestBitOnUint32 (n: uint32)= 
         (n &&& 1u)  = 1u  
 
let getUnMaskedNum  numForMask =
    let rec sub digCharRem numForMaskRem res =
        match digCharRem with
        | [] -> res
        | h :: tl -> if isLowestBitOnUint32 numForMaskRem then
                        sub tl (numForMaskRem >>> 1) (h::res)
                     else
                        sub tl (numForMaskRem >>> 1) res 
    let result = sub ['0' .. '9'] numForMask []
    System.Int64.Parse(new string (Array.ofList result));;
 
val inline isLowestBitOnUint32 : uint32 -> bool
val getUnMaskedNum : uint32 -> int64
 
使用してみます。
 
> getUnMaskedNum 0b0000000101u;;
val it : int64 = 20L
 
> getUnMaskedNum 0b1101u;;
val it : int64 = 320L
 
では、n桁からm桁までのfalling numberをリストにして返す関数を定義します。
 
> let getFallingNum (n:int) (m:int) =
    [ 0b1u .. 0b1111111111u]
    |> List.map(fun x -> (bitCountUint32 x,x))
    |> List.sort
    |> List.filter(fun (c,_) -> (uint32)n <= c && c <= (uint32)m )
    |> List.map(fun (_,x) -> getUnMaskedNum  x);;
 
val getFallingNum : int -> int -> int64 list
 
使用してみます。
> getFallingNum 2 4;;
val it : int64 list =
  [10L; 20L; 21L; 30L; 31L; 32L; 40L; 41L; 42L; 43L; 50L; 51L; 52L; 53L; 54L;
   60L; 61L; 62L; 63L; 64L; 65L; 70L; 71L; 72L; 73L; 74L; 75L; 76L; 80L; 81L;
   82L; 83L; 84L; 85L; 86L; 87L; 90L; 91L; 92L; 93L; 94L; 95L; 96L; 97L; 98L;
   210L; 310L; 320L; 321L; 410L; 420L; 421L; 430L; 431L; 432L; 510L; 520L;
   521L; 530L; 531L; 532L; 540L; 541L; 542L; 543L; 610L; 620L; 621L; 630L;
   631L; 632L; 640L; 641L; 642L; 643L; 650L; 651L; 652L; 653L; 654L; 710L;
   720L; 721L; 730L; 731L; 732L; 740L; 741L; 742L; 743L; 750L; 751L; 752L;
   753L; 754L; 760L; 761L; 762L; 763L; 764L; ...]
 
> getFallingNum 8 9;;
val it : int64 list =
  [76543210L; 86543210L; 87543210L; 87643210L; 87653210L; 87654210L; 87654310L;
   87654320L; 87654321L; 96543210L; 97543210L; 97643210L; 97653210L; 97654210L;
   97654310L; 97654320L; 97654321L; 98543210L; 98643210L; 98653210L; 98654210L;
   98654310L; 98654320L; 98654321L; 98743210L; 98753210L; 98754210L; 98754310L;
   98754320L; 98754321L; 98763210L; 98764210L; 98764310L; 98764320L; 98764321L;
   98765210L; 98765310L; 98765320L; 98765321L; 98765410L; 98765420L; 98765421L;
   98765430L; 98765431L; 98765432L; 876543210L; 976543210L; 986543210L;
   987543210L; 987643210L; 987653210L; 987654210L; 987654310L; 987654320L;
   987654321L]
 
> getFallingNum 10 10;;
val it : int64 list = [9876543210L]
スポンサーサイト

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

trackback


この記事にトラックバックする(FC2ブログユーザー)

falling number

【F#,組合せ】falling number

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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