首页 > 代码库 > 递归、枚举
递归、枚举
1.汉诺塔问题
#include<stdio.h>void han(int,char,char,char );int main(){ int n; char a=‘A‘,b=‘B‘,c=‘C‘; scanf("%d",&n); han(n,a,b,c);}void mov(char a,char b){ printf("%c=>%c\n",a,b);}void han(int n,char a,char b,char c){ if(n==1) mov(a,c); else { han(n-1,a,c,b); mov(a,c); han(n-1,b,a,c); }}
2.进制转换问题
输入两个数，一个表示现有的数eg，另一个表示要转换的几进制数ch。用eg模ch，并用一个数组来存即可。
#include<stdio.h>int main(){ int a[10000]; int eg,ch; int i,j; scanf("%d%d",&eg,&ch); for(i=0; i<10000; i++) a[i]=0; for(i=0; i<10000; i++) { a[i]=eg%ch; eg=eg/ch; } for(i=9999; i>-1; i--) if(a[i]!=0) break; for(j=i; j>-1; j--) printf("%d",a[j]);}
3.八皇后问题
定义一个a[8]数组来存，判断是否满足条件，可用a[j]==i||i-t==a[j]-j||t+i==a[j]+j
示意如下
0 -1 -2 -3 -4 -5 -6 -7
1 0 -1 -2 -3 -4 -5 -6
2 1 0 -1 -2 -3 -4 -5
3 2 1 0 -1 -2 -3 -4
4 3 2 1 0 -1 -2 -3
5 4 3 2 1 0 -1 -2
6 5 4 3 2 1 0 -1
7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14
只要判断i-t==a[j]-j和t+i==a[j]+j就可，之后再进行下一列
#include<stdio.h>int a[8];int cnt=0;void et(int a[8],int t){ int i,j; if(t==8) cnt++; else { for(i=0; i<8; i++) { int ok=1; a[t]=i; for(j=0; j<t; j++) { if(a[j]==i||i-t==a[j]-j||t+i==a[j]+j) { ok=0; break; } } if(ok) et(a,t+1); } }}int main(){ et(a,0); printf("%d",cnt);}
4.二分查找
按半查找即可
#include<stdio.h>a[10]={6,8,14,25,36,45,75,85,99,102};int main(){ int er(int t,int up,int down); int t,ant; scanf("%d",&t); ant=er(t,9,0); printf("%d",ant);}int er(int t,int up,int down){ int m; while(up!=down) { m=down+(up-down)/2; if(a[m]==t) return m+1; if(a[m]<t) down=m+1; else up=m; } return -1;}
5 .枚举排列
按照八皇后的方法来做，如下
a[1000]用来存结果，pl函数内if语句判断是否到边际，else 用来循环1到n并进行回溯。
#include<stdio.h>int a[1000];int n;int main(){ void pl(int t,int a[1000]); scanf("%d",&n); pl(0,a);}void pl(int t,int a[1000]){ int i,j; if(t==n) { for(i=0;i<n;i++) printf("%d",a[i]); printf("\n"); } else{ for(j=1;j<=n;j++) { int k; int ok=1; for(k=0;k<t;k++) { if(a[k]==j) {ok=0;break;} } if(ok) {a[t]=j;pl(t+1,a);} } }}
6，火柴棍问题
直接枚举，先枚举前两个，计算第三个，判断这三个所需的火柴棍数之和加4是否等于n，即可。
#include<stdio.h>int num[]={6,2,5,5,4,5,6,3,7,6};int cnt=0;int de(int d){ int sum=0; if(d==0) return 6; while(d) { sum+=num[d%10]; d=d/10; } return sum;}int main(){ int n; int i,j; scanf("%d",&n); for(i=0;i<1000;i++) { for(j=0;j<1000;j++) { if(de(i)+de(j)+de(i+j)+4==n) cnt++; } } printf("%d",cnt);}
7
递归、枚举
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。