Gra paragrafowa, przykładowa implementacja w C++

Budowa gry paragrafowej wydaje się prosta: opis, wybór opcji i przejście dalej.

Zamierzam przedstawić swoją propozycję implementacji w C++. 

 

Najpierw założenia: 

Każda lokacja to inna funkcja. Istnieje kilka lokacji dostępnych z dowolnej innej, nazwijmy je 'ogólne'. Są to np.: opcje, finisz, pomoc, statystyki w przypadku gdy coś zbieramy i używamy. Dostęp do tych funkcji jest z petli głównej programu, a przy ich opuszczaniu wracamy do lokacji trzymanych przez wskaźnik. 

Występuje kilka zmiennych statystycznych pokazujących przebieg gry. Wydają się one globalne w programie, gdyż każda z lokacji może, ale nie musi z nich korzystać. 

W mojej implementacji lokacje są trzymane wskaźnikami do funkcji

int (*f) ();

Funkcje zwracają kod wciśniętego klawisza char przekonwertowany do int, co umożliwia dostęp do lokacji ogólnej lub wyście z programu. Wychodzę z gry przez ESC.

Ciało funkcji main(void) jest proste: 

f = enter; // funkcja enter() wprowadza do gry

int i = 0; // zmienna do której odkładam wynik f()

while(1) {

  i = f(); 

  if( i ) i = finisz(); // f=finisz nie pozwala wrócić do opuszczonej właśnie lokacji

  else // ... wywołania lokacji ogólnych

  if( ESC== i ) break; 

}

return 0; 

Ciało lokacji jest nieco bardziej rozbudowane, wszak bywa rozgalęzieniem. Ale można ogólnie wydzielić następujące części (Nr to liczba konkretnej funkcji): 

int nazwaNr () {

  listwa(); // czyszczenie ekranu i podanie opisu stałego (statystyki: zasoby itp.)

  opisNr; // co ma poczytać gracz w tej lokacji

  dzialanieNr; // jeśli może coś zrobić

  int c =  getch; // pobranie komendy od gracza

  nagroda(); // jeśli statystyki mają ulec zmianie

  f = wyborNr(c); // wskazanie nowej lokacji do której gracz przejdzie, nawet gdy c wskaże lokacje ogólną

  return c; // i po zwiedzeniu lokacji ogólnej wskazanej przez c gracz pójdzie do f()

}; 

Jeśli w kodzie piszę lokacje od ostatniej do pierwszej, na ogół większość jest widocznych dla siebie, i nie trzeba ich dodatkowo deklarować. Wyjątkiem są rozgałęzienia kilku niezależnych ścieżek. Lokacje węzłów zbiorczych muszą być wcześniej zadeklarowane.

Kiedy rozkładana liczba jest dwucyfrowa

 Szukanie dzielników liczby N zapisanej w systemie o podstawie większej niż pierwiastek kwadratowy z liczby wydaje się mijać z celem. Tyle przypadków... I co z tego, że istnieje system, w którym liczba N = s*q, s>q ma szczególnie prostą postać:

N = q q _ {s-1}

Jednak na ogół dzielnik można znaleźć zanim napotkamy tę postać. Korzystając z sita wspominanego parę wpisów wcześniej, na dzielnik N natrafimy stosując jeden ze sposobów: podstawa systemu oraz wyraz wolny mają wspólny dzielnik; dystans od wartości startowej jest tym dzielnikiem; dystans rozkłada iloczyn paru dużych liczb pierwszych, wyławiając dzielnik.

W systemie o podstawie odrobinę większym niż pierwiastek kwadratowy, postaci 

N = a b _ {2p}

wartość a jest bliska temu pierwiastkowi kwadratowemu oraz maleje ze wzrostem podstawy systemu. Maleje aż do jedynki, ale możemy zatrzymać szybciej, po przejrzeniu połowy przypadków. Wykorzystamy fakty: 

- wśród k kolejnych liczb naturalnych istnieje dokładnie jedna, która dzieli k; 

- liczba pierwsza mniejsza niż k występuje co najmniej raz w przedziale [k, 2k); 

- iloczyn dwu dużych liczb pierwszych w odpowiednim systemie niedziesiątkowym ma postać N = (r*q) q  _ {2p}, gdzie q jest liczbą pierwszą, oraz drugi z dzielników jest równy s=2rp+1. 

Zmodyfikujemy sito opisane przy liczbach trójcyfrowych na potrzeby liczb dwucyfrowych. Tam sito Eratostenesa działało dla podstaw systemów, teraz  będzie obsługiwało cyfrę dziesiątek. Wartość cyfry jedności będzie oscylowała wokół cyfry dziesiątek. Cyfra dziesiątek maleje, a podstawę systemu trzymamy parzystą.

1) Wybieramy wartość startową bliską pierwiastka kwadratowego z N, zapisujemy ją jako liczbę dwucyfrową a b _ {2p} o podstawie parzystej. 

2) Do wartości a stosujemy sito Eratostenesa, czyli zapamiętujemy kolejne dzielniki d, które wskazują kolejne, coraz mniejsze wielokrotności znajdowanych liczb pierwszych a-d. Połowę początkowej wartości a zapamiętujemy jako wartownika, oraz inicjujemy dystans d od punktu startowego. 

3) Pętla. Zamierzamy przenieść jedynkę z a zwiększajac równocześnie cyfrę jedności b. Jeśli uzyskana wartość jest większa niż a, zabieramy parzystą wielokrotność a zwiększając podstawę systemu (konwersja na system o większej podstawie parzystej, by b było stosunkowo blisko a). Zwiększamy dystans o 1, oraz sprawdzamy, czy w wyniku tzw. trial division przez przyczepione sitem małe liczby pierwsze wobec a pojawiła się liczba pierwsza, podobnie jsk opisano w poprzednim poście. Dystans też może okazać się liczbą pierwszą, traktowaną jako znajdowana. Jeśli rozpoznamy liczbę pierwszą, sprawdzamy jej podzielność przez cyfrę jedności b, co może zakończyć się powodzeniem w znalezieniu dzielnika i zakończeniem. Takie wartości możemy kasować jako już niepotrzebne. 

4) Kontunuujemy przebieg sita, aż znajdziemy dzielnik. Kiedy a zmaleje do wartości wartownika, nie znaleźliśmy dzielników, liczba jest pierwsza. 

Pętla dla liczb pierwszych wykona się tyle razy, ile wynosi połowa wartości punktu startowego. Oprócz trail division jest dzielenie cyfry jedności przez rozpoznawane liczby pierwsze. Dopóki nie rozpoznamy prawidłowo gigantycznych liczb pierwszych w sicie, chyba potrzebujemy pamiętać te postaci. W innym przypadku do sita mogą trafiać liczby złożone. Kiedy dystans będzie tak duży, że jego kwadrat przekroczy a, każda napotkana większa wartość jest pierwsza, dystans przestaje być potrzebny. Mamy tyle dzieleń cyfr jedności, ile jest liczb pierwszych. 

Dla liczby złożonej pętla często zatrzyma się, zanim dystans osiągnie wartość mniejszego z dzielników. 

 

Sprawdziłem dodatkowe przyspieszenie, stosując cechy podzielności przez p-1 oraz p+1. Wartości w sicie są zapisywane jako pary (wartość o podstawie p=4k, produkt), w którym produkt przekształca się w postać kanoniczną wartości. Opisana wcześniej heurystyka jest modyfikowana, i raczej nie nadaje się do obliczeń ręcznych. Ale maszynowo może być wydajniejsza, bardziej dopasowana dla obliczeń współbieżnych rozproszonych. Wartość dystansu nieco traci na znaczeniu. Liczby pierwsze ujawniają się nawet przy wstawianiu nowej wartości do sita,

Funkcja sumy cyfr dla wielu liczb trójcyfrowych i dwucyfrowych jest funkcją piłokształtną. Gdy cyfra setek jest już wystarczająco mała i nie zmienia się podczas konwersji, cyfra dziesiątek jest od niej znacznie większa (co najmniej ośmiokrotnie), można łatwo oszacować system, w którym suma ta znów będzie blisko podstawy. Niech n = a*p*p + b*p + c. Iloraz p/(b-a) wyznacza przesunięcie podstawy, przy której znów a+b+c approx p. Stosuję to do sprawdzania pierwszości wartości odkładanych do sita, gdy liczba może być półpierwsza, czyli jest iloczynem dwu liczb pierwszych. Tempo zmiany podstaw z liniowego (x4) przechodzi w wykładnicze. A w ostatniej iteracji się na ogół sypie, ale wtedy mam heurystykę: kwadrat wyrazu wolnego nie przekracza wymaganego przesunięcia wartości podstawy systemu.

Szukanie bardzo dużych dzielników, propozycje

 Już zmieniono tu grafikę na taką, w której trudniej mi się znaleźć. Tylko jeszcze czekam tu na blokadę logowania się. Mam to już na kontach w Linkedin oraz na nowo otwartej skrzynce pocztowej. Stara jest technicznie blokowana, a na nową nie mogę się zalogować z racji nieoczekiwanego błędu.

Zamierzam tu podsumować swoje jeszcze nie przetestowane do końca spostrzeżenia. Nie wiadomo, jak dalej potoczy się moje narastające wykluczenie... 

Przypomnę:

Cyfrą jest nieujemna liczba ograniczona z góry przez podstawę systemu. Zatem, dla systemów o podstawach rzędu milionów, cyframi stają się liczby nawet rzędu tysięcy w systemie dziesiątkowym. Dalej używam pojęć  np. 'cyfra setek' dla wskazania pozycji cyfry w liczbie. 

Dla odpowiednio dużej podstawy systemu p, każdą odpowiednio dużą liczbę można zapisać jako trójcyfrową [a, b, c]_p. I o takich będę dalej pisać.

Jeśli liczba n = p*q, p<q, to można zapisać liczbę q w systemie o podstawie p dla pewnych danych parametrów  a, b:

q = [a, b]_p

oraz n = p*q = [a, b, 0]_p .

Zobaczmy, co się stanie z tą wartością, gdy zmienimy podstawę systemu o 1, czyli zamiast p zastosujemy podstawy systemów: p-1, p+1, bez zmiany wartości liczby n (co sztucznie powiększone, odejmiemy itp.): 

[a, b+2a, a+b+0] _ {p-1}

[a, b-2a, a-b+0] _ {p+1}

Przywracając cyfrę jedności c=0, uzyskujemy warunki dla podstaw systemów sąsiadujących z systemem o podstawie dzielnika: w jednym suma cyfr jest równa podstawie systemu (por. cecha podzielności przez 9), w drugim naprzemienna suma cyfr jest równa 0 (por. cecha podzielności przez 11). 

Właściwie powinienem pisać, że dostaję całkowite wielokrotności podstawy, ale dla liczb nieparzystych n o bardzo dużych podstawach mamy redukcję do tych warunków. A dodatkowo, funkcja sumy cyfr liczby trójcyfrowej w kolejnych systemach liczbowych jest funkcją przedziałami monotoniczną. Rozmiar 'ząbków' rośnie wraz ze wzrostem wartości. Aż się narzuca algorytm wyżarzania lub bisekcji dla szukania wartości podstaw okalających dzielnik.

Kolejnym podejściem, wykładniczym względem krotności cyfr zapisu binarnego liczby, jest stosowanie tych cech, gdy liczbę zapiszemy najpierw jako iloczyn 

n = 4*d+2*e+1 , 

e jest cyfrą dziesiątek liczby n w systemie binarnym, całe wyrażenie jest wielomianem (d jest za duże by być cyfrą w binarnym), oraz traktując jako liczbę trójcyfrową mamy dwie rekursywne gałęzie, w pierwszej podwajamy podstawę systemu, w drugiej przechodzimy na system o 1 większy i też podwajamy podstawę. Póki mamy odpowiednio duże 'cyfry setek', sprawdzamy sumę i naprzemienną sumę współczynników, jak wyżej. 

Czyli rekursja przebiega: 2 -> (4 -> 8 -> ...  4+1=5 -> ...) 2+1=3 -> ...

Możliwe własności dzielników liczb w palindromach

 Zastanawiałem się, czy można uzyskać palindrom nad systemem o podstawie o jeden mniejszej niż któryś z dzielników d liczby n. 

Palindrom wyglądałby tak:  a  a+b  a+b  a, wykorzystując fakt, że przy tej podstawie dzielnik wygląda następująco d = 1 1 _{d-1}. 

Lecz dla większych wartości pozostały n/d musiałby być przedstawiony jako palindrom nad tym systemem. Możliwe, ale bardzo kłopotliwe. 

 

Zaś dzielniki w palindromach nad systemem binarnym długości 3 mogą mieć postacie następujące 

ad   bd   ad _2

gdzie d jest dzielnikiem, oraz n/d = 4a+2b+a = 5a+2b. Nieskończenie wiele możliwości, lecz jeśli chcieć znaleźć któryś, trzeba znać d lub n/d. Niknie w tłumie.

W tym szczególnym przypadku iloraz wyrazu skrajnego do środkowego wynosi

(ad)/(bd) = a/b. 

Kolejna wersja przeglądu zupełnego sitem

Wspominałem już o możliwościach przeglądu zupełnego za pomocą sita. Wtenczas potrzebowałem jako lemat tablicę liczb pierwszych nie większych niż pierwiastek czwartego stopnia z liczby rozkładanej. 

W tej wersji nadal pozostanie struktura stogu, w której odkładam parę: 

[podstawa systemu p, lista jej znanych dzielników pierwszych d_i] 

struktura działa tak samo ja opisałem wcześniej: po pobraniu wartości, zanim ulegnie skasowaniu, odkłada na stóg wartości [p - d_i, d_i] dla wszystkich znanych dzielników p. 

Wówczas należało odróżnić dzielniki wykryte od już przetestowanych. Teraz w strukturze tej odkładane są tylko znane liczby pierwsze, sprawdzone pod kątem podzielności. 

 

Potrzebuję drugiej struktury: listy par, w której trzymam duże wartości będące iloczynami liczb pierwszych lub takimi liczbami, oraz albo ich wartość początkową, albo odległość (dystans) od miejsca startowego algorytmu. Jest to niezbędne, gdy przy wyznaczaniu odległości znajdujemy liczbę pierwszą, aby ją właściwie umieścić w strukturze stogu. Wygodniej jest użyć odległości, chociażby z uwagi na mniejszą wartość choć bardziej skomplikowane jest wtedy znalezienie wielokrotności aktualnego dystansu.

 

Jak to wygląda w praktyce -  na początku. 

Liczbę rozkładaną n przedstawiam w postaci 

n = (a*p+b)*p+c

np. n = (1 * 38 8878 4050 9055 + 2)* 38 8878 4050 9055 - 21 1614 4142 3728

Wartością początkową będzie bliska pierwiastkowi kwadratowemu b= 38 8878 4050 955, którą w każdej iteracji zmniejszamy o 1 do połowy jej wartosci, lub przez odpowiednio dużą potęge 2^i ( 2^i < sqrt n < 2*2*i ). Równie dobrze możemy przesunąć do najbliższej potęgi 2 większej niż pierwiastek kwadratowy z n, przyjąć a=1 oraz b ujemne.

Liczbę możemy równoważnie zapisywać na inne sposoby:

n = (1 * 38 8878 4050 9055 + 1)* 38 8878 4050 9055 + 17 7263 9908 5327

n = (1 * 38 8878 4050 9060 - 9)* 38 8878 4050 9060 + 17 7263 9908 5347

n = (1 * 70 3687 4417 7655 - 48 8781 7820 0808) * 70 3687 4417 7655 - 7 3130 0816 6378

Dobór, według wielkości wartości, wartości początkowych itp. 

 

W poprzednim algorytmie znajdowałem, że 

38 8878 4050 9055  ma dzielniki:  5, 19, 41, 239, 177 4231, i dzieliłem c = 17 7263 9908 5327 przez każdy z nich. 

Teraz nie znam tych dzielników, zatem w strukturze listy par odkładam np. wartość 38 8878 4050 9055 i tą samą wartość (odległość 0). Po czym obliczam największy wspólny dzielnik 

gcd( 38 8878 4050 9055 , 17 7263 9908 5327 ) 

zatrzymując, gdy wartość gcd() zmniejszy się poniżej odległości. W strukturze stogu nic na razie nie odkładam. W ten sposób wiem, że dzielniki tej liczby są względnie pierwsze z liczbą rozkładaną, nie znając jeszcze tych dzielników. No chyba że znajdę dzielnik całej liczby, zwrócony przez gcd()!

Biorę następną wartość z podstawą mniejszą o 1, ze zwiększoną odległością o 1, w której modyfikuję konwersją: b=b+2, c = c+b-a, wartość n jest niezmiennikiem: 

n = (1 * 38 8878 4050 9054 + 4)* 38 8878 4050 9054 - 21 1614 4142 3725

Wśród obu wartości p, p-1 dokładnie jedna jest parzysta, zatem w strukturze par dzielę przez odpowiednie potęgi 2 zmniejszając wartość pierwszego elementu pary, i znajduję pierwszą liczbę pierwszą, która zaznacza pozycje parzyste w strukturze stogu: 

[38 8878 4050 9054-2 ;  2]

W drugiej strukturze wyeliminowane są zarazem wszystkie wystąpienia 2. Jest ona tylko w stogu, i ta liczba pierwsza zmniejsza podstawę p dla liczenia wspólnego dzielnika. 

Przyjmując następną wartość, wiem, że spośród wszystkich odłożonych w strukturze par i pobranej, co najwyżej jedna jest podzielna przez aktualną odległość. Jeśli jej nie znajdę, odległość jest liczbą złożoną, z już uwzględnionymi czynnikami pierwszymi. 

Myślałem, by sprawdzać kolejno wszystkie wartości struktury par w poszukiwaniu właciwej, a po jej znalezieniu, podzieleniu przezeń. Ale widzę szybszy sposób, mam dwa wskaźniki, jeden na wartość największą struktury, drugi na najmniejszą, zaś wartości z jedynką usuwamy ze struktury.  Jest to potrzebne z dwu powodów: wartość największa wskazuje resztę z dzielenia wskazywanej podstawy przez aktualny dystans, co w prosty sposób wskazuje właściwą wartość, którą normalnie dzielimy. Jest podzielna, uzyskujemy nową liczbę pierwszą do wyeliminowania ze struktury par i przeniesienia do stofu (zarazem już sprawdzona, że nie jest dzielnikiem n).

Jeśli po wyrugowaniu znalezionej liczby pierwszej ze struktury par uzyskamy wartość 1, kasujemy parę. Sprawdzamy, która jest najmniejsza, jeśli okaże się, że najmniejsza jest tylko dwucyfrowa w systemie o podstawie dystansu, jest to kolejna liczba pierwsza do wyrugowania, tzn. przeniesienia do stogu.    

Np. 

struktura par ma wartości (punkt startowy 70 3687 4417 7664 - potęga 2)

dystans 2   wartość 35 1843 7208 8831
dystans 3   wartość 70 3687 4417 7661 (największa)

Po kilku iteracjach znajdziemy się w odległości 7 od punktu startowego, czyli podstawą jest 70 3687 4417 7657. Sprawdzamy liczbę 7, szukając reszty z dzielenia przez 7 wartości z dystansu 3. Znajdujemy resztę 6, czyli przez 7 podzielna jest liczba z dystansu 3-(7-6)=2.
Mamy nową wartość dla tego dystansu po wyrugowaniu liczby pierwszej 7
dystans 2   wartość 5 0263 3886 9833

I wiemy, że liczba nie dzieli się przez 7, co sprawdziliśmy kilka iteracji wcześniej. Po kolejnych dwu iteracjach dystans wrazsta do 9. Reszta sugeruje, ze liczba ta znajduje się dla dystansu 7, ale mamy tam wartość 7 8187 4935 3073, która nie jest podzielna przez 9, zatem dystans 9 = 3*3 jest liczbą zlożoną z uwzględnionymi już czynnikami.  Ta ogromna wartość jest liczbą pierwszą, która rozpoznana jako pierwsza przejdzie do stogu dopiero przy dystansie 2796203.

I ten sposób sprawdza początkowo dosyć szybko małe liczby pierwsze i giganty. Z biegiem czasu mniejsze liczby pierwsze rozkładają podstawę  systemu stogu, tak że wspólny dzielnik od razu jest widoczny, A po jeszcze dłuższym okresie zostają do sprawdzenia tylko liczby pierwsze, często większe niż podstawa systemu.
Są one wyłapywane przez ich nieobecność w strukturze stogu podczas pobierania kolejnej wartości o 1 mniejszej, lub przechodzą ze struktury par przy dużym dystansie.

Możliwość dalszej modyfikacji znajdowania największego wspólnego dzielnika

Miotam się ostatnio między programowaniem w stylu gier paragrafowych, a kontynuacją wymyślania sposobów rozkładu. 

Można jeszcze bardziej zmodyfikować sposób obliczania wspólnego dzielnika. Wiem już, że mogę dzielić argumenty przez małe liczby, które są podzielne przez dokładnie jeden z argumentów, oraz zatrzymać algorytm, kiedy osiągnie odpowiednio małą wartość przy narastajacej wiedzy o braku dzielników w tym zakresie. 

Można to robić mniej zachłannie, co o dziwo jest w stanie zwiększyć szybkość zmniejszania się argumentów.
Jeśli oba argumenty są nieparzyste, i wiem, że wspólnym dzielnikiem nie jest wielokrostość 2 lub 5, mnożę jeden z argumentów przez małą stałą, by uzyskać taką samą cyfrę najmniej znaczącą. Następnie odejmuję. Uzyskana różnica jest podzielna przez 10, dzielę przezeń, potem jeszcze przez ewentualne dwójki. W ten sposób w jednej iteracji mogę zmniejszyć wartość o rząd wielkości. 

Zobaczmy na przykładzie liczb Fibonacciego, które tworzą najdłuższy ciąg zbieżny do wspólnego dzielnika: 

nwd(377, 233) 

Ponieważ 3*9 = 27 mają tę samą cyfrę najmniej znaczącą, liczę nwd( 377, 9*233) = nwd( 377, 2097), Odejmuję je 2097-377 i dzielę przez 10 i jeszcze kilka 2. Uzyskuję: 

nwd( 233, 43 )

Postępując jak wcześniej (tym razem cyfra 3 taka sama, bez mnożenia), dostaję

233-43 = 19*10

czyli nwd(233, 43) = nwd( 43, 19). 

Można kontynuować, uzyskując w kolejnym kroku nwd (3*43, 19), lecz rozsądek podaje, by wrócić do standardu i uzyskać parę nwd(19, 5). Kolejna operacja (ze zmianą znaku) zwraca nwd (19,4*5) = nwd (19,20) = 1. 

Łącznie 4 iteracje, a standardowym odejmowaniem algorytmu Euklidesa byłoby 13.  

Stosuję to do sprawdzania kolejnego algorytmu rozkładu przeglądem zupełnym z sita, w którym potrzebowałem znać tablicę liczb pierwszych nie większych niż co najwyżej pierwiastek czwartego stopnia z liczby rozkładanej. Chyba nie potrzebuję znać tej tablicy kosztem dodatkowej struktury.