`
zhuyi8319
  • 浏览: 21161 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

换零钱问题

阅读更多

上个月把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));
  }
 }
}

分享到:
评论
3 楼 抛出异常的爱 2007-06-11  
zhuyi8319 写道
我在大学讲递归的时候,用的是 八皇后,呵呵,当时觉得很难理解,其实现在我在理解一些稍微复杂点的递归算法,都觉得头疼,可是几乎每本算法书都说递归是最好理解的,埃,是不是我脑子笨啊,
递归是另一种意义上的遍历。
理想状态下他能把迷宫的所有可能性都走遍。。。。
(不过每走一步都进行压栈。。
如果有传说中的左死墙不知道会怎么样。。。。)

他用这种方式的空间复杂度非常的大,但非常的好写
才不到十行的代码。。。。。

PS:好写不代表好想。。。。我的脑子也是非常的头痛。。。
看来普通人与大牛的区别不在于马力小时(对普通问题的思考),
2 楼 zhuyi8319 2007-06-11  
我在大学讲递归的时候,用的是 八皇后,呵呵,当时觉得很难理解,其实现在我在理解一些稍微复杂点的递归算法,都觉得头疼,可是几乎每本算法书都说递归是最好理解的,埃,是不是我脑子笨啊,
1 楼 抛出异常的爱 2007-06-11  
迷宫 —— 递归
(我们老师讲递归时用了走迷宫的例子。PS:我们大学没有算法课只有pascal)

相关推荐

    整钱换零钱问题.cpp

    整钱换零钱问题.cpp

    最少零钱问题,最少硬币问题

    最少零钱问题,最少硬币问题,动态规划算法,找零钱问题,

    兑换零钱C语言源码

    算法设计课程代码,此代码为零钱兑换的C语言代码,感谢下载

    论文研究-兑换零钱问题的动态规划算法研究.pdf

    兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的...

    换零钱程序

    "换零钱程序"是一个专为财务人员设计的实用工具,旨在简化工资发放过程中零钱的准备和管理。在日常的财务管理中,特别是在发工资时,确保足够的零钱以供员工兑换是至关重要的。这个程序的出现,就是为了帮助会计人员...

    算法设计与分析找零钱问题贪心算法

    在众多算法问题中,找零钱问题尤其引人注目,它不仅是一个理论上的经典问题,更在实际生活和商业应用中具有广泛的影响力。贪心算法作为解决这一问题的常用策略,因其简单高效而在不少场景下受到青睐。 找零钱问题...

    编一个程序,把一张面值100元的钞票换成5元,1元和5角面值的钞票,要求100元换以上的零钱100张,且要求每种不少于一张。请问,有哪几种换法?

    编一个程序,把一张面值100元的钞票换成5元,1元和5角面值的钞票,要求100元换以上的零钱100张,且要求每种不少于一张。请问,有哪几种换法?

    分类讨论思想学案.doc

    通过这些练习,学生将面对各种实际问题,如人民币换零钱问题、绝对值的处理、圆的几何性质应用、完全平方公式、等腰三角形周长计算以及圆与直线的相切问题等,这些问题都需要学生运用分类讨论的方法来求解。...

    零钱计算器

    零钱计算器是一款专为处理日常生活中零散货币计算问题而设计的应用程序,它极大地简化了在日常生活、商业交易或财务管理中对零钱和散钱进行精确计算的过程。这款计算器通常具备用户友好的界面和简单易用的功能,使得...

    找零钱 JAVA 实现

    找零钱JAVA程序实现 本文将详细介绍一个使用JAVA语言编写的找零钱程序的实现过程,并对程序的标题、描述、标签和部分内容进行解释。 标题解释 本程序的标题为“找零钱JAVA实现”,这表明该程序的主要功能是使用...

    C语言基本练习题.doc

    4. 钞票换零钱问题:这是一个典型的组合问题,通过三层循环遍历所有可能的1元、2元和5元纸币组合,找出满足条件的组合。此题考察了循环结构和条件判断的应用。 5. 自由落体与反弹问题:题目中运用了循环和累加运算...

    湖南省计算机考试C语言机考试题.pdf

    - 硬币换零钱问题,属于典型的组合优化问题,可以用动态规划或回溯法解决。 - 求同构数,可能涉及到对每个数的平方根进行判断,以及字符串处理。 6. 数字特性检验: - 检查数是否满足特定除法余数条件,可以使用...

    php之75道经典逻辑思考题

    #### 题目14:电影院换零钱问题 **解答:** 这是一个经典的卡特兰数问题,可以通过卡特兰数的公式求解: - 卡特兰数的第n项表示合法的排队方式数量。 - 具体计算略。 #### 题目15:买卖鸡的盈利问题 **解答:** ...

    vba实例教程

    循环结构则涉及如何使用For...Next、Do...Loop等语句实现特定任务,如密码验证、求最大公约数和最小公倍数,以及多重循环在换零钱问题中的应用。此外,数组的使用让处理批量数据更为便捷,例如数据排序、随机生成...

    找零钱问题的贪心算法.pdf

    在找零钱问题中,贪心策略是每次都选取最大面值的硬币来尽可能多地减少硬币的数量。这种策略基于一个假设:每次选择局部最优解,最终会得到全局最优解。 找零钱问题的具体描述是这样的:给定一组硬币面值,如2角5分...

    75道逻辑思维题

    #### 题目14:电影院换零钱问题 **解题思路:** - 本题涉及组合数学。 - 问题转化为寻找特定的排列组合数,答案为C(n,n)。 #### 题目15:买卖鸡的利润计算 **解题思路:** - 本题涉及基础数学计算。 - 最终亏损1...

    Excel_VBA典型实例大全

    - **例028**: 使用多重循环解决换零钱问题。 **4. 使用数组** - **例029**: 使用数组进行数据排序。 - **例030**: 使用数组模拟彩票幸运号码生成。 - **例031**: 使用数组填充单元格区域。 #### 四、Range对象操作...

    微信提现到零钱V3接口的对接java实现demo.rar

    微信提现到零钱V3接口的对接Java实现主要涉及到微信支付平台的相关开发,这是一个关键的金融功能,允许用户将资金从微信支付账户转移到他们的微信零钱。以下是对这个实现过程的详细说明: 1. **微信支付接口对接**...

    Java编写的零钱转换程序

    呵呵,呵呵,刚学,呵呵,y。daniel liang编的书上的作业题

    微信支付,企业付款到零钱

    这一功能使得企业能够直接将款项转账至用户的微信零钱账户,无需经过银行或其他第三方支付平台,大大简化了支付流程,提高了资金流转效率。 在微信支付的企业付款到零钱服务中,企业和开发者可以通过API接口进行...

Global site tag (gtag.js) - Google Analytics