y = f (x) x:入力、y:出力 f(x)

全文

(1)

算法の設計と解析

第八回

2005.01.17

y = f (x) x:入力、y:出力 f(x)

を計算機上に設計する。

f (x) =

 

g(x) x

が条件

T

を満たす

h(x)

条件を満たさない

y

k

= f (y

k−1

) x (−∞, ∞) t (0, ∞)

∂f

∂t

=

∂x2f2 これを

f (x, 0)

を入力として数値計算に変える

計算機上での表現

0, 1 Boolean 2

進数

exe

ファイル

obj← C

言語

数の定義

ここで扱う数の範囲は、N+

∪ {0}

とする。

ただし、N+は自然数の集合である。

N

+の定義をするのに、0

≺(後継子 successor)

を使う。

1. (x) = x + 1 2. ≺≺ (x) =≺ (x) + 1 1:

N

+

∪ {0}

の定義

2:

の再帰定義

とすると、≺≺≺

...(0) = n

となる。

以降、1進数で表現する。0 : 11 : 112 : 111...n

: 11...1 | {z }

n+1

1

(2)

足し算

x, y N

+

∪ {0}

の、x,yに対応する表現:第一引数に

を第二引数回数作用させる。

1....1

| {z }

x+1

+ 1....1 | {z }

y+1

1....1 | {z }

x+y+1

(1)

引き算

 (x) = x 1x  (x) N

+

∪ {0}

x y = ÂÂ ... Â (x)

| {z }

y

割り算

[x/y] = m : x = my + r(0 r y)

(x):上昇演算子 Â (x):下降演算子

負の数

1 + x = 0 x = -1 * 1 :-1

の定義

 (x) = x + (−1) 1

引き算を定義する。

x −y ˙ =

½ x 1 x y 0 x < y

x y =

½ x −y ˙ x y (y −x) ˙ x < y

逆ポーランド記法

N

+

∪ {0}

の上の計算は、2項演算,

a b∗ ∈ {+, −, ×, ÷} (2)

で、以下のように変換される

a + b +ab (a + b) × c → ×c + ab

2

Updating...

参照

Updating...

関連した話題 :