Zadanie z użyciem rekurencji, jak?

Odpowiedz Nowy wątek
2019-01-05 11:29
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?

Pozostało 580 znaków

2019-01-05 11:34
Smutny Kura
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?

Pozostało 580 znaków

2019-01-05 11:36
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?

Pozostało 580 znaków

2019-01-05 11:55
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))

Pozostało 580 znaków

2019-01-05 12:36
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));
        }   
    }
}
edytowany 1x, ostatnio: neves, 2019-01-05 12:36
Moje rozwiązanie, wydaje się prostsze (nie używam dodatkowych struktur danych), ale jest rodzajem "oszustwa", nie da się go, np., łatwo uogólnić do większych kwot. - lion137 2019-01-05 12:52

Pozostało 580 znaków

2019-01-06 03:38
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();
            }
Najlepsza rekurencja ever! - somekind 2019-01-06 03:49
O rekurencji to było jedynie przypuszczenie autora postu, w treści zadania nic o tym nie było. Zastanowiło mnie raczej, że to było "najtrudniejsze zadanie"... - akerman 2019-01-06 03:53
Założyłem, że skoro autor wpisał w tytule "rekurencja", to jest to jakieś odgórne wymaganie. Ale może faktycznie go przeceniłem. - somekind 2019-01-06 16:39

Pozostało 580 znaków

2019-01-06 12:46
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
edytowany 1x, ostatnio: Burmistrz, 2019-01-06 12:47

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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