Zadanie z użyciem rekurencji, jak?

0

Mam do napisania program w C# o treści:

Dysponując monetami 1 zł, 2 zł, 5 zł sprawdź, na ile różnych sposobów można wypłacić 10 zł. Napisz program, który wyświetli w oknie konsoli wszystkie możliwe kombinacje.

Jest to ostatnie najtrudniejsze zadanie, które nawet nie wiem jak ruszyć. W necie wyczytałem, że w tym przypadku chyba trzeba będzie użyć rekurencji, natomiast kompletnie nie wiem jak się do tego zabrać. Może ktoś coś podpowiedzieć? W ogóle jak napisać algorytm do rekurencji?

0
588490 napisał(a):

Mam do napisania program w C# o treści:

Dysponując monetami 1 zł, 2 zł, 5 zł sprawdź, na ile różnych sposobów można wypłacić 10 zł. Napisz program, który wyświetli w oknie konsoli wszystkie możliwe kombinacje.

Jest to ostatnie najtrudniejsze zadanie, które nawet nie wiem jak ruszyć. W necie wyczytałem, że w tym przypadku chyba trzeba będzie użyć rekurencji, natomiast kompletnie nie wiem jak się do tego zabrać. Może ktoś coś podpowiedzieć? W ogóle jak napisać algorytm do rekurencji?

Zakładając że masz nieograniczoną ilość tych monet?

0

Nie jestem pewien, ale chyba tak. Wkleiłem całą treść polecenia. Czy duża różnia w kodzie będzie dla wersji z ograniczoną i nieograniczoną ilością monet?

0

Możesz użyć algorytmu liczącego podzbiory danego zbioru sumujące się do podanej liczby, trzeba tylko, odpowiednio (aby, np. jedynki dawały w sumie 10, to potrzeba ich 10) dodać liczb do zbioru, pseudokod (Python):

def allSubsets(numSet, targetSum, arrayPart = []):
	s = sum(arrayPart)
	if s == targetSum:
		print(targetSum, arrayPart)
	if s >= targetSum:
		return 
	for i in range(len(numSet)):
		n = numSet[i]
		rest = numSet[i+1:] # elements from i + 1 to the end
		allSubsets(rest, targetSum, arrayPart + [n])



print(allSubsets([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 5, 5], 10))
2
class Program
{
    static Stack<int> usedCoins = new Stack<int>();

    static void CalculateAllCombinations(int[] availableCoins, int availableCoinsIndex, int moneyAmount, List<int[]> result)
    {
        if (moneyAmount == 0)
        {
            result.Add(usedCoins.ToArray());
            return;
        }
        for (int i = availableCoinsIndex; i < availableCoins.Length; ++i)
        {
            int coin = availableCoins[i];
            if (moneyAmount - coin >= 0)
            {
                usedCoins.Push(coin);
                CalculateAllCombinations(availableCoins, i, moneyAmount - coin, result);
                usedCoins.Pop();
            }
        }
    }

    static void Main(string[] args)
    {
        var result = new List<int[]>();
        CalculateAllCombinations(new int[] { 5, 2, 1 }, 0, 10, result);

        foreach (int[] i in result)
        {
            Console.WriteLine(String.Join(" ", i));
        }   
    }
}
1

Nie za bardzo komplikujecie Panowie?

void FindAllCombinations()
            {               
                int numer = 1;
                for (int ile1 = 0; ile1 <= 10; ile1++)
                {
                    for (int ile2 = 0; ile2 <= 5; ile2++)
                    {
                        for (int ile5 = 0; ile5 <= 2; ile5++)
                        {
                            if (ile1 * 1 + ile2 * 2 + ile5 * 5 == 10)
                            {
                                Console.WriteLine($"{numer++}. {ile1} x złotówka, {ile2} x dwa złote, {ile5} x pięć złotych");
                            }
                        }
                    }
                }
                Console.ReadLine();
            }


0

Moje rozwiązanie wyświetla od razu znalezione kombinacje monet, funkcja nie zwraca wyniku. Nie znajduje takich samych kombinacji w innej kolejności.

readonly static int[] Coins = { 1, 2, 5 };

static void FindSubset(List<int> subset, int total)
{
    if (subset.Sum() == total)
    {
        Console.WriteLine(string.Join(", ", subset));
    }
    else if (subset.Sum() < total)
    { 
        foreach (int coin in Coins.Where(coin => coin >= subset.LastOrDefault()))
        {
            subset.Add(coin);
            FindSubset(subset, total);
            subset.RemoveAt(subset.Count - 1);
        }
    }
}

Wynik dla FindSubset(new List<int>(), 10);:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 2
1, 1, 1, 1, 1, 1, 2, 2
1, 1, 1, 1, 1, 5
1, 1, 1, 1, 2, 2, 2
1, 1, 1, 2, 5
1, 1, 2, 2, 2, 2
1, 2, 2, 5
2, 2, 2, 2, 2
5, 5

1 użytkowników online, w tym zalogowanych: 0, gości: 1