Przeszukaj forum
Pokazywanie wyników dla tagów 'algorytmy'.
Znaleziono 1 wynik
-
Przenoszę to z wątku o spotkaniach w Warszawie, żeby nie robić spamu. Na początek ciekawostka, która niszczy system (czyli powinno się spodobać Chemikowi): https://www.destroyallsoftware.com/talks/wat Na ostatnim spotkaniu ktoś coś mówił o rekurencji w trójkącie pascala. Spróbuj tak: /* row - row number, starting from 1, pos - position in a row, starting from 1 */ unsigned long long pascal(int row, int pos) { if ((row < 1) || (pos <1) || (row < pos)) { return 0ul; } if ((pos == 1) || (pos == row)) { return 1ul; } return pascal(row-1, pos-1) + pascal(row-1, pos); } Problem w tym, że czas wykonania tej funkcji będzie posnął wykładniczo i dlatego to nie jest dobre rozwiązanie tego problemu. Hm, może powinienem na to założyć osobny wątek. Odpowiedź: Dziękuję, że piszesz. To ja pytałem o ten Trójkąt Pascala (w realu nazywam się Witek - jestem jedną z nielicznych osób, które były w sobotę u Arpegiusa i to ja męczyłem Ciebie wtedy na meecie w Lisopadzie). Problem polega na tym, że kod ma być w Pythonie lub Logo, a nie w C++. Moja odpowiedź: Po pierwsze napisałem, że to jest tak naprawdę źle, bo za długo będzie liczyć, wielokrotnie wykonując pascal() dla tych samych argumentów. Lepsze rozwiązanie wykorzystuje tablicę trójkątną do memoizacji. Przy czym nawet tego nie kompilowałem, więc pewnie gdzieś jest błąd. Aha i to nie jest odporne na wątki, do tego memory musiałoby być parametrem funkcji pascal_rec. unsigned long long *memory = NULL; // For memoization. static unsigned long long pascal_rec(int row, int pos); // Recursive helper function /* row - row number, starting from 1, pos - position in a row, starting from 1 */ unsigned long long pascal(int row, int pos) { if ((row < 1) || (pos <1) || (row < pos)) { return 0ul; } // Stupid values if ((pos == 1) || (pos == row)) { return 1ul; } // Trivial problem /* An even better solution would be to keep memory, resize it with realloc and fill as needed, but let's keep it simple and stupid. */ memory = calloc(((row-1)*(row-2))/2, sizeof(unsigned long long)); if (memory == NULL) { return 0; } unsigned long long ret = pascal_rec(row-1, pos-1) + pascal_rec(row-1, pos); free(memory); memory = NULL; return ret; } static inline ind(int row, int pos) // Compute index in memory { return (row*(row-1)/2) + (pos-1); } static unsigned long long pascal_rec(int row, int pos) { if (memory[ind(row,pos)] != 0) // Advantage of memoization - cutting off recursive calls on the same arguments as in the past. { return memory[ind(row,pos)]; } if ((pos == 1) || (pos == row)) // Trivial problem { memory[ind(row,pos)] = 1ul; } else { memory[ind(row,pos)] = pascal_rec(row-1, pos-1) + pascal_rec(row-1, pos); // Use recursion, but store intermediate results in memory } return memory[ind(row,pos)]; } Ugh, ale ten edytor tekstu jest toporny. A na inne języki programowania to sam sobie przetłumacz. Tutaj jest tylko idea. To teraz problem ode mnie: Mamy tablicę n-1 elementową z unikatowymi wartościami od 0 do n-1 (albo jak kto woli od 1 do n). To znaczy że są w niej wszystkie liczby z podanego zakresu, za wyjątkiem jednej. Znajdź tę brakującą liczbę.
