如何使用递归在C#中获得硬币更改问题的最小可能组合
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了如何使用递归在C#中获得硬币更改问题的最小可能组合，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4342字，纯文字阅读大概需要7分钟。
内容图文
我是C#的新手,我有一个要解决的递归问题.我希望在这个硬币更换问题中获得最少数量的硬币.我已经为它调整了算法,但我需要返回一个类型为Change的对象,它将包含最小可能的组合.
我试图实现一个算法,但我有所有可能的组合.
using System;
using System.Collections.Generic;
using System.Linq;
// Do not modify change
class Change
{
public long coin2 = 0;
public long bill5 = 0;
public long bill10 = 0;
}
class Solution
{
// Do not modify method signature
public static Change OptimalChange(long s)
{
Change _change = new Change();
//To implement here
return _change;
}
public static int GetCombinations(int total, int index, int[] list, List<int> cur)
{
if (total == 0)
{
foreach (var i in cur)
{
Console.Write(i + " ");
}
Console.WriteLine();
return 1;
}
if (index == list.Length)
{
return 0;
}
int ret = 0;
for (; total >= 0; total -= list[index])
{
ret += GetCombinations(total, index + 1, list, cur);
cur.Add(list[index]);
}
for (int i = 0; i < cur.Count(); i++)
{
while (cur.Count > i && cur[i] == list[index])
{
cur.RemoveAt(i);
}
}
return ret;
}
}
public class Program
{
public static void Main()
{
Console.WriteLine("Hello Change");
int s = 41;
/*Change m = Solution.OptimalChange(s);
Console.WriteLine("Coins(s) 2euros :" + m.coin2);
Console.WriteLine("Bill(s) 5euors :" + m.bill5);
Console.WriteLine("Bill(s) 10euors :" + m.bill10);
long result = m.coin2*2 + m.bill5*5 + m.bill10*10;
Console.WriteLine("\nChange given =", + result);*/
Solution sol = new Solution();
int[] l = {
2,
5,
10
};
Solution.GetCombinations(s, 0, l, new List<int>());
}
}
预期结果
示例：可用的硬币为{2,5,10}
– 我输入了12 –
该计划应该返回
硬币2欧元：1
比尔5个人：0
Bill(s)10euors：1
– 我输入了17 –
该计划应该返回
硬币2欧元：1
比尔5个人：1
Bill(s)10euors：1
解决方法:
首先,了解递归的基本概念是什么：
>如果我们可以在没有递归的情况下解决问题,请解决它并返回解决方案.
>如果我们不能,那么将问题减少到一个或多个较小的问题,递归地解决每个较小的问题,并结合解决方案来解决更大的问题.
其次,了解动态编程的基本思想是什么：
>递归解决方案经常多次重新计算同样的问题;存储解决方案有时更有效,而不是重新计算它.
好吧,让我们来解决你的问题吧.
// Do not modify change
class Change
{
public long coin2 = 0;
public long bill5 = 0;
public long bill10 = 0;
}
Pish tosh.这堂课太可怕了.修理它！
sealed class Change
{
public long Two { get; }
public long Five { get; }
public long Ten { get; }
public Change(long two, long five, long ten)
{
this.Two = two;
this.Five = five;
this.Ten = ten;
}
public Change AddTwo() => new Change(Two + 1, Five, Ten);
public Change AddFive() => new Change(Two, Five + 1, Ten);
public Change AddTen() => new Change(Two, Five, Ten + 1);
public long Count => Two + Five + Ten;
public long Total => Two * 2 + Five * 5 + Ten * 10;
}
从一个可以帮助您的数据结构开始,而不是一个伤害您的数据结构.
现在,让我们编写一个递归函数：
public static Change OptimalChange(long s)
{
// Are we in the base case? Solve the problem.
// If not, break it down into a smaller problem.
}
什么是基本情况？实际上有两个.如果总和为负,则没有解,如果总和为零,则存在零解.
public static Change OptimalChange(long s)
{
if (s < 0)
return null;
if (s == 0)
return new Change(0, 0, 0);
好吧,这很容易.困难的部分是什么？好吧,如果有一个解决方案,那么它有两个,或者它有五个,或者它有十个,对吧？或者也许全部三个.所以让我们找出答案.
public static Change OptimalChange(long s)
{
if (s < 0)
return null;
if (s == 0)
return new Change(0, 0, 0);
Change tryTen = OptimalChange(s - 10)?.AddTen();
...
你能从这里拿走吗？
当您拥有实现所需操作的数据结构时,看看问题会变得多么容易？再次总是创建一个可以帮助您的数据结构.
下一个问题：该算法效率很低.为什么？因为我们不断重做我们已经做过的问题.假设我们正在评估OptimalChange(22).这称为OptimalChange(12),它调用OptimalChange(7),它调用OptimalChange(5).但OptionalChange(12)也调用OptimalChange(10),它再次调用OptimalChange(5).答案没有改变,但我们再次进行计算.
那么我们该怎么办？我们使用动态编程技术.有两种方法可以做到：
>继续递归,并记住递归函数.
>创建一个变更数组,并随时填写.
但等等,问题多于性能问题.我们使问题最小化10次,每次最少2次,但参数很长;它可能是数十亿或数万亿.如果我们有一个递归的解决方案,我们将打击堆栈,如果我们有一个基于阵列的解决方案,它太大了.
在给定的可能输入范围内,我们需要更聪明地解决这个问题.想想吧;我们可以分析地解决问题,没有递归,数组或长时间运行的循环？或者,等效地,有没有办法快速减少极小问题的大问题？然后可以通过动态编程解决小问题.
就像家庭作业问题一样,记住你受到良好学术规则的约束.如果你在家庭作业解决方案中使用SO的想法,你必须给予信任.不这样做是抄袭,如果你坚持下去,你会被驱逐出体面的学校.
内容总结
以上是互联网集市为您收集整理的如何使用递归在C#中获得硬币更改问题的最小可能组合全部内容，希望文章能够帮你解决如何使用递归在C#中获得硬币更改问题的最小可能组合所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。