C語言系列 : 以Recursive and Iterative完成八個皇后、河內塔、Factorial和Fibonacci

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++;
}

執行結果::

_______________________________________________

我們透過閱讀,拼湊出真實世界的面貌,
並在反覆的探索及思維中,打破由自我無知與偏見所建立的籓籬。