トップ «前の日記(2003-06-16) 最新 次の日記(2003-06-18)» 月表示 編集

日々の流転


2003-06-17 [長年日記]

λ. ドイツ語

藁谷先生は面白いなぁ。

λ. 萩野服部研

SICP 5.1 「レジスタ計算機の設計」

Tags: tom

λ. [a1; a2...; an] と[b1; b2...; bn] を受け取って, [(a1, bn); (a2, bn - 1); ...; (an, b1)] を返す関数

水凪さんの日記の4/17に載っていた問題。帰りの電車とバスの中で結構真剣に考えてしまった。気づけば簡単。

長さの等しい二つのリスト[a1; a2...; an]と [b1; b2...; bn]を 受け取って, [(a1, bn); (a2, bn - 1); ...; (an, b1)] を返す関数を書きなさい。 ただし、

  • nをあらかじめ知ることはできない
  • 与えられた二つのリスト以外のリストを使ってはならない
  • 再帰呼び出しは高々(n + 1)回しか行ってはならない
  • 全体の計算量はO(n)でなければならない
Tags: quiz
本日のツッコミ(全5件) [ツッコミを入れる]
ψ nobsun (2003-06-19 17:47)

hoge :: [a] -> [b] -> [(a,b)]<br>hoge as bs = zip as (reverse bs)<br>で、見掛上再帰なし。じゃだめですよねぇ。<br>三つめの条件がよくわからないです。むずかすぃ

ψ あおき (2003-06-19 20:05)

これでいいんですかね…<br><br>xzip xs ys = f where (f,s) = xzip' xs ys<br><br>xzip' [] ys = ([], ys)<br>xzip' (x:xs) ys = ((x,y):list, ys')<br> where (list, (y:ys')) = xzip' xs ys

ψ さかい (2003-06-19 22:55)

確かに問題が結構曖昧ですよね。<br><br>nobsunさんのは、zipとreverseはそれぞれn回の再帰で実行できるので、<br>条件の解釈にもよるかも知れませんが、3つ目の条件は満たしてると思います。<br>ですが、reverseで一時的なリストを作っているので、<br>2つ目の条件で多分アウトです。(^^;<br><br>あおきさんのは文句なしであってると思います。<br>ちなみに、リンク先の4/25の日記に解答があるのですが、<br>あおきさんの解答の方がスマートですね。

ψ ささだ (2003-06-20 00:23)

Haskell ワカリマセーン.ruby か scheme で書いてー.

ψ nobsun (2003-06-20 11:01)

あっ。なるほど。mapAccumR だ。<br>xzip as bs = snd $ xzip' as bs<br>xzip' = flip (mapAccumR f) where f (y:ys) x = (ys,(x,y))<br>ですね。