[程序员递归面试问题及解析]面试例题 2：八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是 19 世纪著名的数学家高斯 1850 年提出：在 88 格的国际象棋盘上摆放 8 个皇后，使其不能互相攻击，...+阅读
面试例题 1：一个射击运动员打靶，靶一共有 10 环，连开 10 枪打中 90 环的可能性有多少种？请用递归算法编程实现。[中国某著名通信企业 H面试题]
解析：靶上一共有 10 种可能1 环到 10 环，还有可能脱靶，那就是 0 环，加在一起共 11 种可能。这是一道考循环和递归的面试题。我们在这个程序中将利用递归的办法实现打靶所有可能的演示，并计算出结果。读者会问，难道一定要使用递归？当然不是。我们也可以连续用 10个循环语句来表示程序，代码如下：
for (i1=0;i1=10;i1++)
{
for (i2=0;i2=10;i2++)
{
for (i3=0;i3=10;i3++)
{
......
for (i10=0;i10=10;i10++)
{
if(i1+i2+i3+...+i10=90)
Print();
}
......
}
}
}
但是，上面的循环程序虽然解决了问题，但时间复杂度和空间复杂度无疑是很高的。比较好的办法当然是采用递归的方式，事实上公司也就是这么设计的。递归的条件由以下 4 步完成：
（1）如果出现这种情况，即便后面每枪都打 10 环也无法打够总环数 90，在这种情况下就不用再打了，则退出递归。代码如下：
if(score 0 || score (num+1)*10 ) 次数num 为0～9
{
return;
}
（2）如果满足条件且打到最后一次（因为必须打 10 次），代码如下：
if(num == 0)
{
store2[num] = score;
Output( store2);
return;
}
（3）如果没有出现以上两种情况则执行递归，代码如下：
for(int i = 0; i = 10; ++i)
{
这里实际上为了方便把顺序倒了过来，store2[9]是第1 回
store2[8]是第 2 回store2[0]是第 10 回
store2[num] = i;
Cumput(score - i, num - 1,store2);
}
（4）打印函数，符合要求的则把它打印出来。代码如下：
public static void Output(int[] store2)
{
for(int i = 9; i=0; --i)
{
Console.Write( {0},store2[i]);
}
Console.WriteLine();
sum++;
}
答案：
用 C#编写的完整代码如下：
using System ;
public class M
{
public static int[] store;
相当于设置了全局变量
这个全局变量sum 是包含在M 类中的
public static int sum;
public M()
{
int sum =0;
int[] store = {1,2,3,4,5,6,7,8,9,0};
}
打印函数
符合要求的则把它打印出来
public static void Output(int[] store2)
{
for(int i = 9; i=0; --i)
{
Console.Write( {0},store2[i]);
}
Console.WriteLine();
sum++;
}
计算总数，返回 sum 值
public static int sum2()
{
return sum;
}
public static void Cumput(int score, int num, int[] store2 )
{
如果总的成绩超过了90 环（也就是 score0），或者如果剩下要打靶
的成绩大于10 环乘以剩下要打的次数，也就是说即便后面的都打10 环
也无法打够次数，则退出递归
if(score 0 || score (num+1)*10 ) 次数num 为 0～9
{
return;
}
如果满足条件且达到最后一层
if(num == 0)
{
store2[num] = score;
Output( store2);
return;
}
for(int i = 0; i = 10; ++i)
{
store2[num] = i;
Cumput(score - i, num - 1,store2);
}
Console.Write( {0},store2[5]);
}
}
public class myApp
{
public static void Main( )
{
int[] store;
store = new int[10];
int sum = 0;
int a=90;
int b=9;
Output();
M.Cumput(90,9,store);
sum = M.sum2();
M.Cumput2(a,b,store);
Console.Write( {0},store[3]);
cout总数:sumendl;
Console.Write( 总数: {0},sum);
}
}
程序结果一共有 92 378 种可能。
也可以用 C++编写，代码如下：
#include iostream
using namespace std;
int sum;
int store[10];
void Output()
{
for(int i = 9; i=0; --i)
{
coutstore[i] ;
}
coutendl;
++sum;
}
void Cumput(int score, int num)
{
if(score 0 || score (num+1)*10 ) 次数num 为0～9
return;
if(num == 0)
{
store[num] = score;
Output();
return;
}
for(int i = 0; i = 10; ++i)
{
store[num] = i;
Cumput(score - i, num - 1);
}
}
int main(int argc, char* ar[])
{
Cumput(90, 9);
cout总数:sumendl;
return 0;
}
延伸阅读：
java程序员面试自我介绍自我介绍是向别人展示你自我介绍好不好。下面是ja程序员面试自我介绍，一起来看一下吧。 ja程序员面试自我介绍 ja程序员应试者应充分利用各种个人资源。想了解ja程序员面试指...
程序员面试自我介绍优秀模板确定自我介绍的具体内容，应兼顾实际需要、所处场景，并应具有鲜明的针对性，切不可“千人一面”，一概而论。以下是本站网小编为你提供的程序员面试自我介绍优秀模板，供大家参考。...
Java程序员面试中的多线程问题0、Ja中多线程同步是什么?在多线程程序下，同步能控制对共享资源的访问。如果没有同步，当一个Ja线程在修改一个共享变量时，另外一个线程正在使用或者更新同一个变量，这样容易导致...
程序员在面试中如何占据主动其实，面试是一个双向选择的过程(如果你不这么认为，说明你还不够自信)，你大可不必在面试中完全处于被动，相反，你也可以问面试官一些问题，以便看看这个公司是否合你胃口比如，你可以问...
php程序员面试经历(一) 明天还有两场面试，本来想着早点休息的，可是纠结了一番，还是决定写下此文。 因为对深圳的环境还是不太熟悉，即使早上的面试时间是十点半，可我还是七点十五分起床了，然后刷牙洗...
名企招聘C++程序员笔试题名企招聘C++程序员笔试题 单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1-2-3-4-5 通过反转后成为5-4-3-2-1。 最容易想到的...
了解程序员面试技巧在开始求职之前，需要做一些准备工作。比方说要知道自己喜欢什么东西而去求职，否则是没有意义的。仅仅成为一名好的编码人员是不够的，你必须理解市场想要的是什么，如何提高自己的...
程序员自我介绍简历程序员面试自我介绍【1】 我叫xxx，今年21岁，毕业于xx解放军信息工程大学计算机科学与技术专业，拥有扎实的core ja基础，良好的编程风格;熟悉jsp+servlet+jabean模式的web开发;熟...
如何面试ios程序员1、面试的目的 求职者通过表现证明自己对岗位的胜任 公司通过面试找到符合职位需求的员工 面试者面试的表现影响着公司用人选择，对于软件工程师，我的感觉技术面试往往是天王山...
