Algorithm/알고리즘 (기초)

러시아 농부 곱셈법

러시아 농부 곱셈법 A * B 연산이 있을 때 A는 계속 2배로 하고 B는 계속 1/2배로 해서 B가 1이 될때 까지 반복한 결과가 곱셈의 답이 된다는 알고리즘이다. 설명 B가 짝수일 때 $A_B = (A_2) * (B/2)$ B가 홀수일 때 $A_B = (A_2) * (B/2) + A$ 여기서 나누기 연산은 나머지를 버리는 연산이고, 부족한 A만큼을 채워준다고 생각하면 쉬울 것이다. 따라서 B가 홀수일 때는 A만큼을 더해준다. 증명 A*B 연산을 러시아 농부 곱셈법을 이용해서 한다고 하자. 러시아 농부 곱셈법 함수를(Russian Farmer) RF(A,B)라고 하자. 1. 초기값 증명 B가 1일 때 B가 1이 될 때 까지 반복하는 것이므로 바로 종료 따라서 $RF(A,B)$는 A가 답이 된다. B가 ..

2.4 DIVISIBILITY

2.4 DIVISIBILITY 24 Prove by induction on $n \geq 0$ that $n^3 + 2n$ is divisible by 3 24-1. Basis Condition n = 0일 때 성립하는가? $$ \begin{aligned} n^3 + 2n \mod 3 &= n^3 + 2n - 3 \lfloor \frac{n^3+2n}{3} \rfloor \\ 0 \mod 3 &= 0 - 3 \lfloor 0/3 \rfloor \\ &= 0 \end{aligned} $$ 이므로 성립한다. 24-2. Induction (귀납 가정) n = k일 때 성립한다고 가정하자. $$ \begin{aligned} n^3 + 2n \mod 3 &= n^3 + 2n - 3 \lfloor \frac{n^3..

2.3 FLOORS AND CEILINGS

2.3 FLOORS AND CEILINGS Suppose x ∈ IR+.The floor of x, denoted x , is defined to be the largest integer that is no larger than x.The ceiling of x, denoted x, is defined to be the smallest integer that is no smaller than x. 24 Prove by induction on $n \geq 0$ that $$\left \lfloor \frac{n}{2} \right \rfloor = \begin{cases}n/2 &\text{if n is even} \\(n-1)/2 & \text{if n is odd}\end{cases}$$ 24-1. ..

2.2 INEQUALITIES

2.2 INEQUALITIES 18 Prove by induction on $n \geq 1$ that if $x > -1$, then $(1+x)^n \geq 1 + nx$ 18-1. Basis Condition n = 1일 때 성립하는가? $$ \begin{aligned} (1+x)^1 &\geq 1 + 1x \\ &\geq 1 + x \\ \end{aligned} $$ 이므로 성립한다. 18-2. Induction (귀납 가정) n = k일 때 성립한다고 가정하자. $$ \begin{aligned} (1+x)^k \geq 1 + kx \end{aligned} $$ 가 성립한다고 하자. 18-3. Induction Proof (가정을 이용한 증명) n = k + 1일 때를 증명해보자 $$ \begin..

2.1 SUMMATIONS

2.1 SUMMATIONS 1. Prove by induction on $n >= 0$ that $$\sum_{i=1}^n i = n(n+1)/2$$ 1-1. Basis Condition n = 1일 때 성립하는가? $$\sum_{i=1}^1 i = 1(1+1)/2 = 1$$ 이므로 성립한다. 1-2. Induction (귀납 가정) n = k일 때 성립한다고 가정하자. $$\sum_{i=1}^k i = k(k+1)/2$$ 가 성립한다고 하자. 1-3. Induction Proof (가정을 이용한 증명) n = k + 1일 때를 증명해보자 $$\sum_{i=1}^{k+1} i = (k+1)(k+2)/2$$ 가 성립함을 증명해야 한다. 이는 1~k 까지의 합 + (k+1) 이므로.. $$(k+1) + \s..