跳到主要内容

千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2024年8月実施 専門 B11

标签：

Author​

祭音Myyura (co-authored with GPT 6 Astra)

Description​

次の OCaml プログラムを考える。

let rec ins l x =
  match l with
  | [] -> [x]
  | y :: ys -> y :: (ins ys x)
let rec rev0 l =
  match l with
  | [] -> []
  | x :: xs -> ins (rev0 xs) x

(1) rev0 の機能を述べよ。(2) 同じ結果を返し、長さ nn の入力に対するパターンマッチ回数が O(n)O(n) となる rev1 を定義せよ。

「有効なキュー操作」とは push m または pop () の列で、どの先頭部分でも push の数が pop の数以上のものをいう。

(3) 次の実装で長さ nn の有効な操作列における最大パターンマッチ回数を f(n)f(n) とすると、f(n)=O(nk)f(n)=O(n^k) となる最小整数 kk は何か。理由を述べよ。

let r : int list ref = ref []
let push x = (r := ins !r x)
let pop () = match !r with x :: xs -> (r := xs; x)

(4) 次の空欄を埋め、長さ nn の有効な操作列の最大パターンマッチ回数が O(n)O(n) となるキューを実装せよ。

let r : int list ref = ref []
let s : int list ref = ref []
let push x = (s := x :: !s)
let pop () = match !r with
  | x :: xs -> (r := xs; x)
  | [] -> (* 空欄 *)

题目描述​

(1) 说明 rev0 计算什么。(2) 给出等价且模式匹配次数为线性的 rev1。(3) 对以尾部插入实现的队列，求 nn 次有效操作所需模式匹配次数的最小多项式阶。(4) 补完双列表队列，使任意有效的 nn 次操作总成本为 O(n)O(n)；有效表示任何前缀的入队次数都不少于出队次数。

Kai​

(1)​

ins l x は l の末尾に x を追加する。従って rev0 は入力リストの順序を逆転する。

(2)​

let rev1 l =
  let rec loop acc rest =
    match rest with
    | [] -> acc
    | x :: xs -> loop (x :: acc) xs
  in
  loop [] l

パターンマッチは n+1n+1 回である。

(3)​

長さ jj のキューへの push は j+1j+1 回のパターンマッチを行う。すべて push の操作列なら総数は 1+2+⋯+n=n(n+1)/21+2+\cdots+n=n(n+1)/2。一方、各操作は高々 n+1n+1 回なので全体は O(n2)O(n^2)。従って最小整数は k=2\boxed{k=2}。

(4)​

r := rev1 !s;
s := [];
match !r with
| x :: xs -> (r := xs; x)
| [] -> failwith "empty queue"

r には取り出す順、s には追加した順の逆順で要素を保存する。r が空になったときだけ s を一度逆転して移す。各要素は高々一度逆転の対象になり、一度取り出される。従って逆転の総コストも取り出しの総コストも O(n)O(n) である。有効な操作列では例外の分岐には到達しない。

本页目录