계산기코어 2.1 뜯어보기 7강. 조합
안녕하세요? noname01입니다.
이번에는 조합을 계산하는 트리거를 살펴 봅시다.
먼저 조합의 정의부터 살폅봅시다.
nCr = nPr / r!
자 순열을 계산하는 트리거와 팩토리얼을 계산하는 트리거, 그리고 나눗셈을 계산하는
트리거를 모두 알아 봤으니 그걸 섞으면 되겠죠??
여기서 잠깐!! 고등학교 수학1 과정을 공부해 보신 분들이라면 다들 "nCr = nC(n-r)"
이 성립한다는 사실을 잘 알고 계실겁니다. 그런데 뜬금없이 이게 왜 나오냐구요?? 앞서
순열과 팩토리얼을 계산하는 트리거를 보시면 아시겠지만 두 계산 모두 r값이 작아지면
계산을 위한 반복작업이 줄어들어 계산이 빨라지게 됩니다. 즉 조합을 계산할때 r과
(n-r)을 비교하여 더 작은 수를 적용해 계산하면 더 빠르게 동일한 결과를 얻어낼 수
있습니다.
그래서 계산하기 전 n이 r보다 큰지 검사하는 과정에서 두 수의 차도 함께 구합니다.
그리고 먼저 nPr을 계산해서 A값에 대입해두고, r!을 계산해서 B값에 대입한 뒤 나눗셈을
수행합니다.
그런데 곱셈의 경우 우리는 완벽하게 하나의 계산으로 포장을 했기 때문에 c값에 다음 값
8^7 * 1 : X=a+b; a=b=0;
을 더해주기만 하면 자동으로 a와 b를 곱한 값이 X에 대입되는데, 나눗셈의 경우 이렇게
포장을 하지 못했죠. 그래서 조합을 계산할때 꼼수를 씁니다. 순열은 순열대로 계산해서
변수 A에 대입해두고 팩토리얼은 팩토리얼대로 계산해서 변수 B에 대입해둔뒤 아예 제어변수
C를 조합 계산 영역에서 나눗셈 계산 영역으로 이동시켜 버립니다. 그러면 마지막 과정인
나눗셈이 수행되어 X에 그 결과값이 대입되겠죠.
자 그럼 이 과정을 수행하기 위해 호출해야 하는 트리거를 살펴봅시다.
------------------------------------------------
◎시작
8^9 * 1 : a=A;
8^8 * 1 : b=B;
8^7 * 3 : x=compare(&a, &b); //a와 b의 크기를 비교합니다.
8^7 * 1 : X=a+b; a=b=0; //a와 b의 차를 X에 대입합니다.
X : ①동작
------------------------------------------------
①
X : x값을 비교한다.
x의 값이 2 이하일 경우 ②동작 //a >= b 인 경우로 이상없음
x의 값이 3 이상일 경우 ③동작 //a < b 인 경우로 오류발생
------------------------------------------------
② //A와 B의 차와, B의 크기를 비교합니다.(r과 n-r중 더 작은값을 구하기 위한 비교)
8^9 * 5 : a=X; //시작 과정에서 X에 대입된 a와 b의 차를, 다시 a에 대입합니다.
8^8 * 1 : b=B;
8^7 * 3 : x=compare(&a, &b);
X : ④동작
------------------------------------------------
------------------------------------------------
③
X : 오류처리를 위해 C값을 996으로 점프 //오류코드는 2강 참고
------------------------------------------------
④
X : x값을 비교한다.
x의 값이 2 이하일 경우 ⑤동작 //(A-B) >= B 인 경우로 ACB를 계산
x의 값이 3 이상일 경우 ⑥동작 //(A-B) < B 인 경우로 AC(A-B)를 계산
------------------------------------------------
⑤
X : X=1;
X : ⑨동작
------------------------------------------------
------------------------------------------------
⑥
8^8 * 7 : B=X; X=0; //B에 원래 값 대신 A-B를 대입
X : ⑦동작
------------------------------------------------
------------------------------------------------
⑦
X : X=1;
X : ⑨동작
------------------------------------------------
------------------------------------------------
⑧
X : --A; //A를 1 감소시킵니다. 6강 순열 부분의 ⑤번 연산과정 참고
X : ⑨동작
------------------------------------------------
⑨
X : B값을 비교한다.
B값이 0 이하일 경우 ⑩동작
B값이 1 이상일 경우 ⑪동작
------------------------------------------------
⑩
8^9 * 7 : A=X; X=0; //계산된 APB를 A에 대입한다.
X : ⑫동작
------------------------------------------------
------------------------------------------------
⑪
8^9 * 1 : a=A;
8^8 * 2 : b=X;
8^6 * 4 : X=t=0;
8^6 * 1 : X=a*b; t=a; a=b=0;
X : --B; //B값을 1 감소시킵니다.
X : ++R; //B!을 계산해야 하므로 B의 값이 1 줄어들때마다 R의 값을 1 증가시킨다.
X : ⑧동작
------------------------------------------------
------------------------------------------------
⑫ //APB가 계산되었으므로 이제 R에 대입된 B값을 이용하여 B!을 계산한다.
X : X=1;
X : ++R; //R값을 1 증가시킵니다. 6강 팩토리얼 부분의 시작과정 참고
X : ⑬동작
------------------------------------------------
⑬
X : R값을 비교한다.
R값이 1 이하일 경우 ⑭동작 //어차피 1은 곱하나 마나 이므로 바로 계산완료
R값이 2 이상일 경우 ⑮동작
------------------------------------------------
⑭
8^8 * 7 : B=X; X=0; //계산된 B!을 B에 대입한다.
X : ⓐ동작
------------------------------------------------
------------------------------------------------
⑮
X : --R; //B값을 1 감소시킵니다.
8^9 * 2 : a=b=R;
8^8 * 2 : b=X;
8^6 * 4 : X=t=0;
8^6 * 1 : X=a*b; t=a; a=b=0;
X : ⑬동작
------------------------------------------------
------------------------------------------------
ⓐ //마지막으로 A/B를 연산하기 위한 과정
X : 나눗셈 연산을 위해 C값을 1190으로 점프 //제어변수 범위는 2강 참고
------------------------------------------------
사실 거듭제곱 이후의 연산들은 모두 기존에 만들어둔 연산들을 이용해, 그 정의에 따라
순서대로 연산한 것으로 특별히 어려운 점은 없을 것입니다.
이제 조합 연산을 실제로 구현한 트리거를 살펴봅시다.
앞에서도 몇번 그랬지만 설명한 실행단위와 트리거의 순서가 약간 다를 수도 있습니다.
이제 우리는 조합을 계산하는 트리거까지 살펴 보았습니다. 다음강에서 마지막으로 난수를
생성하는 트리거를 살펴봅시다.
원래는 여기에 합치려 했는데 합치면 분량이 너무 늘어날듯 해서 따로 분리하기로 했답니다.
[50]계산기코어 2.1 뜯어보기 1강. 전체구조와 호출방식
[50]계산기코어 2.1 뜯어보기 2강. 오류와 입력처리
[50]계산기코어 2.1 뜯어보기 3강. 덧셈, 뺄셈, 곱셈
[50]계산기코어 2.1 뜯어보기 4강. 나눗셈
[50]계산기코어 2.1 뜯어보기 5강. 제곱근
[50]계산기코어 2.1 뜯어보기 6강. 거듭제곱, 팩토리얼, 순열
[50]계산기코어 2.1 뜯어보기 7강. 조합
[50]계산기코어 2.1 뜯어보기 8강. 난수 생성
