V poli a je nejaká permutácia n rôznych
čísel. Program počíta, koľko prvkov v poli sa nachádza
v cykloch dĺžky 3
permutácia 5,3,6,8,7,2,1,4
obsahuje 2 trojprvkové cykly, teda p=6
riešením je ľubovoľná permutácia 9 čísel,
ktorá sa skladá z 3 trojprvkových cyklov, napr.
2,3,1, 5,6,4, 8,9,7
Nakoľko sa od n v cykle postupne odpočítavajú
nepárne čísla 1, 3, 5, 7, ... až kým nedostaneme záporné
číslo, zrejme pre všetky hodnoty z <m2,(m+1)2-1> cyklus beží
rovnako dlho. Preto sa stačí zaoberať len druhými mocninami
celých čísel. Označme s také celé číslo,
pre ktoré (s-1)2<=n<s2, potom vonkajší cyklus beží
s-krát a vnútorný cyklus spolu s2-krát. Vzorec
pre trvanie programu je 5s+2s2+5
pre n=123 program bežal 3.53 sekundy
stačí otestovať pre niekoľko n – druhých mocnín:
pre n=9 čas 57
pre n=16 čas 80
pre n=25 je čas 107 desatín sekundy
Postupnou konštrukciou stromu (po hodnoty menšie ako
100) zistíme hodnoty, ktoré sa dajú vygenerovať rôznymi
spôsobmi:
1.krok: 2(3,5)
2.krok: 3(5,8), 5(9,14) => celý podstrom pod
5 sa dá vygenerovať rôznymi postupnosťami