递归

分书问题

思路

(1) 定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋给这个二维数组。可定义：

int like[5][5] = { {0,0,1,1,0}, {1,1,0,0,1}, {0,1,1,0,1}, {0,0,0,1,0}, {0,1,0,0,1} };

(2) 定义一个整型一维数组book[5]，用来记录书是否已被选用。用下标作为5本书的编号，被选过元素值为1，未被选过元素值为0，初始化皆为0。

int book[5] = {0,0,0,0,0};

(3) 画出思路图。

① 定义试着给第i人分书的函数Try(i)，i = 0,1,2,3,4。

② 试着给第i个人分书，先试分0号书，再分1号书，分2号书，……，因此有一个与结点，让j表示书，j=0，1，2，3，4。

③条件c是由两部分“与”起来的，“第i个人喜欢j书，且j书尚未被分走”。满足这个条件是i人能够得到j书的条件。

④ 如果不满足c条件，则什么也不做，这是直接可解结点。、

⑤ 满足c条件，做三件事：
第一件事：将j书分给i，用一个数组take[i]=j,记住书j给了i，同时记录j书已被选用，book[j]=1.
第二件事：查看i是否为4，如果不为4，表示尚未将所有5个人所要的书分完，这时应递归再试下一个人，即Try(i+1)。若果i==4，则应先使方案数n=n+1，然后输出第n个方案下的每个人所得之书。
第三件事：回溯。让第i人退回j书，恢复j书尚未被选的标志，即book[j]=0.这是在已输出第n个方案之后，去寻找下一个分书方案所必需的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>

int like[5][5] = { {0,0,1,1,0}, {1,1,0,0,1}, {0,1,1,0,1}, {0,0,0,1,0}, {0,1,0,0,1} }; //表示书的喜好情况 
int book[5] = {0,0,0,0,0};  //表示书是否分走 
int take[5] = {0};  //表示分书情况 
int n = 0;
 
void Try(int i){

	int j,k;

	for(j = 0 ; j < 5 ; j++){ //表示书号 
		if(like[i][j] == 1 && book[j] == 0){//这人喜欢这书且书还没被分走 
			take[i] = j;//记录该人拿走该书
			book[j] = 1;//记录该书已被分走 
			if(i == 4){ //所有人都分好书
				n++;//方案数增加，准备打印分数方案
				printf("==========第%d个方案是==========\n",n);
				for(k = 0 ; k < 5 ; k++){
					printf("第%d个人拿的第%d本书\n",k+1,take[k]+1); 
				}		
			}
			else{//书还没分完 
				Try(i+1);//满足这个人的需求后，继续尝试分后边的书 
			}
			book[j] = 0;//回溯时将书退回
		}//如果没有找到就继续尝试下一本书 	
	}
}

int main(){
	
	Try(0);
}

八皇后问题

思路

将整个问题拆解成几个小问题，分步解决。

1.判断是否可以放下皇后棋子（同行同列同对角线上还没有棋子）

2.try函数用来实现递归和回溯

3.打印结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//法一
#include <stdio.h>
#include <math.h>


int place[8] = {0};		//皇后放置的位置
int snum = 0;			//方法总数
void showResult();
int canPlace(int i,int j);
void try(int i);

void showResult(){
	int i;
	printf("===第%d个方案\n",++snum);
	for( i = 0 ; i < 8 ; i++ ){
		printf("第%d行的皇后放置在第%d列\n",i,place[i]);
	}
}
int canPlace(int i,int j){
	int k;
	for(k = 0 ; k < 8 ; k++ ){
		if(place[k] == j || abs(place[k] - j ) == abs(k - i))
			return 0;
	}
	return 1;
}

void try(int i){
	int j;
	if(i == 7){
		showResult();
		return;
	}
	for(j = 0 ; j < 8 ; j++ ){
		if(canPlace(i,j)){ 
			place[i] = j;
			try(i+1);
			place[i] = 0;
		} 
	}
}

int main(){
	try(0);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//相对于法一，法二使用的二维数组更加直观
#include <stdio.h>
#include <math.h>


int chessboard[8][8] = {0};//棋盘的位置是否有元素 
int snum = 0;
int isDanger(int row,int col){ 
	int i,j;
	for( i = 0 ; i < 8 ; i++ ){//row
		if(chessboard[row][i] == 1)
			return 0;
	}
	for( i = 0 ; i < 8 ; i++ ){//column
		if(chessboard[i][col] == 1)
			return 0;
	}
	for( i = 0 ; i < 8 ; i++ ){
		for( j = 0 ; j < 8 ; j++ ){
			if( chessboard[i][j] == 1 && abs(i-row) == abs(j-col) )
				return 0;
		}
	}
	return 1;
}


void printResult(){
	int i,j;
	printf("====第%d个方案====\n",++snum);
	for( i = 0 ; i < 8 ; i++ ){
		for( j = 0 ; j < 8 ; j++ ){
			if( chessboard[i][j] == 1 )
				printf("chessboard[%d][%d]\n",i,j);
		}
	}
}


void eightQueen(int row)
{
	int col;
	if( row > 7 ){
		printResult();
		return ;
	}
	for( col = 0 ; col < 8 ; col++ ){
		if(isDanger(row,col)){
			chessboard[row][col] = 1;
			eightQueen( row + 1 );
			chessboard[row][col] = 0;
		}
	}
}

int main(){

	eightQueen(0);
	
	return 0;

}

背包问题

思路

每个物品有两种状态及放入和未放入。我们假设除最后一个以外的前面已经是最优解，再找出最后一个的最优解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>


int weight[5] = {2,2,6,5,4};
int value[5] = {6,3,5,4,6};

int exp(int i,int j){
	int value1,value2;
	int max = 0;
	
	if(weight[i] <= j && i != -1){					   //物体质量小于背包容量且不是无效数据 
		value1 = exp(i-1,j-weight[i]) + value[i];      //这个物体放入后的价值
		value2 = exp(i-1,j);						   //不放的价值
		value1 > value2 ? (max = value1) : (max = value2); //比较选择放入或不放
	}
	return max;
}

void main(){
	int result;
	result = exp(4,10);//需要检测的物体个数，背包容量
	printf("%d",result);
}

回溯

素数环问题

用1~n共n个不重复整数构造一个环形结构，使相邻两个数之和为素数。

如下图是一个n=6的素数环。

思路

同样把问题拆解成几个负责不同功能的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <math.h>

int isPrime(int n) //判断是否为素数
{
	int i,k;
	k = (int)sqrt(n);
	for(i=2;i<=k;i++)
	{
		if(n%i==0)
			return 0;
	}
	return 1;
}

int canPlace(int *p,int i,int j,int n)  //传入数组首指针，要放置的位置，要放置的数值，数组大小，函数用来检查能不能放入该数
{
	int k,flag;
	for(k=0;k<i;k++)	//检查前面是否已经使用过该数
	{
		if(p[k]==j)
			return 0;
	}
	flag = isPrime(j+p[i-1]); //若放置则与前数和是否为素数
	if(flag==1 && i==n-1)     //若是最后一个位置则需要和第一个数构成素数环
	{
		flag = isPrime(j+p[0]); 
	}
	return flag;
}

void showResult(int *p,int n)  //传入数组首地址和数组大小
{
	int i;
	static count = 0;
	printf("****第%d个解****\n",++count);
	for(i=0;i<n;i++)
	{
		printf("%d ",p[i]);
	}
	printf("\n");
}

void primeCycle(int n)
{
	int i=1,j,k;
	int *p = (int *)malloc(sizeof(int)*n);  //动态开辟数组空间
	memset(p,0,n*sizeof(int));   //数组置零
	p[0] = 1;  //先给第0号位赋上值 ，因为是环状结构，为避免出现相同结构的解，将第一个元素固定。
	while(i>=1)
	{
		for(j=p[i]+1;j<=n;j++)   //找出能在该位置放置的满足条件的第一个数。如果是第一次寻找，则j从1开始，若是回溯，则从上次									确定的值开始
		{
			if(canPlace(p,i,j,n)==1)
			{
				p[i] = j;
				break;
			}
		}
		if(j>n)   //如果上一个循环正常结束，即该位置没有可放置的数
		{
			p[i--] = 0;   //p[i]=0;i--;回溯至上一个位置,这个位置置0。
		}
		else if(i==n-1)   //如果最后一个位置的数也放置完毕，则输出结果，并将前一个数置零以便寻找下一种解情况
		{
			showResult(p,n);
			p[i--] = 0;
		}
		else              //如果还没有放置完数，则将i++继续进行大循环。
			i++;
	}
	free(p); //释放空间
	printf("finished\n");
}

void main()
{
	int n;
	printf("Input an integer\n");
	scanf("%d",&n);
	primeCycle(n);
}

待编辑…