两个面试题目 - 黑马程序员技术交流社区

#include <stdio.h>
#include <stdlib.h>
#define GOAL 90 //目标环数
#define MAX_SRE 10 //每次射击的最大环数
#define MAX_CNT 10 //总共射击次数
int score[MAX_CNT]; //有效环数
int num = 0; //可能的射击组合数
//筛选有效环数，返回可能的组合数，否则返回-1
int ValidScore(int sre, int cnt, int balance)
{
balance -= sre; //这次射击以后还需要射击的总环数
if(balance<0 || balance>((MAX_CNT-cnt)*MAX_SRE)) //退出递归的条件
{
cnt--; //当最后一环不符合要求时，能不影响后面的打印判断
return -1; //不符合条件，结束递归
}
else
{
score[cnt-1] = sre; //存储有效环数
while(cnt < 9) //控制射击次数
{
cnt++;
score[cnt-1] = -1; //设置一个循环推出条件
for(sre=MAX_SRE; sre>=0; sre--) //从高分往下寻找合适的分数
{
if(-1 == ValidScore(sre, cnt, balance)) //若此分不能满足要求，那么低于它的分更不能满足要求了
break;
}
if(-1 == score[cnt-1]) //若通过上面的for循环，在第cnt次里没有满足要求的环数了，那第cnt次以后的次数就根本不用再继续寻找了
break;
}
if(9 == cnt && balance <= MAX_SRE) //最后一次设计可以不用循环来控制，而是直接等于除了前九次以外还需要的环数
{
score[cnt] = balance; //最后一次需要射击的环数
//打印每一种可能的结果（如果要测目标环数为90的话，建议把这小段注释了，因为总共有92386种可能性）
printf("有效得分：");
for(cnt=0; cnt<MAX_CNT; cnt++)
printf(" %d", score[cnt]);
printf("\n");
num++; //找到一种可能性，总数加一
}
}
return num;
}
int main()
{
int cnt = 1; //射击次数
for(score[0]=MAX_SRE; score[0]>=0; (score[0])--)
ValidScore(score[0], cnt, GOAL); //递归筛选有效环数
printf("总共有 %d 种可能。\n", num);
return 0;
}

复制代码

using System;
class Program
{
static int count = 0;
static void Main(string[] args)
{
shoot(10, 90);//开10枪打90环
Console.WriteLine(count);
}
static void shoot(int num, int score)
{
if (score < 0 || score > num * 10)
return;
else if (num == 0)
count++;
else
for (int i = 0; i <= 10; i++)
{
shoot(num - 1, score - i);
}
}
}

复制代码