Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C] Kombinacje bez powtórzeń rekurencyjnie

Ostatnio zmodyfikowano 2013-12-10 14:06
Autor Wiadomość
korba246
Temat założony przez niniejszego użytkownika
[C] Kombinacje bez powtórzeń rekurencyjnie
» 2013-12-09 17:11:59
Napisz procedure która generuje wszystkie podzbiory k-elementowe zbioru liczb od 1 do n (drukuje podzbiory na ekranie).

Mam taki program kompiluje się ale wyświetla złe wyniki. Mógłby ktoś pomóc?
C/C++
#include<stdio.h>
#include<stdlib.h>
int kombinacje( int n, int k, int i )
{
    int tab[ n ]; int start;
    int j;
   
    if( i == k + 1 )
    { for( j = 1; j <= k; j++ )
             printf( "%d", tab[ j ] );
       
    }
   
    else {
        if( i == 1 )
             start = 1;
       
        else start = tab[ i - 1 ] + 1;
       
        for( tab[ i ] = start; tab[ i ] < n; tab[ i ] ++ )
        {
            if(( k - i ) <=( n - tab[ i ] ) ) kombinacje( n, k, i + 1 );
           
        }
    }
}

int main()
{
   
    int n;
    int k;
    int i;
   
    printf( "podaj n" );
    scanf( "%d", & n );
    printf( "podaj k" );
    scanf( "%d", & k );
   
    printf( "podaj i" ); scanf( "%d", & i );
   
    kombinacje( n, k, i );
   
    return 0;
}
P-98810
Wiesiek
» 2013-12-10 07:34:34
Jeśli się kompiluje, to powinieneś się cieszyć, że kompilatorowi nie przeszkadza deklaracja "int tab[n];" (n jest zmienną). A na poważnie, to powinieneś prześledzić zmianę wartości zmiennych. Niezbyt jasne jest znaczenie zmiennej "i", ale prawdopodobnie chcesz, aby zmienna ta startowała od 1.
Jako wartości wejściowe zmiennych n,k,i przyjmij 3,2,1.
Następuje wywołanie funkcji kombinacje(3,2,1), w niej zmienna start dostaje wartość 1, a tab wartość {*,1,*} (* oznacza wartość nieokreśloną, czyli przypadkową).
W kolejnym kroku następuje wywołanie funkcji kombinacje(3,2,2).
W trakcie jej wykonywania następuje przypisanie "start = tab[ i - 1 ] + 1;", ale tab[1] nie jest zainicjowane, więc start dostaje przypadkową wartość.
Teraz wykonywanie pętli for staje się nieprzewidywalne.

Opracowując algorytm wypisywania kombinacji możesz ewentualnie poczytać o algorytmach z powrotami (taki występuje w rozwiązaniu problemu ośmiu hetmanów, albo problemu skoczka szachowego).
P-98875
Adik80
» 2013-12-10 12:07:06
Zgodnie ze standardem C99 dostepna jest "Varaible length array" wiec jest to poprawne (w C++ jako rozszerzenie w gcc).
Kod jest nieczytelny i ciezko wyczuc co chcesz tam zrobic. Jesli to sa kolejne lementy, to nie potzrebujesz tablicy:
C/C++
void wypisz( int i, int k, int n )
{
    for( int j = 0; j < k; ++j )
         printf( "%d ", i + j );
   
    printf( "\n" );
    if( i + k <= n )
         wypisz( i + 1, k, n );
   
}

int main()
{
    int n, k;
    scanf( "%d %d", & n, & k );
    wypisz( 1, k, n );
}
P-98882
Wiesiek
» 2013-12-10 14:06:42
Nie śledzę za bardzo standardów, więc nawet nie wiedziałem (na swój sposób ciekawe, bo oznacza to, że zmienne lokalne VLA nie są przechowywane w rekordzie aktywacyjnym funkcji).
Niestety rozwiązanie podane przez Adik80 też nie zawiera algorytmu z powrotami. Zdaje się, że przy n=3, k=2 wygeneruje {1,2} oraz {2,3} (bez pary {1,3}). Z powrotami będzie wyglądać mniej więcej tak:
C/C++
int * wynik;
int n, k;

void wypisz( int i, int p )
//szukamy podzbioru p-elementowego o elementach od i do n
{
    //j - wartość pierwszego elementu podzbioru p-elementowego
    for( int j = i, j <= n - p + 1, j++ )
    {
        wynik[ k - p ] = j;
        if( p == 1 ) wyswietl_zawartosc_tablicy_wynik();
        else wypisz( j + 1, p - 1 );
       
    }
}

int main()
{
    scanf( "%d %d", & n, & k );
    wynik = new int[ k ];
    wypisz( 1, k );
    delete[] wynik;
}
P-98890
« 1 »
  Strona 1 z 1