首页 > 代码库 > 递归计算战士打靶S次打了N环一共同拥有多少种可能的问题
递归计算战士打靶S次打了N环一共同拥有多少种可能的问题
问题描写叙述
一个战士打了10次靶。一共打了90环,问一共同拥有多少种可能,并输出这些可能的组合。
思路
首先。嵌套10层循环进行穷举是不可取的,一是由于速度太慢,二是假设改成打20次靶就完蛋了。
事实上这就是一个树的搜索问题。
1. 设第一次打了0环。那么第二次可能打0 ~ 10环这些可能
2. 以第一次打的0环为root,将第二次全部可能的环数都做为root的子结点
3. 反复1, 2步
这样就构成了一棵树。表示当第一次打了0环时全部的可能性。
我们要做的就是从上到下遍历这棵树。当经过的结点之和等于90时,即命中。
然后再将根结点值改成1,直到10。
那么问题来了,一棵树须要遍历多少种组合呢?设打靶次数为t, 那么全部的组合数 = 1+(11)t?1=1+(11)9 种。这个结果已经超过了4亿, 显然全部遍历一遍时间上是不能忍的。我们能够通过剪枝思想来去掉部分不必要的遍历,即推断一下即便以后全打10环时能不能满足90环的要求,假设不能则不须要继续递归了。
另一个问题,我们真的要手动创建一个树形数据结构来运行上面的过程吗?假设这样做理论上是没问题的,可是会消耗大量的内存。 事实上我们能够使用递归的方式来模拟树的遍历。
实现
定义方法
int shoot(int score, int left, int totalScores, Dequeue<Integer> path)
表示已经打了score
环。还要打left
枪,总环数为totalScores
时全部的结果数。这里path是一个栈数据结构。用来记录递归调用的路径,从而记录了一次可能组合的各个环数。
完整代码例如以下:
public class Main {
public static int SHOOT_TIMES = 10;
public static void main(String[] args) {
System.out.println(shoot(0, SHOOT_TIMES, 90, new LinkedList<>()));
}
/**
* 返回打score环且仅仅能打left枪且总环数为TOTAL_SCORES的全部结果数
* @param score
* @param left
* @param path
* @return
*/
public static int shoot(int score, int left, int totalScores, Deque<Integer> path) {
int tot = 0;
if (1 == left) {
// 剪枝
// 去掉明显不可能的结果
// 即在最后一枪时计算距离90环还剩下的环数,
// 假设环数大于10。则不可能打满
int left_scores = totalScores - score;
// 当剩下的环数在0 ~ 10之间时。表明这是一个可取的组合
if (left_scores >= 0 && left_scores <= 10) {
path.push(left_scores);
printStack(path);
path.pop();
++tot;
}
path.pop();
return tot;
}
for (int i = 0 ; i <= 10 ; ++i) {
// 剪枝.
// 计算已经打了score环时还剩下多少环.
// 假设即便剩下全打10环还打不满90环,则表示这不是一个可取的结果
if (totalScores - (score + i) <= 10 * left) {
path.push(i);
tot += shoot(score + i, left - 1, totalScores, path);
}
}
if (false == path.isEmpty()) {
path.pop();
}
return tot;
}
/**
* 打印出栈内的全部元素
* @param list
*/
private static void printStack(Deque<Integer> list) {
int ix = 0;
int LEN = list.size();
for (Integer n : list) {
if (ix == LEN - 1) {
System.out.printf("%d\n", n);
break;
}
System.out.printf("%d, ", n);
++ix;
}
}
}
递归计算战士打靶S次打了N环一共同拥有多少种可能的问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。