换零钱问题

上个月把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
• 浏览 2738
• 评论(3)
• 论坛回复 / 浏览 (3 / 4207)
• 查看更多

评论

3 楼 抛出异常的爱 2007-06-11  

zhuyi8319 写道

我在大学讲递归的时候，用的是 八皇后，呵呵，当时觉得很难理解，其实现在我在理解一些稍微复杂点的递归算法，都觉得头疼，可是几乎每本算法书都说递归是最好理解的，埃，是不是我脑子笨啊，

递归是另一种意义上的遍历。
理想状态下他能把迷宫的所有可能性都走遍。。。。
（不过每走一步都进行压栈。。
如果有传说中的左死墙不知道会怎么样。。。。）

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

PS：好写不代表好想。。。。我的脑子也是非常的头痛。。。
看来普通人与大牛的区别不在于马力小时（对普通问题的思考），

2 楼 zhuyi8319 2007-06-11  

我在大学讲递归的时候，用的是 八皇后，呵呵，当时觉得很难理解，其实现在我在理解一些稍微复杂点的递归算法，都觉得头疼，可是几乎每本算法书都说递归是最好理解的，埃，是不是我脑子笨啊，

1 楼 抛出异常的爱 2007-06-11  

迷宫 —— 递归
（我们老师讲递归时用了走迷宫的例子。PS：我们大学没有算法课只有pascal）