097 C - Base -2 Number

入出力

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

参考

正のnに対するn進展開とn進展開を十進展開に直す関数をライブラリに記録しています. 具体的にはArithmetics.fsxのdecimalToNaryとnaryToDecimal関数です. 必要に応じて参照してください.

解説1: 再帰関数

大枠

うまく実装すれば処理できると思いますが, ここでは単純にN=0かどうかで場合わけします. 本体の処理は再帰関数で対応するため, 大枠は次のように実装します.

1
2
3
  let rec frec acc n = "再帰関数"
  if N=0 then [0] else frec [] N
  |> List.map string |> String.concat ""

再帰関数は数値のリストを作って, 最後にString.concatで連結します.

再帰関数

まず引数にわたってくるnを2で割ってどんどん小さくします. n=0になったら積んできたリストを返せばよいため, if n=0 then accは規定路線です. あとは本体の再帰プロセスを考えます.

-2進の部分で少し工夫が必要です. 結論から書くと次のように書けます.

1
2
3
  let rec frec acc n =
    if n=0 then acc
    else let k = abs (n%2) in frec (k::acc) ((k-n)/2)

F#の%は負の数に対して負の値を返すため, absをかませて正の値にした上でaccに積みます. 次にfrecに食わせる値は(k-n)/2にしています. もちろんここは(n-k)/(-2)でいいのですが, 符号分を手計算で処理しています.

解説2: unfoldによる処理

同じ処理をunfoldで書きます. こちらは結論だけにします.

1
2
3
4
5
6
7
let solve N =
  if N=0 then [|0|]
  else N |> Array.unfold (fun k -> if k=0 then None else let m = abs(k%(-2)) in Some (m, (m-k)/2)) |> Array.rev
  |> Array.map string |> String.concat ""

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

unfoldは公式リファレンスまたはReference.fsxを参照してください.