C语言通过深度优先搜索来解电梯问题和N皇后问题的示例
N皇后问题 #include <stdio.h> #include <math.h> #define MAX 101 int total = 0; char m[MAX][MAX]; int is_ok(int s,int i,int *a) { int j ; for(j=1 ; j< s ; j++) if( (abs(i-a[j]) == abs(s-j)) || (i == a[j])) /*按行填入,所以只要检查列和斜列是否有皇后即可*/ return 0 ; return 1 ; } void nfind(int s,int n,int *a) { int i,p,q; if( s > n) { total ++ ; printf("========The num of %d is ========== ",total); for(p=1 ; p<= n ; p++) { for(q=1; q<=n ; q++) printf("%c ",m[p][q]); printf(" "); } } else { for(i=1 ;i<= n; i++) if(is_ok(s,i,a)) { a[s]=i ; m[s][i]='O' ; nfind(s+1,n,a); m[s][i]='*' ; } } } int main(void) { int n,a[MAX]={0}; scanf("%d",&n); memset(m,'*',sizeof(m)); nfind(1,a); printf(" total=%d ",total); system("pause"); return 0; } 电梯问题 5 1 5 3 3 1 2 5 示例输出: 复制代码 代码如下: 3 实现代码: #include <stdio.h> #define MAX 501 int a,b,n ; int v[MAX],flag=0 ; void trytofind(int x,int total) { if(x-v[x] == b || x+v[x] == b) { if ( total < flag || flag == 0) flag = total ; } else { if(x+v[x] <= n) trytofind(x+v[x],total+1); if(x-v[x] >= 1) trytofind(x-v[x],total+1); } } int main(void) { int i,j,k ; scanf("%d %d %d",&n,&a,&b); for(i=1 ; i<= n; i++) scanf("%d",&v[i]); trytofind(a,1) ; if(flag) printf("%d ",flag); else printf("-1 "); system("pause"); return 0 ; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |