Kombinacja bez powtórzeń

Question

Witam, chce wykonać zadanie z kombinacją bez powtórzeń ale kompletnie nie umiem ułożyć kod w oparciu o to. Znam wzór, zrobiłem już jedno zadanie z permutacją lecz nie wiem jak sformułować kod aby działał poprawnie. Chciałbym też zwrócić uwagę na to, że napisanie kodu powinienem oprzeć na pętli for.

Zadanie:
Robot kucharski Don_Giovanni_Elemental16 specjalizuje się w wytwarzaniu oryginalnej włoskiej pizzy. Proces zawsze rozpoczyna się od ułożenia ciasta, posmarowania go sosem pomidorowym oraz posypania mozzarellą. Następnie Don_Giovanni_Elemental16 układa dodatki wg zamówienia. Klient poprosił o pewną liczbę dodatków (większą od 0), obojętnie jakich. 
Uzupełnij funkcję int pizza ( int n, int k ), aby zwracała liczbę wszystkich możliwych kombinacji pizzy (w tym również tych wyjątkowo ohydnych) zakładając, że n to liczba dostępnych dodatków, a k to liczba zamówionych dodatków oraz, że każdy dodatek można w pizzy użyć najwyżej raz.

Mam również wskazówkę do tego zadania, próbowałem coś z tym zrobić ale nie rozumiem tego:

We wzorze na liczbę kombinacji trzy razy występuje wyrażenie z silnią. Dla ułatwienia i dla lepszej czytelności kodu, przypisz wyniki tych wyrażeń trzem różnym zmiennym - np. n_silnia, k_silnia, n_minus_k_silnia. Mając wartości tych trzech zmiennych łatwo obliczysz liczbę kombinacji - z silnią poradziłeś już sobie w poprzednim ćwiczeniu. Uważaj, aby Twoje pętle wykonały się odpowiednią ilość razy. Pamiętaj, że inkrementacja licznika w nagłówku pętli następuje PO wykonaniu pętli, a nie przed (w przeciwieństwie do sprawdzenia warunku).

Z góry dziękuje za podpowiedź, podsyłam również początek kodu.

int pizza( int n, int k )
{
    return 0;
}

 

Comments

Ale jak znasz wzor to w czym problem?

---

Generalnie to wiem, że musze użyć permutacji na n oraz na k, przynajmniej tak mi się wydaje. Niekoniecznie wiem jak to zrobić to na 2 różnych zmiennych.

int pizza( int n, int k )
{
    int n_silnia, k_silnia, n_minus_k_silnia,  C;
    
    
    for(int i = 1; i <= n; i++)
    {
    n_silnia *= i;
    n = n_silnia;
    }
    
    for(int i; i <= k; i++)
    {
    k_silnia *= i;
    k = k_silnia;
    }
 
    n_minus_k_silnia = n - k;
    
    C = n / ( k * n_minus_k_silnia);
 
    return C;
}

To jest kod który mi wyszedł. Domyślam się, że jest kompletnie zły ale chce pokazać wmiarę mój tok myślenia żeby można było mi dać jakąś wskazówkę. Nie wiem czy mam w jakiś sposób zwrócić permutacje wczesniej k i n albo czy w ogóle mogę uzywać dwa razy i do n i k, czy może źle obliczyłem (n-k)!.

 

---

Hej,

co do linii gdzie deklarujesz zmienne, w C i C++ w ten sposób zadeklarowane zmienne będą miały losowa wartość, zainicjalizuj je.

Co do pętli gdzie używasz zmiennej i, używasz jej tak

for(int i = 1; i <= n; i++)

co znaczy. ze zmienna i będzie istniała tylko dla tej pętli, a później zostanie usunięta.

Nawet gdyby nie była usunięta, to na początku pętli przypisujesz do i 1, wiec spokojnie możesz jej użyć jeszcze raz w drugiej pętli.

 

Co jest nie tak w pętli to, że ma ona działać, dopóki i będzie mniejsze od n, ale w każdej iteracji pętli przypisujesz do n aktualna wartość n_silnia, która będzie zawsze większa lub równa i, wiec skończysz z pętla, która będzie działać w nieskończoność.

Nie modyfikuj k i n, wyniki operacji silni masz w n_silnia i k_silnia.

Z wzorem C = ... nie pomogę, bo jestem zerem z matematyki :)

Pozdro

---

Dzięki wielkie za pomoc! Po kilkunastu próbach wreszcie się udało.

Ostatecznie zrobiłem tak:

int pizza( int n, int k )
{
    int n_silnia=1, k_silnia=1, n_minus_k_silnia=1, n_minus_k;
    int C=0;
    
    n_minus_k = n - k;
    
    
    for(int i=1; i <= n; i++)
    {
        n_silnia *= i;
    }
    
    for(int i=1; i <= k; i++)
    {
        k_silnia *= i;
    }
    
    for(int i=1; i<= n_minus_k; i++)
    {
        n_minus_k_silnia *= i;
    }
    
 
    C = n_silnia / ( k_silnia * n_minus_k_silnia);
 
    return C;
}

Faktycznie trzeba było nadać wartości zmiennym oraz odpowiednio ułożyć pętle. Jeszcze raz dzięki za pomoc!

---

Super, ze się udało, nie wiem, czy cię interesują dodatkowe uwagi, ale wstawiam:

Deklaruj zmienne, jak najbliżej miejsca, gdzie są definiowane. Konwencja, jakiej używasz pochodzi, ze starego C, gdzie trzeba było wszystkie zmienne deklarować na początku albo program się nie kompilował.

 

przykładowo  "C = n_silnia / ( k_silnia * n_minus_k_silnia); "

może być "int C = n_silnia / ( k_silnia * n_minus_k_silnia); "

 

Ze zmiennymi jak n_silnia, gorzej, bo są wypełniane w pętli, ale tez lepiej zaraz przed forem zainicjalizowac zmienna.

x3 z rzedu wykonujesz te sama operacje liczenia silni, wiec to się prosi, żeby wyciągnąć ten kod do osobnej metody.

Wtedy problem ze zmiennymi jak n_silnia tez się rozwiązuje, bo możesz napisać

int k_silnia = silnia(k);

 

W pętli liczącej silnie możesz przypisać zmiennej i 2, zamiast 1 żeby pominąć nic nierobiąca pierwsza iteracje pętli k_silnia *= i; (k_silnia = 1 * 1)

Answer 1

Bardziej optymalny kod na obliczanie kombinacji nie może liczyć bezpośrednio silni, gdyż już przy niewielkich wartościach nastąpi przekroczenie zakresu zmiennych - spróbuj wywołać pizza(100,5).  

To co powinieneś zrobić to skrócić wzór i  wykonywać każde mnożenie równocześnie z dzieleniem.

(N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-K+1)/K

size_t combination( int n , int k )
{
    if( k == 0 ) return 1;

    /*
     Dla dużych wartości k ( większych od n / 2 ) 
     w celu dodatkowego zmniejszenia ilości obliczeń 
     możemy skorzystać z własności kombinacji:     
     kombinacja( n , k ) = kombinacja( n , n - k )
    */
    if( k > n / 2 ) return combination( n , n - k );

    size_t result {1};

    for( int i {1} ; i <= k ; ++i )
    {
        result *= n - i + 1;
        result /= i;
    }

    return result;
}