求教一道知名通信公司笔试题目？

来源：百度知道 编辑：UC知道 时间：2024/06/04 04:01:18
运动员打10次气枪总共打中了90环，其中每次可打中0环，1环，2环。。。10环。请编写C/C++程序，打印出所有的可能打法。意思就是打印出10次中每次可能打中多少环加起来为90，列出所有的可能组合。谢谢了！！！给个思路也好，重点是算法思路是怎样的。。。
二楼的算法时间太长了，请不要使用递归，10重循环加剪枝比你的时间快一倍！！

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int print(int i,int l,string s,ofstream& fout)
//i是第几轮, l是剩下的环数, s是之前的纪录, fout是文件输出流
{
if(i==10 && l == 0) //如果是第十轮且剩下的环数是0,就输出记录.
{
cout << s << endl;
fout << s << endl;
return 1;
}
else if(i == 10) return 0; //如果到第十轮还没到90环就返回0
if((double)l/(10-i)>10) return 0; //如果在剩下的轮数不可能到达90环,就返回0
int sum = 0;
for(int j=0;j<=10 && l-j>=0;j++) //在本轮中从0到10进行循环递归...
{
string temp = s; //新纪录 == 旧记录
char t = j+'0';
if(j==10) temp += "10"; //新纪录添加10
else temp += t; //新纪录添加t
temp += " ";
sum += print(i+1,l-j,temp,fout); //递归
}
return sum;
}

int main()
{
ofstream fout("result.txt");
int i = print(0,90,"",fout);
cout << "The