锁定老帖子 主题:换零钱问题
精华帖 (0) :: 良好帖 (0) :: 灌水帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2007-06-10
上个月把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 static int[] changeArray = new int[100]; static void InitArray() arrayIndex = 0; static void PrintChange() for(int i = 0 ; i < 100 ; i++) if ( changeArray[i] != 0) // Console.WriteLine();
int lastIndex = 0; for(int i = 0 ; i < 100 ; i++) } //delete all the same change int step; for( step = lastIndex ; step >=0 ; step--) } //reset the arrayindex; arrayIndex = step + 1;
static int CountChange(int amount ,int kindOfCoins)
Console.WriteLine("-----------------------------------------------"); return 1;
// int num2 = CountChange(amount - FirstDenomination(kindOfCoins) ,kindOfCoins );
return num1 + num2 ; } } static int FirstDenomination(int kindOfCoins) case 1: return 1; }
/// <summary> InitArray(); // CountChange(10 ,2);
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2007-06-11
迷宫 —— 递归
(我们老师讲递归时用了走迷宫的例子。PS:我们大学没有算法课只有pascal) |
|
返回顶楼 | |
发表时间:2007-06-11
我在大学讲递归的时候,用的是 八皇后,呵呵,当时觉得很难理解,其实现在我在理解一些稍微复杂点的递归算法,都觉得头疼,可是几乎每本算法书都说递归是最好理解的,埃,是不是我脑子笨啊,
|
|
返回顶楼 | |
发表时间:2007-06-11
zhuyi8319 写道 我在大学讲递归的时候,用的是 八皇后,呵呵,当时觉得很难理解,其实现在我在理解一些稍微复杂点的递归算法,都觉得头疼,可是几乎每本算法书都说递归是最好理解的,埃,是不是我脑子笨啊, 递归是另一种意义上的遍历。
理想状态下他能把迷宫的所有可能性都走遍。。。。 (不过每走一步都进行压栈。。 如果有传说中的左死墙不知道会怎么样。。。。) 他用这种方式的空间复杂度非常的大,但非常的好写 才不到十行的代码。。。。。 PS:好写不代表好想。。。。我的脑子也是非常的头痛。。。 看来普通人与大牛的区别不在于马力小时(对普通问题的思考), |
|
返回顶楼 | |
浏览 4207 次