确定将一定数量的钱(以分为单位)转换成两角五分的硬币,一角硬币,五分和一分硬币的方法总数。
import java.util.Stack;
public class Coin {
private static int[] coins = {25,10,5,1};
private static Stack<Integer> roots =new Stack<Integer>();
private static void divide(int num){
for (int coin : coins){
if (num - coin >=0 && (roots.size()==0 || coin <= roots.get(roots.size()-1))){
roots.push(new Integer(coin));
if (num - coin > 0){
divide (num - coin);
} else { // Get one
for (Integer root: roots){
System.out.print (root);
System.out.print (" ");
}
System.out.print ("\n");
}
roots.pop();
}
}
}
public static void main(String[] args) {
Coin.divide(17);
}
}
运行结果(1角7分的硬币的所有可能的分法):
10 5 1 1
10 1 1 1 1 1 1 1
5 5 5 1 1
5 5 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
分享到:
相关推荐
总的来说,8枚硬币问题是一个挑战性的算法问题,它涉及到计算机科学中的基本概念如递归、动态规划以及问题的减治法解法。通过理解和解决这个问题,开发者可以提升对算法设计和复杂度分析的理解,这对于任何IT专业...
8枚硬币问题的最优解法是在3次称量内找出假币。第一次称量将8枚硬币减少到4枚,第二次称量进一步减少到1或2枚,第三次称量确定假币及它的重量状态。 在C语言中实现这个算法,需要定义一个递归函数,参数可以是待...
通过减治法解决n枚硬币问题,不仅可以锻炼我们的逻辑思维能力,还展示了如何在复杂问题中运用简单策略找到高效解法。这个问题在计算机科学面试中经常出现,因为它能很好地检验候选人的算法理解及问题解决能力。
2. **递归解法**:一种直观的解决方案是采用递归。我们可以尝试用最大的硬币面额来尽可能多地匹配,然后对剩下的金额递归地执行相同操作。然而,这种做法可能会导致大量的重复计算,效率较低。 3. **动态规划**:更...
从第一个硬币开始,尝试翻转或不翻转,然后递归地处理下一个硬币,直到达到目标状态或确定无法达到目标状态并回溯。 4. **数学分析**:某些翻硬币问题可能有特殊的数学结构,可以通过分析得出解决方案。例如,如果...
对于诸如斐波拉契数列,直接的暴力解法相当于求一遍递归树所有的节点,即2^n的复杂度。其中原因就是重复计算了大量节点。 解决方法1--自顶向下:可以在递归调用重复调参的同时,使用一个数组(备忘录)来记录已经...
除了基本的动态规划解法,还可以考虑贪心算法,但这通常不适用于硬币兑换问题,因为贪心策略(如每次都选取面值最大的硬币)并不一定能得到最少的硬币数量。例如,如果面值分别为1、3、4,目标金额是6,贪心策略会...
在实验一中,我们将重点学习如何运用动态规划解决三个经典问题:最少硬币问题、最小M段和以及最长子序列。 首先,我们来看最少硬币问题。这个问题的目标是找出给定面值的硬币组合,使得凑成指定金额时所需的硬币...
Python硬币兑换问题是一个经典的计算机科学问题,通常用于教授动态规划和回溯法等算法。在现实生活中,这个问题可能出现在银行或自动售货机中,需要找到最少数量的硬币来组成一个特定的金额。在这个问题中,我们有一...
在树类问题中,“二叉树的层次遍历”(Level Order Traversal)可以使用队列进行层次遍历,而“二叉搜索树的最小绝对差”(Minimum Absolute Difference in BST)则需利用二叉搜索树的特性进行迭代或递归求解。...
每增加一枚硬币,我们就递归地调用自身,减少目标金额,并增加硬币总数。若找到一种组合使得硬币总数为零且目标金额也为零,说明找到了一个可行的找零方案,返回true。如果遍历完所有可能的硬币组合都无法满足条件,...
在找零问题中,回溯法同样适用,尤其是在硬币面额有限且需要找到最少硬币数目的情况下。 找零问题描述: 假设我们有一组不同面额的硬币,需要找出一种方式,使用最少数量的硬币来凑足给定的金额。在这个例子中,...
解法中使用了递归的策略,对于n个盘子,可以分解为n-1个盘子的移动加上最后一个盘子的直接移动,如此类推。这个算法的经典之处在于,它展示了递归思想在解决复杂问题时的强大能力。 2. 费式数列(Fibonacci ...
问题的解法是利用贪心策略来决定每一步如何选择喷水器,确保覆盖范围最大化,从而达到减少喷水器数量的目的。 在编写和发布与贪心法相关的内容时,需要保持严谨的态度,确保提出的算法和观点是经过深思熟虑和验证的...
然而,NP难(NP-hard)问题并不保证存在多项式时间解法,但可以将它们转换为已知的NP完全问题。第三题表明,不能简单地将NP难问题转化为NP完全问题以求解。 4. 最大流与最小割 在无向图中,两个顶点间最大流的值...
2. **换分币**:这个问题涉及最小化硬币找零的数量。假设我们有不同面值的硬币,目标是找出最少数量的硬币来组成给定的金额。这可以通过动态规划算法来解决,通过构建一个二维数组来记录最小硬币数量。 3. **九宫格...