Spróbowałem napisać faktoryzację przeglądem zupełnym z użyciem systemu Fibonacciego. Udało się, choć mam jakąś dziwną usterkę.
Przypomnę zasadę tego typu: liczbie n zapisanej pierwotnie w systemie Fibonacciego zwiększam wartości 'cyfr' usiłując uzyskać tylko dwie wartości: liczbę p albo 0. Jeśli się uda, p jest dzielnikiem liczby n, jeśli nie, zwiększam p oraz za pomocą przekształceń niezmienniczych wartości liczby modyfikuję wartości stojące na miejscu 'cyfr'. n = [p,0,0,p,0,....,p,0, 0 albo p] = p *coś
Mam cztery przekształcenia niezmiennicze:
[a,0,0] = [0,a,a]
[0,a,a] = [a,,0,0]
[0,2*a,0,0] = [a,0,0,a]
[0,0,3*a,0,0] = [a,0,0,0,a]
uważając na przypadki szczególne pozycji najmniej znaczących.
Program główny. Najpierw zapisuje liczbę w systemie Fibonacciego jako ciąg jedynek oraz zer, po czym dla danego p porównuje 'cyfrę' z p.
Pętla zewnętrzna zwiększa p o 1, oraz od 'cyfr' najbardziej znaczących modyfikuje wartości podanymi schematami. Pięknie działa... dla małych wartości n.
A dla dużych? Pojawia się dosyć specyficzny błąd wyprowadzenia liczby z postaci, z której można odczytać dzielnik, Co nie znaczy, że wartość uległa zmianie. Z niejasnych dla mnie powodów nie można zastosować zwykłej pętli typu
for c in range(len(liczba), 0, -1) {...}
gdyż czasem pojawia się nieco inna wartość na pozycji którejś z cyfr. Zamiana pętli na równoważną:
c = len(liczba)
while( c>0 ) {
c-=1
{...}
}
powoduje, że wyświetlany podgląd 'cyfr' liczby może, choć nie musi ominąć ten błąd prowadząc do innego wyniku. wbrew definicji algorytmu jako 'jednoznacznego sposobu uzyskania wyniku z danych wejściowych'. Zawsze błąd pojawia się na pozycji 3 najmniej znaczącej (odpowiednik 'tysięcy'), kiedy reszta jest całkowitą wielokrotnością 3.
Zatem w programie w przypadku sugestii znalezienia dzielnika jako 'cyfry najmniej znaczącej' należy ją sprawdzić, np. sprawdzając krotność róźnych wartości 'cyfr'. Jeśli są trzy, ta różniąca się nie musi występować tam gdzie chcę ją sprawdzać, i iteracja musi się powtórzyć dla tego samego p by ją (już zmienioną) wstawić w odpowiednie miejsce dla odczytania wyniku.
Istnieje bardzo powolna tendencja zmniejszania długości ciągu potrzebnego na zapis 'cyfr'.
Kryterium stopu jest pierwiastek kwadratowy z liczby, bo okazało się, że dla liczb pierwszych jest co prawda szybsze kryterium stopu, spełniane jednak często przez liczby złożone. Zatem nie do użycia.
