http://blog.csdn.net/paradise80/archive/2004/12/05/205519.aspx
田东专栏修改后的C#代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Implememtations
{
/// <summary>
/// Calculates the minimum count of change.
/// </summary>
public class MoneyChanger
{
/// <summary>
/// Initializes an instance of <c>MoneyChange</c> with par values.
/// </summary>
/// <param name="parValues">Par values(e.g 10, 5, 2, 1 for RMB).</param>
public MoneyChanger(int[] parValues)
{
if (parValues == null)
{
throw new ArgumentNullException("parValues");
}

this.parValues = this.FilterParValues(parValues);

if (this.parValues.Count == 0)
{
throw new ArgumentException("Invalid par values");
}
}

/// <summary>
/// Gets change with minimum count of par values.
/// </summary>
/// <param name="amount">Total amount to be changed.</param>
/// <returns>(parValue, count) pairs.</returns>
public virtual Dictionary<int, int> Change(int amount)
{
Dictionary<int, int> result = new Dictionary<int, int>(this.parValues.Count);

foreach (int par in this.parValues)
{
result.Add(par, amount / par);
amount %= par;
}

return result;
}

#region Fields

/// <summary>
/// Stores par values.
/// </summary>
private List<int> parValues;

#endregion Fields

#region Supports Methods

/// <summary>
/// Filters par values with following rules:
/// 1. All values are greater then zero.
/// 2. All have different value.
/// 3. Sorted in descending order.
/// </summary>
/// <param name="parValues">Array of par values.</param>
/// <returns>Filtered par values.</returns>
private List<int> FilterParValues(int[] parValues)
{
List<int> temp = new List<int>(parValues.Length);
List<int> list = new List<int>(parValues.Length);

// Filters positive integers.
foreach (int par in parValues)
{
if (par > 0)
{
temp.Add(par);
}
}

// Sorts values.
temp.Sort();

// Adds to list in descending order.
for (int i = temp.Count - 1; i >= 0; i--)
{
if (list.Count > 0)
{
// Ingores the duplicate value.
if (temp[i] == list[list.Count - 1])
{
continue;
}
}

list.Add(temp[i]);
}

return list;
}

#endregion Supports Methods
}
}  回复  更多评论