1,一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法编程实现。[中国某著名通信企业H面试题]
2，2：八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是19世纪著名的数学家高斯1850年提出：在8×8格的国际象棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。[英国某著名计算机图形图像公司面试题]
有多少人看过，写过

第一题，想半天，也没啥思路
百度了个详细的

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define GOAL 90    //目标环数
   
5. #define MAX_SRE 10    //每次射击的最大环数
   
6. #define MAX_CNT 10    //总共射击次数
   
7. 
   
8. int score[MAX_CNT];    //有效环数
   
9. int num = 0;    //可能的射击组合数
   
10. 
    
11. //筛选有效环数，返回可能的组合数，否则返回-1
    
12. int ValidScore(int sre, int cnt, int balance)
    
13. {
    
14.     balance -= sre;    //这次射击以后还需要射击的总环数
    
15. 
    
16.     if(balance<0 || balance>((MAX_CNT-cnt)*MAX_SRE))    //退出递归的条件
    
17.     {
    
18.         cnt--;    //当最后一环不符合要求时，能不影响后面的打印判断
    
19.         return -1;    //不符合条件，结束递归
    
20.     }
    
21.     else
    
22.     {
    
23.         score[cnt-1] = sre;    //存储有效环数
    
24. 
    
25.         while(cnt < 9)    //控制射击次数
    
26.         {
    
27.             cnt++;
    
28.             score[cnt-1] = -1;    //设置一个循环推出条件
    
29. 
    
30.             for(sre=MAX_SRE; sre>=0; sre--)    //从高分往下寻找合适的分数
    
31.             {
    
32.                 if(-1 == ValidScore(sre, cnt, balance))    //若此分不能满足要求，那么低于它的分更不能满足要求了
    
33.                     break;
    
34.             }
    
35. 
    
36.             if(-1 == score[cnt-1])    //若通过上面的for循环，在第cnt次里没有满足要求的环数了，那第cnt次以后的次数就根本不用再继续寻找了
    
37.                 break;
    
38.         }
    
39. 
    
40.         if(9 == cnt && balance <= MAX_SRE)    //最后一次设计可以不用循环来控制，而是直接等于除了前九次以外还需要的环数
    
41.         {
    
42.             score[cnt] = balance;    //最后一次需要射击的环数
    
43. 
    
44.             //打印每一种可能的结果（如果要测目标环数为90的话，建议把这小段注释了，因为总共有92386种可能性）
    
45.             printf("有效得分：");
    
46.             for(cnt=0; cnt<MAX_CNT; cnt++)
    
47.                 printf(" %d", score[cnt]);
    
48.             printf("\n");
    
49. 
    
50.             num++;    //找到一种可能性，总数加一
    
51.         }
    
52.     }
    
53. 
    
54.     return num;
    
55. }
    
56. 
    
57. int main()
    
58. {
    
59.     int cnt = 1;    //射击次数
    
60. 
    
61.     for(score[0]=MAX_SRE; score[0]>=0; (score[0])--)
    
62.         ValidScore(score[0], cnt, GOAL);    //递归筛选有效环数
    
63. 
    
64.     printf("总共有 %d 种可能。\n", num);
    
65. 
    
66.     return 0;
    
67. }
    

复制代码

//其实第一个问题属于背包问题。答案是92378

1. using System;
   
2. class Program
   
3. {
   
4.     static int count = 0;
   
5.     static void Main(string[] args)
   
6.     {
   
7.         shoot(10, 90);//开10枪打90环
   
8.         Console.WriteLine(count);
   
9.     }
   
10.     static void shoot(int num, int score)
    
11.     {
    
12.         if (score < 0 || score > num * 10)
    
13.             return;
    
14.         else if (num == 0)
    
15.             count++;
    
16.         else
    
17.             for (int i = 0; i <= 10; i++)
    
18.             {
    
19.                 shoot(num - 1, score - i);
    
20.             }
    
21.     }
    
22. }
    

复制代码

觉得讲递归算法不错
http://www.cnblogs.com/serviceboy/archive/2009/07/19/1526590.html

算法写得很好！