Solved the question include Factorial, Fibonacci, Hani Tower and Eight Queens Question.
完整程式碼:
//複習recursive及iteration
/*
同樣功能用recursive(遞迴)及iteration(疊代法)的方式去寫:
功能1 : 計算Factorial numbers (N階層) N!=N*(N-1)*...*3*2*1
功能2 : 計算費氏數列 Fibonacci(N)= F(N-1)+F(N-2) = 2*F(N-2)+F(N-3)
功能3 : 河內塔
功能4 : 八個皇后問題
*/
#include "pch.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
void introdution(void);//introduction
int Factorial_numbers_recur(int);//功能1 recursive
int Factorial_numbers_iter(int);//功能1 iteration
int Fibonacci_recur(int);//功能2 recursive
int Fibonacci_iter(int); //功能2 iteration
void HaniTower(int,char,char,char);//功能3 recursive
void eight_queens(int);//功能4 recursive
int attacked(int,int);//功能4中的判斷皇后是否會打架
void out_put_queen(); //功能4中的顯示輸出結果
#define MAXQUEEN 8 //功能4的
int queen[MAXQUEEN] = {}; //功能4的
int total_solution = 0, first = 0; //功能4的
int main()
{
int choose,method,ans,N=0,count= 0;
introdution();//介紹選擇
char a = 'A', b = 'B', c = 'C';
while (1) {
printf("Please choose the function(1/2/3/4/5):");
scanf_s("\n%d",&choose);
switch (choose) {
case 1:
printf("Please choose the method(1:recursive 2:iteration):");
scanf_s("\n%d", &method);
printf("Please enter the N value(Ans = F(N-1)+F(N-2)):");
scanf_s("\n%d", &N);
if(method == 1) ans = Fibonacci_recur(N);//use recursive method
else if(method == 2) ans = Fibonacci_iter(N);//use iteration method
else printf("\n ERROR!Please enter the right command.\n");
printf("The F(%d) answer is %d, and the method is %d.\n", N, ans, method);
printf("—————————————\n");
break;
case 2:
printf("Please choose the method(1:recursive 2:iteration):");
scanf_s("\n%d", &method);
printf("Please enter the N value(Ans = N!):");
scanf_s("\n%d", &N);
if (method == 1) ans = Factorial_numbers_recur(N);//use recursive method
else if (method == 2) ans= Factorial_numbers_iter(N);//use iteration method
else printf("\n ERROR!Please enter the right command.\n");
printf("The %d! answer is %d, and the method is %d.\n",N,ans,method);
printf("—————————————\n");
break;
case 3:
printf("Please enter the N layers of HaniTower:");
scanf_s("\n%d", &N);
printf("**********************\n");
HaniTower(N,a,b,c);
printf("**********************\n");
if (N == 1)count = 1;
else count = pow(2,N)- 1;
printf("Total moves number is %d\n\n", count);
printf("—————————————\n");
break;
case 4:
eight_queens(0);
printf("\nthe total solutions for eight queen question are %d.\n",total_solution);
total_solution = 0;
first = 0;
printf("—————————————\n");
break;
case 5:
return 0;
break;
default:
break;
}
}
}
void introdution(void) {//introduction
printf("You can choose many funtions:(1/2/3/4) \n");
printf("\n******************************************\n");
printf(" 1.Count the Fibonacci numbers \n");
printf(" 2.Count the Factorial numbers \n");
printf(" 3.Count the HaniTower quension \n");
printf(" 4.Count the Eight queens quension \n");
printf(" 5.Introduction \n");
printf(" 6.Exit \n");
printf("********************************************\n");
}
/*功能1*/
int Fibonacci_recur(int N) {//功能1 recursive
int ans = 0;
if (N == 0)ans = 0;
else if (N == 1)ans = 1;
else ans = Fibonacci_recur(N - 1) + Fibonacci_recur(N - 2);
return ans;
}
int Fibonacci_iter(int N) { //功能1 iteration
int prev_1 = 0,prev_2 = 0,total = 0;
for (int i = 0; i <= N; i++) {
if (i == 0) {
total = 0;
}
else if (i == 1) {
total = 1;
}
else {
prev_2 = total;
total = total + prev_1;
prev_1 = prev_2;
}
}
return total;
}
/*功能2*/
int Factorial_numbers_recur(int N) {//功能2 recursive
int ans = 0;
if (N == 1) {
ans = 1;
}
else ans = N * Factorial_numbers_recur(N-1);
return ans;
}
int Factorial_numbers_iter(int N) {//功能2 iteration
int ans = 1;
for (int i = 1; i <= N; i++) {
ans = ans * i;
}
return ans;
}
/*功能3*/
void HaniTower(int N, char a, char b, char c) {//功能3 recursive
//將(N-1)層的河內塔藉由C從A移到B (a,c,b)
//將第N層從A移到C
//將(N-1)層的河內塔藉由A從B移到C (b,a,c)
if (N == 1) {
printf("move disk 1 from %c to %c\n", a, c);
}
else
{
HaniTower(N - 1, a, c, b);
printf("move disk %d from %c to %c\n", N, a, c);
HaniTower(N - 1, b, a, c);
}
}
/*功能4*/
void eight_queens(int q) {//功能4 recursive
//q :第幾行的queen
int i = 0; //第幾列
while (i<MAXQUEEN) {
if (!attacked(i, q)) {
queen[q] = i;
if (q == 7) {
out_put_queen();
}
else eight_queens(q+1);
}
i++;
}
}
int attacked(int row,int col) {
for (int i = 0; i < col; i++) {
if (queen[i] == row) {
return 1;
}
}
if (col != 0) {
if (queen[col - 1] == (row + 1) || queen[col - 1] == (row - 1)) {
return 1;
}
else return 0;
}
else return 0;
}
void out_put_queen() {
if (first == 0) {
printf("The first answer is :\n");
printf("————————\n");
for (int q = 0; q <= 7; q++) {
for (int i = 0; i <= 7; i++) {
printf("|");
if (i == queen[q]) {
printf("§");
}
else printf(" ");
}
printf("|");
printf("\n————————\n");
}
first = 1;
}
total_solution++;
}
執行結果::
_______________________________________________
我們透過閱讀,拼湊出真實世界的面貌,
並在反覆的探索及思維中,打破由自我無知與偏見所建立的籓籬。