3.凑算式 B DEF A + --- + ------- = 10 C GHI （如果显示有问题，可以参见【图1.jpg】） 这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。 比如： 6+8/3+952/714 就是一种解法， 5+3/1+972/486 是另一种解法。 这个算式一共有多少种解法？ 注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。
思路：不能认为这三个数都是整数，可能3个分数加起来正好组成一个整数，举个例子啊1/3+2/3=1，前2个数都是分数可结果是整数，用double可能会造成精度问题，所以要最好将式子变一下，ACGHI+BGHI+CDEF=10CGHI
答案：29
5.抽签 X星球要派出一个5人组成的观察团前往W星。 其中： A国最多可以派出4人。 B国最多可以派出2人。 C国最多可以派出2人。 .... 那么最终派往W星的观察团会有多少种国别的不同组合呢？ 下面的程序解决了这个问题。 数组a[] 中既是每个国家可以派出的最多的名额。 程序执行结果为： DEFFF CEFFF CDFFF CDEFF CCFFF CCEFF CCDFF CCDEF BEFFF BDFFF BDEFF BCFFF BCEFF BCDFF BCDEF .... (以下省略，总共101行) #include <stdio.h> #define N 6 #define M 5 #define BUF 1024 void f(int a[], int k, int m, char b[]) { int i,j; if(k==N){ b[M] = 0; if(m==0) printf("%s\n",b); return; } for(i=0; i<=a[k]; i++){ for(j=0; j<i; j++) b[M-m+j] = k+'A'; } } int main() { int a[N] = {4,2,2,1,1,3}; char b[BUF]; f(a,0,M,b); return 0; } 仔细阅读代码，填写划线部分缺少的内容。 注意：不要填写任何已有内容或说明性文字。
#include <stdio.h> #define N 6 #define M 5 #define BUF 1024 //a为每个国家可以派出的人数，k为目前正在k国选人，m为剩余的人数，b为保存已经选到的人数 void f(int a[], int k, int m, char b[]) { int i,j; //6个国家都选过了 if(k==N){ //相当于b[M] = '\0';加结束符 b[M] = 0; //人都选够了 if(m==0) printf("%s\n",b); return; } //枚举每个国家选的人数 for(i=0; i<=a[k]; i++){ //选j个k国家的人 for(j=0; j<i; j++) b[M-m+j] = k+'A'; //在剩下的国家中选m-j个人 f(a,k+1,m-j,b); } } int main() { int a[N] = {4,2,2,1,1,3}; char b[BUF]; f(a,0,M,b); return 0; }7.剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来，要求必须是连着的。 （仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。 请你计算，一共有多少种不同的剪取方法。 请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：先枚举每次剪得数字，最后深搜看能否连到一块
答案：116
public class Main { static int[][] map = new int[3][4]; static int[] num = new int[5]; //是一个标记每次剪的数的数组，方便搜索 static int[][] visit = new int[3][4]; static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}}; //total表示的是满足条件的总数，can表示的是每次剪时能连到一块的数量 static int total = 0,can = 0; public static void main(String[] args) { int sum = 1; for (int i=0; i<3; i++) { for (int j=0; j<4; j++) { map[i][j] = sum++; } } sum = 1; for (int i=1; i<=5; i++) sum *= i; dfs(0); //除以5的阶乘的原因是12345,12354等5的全排列都能满足条件，而这是一种剪法 System.out.println(total / sum); } private static void dfs(int cur) { if (cur == 5) { int x = 0,y = 0; for (int i=0; i<3; i++) { for (int j=0; j<4; j++) { visit[i][j] = 0; } } for (int i=0; i<3; i++) { for (int j=0; j<4; j++) { for (int k=0; k<5; k++) { if (map[i][j] == num[k]) { visit[i][j] = 1; x = i; y = j; } } } } can = 0; judge(x,y); if (can == 5) total++; return; } for (int i=1; i<=12; i++) { int j; for (j=0; j<cur; j++) { if (i == num[j]) break; } if (j == cur) { num[cur] = i; dfs(cur+1); } } } private static void judge(int x,int y) { if (visit[x][y] == 0) return; can++; visit[x][y] = 0; for (int i=0; i<4; i++) { int newx = x + dir[i][0]; int newy = y + dir[i][1]; if (newx >=0 && newx <=2 && newy >= 0 && newy <= 3) judge(newx,newy); } } }