Algoritmo di Euclide

Risolvi entrambi i problemi usando l’ambiente array in modo “creativo”

Andrea, la lettura delel guide non è il tuo forete, a quanto pare; il comando per tirare una riga orizzontale che passi sotto alle colonne da n a m è [tt]\cline{m-n}[/tt]

Certo che le spaziature non sono quelle matematiche ma \arraycolsep serve appunto per regolare la semi distanza di due colonne adiacenti in una matrice.

Siccome non esiste un ambiente già fatto per “disegnare” l’algoritmo di Euclide (ma lo si descrive molto meglio con un successione di espressioni, solo gli esempi numerici richiedono di trafficare con gli array), purtroppo bisogna arrangiarsi in modo creativo; fare provare, controllare, correre e ripetere finao a quando si è soddisfatti.

Tieni presente che \arraycolsep di default dovrebbe essere 6pt, quindi lo spazio globale fra due formule contenute in celle adiacenti dovrebbe essere di 12pt cioè di circa 4mm; è ovvio che quel valore di 6 pt può essere ridotto a meno della metà.

Sia \cline sia \arraycolsep si trovano certamente nella GuidaGuIT; cercali con l’indice analitico.

forse ho capito male ma se vuoi commentare dei passaggi di calcoli
magari con qualche freccetta che non guasta
guarda qui
tkz-linknodes
ciao
claudio

ottimo anche con beamer

edit
una guardata la darei anche qui
xlop

(ci sono rriuscito alla fine)

Andrea, ora è un p’ tardi e preferisco andare a nanna.
Domani ti mando sorgente e pdf della disposizione per le divisioni successive che ho realizzato tra polinomi un ventina di anni fa, e che ora ti adatto per i numeri interi; il trucco per scrivere il meno possibile e non ricopiare o reimpostare nessuna divisione è quello di disporre le divisioni successiva, con i quozienti a destra del rispettivo divisore e i resti sotto il rispettivo dividendo, ma scambiando la destra e la sinistra ad ogni successiva divisione.

La tabella con array richiede quattro colonne due filetti verticali (quelli che non bisognerebbe mai usare, ma qui li si usa in modo creativo, volendo con i numeri colorati, che secondo me, visto il ruolo dei vari operandi che ora sono resti ora divisori, è meglio non usare.Aspetta domani e vedrai che è semplice.

Come giustamente dici tu, per l’algoritmo di Euclide un esempio vale più di mille parole.

Fai girare questo semplice file .tex:`% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode
\documentclass{book}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[italian]{babel}
\usepackage{amsmath,amssymb}

\begin{document}
\begin{center}
L'algoritmo di Euclide con la disposizione delle divisioni successive di Claudio
\end{center}

L'algoritmo di Euclide serve per trovare il MCD di due numeri interi $N_0$ e $N_1$ e, senza perdita di generalità, assumiamo $N_0 >N_1$. L'algoritmo si svolge come segue:
\begin{equation}
\begin{aligned}
N_0 &= q_1 N_1 + N_2\\
N_1 &= q_2 N_2 + N_3\\
\dots&=\dots \\
N_{n-1}&= q_n N_n +0
\end{aligned}
\end{equation}
dove $q_1, q_2, \dots, q_n$ sono i successivi quozienti interi delle divisioni $N_{i-1}/N_i$ per $i-1, 2,\dots, n$. Risulta che $N_n$ è il MCD dei due primi numeri interi $N_0$ e $N_1$.

Per organizzare le divisioni successive riscrivendo il minimo delle informazioni necessarie si può procedere in verticale eseguendo le divisioni ora da sinistra a destra ora da destra a sinistra, alternativamente. Per lasciare libero il posto in verticale per le sottrazioni necessarie per calcolare i successivi resti, i quozienti vanno messi accanto al divisore.
\begin{equation}\renewcommand\arraystretch{1.5}
\begin{array}{r|r|r|l}
& N_0 & & \\\cline{3-4}
& q_1N_1 & N_1 & q_1 \\\cline{1-2}
q_2 & N_2 &q_2N_2 & \\\cline{3-4}
& q_3N_3 & N_3 & q_3 \\\cline{1-2}
\hdotsfor{4} \\\cline{3-4}
& \dots & N_n & q_n \\\cline{1-2}
& 0
\end{array}
\end{equation}

Esempio: determiniamo il MCD fra 2993 e 1095:
\begin{equation}\renewcommand\arraystretch{1.5}
\begin{array}{r|r|r|l}
& 2993 & & \\\cline{3-4}
& 2190 &1095 & 2 \\\cline{1-2}
1 & 803 &803 & \\\cline{3-4}
& 584 & 292 & 2 \\\cline{1-2}
1 & 219 & 219 & \\\cline{3-4}
& 219 & 73 & 3 \\\cline{1-2}
& 0 & &
\end{array}
\end{equation}
e il MCD è 73.

Come si vede, con questa disposizione dei calcoli non bisogna ricopiare niente e non sono necessarie frecce per indicare dove riutilizzare i resti come divisori. L'unica cosa a cui bisogna fare l'abitudine è scambiare alternativamente il verso della divisione da sinistra a destra e poi da destra a sinistra, fino a quando si raggiunge il resto nullo.

\end{document}`

e vedi come è semplice descrivere anche graficamente l’algoritmo di Euclide con la mia disposizione dei calcoli.

Penso che dal punto di vista mnemonico uno schema come quello di figura (senza griglia, con le frecce ed eliminando pure i prodotti q_iN_i) sia più pratico.
Che ne dite?
[attachment=423]eucl.png[/attachment]

Sì, ma se devi insegnare a fare i conti a mano, devi lasciaro lo spazio per i conti intermedi.:wink:

Sì, è meglio inserire i prodotti, ma tenerli fuori dallo schema principale (quozienti/resti) come in figura.
Grazie, proverò a creare il codice con tikz e lo posterò appena possibile.

[attachment=424]eucl2.png[/attachment]

Ecco una soluzione “spartana” (ma tikz permette qualità grafiche di altissimo livello) del codice, con la figura catturata dal pdf.
`
% ——– eucl.tex (Set.12)———–
% Esempio minimale del pacchetto tikz
%————————————
\documentclass{minimal}
\usepackage{tikz}

\begin{document}
\pagestyle{empty}

\begin{tikzpicture}[set style={{help lines}+=[dashed]}]
\draw[style=help lines] (0,0) grid +(12,12);
\draw (4,11) grid +(1,1);
\draw (6,10) grid +(1,1);
\draw (10,10) grid +(1,1);
%—–
\draw (4,9) grid +(1,1);
\draw (0,9) grid +(1,1);
%—–
\draw (6,8) grid +(1,1);
\draw (4,7) grid +(1,1);
\draw (6,6) grid +(1,1);
\draw (4,5) grid +(1,1);
%——————————————————
% red1
\draw [red,very thick,->] (5,11) — (6,10.5);
\draw [red,thick, ->] (7,10.5) — (8,10.5);
\draw (8.5,10.5) circle (0.5);
\draw [red,thick, ->] (9,10.5) — (10,10.5);
% blue1
\draw [blue,very thick,->] (6,10) — (5,9.5);
\draw [blue,thick,->] (4,9.5) — (3,9.5);
\draw (2.5,9.5) circle (0.5);
\draw [blue,thick,->] (2,9.5) — (1,9.5);

% ……… e così via

% ——– Fill numbers ———–
\node at (4.5,11.5) {2993};
\node at (6.5,10.5) {1095};
\node at (8.5,10.5) {2};
\node at (10.5,10.5) {2190};
%—
\node at (4.5,9.5) {803};
\node at (2.5,9.5) {1};
\node at (0.5,9.5) {803};
%—
\node at (3.5,8.5) {$da\; completare$};
\end{tikzpicture}

\end{document}
`
[attachment=425]scr13.png[/attachment]

capisco che oggi gli studenti di liceo non sanno fare più i conti a mano e tutti dispongono di macchinette, alla peggio della funzione calcolatrice del telefonino, ma mi spieghi come fai ad eseguire le sottrazioni se minuendo è in una colonna e il sottraendo è in un’altra (cioè minuendo e sottraendo non sono incolonnati)?

Il disegno è bello, ma risulta di uso difficile anche con la macchinetta.

Probabilmente sono io che sono troppo abituato al mio schema.

Nota che il mio schema serve anche per le divisioni successive fra polinomi; in quel caso i monomi con la stessa potenza devono essere ben incolonnati; serve anche per le divisioni successive alla prvescia (il quoziente è ottenuto eseguendo la divisione dei monomi di grado più basso, invece che più alto); il procedimento serve per eseguire la sintesi dei circuiti RC, RL e LC a scala, sia in forma canonica (minimo numero di componenti) o anche non canonica.

Capisco che questo non possa chiamarsi algoritmo di Euclide, ma qualunque algoritmo matematico, più o meno, serve per applicazioni che il matematico “inventore” non si sarebbe nemmeno immaginato. Il povero Euclide non sapeva nemmeno che cosa fossero i polinomi e meno che mai la sintesi dei circuiti elettrici lineari passivi a due tipi di componenti. 😉

@lifetime: mi potresti dire se hai un riferimento per la sintassi di

`[set style={{help lines}+=[dashed]}]`

Non ho trovato nulla di simile nel manuale o in rete…

Ciao
Claudio

Questo nuovo schema mi sembra … migliore!
`
% ——– eucl3.tex (Set.12)———–
% Esempio minimale del pacchetto tikz
%————————————
\documentclass{minimal}
\usepackage{tikz}

\begin{document}
\pagestyle{empty}

\begin{tikzpicture}[set style={{help lines}+=[dashed]}]
\draw[style=help lines] (0,0) grid +(12,12);
\draw (4,11) grid +(1,1);
\draw (6,10) grid +(1,1);
\draw (4,10) grid +(1,1);
%—–
\draw (4,9) grid +(1,1);
\draw (6,9) grid +(1,1);
%—–
\draw (6,8) grid +(1,1);
\draw (4,8) grid +(1,1);
%
\draw (4,7) grid +(1,1);
\draw (6,7) grid +(1,1);
%
\draw (6,6) grid +(1,1);
\draw (4,6) grid +(1,1);
%
\draw (4,5) grid +(1,1);
\draw (6,5) grid +(1,1);
%
\draw (6,4) grid +(1,1);
\draw (4,4) grid +(1,1);
%
\draw (4,3) grid +(1,1);
\draw (6,3) grid +(1,1);

%——————————————————
% red1
\draw [red,very thick,->] (5,11.2) — (6,10.8);
\draw [red,thick, ->] (5.25,10.5) — (5,10.5);
\draw [red,thick, ->] (6,10.5) — (5.75,10.5);
\draw (5.5,10.5) circle (0.2);
\draw [red,thick, ->] (4.5,10.2) — (4.5,9.8);
% blue1
\draw [blue,very thick,->] (6,10.2) — (5,9.8);
\draw [blue,thick,->] (5.75,9.5) — (6,9.5);
\draw [blue,thick,->] (5,9.5) — (5.25,9.5);
\draw (5.5,9.5) circle (0.2);
\draw [blue,thick, ->] (6.5,9.2) — (6.5,8.8);
%—————–
% red2
\draw [red,very thick,->] (5,9.2) — (6,8.8);
\draw [red,thick, ->] (5.25,8.5) — (5,8.5);
\draw [red,thick, ->] (6,8.5) — (5.75,8.5);
\draw (5.5,8.5) circle (0.2);
\draw [red,thick, ->] (4.5,8.2) — (4.5,7.8);
% blue2
\draw [blue,very thick,->] (6,8.2) — (5,7.8);
\draw [blue,thick,->] (5.75,7.5) — (6,7.5);
\draw [blue,thick,->] (5,7.5) — (5.25,7.5);
\draw (5.5,7.5) circle (0.2);
\draw [blue,thick, ->] (6.5,7.2) — (6.5,6.8);
%—————–
% red3
\draw [red,very thick,->] (5,7.2) — (6,6.8);
\draw [red,thick, ->] (5.25,6.5) — (5,6.5);
\draw [red,thick, ->] (6,6.5) — (5.75,6.5);
\draw (5.5,6.5) circle (0.2);
\draw [red,thick, ->] (4.5,6.2) — (4.5,5.8);

% ——– Fill numbers ———–
\node at (4.5,11.5) {2993};
\node at (6.5,10.5) {1095};
\node at (5.5,10.5) {2};
\node at (4.5,10.5) {2190};
%—
\node at (6.5,9.5) {803};
\node at (5.5,9.5) {1};
\node at (4.5,9.5) {803};
%—
\node at (6.5,8.5) {292};
\node at (5.5,8.5) {2};
\node at (4.5,8.5) {584};
%
\node at (4.5,7.5) {219};
\node at (5.5,7.5) {1};
\node at (6.5,7.5) {219};
%—
\node at (6.5,6.5) {73};
\node at (5.5,6.5) {3};
\node at (4.5,6.5) {219};
%
\node at (4.5,5.5) {0};

\end{tikzpicture}

\end{document}
`

@ ciandra. Quel riferimento l’ho preso dal big-manual di Tantau. Non ricordo la pagina, ma appena la trovo ne posto il numero.
Ciao
Till Tantau: The TikZ and PGF manual, pagina 81 (su 405), Edizione June 2007

lifetime” post=77427Questo nuovo schema mi sembra … migliore!
`
% ——– eucl3.tex (Set.12)———–
% Esempio minimale del pacchetto tikz
%————————————
\documentclass{minimal}
\usepackage{tikz}

\begin{document}
\pagestyle{empty}

\begin{tikzpicture}[set style={{help lines}+=[dashed]}]
\draw[style=help lines] (0,0) grid +(12,12);
\draw (4,11) grid +(1,1);
\draw (6,10) grid +(1,1);
\draw (4,10) grid +(1,1);
%—–
\draw (4,9) grid +(1,1);
\draw (6,9) grid +(1,1);
%—–
\draw (6,8) grid +(1,1);
\draw (4,8) grid +(1,1);
%
\draw (4,7) grid +(1,1);
\draw (6,7) grid +(1,1);
%
\draw (6,6) grid +(1,1);
\draw (4,6) grid +(1,1);
%
\draw (4,5) grid +(1,1);
\draw (6,5) grid +(1,1);
%
\draw (6,4) grid +(1,1);
\draw (4,4) grid +(1,1);
%
\draw (4,3) grid +(1,1);
\draw (6,3) grid +(1,1);

%——————————————————
% red1
\draw [red,very thick,->] (5,11.2) — (6,10.8);
\draw [red,thick, ->] (5.25,10.5) — (5,10.5);
\draw [red,thick, ->] (6,10.5) — (5.75,10.5);
\draw (5.5,10.5) circle (0.2);
\draw [red,thick, ->] (4.5,10.2) — (4.5,9.8);
% blue1
\draw [blue,very thick,->] (6,10.2) — (5,9.8);
\draw [blue,thick,->] (5.75,9.5) — (6,9.5);
\draw [blue,thick,->] (5,9.5) — (5.25,9.5);
\draw (5.5,9.5) circle (0.2);
\draw [blue,thick, ->] (6.5,9.2) — (6.5,8.8);
%—————–
% red2
\draw [red,very thick,->] (5,9.2) — (6,8.8);
\draw [red,thick, ->] (5.25,8.5) — (5,8.5);
\draw [red,thick, ->] (6,8.5) — (5.75,8.5);
\draw (5.5,8.5) circle (0.2);
\draw [red,thick, ->] (4.5,8.2) — (4.5,7.8);
% blue2
\draw [blue,very thick,->] (6,8.2) — (5,7.8);
\draw [blue,thick,->] (5.75,7.5) — (6,7.5);
\draw [blue,thick,->] (5,7.5) — (5.25,7.5);
\draw (5.5,7.5) circle (0.2);
\draw [blue,thick, ->] (6.5,7.2) — (6.5,6.8);
%—————–
% red3
\draw [red,very thick,->] (5,7.2) — (6,6.8);
\draw [red,thick, ->] (5.25,6.5) — (5,6.5);
\draw [red,thick, ->] (6,6.5) — (5.75,6.5);
\draw (5.5,6.5) circle (0.2);
\draw [red,thick, ->] (4.5,6.2) — (4.5,5.8);

% ——– Fill numbers ———–
\node at (4.5,11.5) {2993};
\node at (6.5,10.5) {1095};
\node at (5.5,10.5) {2};
\node at (4.5,10.5) {2190};
%—
\node at (6.5,9.5) {803};
\node at (5.5,9.5) {1};
\node at (4.5,9.5) {803};
%—
\node at (6.5,8.5) {292};
\node at (5.5,8.5) {2};
\node at (4.5,8.5) {584};
%
\node at (4.5,7.5) {219};
\node at (5.5,7.5) {1};
\node at (6.5,7.5) {219};
%—
\node at (6.5,6.5) {73};
\node at (5.5,6.5) {3};
\node at (4.5,6.5) {219};
%
\node at (4.5,5.5) {0};

\end{tikzpicture}

\end{document}
`

@ ciandra. Quel riferimento l’ho preso dal big-manual di Tantau. Non ricordo la pagina, ma appena la trovo ne posto il numero.
Ciao
Till Tantau: The TikZ and PGF manual, pagina 81 (su 405), Edizione June 2007

😮 Accipicchia… direi che è un po’ datato. 🙂 L’ultima versione, aprile 2012, ha 905 pagine ❗

Infatti nel tuo codice anche la sintassi [tt]\draw(6,6) grid +(1,1);[/tt] per disegnare un semplice rettangolo mi sembrava strana (interessante, ma strana). Con la stessa filosofia di base, io avrei usato [tt]\draw(6,6) rectangle ++(1,1);[/tt].

Ciao
Claudio