Zjištění periody při dělení zlomku
Ahoj,
napadá někoho z vás nějaký dobrý algoritmus, jak zjistit periodu při dělení?
Naprosto každý zlomek, který je zadán jako A/B, přičemž A, B jsou celá čísla, má konečně velkou periodu.
Jak byste periodu zjišťovali automaticky vy? Nemám problém provést výpočet klidně na 100 (i více) desetinných míst a pak v tom nějak hledat. Potřebuji nicméně něco, co mi zaručí to, že nalezená perioda není jenom náhodná skupina čísel, která se sice nějaký čas opakuje, ale po nějaké chvíli přestane, tj. jak velkou oblast následujících čísel má smysl dále testovat?
Jde mi o to, že v současné době velice intenzivně pracuji na nové podobě Mathematicatoru, který bude umět kvalitně pracovat s výpočty a součástí toho budou nejrůznější numerické nástroje na podrobnou analýzu všeho možného a právě periody mi vrtají hlavou.
V příloze je ukázka nové podoby výstupu hledání (zatím neveřejná BETA verze).
Jan B.
23. 04. 2015 21:18
3 odpovědi
Ahoj Honzo,
vím jak na tu periodu přijdeš. Musíš si ale naprogramovat algoritmus pro dělení, nebo ho někde najít. Prostě donutíš algoritmus, aby dělil jako člověk, a jakmile narazíš na stejné číslo v desetinném rozvoji, víš, že bude následovat periodický rozvoj. Teda aspoň myslím, že to tak je... :-)
To mě vede k dalším otázkám... může jako podíl dvou čísel, tedy ze zlomku vzniknout například peridické číslo 14.3537 ? Myšleno tak, že 3537 je periodické? A pokud ano, z jakého zlomku? A obecně, když mám periodické číslo, jak zjistím z jakého zlomku vzniklo?
Nevíte to někdo?
Docela jsem si s tím hrál a napsal jsem klasický školní algoritmus pro dělení "s ocáskem". Zkus si vyhledat nějaký zlomek a uvidíš: http://185.8.237.158/search.php?q=3%2F14
Zpětná detekce zlomku z desetinného čísla už není tak triviální a napsal jsem na to opravdu složitý algoritmus, který si poradí s nejrůznějšími vstupy (funguje i pro opravdu hodně ošklivá a složitá zadání). Konkrétně tvůj příklad vyřeší za méně než sekundu na této adrese: http://185.8.237.158/search.php?q=14.3537
Všechno to jsou ale statistické a numerické metody, takže sice najdu zlomek, který po vydělení generuje takové desetinné číslo, nicméně ti nemohu garantovat, že to je jediné správné řešení (proto to často najde spoustu dalších zlomků, pro které to plně, nebo i jen částečně platí).
Marku, tak jsem asi přišel na algoritmus, co pro každé periodické číslo vždy vrátí jeho zlomkový tvar (a vůbec není složitý). Více viz přílohu.
