(Acest articol a fost publicat pentru prima dată pe R – Win Vector LLCși cu amabilitate a contribuit la R-bloggeri). (Puteți raporta problema legată de conținutul acestei pagini aici)
Doriți să vă distribuiți conținutul pe R-bloggeri? dați clic aici dacă aveți un blog, sau aici dacă nu aveți.
Introducere
Poate fi distractiv să aduci o problemă până în pământ. Nu întotdeauna pot face asta în proiecte plătite, totuși, uneori, o pot face cu proiecte de hobby. În acest caz, voi rezolva problema cu restul lui Dudeney din nou și din nou pentru a argumenta că poate fi rezolvată la scară de creion și hârtie. Problema este următoarea.
O idee bună pentru o soluție este să observați că răspunsul este cel mai mare divizor comun (GCD) a două diferențe ale intrărilor puzzle, cum ar fi 723217 - 480608 = 242609 şi 508811 - 480608 = 28203. Cu toate acestea, „orice idee bună devine munca unei vieți pentru cineva” (Shriekback, Sacred City, „Every force evolves a form”, 1992). Putem efectua calculul rămas în mod explicit la scară de creion și hârtie? Sau trebuie să folosim un computer (cum am făcut în soluția noastră originală bazată pe R)?
Această notă este o serie oarecum implicată de demonstrații pentru a arăta că se poate rezolva această problemă „de mână” (sau cu instrumente minime).
Soluție computerizată
În nota mea originală, am implementat cel mai mare divizor comun cu o reducere iterativă – care ar putea fi scrisă și ca recursivitate. De asemenea, am fi putut accelera decât apelând o funcție gcd de bibliotecă, cum ar fi cea a lui Python math.gcd(). Aici voi încetini lucrurile pentru a completa un tabel. Acest lucru pune un accent mult mai mare pe valori și pe modul în care valorile se relaționează. Acesta este un pas intermediar pentru a elabora singuri calculul manual.
Fiecare dintre celulele din tabelul nostru de rezultate este completată cu un calcul destul de simplu (diviziune, înmulțire, adunare) și nu există atât de multe celule. În principiu, o persoană ar putea efectua calculul pe hârtie. Metodologia este prezentată aici. Următoarea este o scurtă animație (fără sunet) care arată un tabel extins în curs de completare. Pentru problema inițială, este necesară doar prima coloană.
Algoritmul euclidian extins aplicat problemei cu restul lui Dudeney (fără sunet)
Răspunsul puzzle-ului este 79ultima intrare diferită de zero din „r” coloana.
HP15c Calculator Solution (tehnologie 1982)
Acum să presupunem că nu permitem un computer digital programabil din era 2024, deoarece nu le avea în 1924 când nota a fost publicată în Strand Magazine. Putem rezolva problema cu un calculator, de exemplu HP15c (care a apărut în 1982, așa că nici ei nu le-au avut în 1924 – mai multe despre asta mai târziu).
Iată un videoclip (fără sunet) cu mine folosind un calculator HP15c care are un program stocat în „eticheta A” care efectuează un pas de cel mai mare divizor comun. Această metodă setează și calculatorul pentru următorul pas, astfel încât nu este necesară introducerea de date suplimentare. Doar introduc cele două numere de început și repet „f A” pentru a apela subrutina din nou și din nou. Macrocomanda de apăsare a tastei HP15c (sau programul) se află la sfârșitul acestei note.
hp15c rezolvă problema rămasă a lui Dudeney (fără sunet)
A fost o adevărată bucurie în a lucra cu calculatoarele din această epocă. Erau suficient de simpli încât simți că rezolvi problema, dar suficient de puternici pentru a-ți suporta cea mai mare parte a muncii. Am o notă mai veche despre această bucurie aici.
Curta Calculator Solution (tehnologie 1948)
Bine, ce fel de calculatoare ar fi putut avea publicul în 1924? Răspunsurile includ:
Calculatorul Curta din 1948 funcționează foarte mult ca un aritmometru portabil (deși primul folosește o tobă Leibniz în trepte, iar celălalt o roată cu știft). Ambii au folosit deplasarea cifrelor, un registru acumulator și un registru reversibil de numărare a revoluțiilor. Ideea este că aceste tipuri de calculatoare au fost disponibile comercial din anii 1850 până în anii 1960. Deoarece nu am acces la un aritmometru, voi începe calculul celui mai mare divizor comun manual cu un calculator Curta.
Pentru un utilizator familiarizat cu Curta, pașii sunt destul de standard. Nu învăț cum să folosești Curta, ci doar oferind pașii pe care cineva familiarizat cu un Curta ar putea fi de așteptat să-i execute. Pașii ar fi:
- Începeți cu cele două numere întregi pozitive. Pentru a găsi cel mai mare divizor comun, scrieți-le într-o coloană, primul cel mai mare.
- Ștergeți registrele de pe Curta, puneți Curta în modul de adăugare (pârghie apăsată și glisorul de adăugare/scădere la „adăugați sus”).
- Introduceți primul număr în registrul de intrare, adăugați-l la acumulator rotind manivela și ștergeți contorul de rotații.
- Împărțiți cu al doilea număr în metoda obișnuită Curta (setați glisorul de adăugare/scădere la „scădere în jos” și trageți manivela în sus). Scoateți divizorul la diferite schimburi până când registrul este mai mic decât divizorul. Înregistrați registrul ca un nou coeficient în partea de jos a coloanei noastre de numere. (Opțional) înregistrați restul lângă cât.
- Ștergeți registrul și apoi adăugați coeficientul anterior ca următorul dividend. Utilizați ultimul număr notat ca noul coeficient. Repetați pasul de împărțire și asta până când obținem un rest zero.
- Ultimul coeficient diferit de zero este cel mai mare divizor comun.
Vă arăt primii pași în următorul videoclip (fără sunet):
Curta rezolvă problema rămasă a lui Dudeney (fără sunet)
Asta mi-a luat puțin mai puțin de 1,5 minute. Este nevoie de 7 divizii pentru a completa tabelul. Prin urmare, cel mai mare divizor comun poate fi calculat confortabil în mai puțin de 11 minute folosind un calculator mecanic.
Programul HP15c
HP15c a permis macrocomenzi (secvențe necondiționate de taste) și chiar programe (inclusiv condiționale și bucle). De asemenea, are o stivă de valori cu 4 niveluri, un registru lateral numit „LSTx” (care stochează una dintre intrările diferitelor calcule) și un număr de registre denumite. Proiectarea unui calcul pentru HP15c a fost adesea o bucurie. Când calcularea a fost făcută manual, a petrecut ceva mai mult timp proiectând tabelul de rezultate și pașii de calcul.
Un program HP15c care rezolvă problema celui mai mare divizor comun este prezentat mai jos. Puteți găsi astfel de lucruri în manualele excelente și ghidurile de soluții ale vremii.
Soluția
În cazul în care am pierdut complotul, voi reveni la soluția puzzle-ului pentru ultima dată.
Soluția este 79. Toate cele trei numere au același rest relativ la 79.
