Mam takie zadanie:
Z listy liczb naturalnych usuń te, które nie są sumą kilku bezpośrednich swoich poprzedników.
Generalnie rozwiązanie kwadratowe jest robialne: wystarczy odwrócić listę (co robi się w czasie liniowym) i sprawdzać dla każdego elementu, czy jest sumą swoich poprzedników (tzn po odwróceniu już następników).
Chciałbym jednak Was zapytać, czy widzicie jakieś lepsze rozwiązanie tego problemu
[Algorytmy] Operacje na listach
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
[Algorytmy] Operacje na listach
Wskazówka:
Jeśli na liście \(\displaystyle{ [x_1,x_2,\ldots,x_n]}\) liczba \(\displaystyle{ k}\)-ta w kolejności jest sumą kilku poprzednich, to \(\displaystyle{ x_k=s_{k-1}-s_{l-1}}\) dla pewnego \(\displaystyle{ l\in\{1,2,\ldots,k\}}\), gdzie \(\displaystyle{ s_i=x_1+x_2+\ldots+x_i}\).
Ponieważ liczby \(\displaystyle{ x}\) są naturalne, to lista \(\displaystyle{ [s_0,s_1,\ldots,s_n]}\) jest niemalejąca.
Jeśli na liście \(\displaystyle{ [x_1,x_2,\ldots,x_n]}\) liczba \(\displaystyle{ k}\)-ta w kolejności jest sumą kilku poprzednich, to \(\displaystyle{ x_k=s_{k-1}-s_{l-1}}\) dla pewnego \(\displaystyle{ l\in\{1,2,\ldots,k\}}\), gdzie \(\displaystyle{ s_i=x_1+x_2+\ldots+x_i}\).
Ponieważ liczby \(\displaystyle{ x}\) są naturalne, to lista \(\displaystyle{ [s_0,s_1,\ldots,s_n]}\) jest niemalejąca.