首页 > 代码库 > 打靶问题

打靶问题

/**
打靶问题:一个射击运动员打靶,靶一共有10环,连开10枪打中90环的可能性有多少?

思路:这道题的思路与字符串的组合很像,用递归解决。
一次射击有11种可能,命中1环至10环,或脱靶。
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

//函数功能 : 求解number次打中sum环的种数
//函数参数 : number为打靶次数,sum为需要命中的环数,result用来保存中间结果,total记录种数
void ShootProblem_Solution(int number, int sum, vector<int> &result, int &total)
{
    if(sum < 0 || number * 10 < sum) //加number * 10 < sum非常重要,它可以减少大量的递归,类似剪枝操作
        return;
    if(number == 1) //最后一枪
    {
        if(sum <= 10) //如果剩余环数小于10,只要最后一枪打sum环就可以了
        {
            for(unsigned i = 0; i < result.size(); i++)
                cout<<result[i]<<‘ ‘;
            cout<<sum<<endl;
            total++;
            return;
        }
        else
            return;
    }
    for(unsigned i = 0; i <= 10; i++) //命中0-10环
    {
        result.push_back(i);
        ShootProblem_Solution(number-1, sum-i, result, total); //针对剩余环数递归求解
        result.pop_back();
    }
}

void ShootProblem(int number, int sum)
{
    int total = 0;
    vector<int> result;
    ShootProblem_Solution(number, sum, result, total);
    cout<<"total nums = "<<total<<endl;
}

int main()
{
    ShootProblem(10, 90);
    return 0;
}