A04 - Binary Representation 1¶

created: 2022-12-26 mon
ご意見・ご要望はissue・プルリク用のGitHubまで
競技プログラミングのためのF#入門
GitHub上の対応ディレクトリ
公式ページ
要点: 定型処理・零埋め(ゼロパディング)

入出力¶

let N = stdin.ReadLine() |> int
solve N |> stdout.WriteLine

方針¶

よく出てくる定型処理です. 暗記してもいいほどです. 自分用のライブラリを作って記録しておくといいでしょう. 私はArithmetics.fsxに記録しています.

解説1: 再帰¶

大枠¶

今回入力のNは1以上の自然数です. しかしN=0で問題(?)がある実装を紹介するため, 念のため場合分けを明確につけておきます.

結論からいうと再帰関数で0,1の数値からなるリストとして二進展開を作ります. 最初に書いたようにN=0の場合を別にして次のように書きます.

1	`let rec frec acc N = if N=0 then acc else "再帰処理"`

これで[1;1;0;1]のようなリスト(int list)ができます. ここから二進展開の文字列を作って文字列を零埋めします. 零埋めのよい方法がいまだによくわかっていないものの, C#の文字列系のメソッドを使えばいいでしょう. リストを文字列に変換して文字列を零埋めします.

  if N=0 then [0] else frec [] N |> List.map string |> String.concat "" |> fun s -> s.PadLeft(10,'0')

frec [] N以降は次のように処理しています.

List.map stringでint listをstring listに変換する.
System.String.concat ""でstring listを空文字列で連結する.
s.PadLeftで文字列に対して零埋めする.

再帰関数の構成を考える¶

いきなり二進展開で考えるとわかりにくいでしょう. K=10として十進数を十進展開し, 最後にK=2で置き換えると多少なりともわかりやすいはずです.

まず十進展開されたもとの数をNとします. 特にN = 123456789として, これの一番下からK進展開を考えます. 一番下の桁は9だから何とかしてNから9を切り出します. これをNをK = 10で割ったあまりとみなせばN%Kで9が取れます. 次にN/Kを考えると一番下の桁が削れてN1 = 12345678が得られます. これに対してさらにN1%Kを考えると8が得られます. これを再帰的に続けてNk = 0になるまで続ければ求める十進展開が得られます.

箇条書きでは次のように書けます.

K進展開したい数をNとする.
最低桁を取る.
- N%Kで最低桁が得られるからこの値を積む.
- 次の桁を得るためにN1 = N/Kを次のステップに回す.
二桁目を取る.
- N1%KでN1の最低桁, Nの二桁目が得られるからこの値を積む.
- 次の桁を得るためにN2 = N1/Kを次のステップに回す.
これをNk = 0までくり返す.

再帰関数を書く¶

結論だけ書きます.

1	`let rec frec acc N = if N=0 then acc else frec ((N%2)::acc) (N/2)`

解説2: `unfold`¶

F#入門コンテンツでループは再帰の構文糖衣とみなせると書きました. 特にループは配列から配列を作るか, 配列から値を作るか二通りあると書きました. 今回の処理は再帰を使って値から配列(リスト)を生成しています. 特定の場合にはこの逆の処理をしてくれる関数があり, それはunfoldです. 慣れないと難しいため無理に使う必要はありません. しかし関数型言語による処理では時々顔を見せる関数であるため, 念のため紹介します.

本質的には再帰と同じで, 関数についてはリファレンスを見てもらうとして簡潔に結果だけ示します.

let solve N =
  if N=0 then [|0|] else N |> Array.unfold (fun n -> if n=0 then None else Some (n%2,n/2))
  |> Array.rev
  |> Array.map string |> String.concat "" |> fun s -> s.PadLeft(10,'0')

unfoldを使う場合は再帰と違ってArray.revで順序を反転する必要があります.