Tu nie ma w ogóle matematyki i jest dosyć częste na PE, a szczególnie przy początkowych problemach. Napisałem algorytm, który używał programowania dynamicznego(tak jak sugerował
Kaf). Dowiedziałem się, że to było niepotrzebne, bo najdłuższy ciąg Collatza dla wyrazów początkowych od
\(\displaystyle{ 1}\) do
\(\displaystyle{ 10^6}\) ma
\(\displaystyle{ 525}\) wyrazów. Oznacza to, że jest spora szansa, że algorytm typu bruteforce będzie działał. Podejrzewam, że średnia złożoność obliczeniowa algorytmu bruteforce jest wcale niezła. Zresztą na forum PE niektórzy deklarowali, że użyli bruteforce i wynik wyszedł im w kilka sekund.
Jeśli wolisz programowanie dynamiczne(w ramach ćwiczenia), to zdefiniuj tablicę
\(\displaystyle{ A}\) typów
Int o długości
\(\displaystyle{ 10^6+1}\), której
\(\displaystyle{ i}\) te miejsce będzie długością ciągu Collatza, który zaczyna się od
\(\displaystyle{ i}\). Następnie skonstruuj ją rekurencyjnie w ten sposób, że
\(\displaystyle{ A[0]=0}\),
\(\displaystyle{ A[1]=1}\) i jeśli masz już wartości tablicy dla
\(\displaystyle{ 0,1,...,i}\) to wartość w
\(\displaystyle{ i+1}\) znajdujesz w ten sposób, że uruchamiasz ciąg Collatza dla
\(\displaystyle{ i+1}\), liczysz liczbę jego wyrazów zmienną
\(\displaystyle{ k}\), ale jednocześnie sprawdzasz na bieżąco, czy obliczony w danym momencie wyraz
\(\displaystyle{ m}\) tego ciągu nie jest przypadkiem mniejszy od
\(\displaystyle{ i+1}\). Jeśli jest mniejszy, to definiujesz
\(\displaystyle{ A[i+1]=k+A[m]}\). W przeciwnym przypadku liczysz dalej aż
\(\displaystyle{ m}\) będzie mniejszy od
\(\displaystyle{ i+1}\).
Można to jeszcze ulepszyć i dodatkowo sprawdzać za każdym razem czy
\(\displaystyle{ m<10^6+1}\). Wtedy można przy okazji znaleźć od razu
\(\displaystyle{ A[m]}\), ale to chyba sprawia, że kod będzie nieprzejrzysty.
Poprawna odpowiedź to:
Przynajmniej taką mi przyjęli w PE.
Uwaga. Do przechowywania wyrazów ciągu Collatza używaj zmiennej typu
Long, bo dla wyrazów początkowych w okolicach
\(\displaystyle{ 120000}\) ciąg Collatza wychodzi poza
\(\displaystyle{ 2^{32}}\).
