1.1. ์๊ณ ๋ฆฌ์ฆ E(์ ํด๋ฆฌ๋์ ์๊ณ ๋ฆฌ์ฆ(Euclid's algorithm)) ¶
~cpp ์์ ์ ์ m๊ณผ n์ด ์ฃผ์ด์ก์๋, ๊ทธ๊ฒ๋ค์ ์ต๋๊ณต์ฝ์(greatest common divisor) (m๊ณผ n์ ๋ชจ๋ ๋๋๋ ๊ฐ์ฅ ํฐ ์์ ์ ์)๋ฅผ ๊ตฌํ๋ค. E1. [๋๋จธ์ง ๊ตฌํ๊ธฐ] m์ n์ผ๋ก ๋๋๊ณ ๋๋จธ์ง๋ฅผ r์ด๋ผ ํ์.(0 <= r < n) E2. [๊ทธ๊ฒ์ด 0์ธ๊ฐ?] r = 0 ์ด๋ฉด, ์๊ณ ๋ฆฌ์ฆ์ ๋๋๋ค; n์ด ๋ต์ด๋ค. E3. [์ค์ด๊ธฐ] m <- n, n <- r ์ผ๋ก ์ค์ ํ๋ค, ๊ทธ๋ฆฌ๊ณ E1๋จ๊ณ๋ก ๋์๊ฐ๋ค.โ
~cpp Fig 1. ์๊ณ ๋ฆฌ์ฆ E์ ์์๋ |<------------------------------------------------------| โ | -------------------- ------------------ ์๋์ค ------------- | E1.๋๋จธ์ง ๊ตฌํ๊ธฐ |-------->( E2.๊ทธ๊ฒ์ด 0์ธ๊ฐ? )-------->| E3.์ค์ด๊ธฐ | -------------------- ------------------ ------------- |์ โ
m = 119 ์ n = 544 ๊ฐ ์ฃผ์ด์ก๋ค๊ณ ํ์
E1 ๋จ๊ณ์์ ์์. m์ n์ผ๋ก ๋๋๋ฉด ๋ชซ์ 0์ด๊ณ ๋๋จธ์ง๋ 119์ด๋ค. ๊ทธ๋ฌ๋ฏ๋ก r <- 119
E2 ๋จ๊ณ์์ r โ 0 ์ด๋ฏ๋ก ์ ์ฉ๋์ง ์๋๋ค
E3 ๋จ๊ณ์์ m <- 544, n <- 119
์ด๊ฒ์ผ๋ก ์ฒ์์ m < n ์ด๋ฉด ํญ์ m๊ณผ n์ด ๊ตํ๋๋ค๋ ๊ฒ์ ์ ์ ์๋ค
์ฐ๋ฆฌ๋ ๋ค์๊ณผ ๊ฐ์ ์๋ก์ด ๋จ๊ณ๋ฅผ ์ถ๊ฐํ ์ ์๋ค(๊ผญ ํ์ํ์ง ์๋ค)
E1 ๋จ๊ณ์์ ์์. m์ n์ผ๋ก ๋๋๋ฉด ๋ชซ์ 0์ด๊ณ ๋๋จธ์ง๋ 119์ด๋ค. ๊ทธ๋ฌ๋ฏ๋ก r <- 119
E2 ๋จ๊ณ์์ r โ 0 ์ด๋ฏ๋ก ์ ์ฉ๋์ง ์๋๋ค
E3 ๋จ๊ณ์์ m <- 544, n <- 119
์ด๊ฒ์ผ๋ก ์ฒ์์ m < n ์ด๋ฉด ํญ์ m๊ณผ n์ด ๊ตํ๋๋ค๋ ๊ฒ์ ์ ์ ์๋ค
์ฐ๋ฆฌ๋ ๋ค์๊ณผ ๊ฐ์ ์๋ก์ด ๋จ๊ณ๋ฅผ ์ถ๊ฐํ ์ ์๋ค(๊ผญ ํ์ํ์ง ์๋ค)
~cpp E0. [m >= n ์ธ์ง ํ์ธํ๊ธฐ] m < n ์ด๋ผ๋ฉด, m <-> n ์ ๊ตํํ๋ค
E1์ผ๋ก ๋์๊ฐ์ 544/119 = 4+68/119, ๊ทธ๋ฌ๋ฏ๋ก r <- 68
๋ค์ E2๋ ์ ์ฉ๋์ง์๊ณ
E3์์ m <- 119, n <- 68
๋ค์์ํ์์ r <- 51, m <- 68, n <- 51
๋ค์์ r <- 17, m <- 51, n <- 17
๋ง์ง๋ง์ผ๋ก 51์ 17๋ก ๋๋์์๋, r <- 0, ๊ทธ๋ฌ๋ฏ๋ก E2์์ ์๊ณ ๋ฆฌ์ฆ์ ์ข ๋ฃ๋๋ค
119์ 544์ ์ต๋๊ณต์ฝ์๋ 17์ด๋ค
๋ค์ E2๋ ์ ์ฉ๋์ง์๊ณ
E3์์ m <- 119, n <- 68
๋ค์์ํ์์ r <- 51, m <- 68, n <- 51
๋ค์์ r <- 17, m <- 51, n <- 17
๋ง์ง๋ง์ผ๋ก 51์ 17๋ก ๋๋์์๋, r <- 0, ๊ทธ๋ฌ๋ฏ๋ก E2์์ ์๊ณ ๋ฆฌ์ฆ์ ์ข ๋ฃ๋๋ค
119์ 544์ ์ต๋๊ณต์ฝ์๋ 17์ด๋ค
1.2. ์๊ณ ๋ฆฌ์ฆ์ 5๊ฐ์ง ์ค์ํ ํน์ง ¶
1) ์ ํ์ฑ(Finiteness)
์๊ณ ๋ฆฌ์ฆ์ ์ ํํ ๋จ๊ณ ํ์ ํญ์ ์ข ๋ฃ๋์ด์ผ ํ๋ค
์๊ณ ๋ฆฌ์ฆ์ ์ ํํ ๋จ๊ณ ํ์ ํญ์ ์ข ๋ฃ๋์ด์ผ ํ๋ค
2) ๋ช
ํ์ฑ(Definiteness)
์๊ณ ๋ฆฌ์ฆ์ ๊ฐ ๋จ๊ณ๋ ์ ํํ ์ ์๋์ด์ผ ํ๋ค
์๊ณ ๋ฆฌ์ฆ์ ๊ฐ ๋จ๊ณ๋ ์ ํํ ์ ์๋์ด์ผ ํ๋ค
3) ์
๋ ฅ(Input)
์๊ณ ๋ฆฌ์ฆ์ 0๊ฐ ์ด์์ ์ ๋ ฅ์ ๊ฐ์ง๋ค
์๊ณ ๋ฆฌ์ฆ์ 0๊ฐ ์ด์์ ์ ๋ ฅ์ ๊ฐ์ง๋ค
4) ์ถ๋ ฅ(Output)
์๊ณ ๋ฆฌ์ฆ์ ํ๋ ์ด์์ ์ถ๋ ฅ์ ๊ฐ์ง๋ค
์๊ณ ๋ฆฌ์ฆ์ ํ๋ ์ด์์ ์ถ๋ ฅ์ ๊ฐ์ง๋ค
5) ํจ์จ์ฑ(Effectiveness)
์๊ณ ๋ฆฌ์ฆ์ ๋ณดํต ํจ์จ์ ์ผ๋ก ์ํ๋๋๋ก ๊ธฐ๋๋๋ค
์๊ณ ๋ฆฌ์ฆ์ ๋ณดํต ํจ์จ์ ์ผ๋ก ์ํ๋๋๋ก ๊ธฐ๋๋๋ค
1.3. ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ๋ ์ ์ํ์ ์งํฉ๋ก ์ ๊ด๊ณ๋ก ๋ํ๋ด๊ธฐ ¶
๊ณ์ฐ์ ์ธ ๋ฐฉ๋ฒ(computational method)์ 4์์ (Q,I,ฮฉ,f)๋ก ํ์์ ๊ฐ์ถฐ ์ ์ํ์
Q๋ ๋ถ๋ถ์งํฉ I์ ฮฉ๋ฅผ ํฌํจํ๋ ์งํฉ์ด๋ค
f๋ Q์์ Q ์๊ธฐ์์ ์ผ๋ก ๊ฐ๋ ํจ์์ด๋ค
ฮฉ์ ๋ชจ๋ ์์ q์ ๋ํ์ฌ f(q)๋ q์ ๊ฐ์์ผ ํ๋ค.
Q : ๊ณ์ฐ
I : ์ ๋ ฅ
ฮฉ : ์ถ๋ ฅ
f : ๊ณ์ฐ ๊ท์น
์งํฉ I์ ์์ x์ ์ ๋ ฅ์ ๊ณ์ฐ์์ด, x0, x1, x2,..., ๋ฅผ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค
Q๋ ๋ถ๋ถ์งํฉ I์ ฮฉ๋ฅผ ํฌํจํ๋ ์งํฉ์ด๋ค
f๋ Q์์ Q ์๊ธฐ์์ ์ผ๋ก ๊ฐ๋ ํจ์์ด๋ค
ฮฉ์ ๋ชจ๋ ์์ q์ ๋ํ์ฌ f(q)๋ q์ ๊ฐ์์ผ ํ๋ค.
Q : ๊ณ์ฐ
I : ์ ๋ ฅ
ฮฉ : ์ถ๋ ฅ
f : ๊ณ์ฐ ๊ท์น
์งํฉ I์ ์์ x์ ์ ๋ ฅ์ ๊ณ์ฐ์์ด, x0, x1, x2,..., ๋ฅผ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค
~cpp x0 = x ์ด๊ณ xk + 1 = f(xk) (k >= 0)ฮฉ์ ์ํ๋ xk ์ ๋ํ์ฌ k๊ฐ ๊ฐ์ฅ ์์ ์ ์๋ผ๋ฉด ๊ณ์ฐ์์ด์ k๋จ๊ณ์์ ์ข ๋ฃ๋๋ค๊ณ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด ๊ฒฝ์ฐ์ x๋ก๋ถํฐ ๊ฒฐ๊ณผ xk๊ฐ ์์ฑ๋๋ค๊ณ ํ๋ค.
์๊ณ ๋ฆฌ์ฆ E๋ ๋ค์๊ณผ ๊ฐ์ด ์ด๋ฐ ๊ด๊ณ๋ก ํ์ํ๋๋ค.
Q๋ฅผ ๋ชจ๋ ๋จ์ผ (n), ๋ชจ๋ ์์์๋ ์ (m,n), ๋ชจ๋ ์์์๋ 4์ (m,n,r,1), (m,n,r,2), (m,n,p,3) (m,n,p๋ ์์ ์ ์, r์ ์์ด ์๋ ์ ์)์ ์งํฉ์ด๋ผ ํ์.
I๋ฅผ ๋ชจ๋ ์ (m,n)์ ๋ถ๋ถ์งํฉ์ด๋ผ ํ์.
ฮฉ๋ฅผ ๋ชจ๋ ๋จ์ผ (n)์ ๋ถ๋ถ์งํฉ์ด๋ผ ํ์.
f๋ ๋ค์๊ณผ ๊ฐ์ด ์ ์๋๋ค.
Q๋ฅผ ๋ชจ๋ ๋จ์ผ (n), ๋ชจ๋ ์์์๋ ์ (m,n), ๋ชจ๋ ์์์๋ 4์ (m,n,r,1), (m,n,r,2), (m,n,p,3) (m,n,p๋ ์์ ์ ์, r์ ์์ด ์๋ ์ ์)์ ์งํฉ์ด๋ผ ํ์.
I๋ฅผ ๋ชจ๋ ์ (m,n)์ ๋ถ๋ถ์งํฉ์ด๋ผ ํ์.
ฮฉ๋ฅผ ๋ชจ๋ ๋จ์ผ (n)์ ๋ถ๋ถ์งํฉ์ด๋ผ ํ์.
f๋ ๋ค์๊ณผ ๊ฐ์ด ์ ์๋๋ค.
~cpp f((m,n)) = (m,n,0,1}; f((n)) = (n); f((m,n,r,1)) = (m, n, m์ n์ผ๋ก ๋๋ ๋๋จธ์ง, 2); r = 0 ์ด๋ฉด f((m,n,r,2)) = (n), ๊ทธ๋ ์ง ์์ผ๋ฉด (m,n,r,3); f((m,n,p,3)) = (n,p,p,1).
2. 1.3. MIX ¶
์ด ์ฑ
์ ์๋ง์ ๋ถ๋ถ์์ MIX์ธ์ด๊ฐ ๋ฑ์ฅํ๋ค. ๋ฐ๋ผ์ ๋
์๋ ์ด ์ ์ ์ฃผ์ ๊น๊ฒ ๊ณต๋ถํด์ผ ํ๋ค.
2.1.1. ์ฉ์ด๊ณผ ํ๊ธฐ๋ฒ ¶
- Words( Partitial fieslds of wordsํฌํจ)
์ฌ์ฏ ๋ฐ์ดํธ๋ก ์ด๋ฃจ์ด์ง๋ค. ํ ๋ฐ์ดํธ์๋ 0~63๊น์ง ์ซ์๊ฐ ๋ค์ด๊ฐ ์ ์๋ค. ๊ทธ๋ฆผ์ผ๋ก ๋ํ๋ด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
0 1 2 3 4 5 ยฑ Byte Byte Byte Byte Byte
์) (0:0)๋ ๋ถํธ, (1:5)๋ ๋ถํธ๊ฐ ์๋ ์ซ์, (3:4)๋ 3,4๋ฒ์งธ ๋ฐ์ดํธ
- Registers
๋ ์ง์คํฐ๋ ์์ ์๋ฌธ์ r์ ๋ถ์ฌ ํ๊ธฐ
A, X register
ยฑ Byte Byte Byte Byte Byte
I register - rI1~rI6๊น์ง ์์. - Instruction format
0 1 2 3 4 5 ยฑ A A I F C
F - ๋ช ๋ น์ด์ ๋ณ๊ฒฝ(a modification of the operation code). (L:R)์ด๋ผ๋ฉด 8L+R = F
ยฑAA - ๋ฉ๋ชจ๋ฆฌ ์ฃผ์(the address)
I - ์ธ๋ฑ์ค(the index specification). ๊ฐ์ด 1~6์ผ๋ก rI1~rI6์ ์๋ ๋ด์ฉ๊ณผ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ฅผ ๋ํจ
์ฌ๊ธฐ์ ๋ํด์ง ์ฃผ์๋ฅผ M, M์ ๋ค์ด์๋ ๊ฐ์ CONTETNS(M)์ด๋ผ๊ณ ํ๋ค.
- Notation
~cpp OP ADDRESS, I(F)
๊ฐ์ ํ์์ผ๋ก ์ด๋ค.
''์) LDA๋ ๋ช ๋ น์ด ์ฝ๋๊ฐ 8์ด๋ค.
LDA 2000, 2(0:3) ์ || + || 2000 |||| 2 || 3 || 8 || ๊ณผ ๊ฐ๋ค.''
ยฑ | Byte | Byte |
+ | Byte | Byte |
Overfolw toggle - on, off
Comparison indicator, - EQUAL, LESS, GREATER
Input, Output Devices
2.1.2. ์ฐ์ฐ ¶
- Loading operators.
CONTENTS(M)์ ๋ ์ง์คํฐ์ ๋ฃ๋๋ค.
LDA, LDX, LDi, LDAN, LDXN, LDiN์ด ์๋ค.
- Storing operators.
๋ ์ง์คํฐ์ ๊ฐ์ CONTENTS(M)์ ๋ฃ๋๋ค.
STA, STX, STi, STJ, STZ๊ฐ ์๋ค.
- Arithmetic operators.
์ฌ์น์ฐ์ฐ์ ํ๋ค. ADD, SUB, MUL, DIV๊ฐ ์๋ค.
- Address transfer operators.
์ด ์ฐ์ฐ์์ M์ ๋ฉ๋ชจ๋ฆฌ ์ ์ ๊ฐ๋ฆฌํค์ง ์๊ณ , ๊ทธ๋ฅ ๋ถํธ์๋ ์ซ์๋ก ์ฐ์ธ๋ค. ENTr, ENNr, INCr, DECr๊ฐ ์๋ค. ( r์ A, X, 1~6)
์) ENTA 2000 - > rA || + || 0 || 0 || 0 || 2000 ||
- Comparison operator
๋ ์ง์คํฐ์ CONTENTS(M)์ ๋น๊ตํด์ LESS, GREATER, EQUAL์ ์ค์ ํ๋ ๋ช ๋ น์ด์ด๋ค. CMPA, CMPX, CMPi๊ฐ ์๋ค. CMPi๋ฅผ ํ ๋๋ ์์ ์ธ ์๋ฆฌ๊ฐ 0์ด๋ผ๊ณ ๊ฐ์ ํ๋ค.
- Jump operators.
M์ด ๊ฐ๋ฆฌํค๋ ๋ฉ๋ชจ๋ฆฌ ์ ๋ก ์ ํํ๋ค. JSJ๋ฅผ ๋นผ๋ฉด ์ ํ๋ฅผ ํ๋ฉด์ ์ ํ ๋ช ๋ น์ด ๋ค์ ์์น๋ฅผ rJ์ ์ ์ฅํ๋ค. the comparison indicator๋ฅผ ์ด์ฉํ๊ฑฐ๋(JL, JE, JG, JGE, JLE, JNE) , ๋ ์ง์คํฐ(JrN, JrZ, JrP, JrNN, JrNZ, JrNP)๋ฅผ ์ด์ฉํ๋ค.
- Miscellaneous operators.
์ํํธ ๋ช ๋ น์ rA์ rX๋ฅผ ์ฌ์ฉํ๋ค. SLA, SRA, SLAX, SRAX, SLC, SRC๊ฐ ์๋ค. M์ ์ํํธํ๋ ํ์๋ฅผ ๋ํ๋ธ๋ค.
MOVE๋ช ๋ น์ F๋งํผ CONTENTS(M)์ rI1์ด ๊ฐ๋ฆฌํค๋ ๋ฉ๋ชจ๋ฆฌ ์ ๋ก ๊ฐ์ ๋ณต์ฌํ๋ค.
''์1) rI1 = 1001์ผ ๋ MOVE 1000,(3)
CONTENTS(1000) -> CONTENTS(1001), rI1 = 1002๊ทธ๋ผ ๋ค์์ ์ด๋ป๊ฒ ๋๋?
CONTENTS(1001) -> CONTENTS(1002), rI1 = 1003
CONTENTS(1002) -> CONTENTS(1003), rI1 = 1004''
์2) rI1 = 2000์ผ ๋ MOVE 1000,(3)
''CONTENTS(1000) -> CONTENTS(2000), rI1 = 2001
CONTENTS(1001) -> CONTENTS(2001), rI1 = 2002
CONTENTS(1002) -> CONTENTS(2002), rI1 = 2003''
(rI1๊ฐ์ด ์ค๊ฐ์ค๊ฐ ๋ฐ๋๋๊ฒ ์๋๋ผ ๋ค ๋๋๊ณ F๋งํผ ๋ํด์ง๋ค๊ณ ์๊ฐํ๋ฉด๋ผ --์ธํ)
NOP ๋ช
๋ น์ ์๋ฌด๊ฒ๋ ํ์ง ์๋๋ค. - Input-output opertors.
ํ์ํ ๋ ๋ณด๋ ค๊ณ ์๋ตํ๋ค.
- Conversion operators.
NUM์ rAX๋ฅผ ๊ฐ์ง๊ณ ์ซ์๋ก ๋ฐ๊พธ์ด rA์ ์ ์ฅํ๋ค. ๊ฐ ๋ฐ์ดํธ๊ฐ ํ ์๋ฆฌ๋ก ๋ฐ๋๋๋ฐ, ์ผ์ ์๋ฆฌ๋ง ๊ฐ์ง๊ณ ๋ฐ๊พผ๋ค(10 -> 0, 23->3 )
CHAR๋ rA๋ฅผ ๊ฐ์ง๊ณ ๋ฌธ์ ์ฝ๋๋ก ๋ฐ๊พธ์ด rAX์ ์ ์ฅํ๋ค.
- Timing
๊ฐ ๋ช ๋ น์ด๋ ์คํ ์๊ฐ(excution time)์ด ์๋ค.
HLT ๋ช ๋ น์ ๊ธฐ๊ณ๋ฅผ ๋ฉ์ถ๋ค(The machine stops.)
2.2. 1.3.3 Applications to Permutations ¶
MIX ํ๋ก๊ทธ๋จ์ ์์ ๋ฅผ ๋ณด์ฌ์ค๋ค. ์ค์ํ ์์ด์ ์ฑ์ง(properties of permutations)์ ์๊ฐํ๋ค.
์์ด์ abcdef๋ฅผ ์ฌ๋ฐฐ์ด(rearrangement)์ด๋ ์ด๋ฆ๋ฐ๊พธ๊ธฐ(renaming)๋ฅผ ํด์ ์ป๋๋ค๊ณ ๋ณผ ์ ์๋ค. ์ด๋ฅผ ๋ค์๊ณผ ๊ฐ์ด ํ์ํ ์ ์๋ค.(p.164์ฐธ์กฐ)
( a b c d e f )
( c d f b e a )
์ํ ํ์(a cycle notation)๋ก ์ฐ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค( c d f b e a )
( a c f ) ( b d )
ํด์ค : a๊ฐ c๋ก ๋ฐ๋๋ ๊ฒ(a goes to c)์ a->c๋ผ๊ณ ํ์ํ๋ค. ๋ฐ๋ผ์ ์์ ํํ์ a->c->f->a, b->d->b๋ฅผ ๋ํ๋ธ๋ค.e->e๊ฐ์ด ๋ณํ์ง ์๋ ๊ฒ์ ์๋ตํ๋ค.
ํด์ค : a๊ฐ c๋ก ๋ฐ๋๋ ๊ฒ(a goes to c)์ a->c๋ผ๊ณ ํ์ํ๋ค. ๋ฐ๋ผ์ ์์ ํํ์ a->c->f->a, b->d->b๋ฅผ ๋ํ๋ธ๋ค.e->e๊ฐ์ด ๋ณํ์ง ์๋ ๊ฒ์ ์๋ตํ๋ค.
2.2.1. Products of permutations ¶
๋ ์์ด์ ๊ณฑํ๋ค. (ํฉ์ฑํจ์์ ๋น์ทํ๋ค.)
(a b c d e f ) ร (a b c d e f )
(c d f b e a ) (b d c a f e )
= (a b c d e f )
(c a e d f b )
์ด๋ฅผ a cycle notation์ผ๋ก ์ฐ๋ฉด(c d f b e a ) (b d c a f e )
= (a b c d e f )
(c a e d f b )
(a c f ) (b d )(a b d )(e f) = (a c e f b)
๊ณผ์ ์ ์ผ์ชฝ๋ถํฐ ์์ํด์ ์ค๋ฅธ์ชฝ์ผ๋ก ๊ฐ๋ฉด์ ์ฐพ๋ ๋ฐฉ์์ด๋ค. a๋ถํฐ ์์ํ๋ฉด a->c์ด๊ณ , c์์ ์์ํ๋ฉด c->f->e์ด๋ฐ ์์ผ๋ก ์ฐพ์ ์ ์๋ค. ์ด ๊ณผ์ ์ ์ปดํจํฐ๋ก ์๋ํด๋ณด์.2.2.2. Algorithm A ¶
A1. ๋ชจ๋ ์ผ์ชฝ ๊ดํธ์ ํ์ ์ ๋จ๊ธด๋ค. ์ค๋ฅธ์ชฝ ๊ดํธ๋ฅผ ์ผ์ชฝ ๊ดํธ ๋ค์ ๋ฌธ์๋ก ๋ฐ๊พธ๊ณ ํ์ ์ ๋จ๊ธด๋ค.
A3. ๋ค์๋ฌธ์๋ฅผ CURRENT๋ก ์ธํ ํ๋ค.
A4. ์ค๋ฅธ์ชฝ์ผ๋ก ๊ฐ๋ฉด์ CURRENT์ ๊ฐ์ ๋ฌธ์๋ฅผ ์ฐพ๋๋ค. ์ฐพ์ ๊ฒฝ์ฐ ํ์ ์ ๋จ๊ธฐ๊ณ A3๋ก ๊ฐ๋ค. (๋ชป ์ฐพ๊ณ ์ค๋ฅธ์ชฝ ๋๊น์ง ๊ฐ๋ฉด A5๋ก ๊ฐ๋ค.)
A5. STARTโ CURRENT์ด๋ฉด CURRENT๋ฅผ ์ถ๋ ฅํ๊ณ ์ ์ผ์ชฝ๋ถํฐ ์์ํด์ A4๋ก ๊ฐ๋ค.( ๊ฐ์ผ๋ฉด A6๋ก ๊ฐ๋ค.)
A6. (์์ ํ ์ฌ์ดํด์ ์ฐพ์์ผ๋ฏ๋ก) ์ค๋ฅธ์ชฝ ๊ดํธ๋ฅผ ๋ซ๊ณ A2๋ก ๊ฐ๋ค.
* Timing์) (a c f g) -> (a c f g a
A2. ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ๊ฐ๋ฉด์ ํ์ ์ด ์๋ ์ฒซ๋ฒ์งธ ๋ฌธ์๋ฅผ START๋ผ๊ณ ํ๋ค. ์ผ์ชฝ ๊ดํธ์ ๊ทธ ๋ฌธ์๋ฅผ ์ถ๋ ฅํ๊ณ ํ์ ์ ๋จ๊ธด๋ค. ๋ชจ๋ ๋ฌธ์์ ํ์ ์ด ๋จ์ ๊ฒฝ์ฐ ์ข
๋ฃํ๋ค.A3. ๋ค์๋ฌธ์๋ฅผ CURRENT๋ก ์ธํ ํ๋ค.
A4. ์ค๋ฅธ์ชฝ์ผ๋ก ๊ฐ๋ฉด์ CURRENT์ ๊ฐ์ ๋ฌธ์๋ฅผ ์ฐพ๋๋ค. ์ฐพ์ ๊ฒฝ์ฐ ํ์ ์ ๋จ๊ธฐ๊ณ A3๋ก ๊ฐ๋ค. (๋ชป ์ฐพ๊ณ ์ค๋ฅธ์ชฝ ๋๊น์ง ๊ฐ๋ฉด A5๋ก ๊ฐ๋ค.)
A5. STARTโ CURRENT์ด๋ฉด CURRENT๋ฅผ ์ถ๋ ฅํ๊ณ ์ ์ผ์ชฝ๋ถํฐ ์์ํด์ A4๋ก ๊ฐ๋ค.( ๊ฐ์ผ๋ฉด A6๋ก ๊ฐ๋ค.)
A6. (์์ ํ ์ฌ์ดํด์ ์ฐพ์์ผ๋ฏ๋ก) ์ค๋ฅธ์ชฝ ๊ดํธ๋ฅผ ๋ซ๊ณ A2๋ก ๊ฐ๋ค.
์ ๋ชจ๋ฅด๊ฒ ๋ค.
2.2.3. Another Approach(Algorithm
¶
What is this computer-oriented method for permutation multipulication?
์ค๋ฅธ์ชฝ์์ ์ผ์ชฝ์ผ๋ก ์ค๋ฉด์ ๋ต์ ์ฐพ๋ ๋ฐฉ๋ฒ์ด๋ค.
(์ฌ๊ธฐ์๋ ์ฑ ์ ์๋ Table2(p.173)๋ฅผ ๋ด์ผ ํ๋ค. ์ธ๋ก ํ ์ค์ด Ti๋ฅผ ๋ํ๋ธ๋ค. ๊ทธ ๋ฐ์ i, j, Z ๊ฐ์ ์ ์ด ๋์ผ๋ฉด ์ดํดํ ์ ์๋ค. n์ ๋ฌธ์์ ๊ฐ์์ด๋ค.)
B1. ๋ชจ๋ 1โคkโคn์ ๋ํด์ Tk โ k. ์ค๋ฅธ์ชฝ๋ถํฐ ์ฝ์ ์ค๋น๋ฅผ ํ๋ค.
B2. ์์ ์ค๋ฅธ์ชฝ๋ถํฐ ํ๋์ฉ ์ฝ์ผ๋ฉด์
B4. Tj โ Z ํ์ B2๋ก.
์ค๋ฅธ์ชฝ์์ ์ผ์ชฝ์ผ๋ก ์ค๋ฉด์ ๋ต์ ์ฐพ๋ ๋ฐฉ๋ฒ์ด๋ค.
(์ฌ๊ธฐ์๋ ์ฑ ์ ์๋ Table2(p.173)๋ฅผ ๋ด์ผ ํ๋ค. ์ธ๋ก ํ ์ค์ด Ti๋ฅผ ๋ํ๋ธ๋ค. ๊ทธ ๋ฐ์ i, j, Z ๊ฐ์ ์ ์ด ๋์ผ๋ฉด ์ดํดํ ์ ์๋ค. n์ ๋ฌธ์์ ๊ฐ์์ด๋ค.)
B1. ๋ชจ๋ 1โคkโคn์ ๋ํด์ Tk โ k. ์ค๋ฅธ์ชฝ๋ถํฐ ์ฝ์ ์ค๋น๋ฅผ ํ๋ค.
B2. ์์ ์ค๋ฅธ์ชฝ๋ถํฐ ํ๋์ฉ ์ฝ์ผ๋ฉด์
) ์ด๋ฉด Zโ0ํ๊ณ B2๋ฐ๋ณต
( ์ด๋ฉด B4๋ก.
๊ทธ ์ธ์๋ i์ธ xi๋ฅผ ๊ฐ์ง๊ณ B3๋ก
B3. ZโTi๋ฅผ ํ๊ณ ๋์ Ti = 0์ด๋ฉด jโi๋ฅผ ํ ๋ค B2๋ก.( ์ด๋ฉด B4๋ก.
๊ทธ ์ธ์๋ i์ธ xi๋ฅผ ๊ฐ์ง๊ณ B3๋ก
B4. Tj โ Z ํ์ B2๋ก.
- Timing
์ฐ์ต๋ฌธ์ 10์ ์๋ค.