Created
June 13, 2014 12:43
-
-
Save na2hiro/ed8a7c716b1a123aa73f to your computer and use it in GitHub Desktop.
IFPH 3.1.4答え
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
IFPH 3.1.4 m*nの評価に必要な評価ステップ数はいくつか. | |
ただし自然数及び加算,乗算は次の通り. | |
data Nat = Zero | Succ Nat | |
(+) :: Nat->Nat->Nat | |
m + Zero = m | |
m + Succ n = Succ (m+n) | |
(*) :: Nat->Nat->Nat | |
m * Zero = Zero | |
m * Succ n = (m*n)+m | |
答 | |
m+nのコストをP(m, n)とすると | |
P(m, 0) = 1 | |
P(m, n) = P(m, n-1) + 1 | |
より関数P(m, n)はnに関する等差数列であり | |
P(m, n) = n+1 | |
m*nのコストをM(m, n)とすると | |
M(m, 0) = 1 | |
M(m, n) = M(m, n-1) + P({m*(n-1)の結果}, m) + 1 | |
= M(m, n-1) + m + 2 | |
よりM(m, n)はnに関する等差数列であり | |
M(m, n) = (m+2)*n+1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment