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? #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; } |
|
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).
|
|
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: 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 ); } |
|
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: int * wynik; int n, k;
void wypisz( int i, int p )
{ 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; }
|
|
« 1 » |