-4
線上等待。〜例如,如果硬幣= [1,2,5]和N = 11,返回真,如果硬幣= [3,77]和N = 100,則返回
給定數量的硬幣以不同的面額,例如[1,2,5],並測試它們是否可以用來彌補一定的金額(N),假設您可以在每個面額中使用無限數量的硬幣。例如,如果硬幣= [1,2,5]和N = 11,返回真,如果硬幣= [3,77]和N = 100,則返回
線上等待。〜例如,如果硬幣= [1,2,5]和N = 11,返回真,如果硬幣= [3,77]和N = 100,則返回
給定數量的硬幣以不同的面額,例如[1,2,5],並測試它們是否可以用來彌補一定的金額(N),假設您可以在每個面額中使用無限數量的硬幣。例如,如果硬幣= [1,2,5]和N = 11,返回真,如果硬幣= [3,77]和N = 100,則返回
的想法是使用一個遞歸函數(在這裏它會計算用一枚第一枚硬幣與其他一批硬幣遞歸地縮小硬幣陣列的大小)。
但SR我不熟悉Objective-C的,所以我寫一個使用C#。使用應將其轉換爲Objective-C。
bool CanDo(int n, int [] arr)
{
if (arr.Length == 1)
{
if (n % arr[0] == 0)
{
return true;
}
}
else
{
var ls = new List<int>(arr);
ls.RemoveAt(0);
int [] newarr = ls.ToArray(); //Create New array by deleting first element(current calculated element) of old array
for(int i = 0; i <= n/arr[0]; i++)
{
int next_n = n - i * arr[0];
if (next_n == 0)
{
return true;
}
else if (next_n < 0)
{
break;
}
else if(next_n > 0)
{
if(CanDo(next_n, newarr))
{
return true;
}
}
}
}
return false;
}
這是在C#中完整的代碼,可以打印到控制檯首次發現的解決方案。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static List<string> resultString = new List<string>();
static bool CanDo(int n, int [] arr)
{
if (arr.Length == 1)
{
if (n % arr[0] == 0)
{
resultString.Add(n/ arr[0] + "*" + arr[0]);
return true;
}
}
else
{
var ls = new List<int>(arr);
ls.RemoveAt(0);
int [] newarr = ls.ToArray(); //Create New array by deleting first element of old array
for(int i = 0; i <= n/arr[0]; i++)
{
if (resultString.Count > 0)
{
resultString.RemoveAt(resultString.Count - 1);
}
int next_n = n - i * arr[0];
if (next_n == 0)
{
resultString.Add(i + "*" + arr[0]);
return true;
}
else if (next_n < 0)
{
break;
}
else if(next_n > 0)
{
if (i != 0)
{
resultString.Add(i + "*" + arr[0] + " + ");
}
if(CanDo(next_n, newarr))
{
return true;
}
}
}
}
return false;
}
static void Main(string[] args)
{
try
{
int[] arr = { 3, 5, 7 };
int N = 20;
resultString = new List<string>();
if (CanDo(N, arr))
{
resultString.ForEach(Console.WriteLine);
Console.Read();
}
else
{
Console.Write("Can't do");
Console.Read();
}
}
catch (Exception ex)
{
//handle exception
}
}
}
}