上个月把sicp第一章看了看,领略到scheme 语言的美妙,非常之简洁,呵呵,
1.2.2 节 是讲的树型递归,里面有个换零钱问题,属于很老问题了,问题简单的说就是 1块钱,要换成 5分,1分,10分,50分,25分,总共有几种换法。
以前我大学的时候好象是用穷举
实现的,现在发现scheme,发现递归实现也不错,然后看了算法,决定用C# 重新写以下,
从scheme 翻译到c# 非常简单,后来发现书上的例子只能得到换法的总数,不能把所有换法 的零钱数的组合输出,
比如, 假设 10分 成 5分和1分,他只能输出 有3种换法,不能把
(1 1 1 1 1 1 1 1 1 1)
(5 1 1 1 1 1)
(5 1)
组合输出,我决定增加一这个功能,刚开始以为很简单,后来还是碰到一些问题,就是得到其中一种后,怎么回滚,继续得到其他组合,表达能力差,我还是放代码吧,如果各位有更好的代码,请贴出来,呵呵
using System;
namespace CountChange
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class Class1
{
static int[] changeArray = new int[100];
static int arrayIndex = 0;
static void InitArray()
{
for(int i = 0 ; i < 100 ; i++)
{
changeArray[i] = 0;
}
arrayIndex = 0;
}
static void PrintChange()
{
for(int i = 0 ; i < 100 ; i++)
if ( changeArray[i] != 0)
Console.Write(changeArray[i] + " ");
// Console.WriteLine();
}
static void RollBackArray()
{
int lastIndex = 0;
int lastChange;
for(int i = 0 ; i < 100 ; i++)
{
if ( changeArray[i] == 0)
{
if( i > 0)
lastIndex = i -1;
else return;
break;
}
}
lastChange = changeArray[lastIndex];
//delete all the same change
int step;
for( step = lastIndex ; step >=0 ; step--)
{
if(changeArray[step] == lastChange)
{
changeArray[step] = 0;
continue;
}
else
break;
}
//reset the arrayindex;
arrayIndex = step + 1;
}
static int CountChange(int amount ,int kindOfCoins)
{
if( amount == 0 )
{
Console.WriteLine("-----------------------------------------------");
PrintChange();
Console.WriteLine();
Console.WriteLine("-----------------------------------------------");
RollBackArray();
return 1;
}
else if(amount < 0 )
{
RollBackArray();
return 0;
}
else if( kindOfCoins == 0)
{
return 0;
}
else
{
//
int num1 = CountChange(amount ,kindOfCoins -1);
// push the change
changeArray[arrayIndex++] = FirstDenomination(kindOfCoins);
int num2 = CountChange(amount - FirstDenomination(kindOfCoins) ,kindOfCoins );
return num1 + num2 ;
}
}
static int FirstDenomination(int kindOfCoins)
{
switch (kindOfCoins)
{
case 1: return 1;
case 2: return 2;
case 3: return 3;
default:
Console.WriteLine("FirstDenomination error kindOfCoins = " + kindOfCoins);
return -1;
}
}
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
//
// TODO: Add code to start application here
//
// init array
InitArray();
// CountChange(10 ,2);
Console.WriteLine(CountChange(10 ,3));
}
}
}
分享到:
- 2007-06-10 23:24
- 浏览 2686
- 评论(3)
- 论坛回复 / 浏览 (3 / 4191)
- 查看更多
相关推荐
整钱换零钱问题.cpp
最少零钱问题,最少硬币问题,动态规划算法,找零钱问题,
算法设计课程代码,此代码为零钱兑换的C语言代码,感谢下载
兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的...
一个财务换零钱程序,方便会计发工资 换零钱
编一个程序,把一张面值100元的钞票换成5元,1元和5角面值的钞票,要求100元换以上的零钱100张,且要求每种不少于一张。请问,有哪几种换法?
呵呵,呵呵,刚学,呵呵,y。daniel liang编的书上的作业题
Java零钱兑换问题leetcode 数据结构与算法 数据结构与算法的Java实现 数据结构 排序算法 O(n^2) O(n^2) O(n^2) O(nlog(n)) O(nlog(n)) O(n) O(nlog(n)) 字符串算法 O(n * m) O(n),极端情况下会退化为O(n * m) 时间...
问题描述:设有 n 种不同的钱币各若干张,可用这 n 种钱币产生许多不同的面值。试设计一个算法,计算给定的某个面值,能有多少种不同的产生方法。例如有 1 分3 张,2 分3 张,5 分 1 张,则能组成 7 分面值的方法有...
写一个程序,从标准输入上读入一个正整数N(1 ),计算出N元人民币兑换成1分、2分和5分的硬币,有多少种可能的组合。将结果以整数的方式输出到标准输出上,占一行。【输入形式】 正整数N。(1 ) 【输出形式】 ...
找零钱 求一元二次方程的根(公式法) 比赛日程(分治法) 两个有序数组的合并 统计投色子(2个)的结果 12小球问题 改进冒泡排序法 螺旋数组 射击环数 猜数字游戏 桶排序 造币厂问题 直接插入排序 搬砖 公车座位巧安排 ...
算法入门,若干实例探讨算法思考模式。。。。。。。。
一人拿一张百元钞票到商店买了25元的东西,店主由于手头没有零钱,便拿这张百元钞票到隔壁的小摊贩那里换了100元零钱,并找回了那人75元钱。那人拿着25元的东西和75元零钱走。过了一会儿,隔壁小摊贩找到店主,说...
这样就达到了空间换时间的目的,最终时间为n。 解决方法2--自底向上:可以将递归问题转化为迭代问题。从当前已经解决的问题出发,构建DP Table,循环计算。 2、凑零钱 对于指定金额,给出在币值范围内进行组合的最少...
html5+css3从入门到精通,最新的书籍,希望帮到好学之人
17_递归-零钱找零问题 18_递归-博物馆大盗问题 19_顺序查找 20_二分查找 21_冒泡排序和选择排序 22_插入排序 23_希尔排序 24_归并排序 25_快速排序 26_Hash散列&ADT Map 27_树的嵌套列表实现 28_树结构的节点链接法...
61.找零钱 62.求一元二次方程的根(公式法) 63.比赛日程(分治法) 64.两个有序数组的合并 65.统计投色子(2个)的结果 66.12小球问题 67.改进冒泡排序法 68.螺旋数组 69.射击环数 70.猜数字游戏 71.桶排序 72.造币厂问题...
小明去x星旅游,他手中只有2张100元的x星币,太不方便,恰好路过x星银行就去换零钱。 小明有点强迫症,他坚持要求200元换出的零钞中2元的张数刚好是1元的张数的10倍,剩下的当然都是5元面额的。 银行的工作人员有点...
贪婪实例:换零钱 const MAXN = 9; let parvalue = [10000, 5000, 1000, 500, 200, 100, 50, 20, 10]; let num = []; for(let i = 0; i < MAXN; i++){ num[i] = 0; } function exchage(n){ var i,j;