关于一道简单的C++面试题.....

Question

原题如下：请用递归做出下面题目！
一人打靶，每靶0-10环，共打了10枪，90环，请求出有多少种可能性？想想啊，有没有效率高的方法！ 当时看了过后，我想都没想就先直接用多重循环先求出正确答案，然后再用递归，可以写了一个11重循环，运行后根本无法显示结果，查看后，发现循环到第7重时，程序正常，结果也正常，但是到第8重时，程序就无法显示结果了。。。照理说 C 是无限嵌套循环，但是这里怎么出现这样的情况？会不会因为是内存的原因？代码如下：#include <iostream>
using namespace std;main()
{
int a,b,c,d,e,f,g,h,i,j,k;
long n=0;
for(a=0;a<12;a++)
for(b=0;b<12;b++)
for(c=0;c<12;c++)
for(d=0;d<12;d++)
for(e=0;e<12;e++)
for(f=0;f<12;f++)
for(g=0;g<12;g++)
for(h=0;h<12;h++)
for(i=0;i<12;i++)
for(j=0;j<12;j++)
for(k=0;k<12;k++)
if(a+b+c+d+e+f+g+h+i+j+k==90)
n++;
cout<<n;
system("pause");
return 0;

}

Answer 1

昏，打10枪每次也只有中和不中2种情况，不需要循环11次啊
你这样11个循环嵌套，循环11^11次方，你算算要运行多久，大概2500亿次，就算忽略各层的比较所用时间，只计算n++这一句的时间，如果用1个3.0Ghz的cpu，相当于每秒有30亿个时钟周期，就算n++的执行只用一个时钟周期=1/30亿秒，执行完全部循环也要2500/30≈83秒，实际算上各层循环的累加和比较所用的时间，绝对不会在2分钟之内运行完。

Answer 2

楼上Silverbullet说错了，每靶0-10环，所以不能简单地分成中和不中两种情况。
不过楼主这个代码也有问题。
第一，每靶0-10环，所以每个循环的判断条件应该是小于11才对。如果是小于12，就变成是每靶0-11环了。
第二，共打了10枪，但却用了11重循环，应该是10重循环才对。
简单地使用多重循环来写这个代码效率很低，因为有10重循环，每重循环有要运行11遍，也就是11的10次方。如果要进行优化，那么就要在每重循环加上一些判断条件过滤掉不必要的循环，但这样整个代码就会很臃肿，所以这个问题确实很适合用递归来解决。
下面是我写的递归的代码，只需要几十毫秒就可以得出答案。

#include <iostream>using namespace std;int count(int t, int c)
{
int i, n, r = 0;
if(c == 0)
return 1;
if(t == 1)
return c < 11 ? 1 : 0;
if(10 * t < c)
return 0;
--t;
n = c < 10 ? c : 10;
for(i = 0; i <= n; ++i)
r += count(t, c - i);
return r;
}int main()
{
cout << count(10, 90) << endl;
system("pause");
return 0;
}

Answer 3

都写得比我好