6. 계승 함수 n! 은 n ≤ 1일 때 1의 값을 갖고 n > 1일 때 n*(n-1)!의 값을 갖는다. n!을 계산하는 반복 함수와 순환 함수를 C++로 작성 하라.
#include <iostream>
using namespace std;
int Factorial(int n);
int main() {
int n;
cout << "n의 값을 입력하세요 : ";
cin >> n;
cout << n << "!의 값은 : " << Factorial(n) << endl;
}
// 반복함수
int Factorial(int n) {
int res = 1;
if (n <= 1)
return 1;
else {
for (n; n > 0; n--)
res *= n;
return res;
}
}
// 순환함수
int Factorial(int n) {
int res;
if (n <= 1)
return 1;
else
return n * Factorial(n - 1);
}
* 코드 실행 시, 반복 함수 부분이나 순환 함수 부분 둘 중에 하나는 주석 처리 후 실행 시켜야 함
( 같은 기능을 하는 같은 이름의 함수임 )
7. 피보나치 수는 다음과 같이 정의된다. i
#include <iostream>
using namespace std;
int Fibonacci(int i);
int main() {
int i;
cout << "몇 번째까지 피보나치 수열을 구할까요 : ";
cin >> i;
cout << "결과 : " << Fibonacci(i) << endl;
}
//순환함수
int Fibonacci(int i) {
if (i == 0)
return 0;
else if (i == 1)
return 1;
else
return Fibonacci(i-1)+Fibonacci(i-2);
}
//반복함수
int Fibonacci(int i) {
int f0 = 0;
int f1 = 1;
int f2;
if (i == 0)
return f0;
else if (i == 1)
return f1;
else {
for (int j = 2; j <= i; j++) {
f2 = f1 + f0;
f0 = f1;
f1 = f2;
}
return f2;
}
}
* 코드 실행 시, 반복 함수 부분이나 순환 함수 부분 둘 중에 하나는 주석 처리 후 실행 시켜야 함
( 같은 기능을 하는 같은 이름의 함수임 )
* 참고 : https://doompa.tistory.com/177
8.
#include <iostream>
using namespace std;
int Binomial_Coefficient(int n, int m);
// 이항 계수는 결국 조합(ex: ₄C₂)과 같은 법칙
int main() {
int n, m;
cout << "n과 m의 값을 입력하세요 : ";
cin >> n >> m;
cout << "[n m]의 값은 " << Binomial_Coefficient(n, m) << endl;
}
int Binomial_Coefficient(int n, int m) {
if (m == 0 || n == m)
return 1;
else
return Binomial_Coefficient(n - 1, m) + Binomial_Coefficient(n - 1, m - 1);
}
* 참고 : https://jaimemin.tistory.com/126
* 이항 계수에 대한 이해
9. 이항 계수를 계산하는 반복 함수를 작성하라. 그리고 그 함수와 동등한 순환 함수로 변환하라.
* 동등한 순환 함수로 변환 하는 것은 8번 문제와 동일하기 때문에 생략
#include <iostream>
using namespace std;
int Binomial_Coefficient(int n, int m);
int main() {
int n, m;
cout << "n과 m의 값을 입력하세요 : ";
cin >> n >> m;
cout << "[n m]의 값은 " << Binomial_Coefficient(n, m) << endl;
}
int Binomial_Coefficient(int n, int m) {
int n_res = 1;
int m_res = 1;
int k = m;
//반복문 안에서 m에 감소연산자 붙어있으므로 반복문을 m번 실행하기 위해
// k 값을 m으로 선언 후 반복 횟수로 지정
if (m == 0 || n == m)
return 1;
else {
for (int i = 0; i < k; i++) {
n_res *= n;
m_res *= m;
n--;
m--;
}
return n_res / m_res;
}
}
* 단순하게 생각해서 짠 코드
* 2중 배열 이용하는 방법도 이해 하기 (https://jaimemin.tistory.com/127님 해결 방법)
10. Ackermann 함수 A(m, n)은 아래와 같이 정의 된다.
이 함수는 m, n의 값이 아주 작을 때에도 급속히 증가하는 성질이 있다. 이 함수를 계산하는 순환 함수를 작성하라. 그리고 이 함수를 계산하는 비순환 함수를 작성하라.
- 순환함수
#include <iostream>
using namespace std;
int Ackermann(int m, int n);
int main() {
int m, n;
cout << "n과 m을 입력하세요 : ";
cin >> m >> n;
cout << "A(" << m << ", " << n << ")의 값 : " << Ackermann(m, n) << endl;
}
//순환함수
int Ackermann(int m, int n) {
if (m == 0)
return n + 1;
else if (n == 0)
return Ackermann(m - 1, 1);
else
return Ackermann(m - 1, Ackermann(m, n - 1));
- 비순환 함수
#include <iostream>
using namespace std;
int Ackermann(int m, int n);
int main() {
int m, n;
cout << "n과 m을 입력하세요 : ";
cin >> m >> n;
cout << "A(" << m << ", " << n << ")의 값 : " << Ackermann(m, n) << endl;
}
//비순환 함수
int Ackermann(int m, int n) {
int list[100000];
int esp = 0;
int count = 0;
list[esp++] = m;
list[esp] = n;
while (1) {
if (esp == 0) {
return list[esp];
}
else if (list[esp - 1] == 0) {
count++;
list[esp - 1] = list[esp] + 1;
esp = esp - 1;
}
else if (list[esp] == 0) {
count++;
list[esp - 1] = list[esp - 1] - 1;
list[esp] = 1;
}
else {
count++;
list[esp + 1] = list[esp] - 1;
list[esp] = list[esp - 1];
list[esp - 1] = list[esp - 1] - 1;
esp = esp + 1;
}
}
}
// A(1, 1)을 넣어서 코드 해석
