经典的递归程序设计中的2到题目
1、八皇后问题
国际象棋棋盘走法,用递归实现所有的可能性;
棋盘:
(1)、代码如下:
#include<stdio.h>
typedef unsigned char boolean;
#define TRUE 1
#define FALSE 0
#define EIGHT 8
void showChess(int (*chess)[EIGHT]); //显示棋盘
boolean isSafe(int (*chess)[EIGHT], int row, int col); //判断这个位置是否安全
void eightQueen(int (*chess)[EIGHT], int row); //八皇后的递归程序
void eightQueen(int (*chess)[EIGHT], int row){
int colIndex;
if(row >= EIGHT){
showChess(chess);
}else{
for(colIndex = 0; colIndex < EIGHT; colIndex++){
if(isSafe(chess, row, colIndex) == TRUE){
chess[row][colIndex] = 1;
eightQueen(chess, row+1);
chess[row][colIndex] = 0;
}
}
}
}
boolean isSafe(int (*chess)[EIGHT], int row, int col){
int rowIndex;
int colIndex;
for(rowIndex = row-1; rowIndex >= 0; rowIndex--){
if(chess[rowIndex][col] == 1){
return FALSE;
}
}
for(rowIndex = row-1, colIndex = col-1; rowIndex >= 0 && colIndex >= 0; rowIndex--, colIndex--){
if(chess[rowIndex][colIndex] == 1){
return FALSE;
}
}
for(rowIndex = row-1, colIndex = col+1; rowIndex >= 0 && colIndex < EIGHT; rowIndex--, colIndex++){
if(chess[rowIndex][colIndex] == 1){
return FALSE;
}
}
return TRUE;
}
void showChess(int (*chess)[EIGHT]){
int i;
int j;
int static count;
printf("解:%d\n", ++count);
for(i = 0; i < EIGHT; i++){
for(j = 0; j < EIGHT; j++){
printf("%4d ", chess[i][j]);
}
printf("\n");
}
}
void main(void){
int chess[EIGHT][EIGHT] = {0};
eightQueen(chess, 0);
}
(2)、运行结果:
因为4个方向,每一个方向都有23种解法!!!
2、全排列问题
从n个数据中挑选m个数据,每个数据只能取一次,输出其全部组合的可能性;
(1)、代码如下:
#include<stdio.h>
#include<string.h>
void fullArray(char *sourceStr, int sourceLen, int *used, int i, char *resStr, int count);
void fullArray(char *sourceStr, int sourceLen, int *used, int i, char *resStr, int count){
int index;
if(i >= count){
printf("%s\n", resStr);
}else{
for(index = 0; index < sourceLen; index++){
if(used[index] == 0){
resStr[i] = sourceStr[index];
used[index] = 1;
fullArray(sourceStr, sourceLen, used, i+1, resStr, count);
used[index] = 0;
}
}
}
}
void main(void){
char sourceStr[80];
int used[80] = {0};
char resStr[80] = {0};
int count;
printf("请输入字符串: ");
gets(sourceStr);
printf("请问要几个进行全排列? ");
scanf("%d", &count);
fullArray(sourceStr, strlen(sourceStr), used, 0, resStr, count);
}
(2)、运行结果:
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。