MakeChangeSequence.cs

usingSystem.Collections.Generic;
usingSystem.Numerics;

namespaceAlgorithms.Sequences;

/// <summary>
/// <para>
/// Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.
/// </para>
/// <para>
/// OEIS: https://oeis.org/A000008.
/// </para>
/// </summary>
publicclassMakeChangeSequence:ISequence
{
/// <summary>
/// <para>
/// Gets sequence of number of ways of making change for n cents
/// using coins of 1, 2, 5, 10 cents.
/// </para>
/// <para>
/// Uses formula from OEIS page by Michael Somos
/// along with first 17 values to prevent index issues.
/// </para>
/// <para>
/// Formula:
/// a(n) = a(n-2) +a(n-5) - a(n-7) + a(n-10) - a(n-12) - a(n-15) + a(n-17) + 1.
/// </para>
/// </summary>
publicIEnumerable<BigInteger>Sequence
{
get
{
varseed=newList<BigInteger>
{
1,1,2,2,3,4,5,6,7,8,
11,12,15,16,19,22,25,
};
foreach(varvalueinseed)
{
yieldreturnvalue;
}

for(varindex=17;;index++)
{
BigIntegernewValue=seed[index-2]+seed[index-5]-seed[index-7]
+seed[index-10]-seed[index-12]-seed[index-15]
+seed[index-17]+1;

seed.Add(newValue);
yieldreturnnewValue;
}
}
}
}