Visualizza il feed RSS

Titolo provvisorio...

Il triangolo no...

Valuta questo inserimento
di pubblicato il 29-12-2011 alle 16:41 (6234 Visite)
Il titolo si rifà alla mia istintiva risposta di fronte all'ennesima richiesta di spiegazioni e informazioni sul triangolo di Floyd: in questo caso, da parte di una giovane studentessa, la cui immaginazione è rimasta evidentemente colpita dall'assegnazione dell'arciclassico esercizio in linguaggio C per la stampa di tale triangolo numerico, accompagnata da spiegazioni alquanto scarne.

Per la cronaca, sulle prime la fanciulla non è stata in grado di cogliere la citazione dal brano di un noto cantautore italiano, in quanto rea di esser nata un paio di decenni troppo tardi...

Chiaramente questa entry è dedicata ad un argomento elementare e quindi destinata agli esordienti, sebbene probabilmente a nessun informatico quadratico medio farà male un buon ripasso sulle innumerevoli proprietà dei numeri notevoli qui coinvolti, in grado di attirare l'attenzione di alcuni dei giganti nella storia della matematica, e anche recentemente protagonisti di tanta divulgazione d'altissima qualità (es. Gardner, Conway etc.).

Il famigerato triangolo di Floyd, situato nei pressi delle torri di Hanoi, non lontano dal più famoso triangolo di Pascal-Tartaglia, è invero uno dei primissimi pontes asinorum che costellano il cammino degli studenti d'informatica.
In rete sono ovviamente disponibili sorgenti di ogni genere nei linguaggi più improbabili, quasi sempre errati o fuorvianti nonostante l'assoluta puerilità del problema.

Il buon Robert Floyd, scomparso nel 2001 e già vincitore del Turing Award, è noto soprattutto per la sua lunghissima collaborazione con Donald E. Knuth, tanto che il suo nome è citato in quasi tutte le opere di quest'ultimo. Molti sono i suoi meriti scientifici (a partire dall'algoritmo di Floyd-Warshall per i cammini minimi e dai suoi contributi seminali alla logica di Hoare), ma naturalmente gli studenti lo incontrano per la prima volta soprattutto grazie ad un modo peculiare di scrivere per esteso un numero triangolare:

Formula LaTeX: \begin{array}{rrrrr}{\color{Emerald} 1} &  &  &  & \\{\color{Red} 2} & {\color{Blue} 3} &  &  & \\ {\color{Red} 4} & 5 & {\color{Blue} 6} &  & \\ {\color{Red} 7} & 8 & 9 & {\color{Blue} 10} & \\ {\color{Red} 11} & 12 & 13 & 14 & {\color{Blue} 15}\end{array}

Per mera pedanteria, desidero ricordare (una e una sola volta) che nel presente contesto, come quasi sempre nella matematica discreta - salvo diversa esplicita specificazione, l'unico "universo" numerico che ci interessa è quello dei naturali, ovvero numeri interi non negativi:

Formula LaTeX: \mathbb{N}=\{0,1,2,3,\dots \},\ \ |\mathbb{N}|=\aleph_0

Nel seguito si dà pressoché ovunque per scontata tale assunzione, per amor di brevità.

La disposizione sopra esemplificata è detta triangolo di Floyd. Tale triangolo è evidentemente costruito come segue: partendo dall'unità, che da sola occupa la prima riga, si scrivono in sequenza (dall'alto verso il basso, e da sinistra verso destra) tutti gli interi positivi successivi in maniera strettamente crescente, in modo tale che ogni riga contenga un numero in più della precedente. Pertanto la prima riga contiene un numero, la seconda due, la terza tre... l'n-esima e ultima contiene ovviamente n numeri.

I numeri allineati a sinistra (1, 2, 4, 7, 11... riportati in rosso nello schema) formano la successione crescente del "ristoratore pigro" o "pizza slicing", così detta a causa della sua principale interpretazione combinatoria di origine geometrica - si tratta infatti del numero massimo di parti ottenibili "affettando" un cerchio con n tagli.
Per contro, i numeri situati a destra (1, 3, 6, 10, 15... riportati in blu nello schema) ossia al termine di ogni singola riga formano (non molto sorprendentemente) la successione parimenti crescente dei numeri triangolari, ossia numeri figurati che qui ci fa comodo definire pari alla somma dei primi n numeri naturali. Tali numeri sono quindi il corrispondente additivo del fattoriale, definito come prodotto di tutti i primi n interi positivi.

Risulta molto evidente ed intuitiva, nella disposizione figurata, la strettissima correlazione tra queste due sequenze, totalmente imperniata sulla formula di Gauss per la sommatoria dei primi n interi positivi.

Formula LaTeX: (1)\ \ 1\,+\,2\,+\cdots+\,n-1\,+\,n\;=\;\sum_{k=1}^{n}{k}\;=\;\frac{n(n+1)}{2}

Partiamo quindi proprio da codesta forma chiusa che consente di ricavare immediatamente l'n-esimo numero della successione data. Sebbene in letteratura la notazione Ln o L(n) venga sovente impiegata per indicare i numeri di Lucas, qui mi prendo la libertà di usare arbitrariamente il simbolo: siano dunque Tn l'n-esimo numero triangolare e Ln il numero n-esimo della successione "pizza slicing" (detta anche dei numeri poligonali centrali), per ogni n naturale:

Formula LaTeX: (2)\ \ T_n\;=\;\sum_{k=0}^{n}{k}\; = \;\frac{n(n+1)}{2}\; = \;\binom{n+1}{2}\; = \;0,\;1,\;3,\;6,\;\dots

Formula LaTeX: (3)\ \ L_n\;= \;1+\frac{n(n+1)}{2}\; =\;1 + T_{n}\; = \;1,\;2,\;4,\;7,\;\dots

Dato il tono smaccatamente didascalico della entry, ricordo esplicitamente che sebbene in letteratura (specialmente nella manualistica di base) la successione dei numeri triangolari parta convenzionalmente da 1 per motivi squisitamente geometrici e di visualizzazione, è sempre possibile (e sensata, per i nostri fini) l'inclusione dello zero come primo elemento di tale successione, in modo tale che T0 = 0.
Tale utile convenzione giustifica in modo immediato la formula di correlazione con i numeri Ln e la relativa manipolazione a livello di programma.

Osservando il triangolo, si scoprono facilmente numerose proprietà la cui dimostrazione algebrica è decisamente immediata, a livello di biennio delle scuole medie superiori.
Mi compiaccio per stavolta di indulgere su taluni di questi dettagli, mostrando in modo esplicito e pedissequo i semplici passaggi ai fini della chiarezza, a rischio di apparire banale e inutilmente pedante. Infatti è in costante aumento la richiesta di spiegazioni da parte di giovani studenti, anche in ordine ai passaggi algebrici più banali ed intuitivi, troppo spesso omessi e dati per scontati in altre sedi.

Ad esempio, consideriamo la generica coppia di numeri triangolari consecutivi (Tn, Tn+1) in modo tale che n sia pari. Si mostra facilmente che codesti numeri così scelti, per qualsiasi n pari, sono sempre ordinatamente multipli di n + 1 ovvero della posizione dispari occupata dal maggiore di essi - contando conformemente alla nostra convenzione posizionale.

Vale la pena di sottolineare anche che lo zero viene normalmente considerato il primo numero pari, per implicita convenzione, nell'universo della matematica discreta.
Infatti, sebbene ad intere generazioni di studenti sia stato erroneamente insegnato il contrario, basandosi sostanzialmente sulle definizioni euclidee, oggi fortunatamente anche nella didattica di base prevale l'orientamento computazionale e costruttivo. Dunque la definizione di numero pari, dall'euclideo "divisibile in due parti", è stata finalmente sostituita da "multiplo del due": una apparentemente insignificante sfumatura, dalla quale invece consegue che lo zero è il primo numero pari - oltre ad essere multiplo di qualsiasi altro naturale, peraltro l'unico possibile multiplo intero minore del valore di partenza, ciò che per secoli ha sbigottito gli occidentali ed ha lasciato una lunga coda di riluttanza didattica, che solo in questi anni può dirsi definitivamente superata. Dal punto di vista computazionale, lo zero (es. in un registro della CPU) si comporta come un qualsiasi altro numero pari, in quanto (anche) il bit meno significativo della sua rappresentazione è comunque nullo, e questo chiude la questione per il lato applicativo.

Dunque la norma appena enunciata vale, senza modifiche, anche quando si abbia n = 0, che rientra - in base a quanto sopra esposto - nel caso di "n pari".
Segue un più completo esempio:

Formula LaTeX: \begin{array}{lll}\\T_2\;=\;3, & T_{\color{Red} 3}\;=\;6 & {\color{Red} 3}|3 \text{ e } {\color{Red} 3}|6\\T_4\;=\;10, & T_{\color{Red} 5}\;=\;15 & {\color{Red} 5}|10 \text{ e } {\color{Red} 5}|15\\T_6\;=\;21, & T_{\color{Red} 7}\;=\;28 & {\color{Red} 7}|21 \text{ e } {\color{Red} 7}|28\end{array}

Come ben noto, il simbolismo b|a indica che b è un divisore di a. Ricordiamo anche che, quando n è un intero positivo pari, esiste sempre un altro distinto naturale m < n tale che n = 2m. Per quanto richiamato sopra, si ha come caso limite n = m = 0, comunque accettabile senza restrizioni perché nei passaggi che seguono le sostituzioni avvengono unicamente al numeratore.
Più in generale, si ha quindi, con una banale sostituzione:

Formula LaTeX: \frac{T_n}{n+1}\; = \;\frac{n(n+1)}{2(n+1)}\; = \;\frac{n}{2}\; = \;\frac{2m}{2}\; = \;m

Mentre per il successivo, n+1, si ha:

Formula LaTeX: \frac{T_{n+1}}{n+1}\; = \;\frac{(n+1)(n+2)}{2(n+1)}\; = \;\frac{n+2}{2}\; = \;\frac{2m+2}{2}\; = \; m+1

Ne risulta pertanto, con estrema chiarezza, che il numero dispari n+1 divide sia Tn che il suo successore Tn+1.

Osservando i risultati, si ha inoltre che i due multipli di n+1 così determinati sono strettamente consecutivi, il che spalanca le porte alla successiva considerazione: la differenza tra due numeri triangolari successivi, diciamo ancora di posizione n ed n+1 per comodità, è sempre pari ad n+1.

Formula LaTeX: (4)\ \ T_{n+1}\;=\;T_n\,+\,n\,+\,1\ \ \ \text{per ogni } n \in \mathbb{N}

La dimostrazione è decisamente puerile:

Formula LaTeX: \begin{align*}T_{n+1}-T_n&=\frac{(n+1)[(n+1)+1]}{2}-\frac{n(n+1)}{2}\\&=\frac{(n+1)[(n+2)-n]}{2}\\&=\frac{2(n+1)}{2}\\&=n+1\end{align*}

Stante la relazione esistente tra i numeri triangolari e la successione "pizza slicing", il lemma appena dimostrato si applica parimenti a quest'ultima successione: la differenza tra due numeri poligonali centrali consecutivi, rispettivamente di posizione n ed n+1, è pari ad n+1. Tale proprietà trova peraltro immediata applicazione nel sorgente C proposto di seguito.

Formula LaTeX: (5)\ \ L_{n+1}\;=\;L_n\,+\,n\,+\,1\ \ \ \text{per ogni } n \in \mathbb{N}

D'altro canto, in un contesto appena più formale, avremmo potuto e voluto definire subito le due successioni in termini strettamente ricorsivi, dai quali è perfino più immediato ricavare per altra via alcune delle proprietà appena viste:

Formula LaTeX: (6)\ \ T_n\;=\;\begin{cases}0 & \text{ per } n\;=\;0 \\ T_{n-1}\;+\;n & \text{ per } n\; \geq \;1 \end{cases}

Formula LaTeX: (7)\ \ L_n\;=\;\begin{cases}1 & \text{ per } n\;=\;0 \\ L_{n-1}\;+\;n & \text{ per } n\; \geq \;1 \end{cases}

Una tale scrittura rende - se possibile - ancor più scolasticamente chiara la comodità di includere T0 = 0 al fine di avere sempre e senza eccezioni, con omogeneità di indici, Ln = Tn + 1.

Tuttavia, qualcosa di ben più sorprendente e interessante si scopre considerando la somma di due numeri triangolari consecutivi qualsivoglia:

Formula LaTeX: \begin{align*}(8)\ \ T_n+T_{n+1} &= \frac{n(n+1)}{2}+\frac{(n+1)(n+2)}{2}\\ &= \frac{(n+1)(2n+2)}{2}\\ &= \frac{2(n+1)(n+1)}{2}\\ &= (n+1)^2\ \ \ \text{per ogni } n \in \mathbb{N}\end{align*}

Si ha dunque, in qualsiasi condizione, un quadrato perfetto!
Di questo fatto è peraltro possibile produrre anche una meravigliosa dimostrazione grafica, usando la tipica notazione triangolare che contraddistingue questi numeri.

Potremmo proseguire molto a lungo elencando le affascinanti proprietà combinatorie dei numeri notevoli qui trattati, che si ritrovano in numerosissime situazioni fondamentali in matematica discreta. Temo però che parlare diffusamente di matrici di Hessenberg, nave di Euler (strettamente connessa sia ai numeri pentagonali che alle partizioni di un naturale) e trasformate di Narayana confligga con la volontà di mantenere strettamente elementare la trattazione. Gli interessati trovano comunque ampissimo materiale di riscontro nei link disseminati, more solito, nel testo e naturalmente sono invitati a richiedere esplicitamente lumi.

Passo quindi, seppure malvolentieri, a ricordare che il triangolo di Floyd, nonostante le sue innumerevoli implicazioni con la teoria dei numeri figurati e oltre, è utilizzato nella didattica elementare soprattutto come scusa per un semplicissimo esercizio di programmazione.

Per rendere tale esercizio un po' meno banale e noioso, propongo un breve sorgente C destinato a stampare triangoli di Floyd a rovescio, sempre allineati a sinistra ma partendo dall'ultima riga. Questo rende un po' meno primitivo il codice, e costringe lo studente a prendere almeno un minimo di confidenza con le proprietà più elementari dei numeri triangolari e poligonali centrali.

/*
** Programma per la stampa del triangolo di Floyd.
** Il triangolo viene rovesciato, quindi con R righe il primo
** numero in angolo superiore sinistro e' l'R-esimo nella 
** successione "Lazy Caterer", ossia il corrispondente  
** numero triangolare aumentato di una unita'. 
*/

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/* Numero di righe del triangolo desiderato */
#define MAX_ROWS   13

/* Limite arbitrario per il buffer della itoa() */
#define MAX_DIGITS 16

/* 
** Restituisce l'ennesimo numero "pigro", entro 
** i limiti di un unsigned int. 
*/
unsigned int LazyCaterer(unsigned int n)
{
	return (unsigned int)(1+(n*(n+1)/2));
}

int main()
{
    unsigned int i, st, k;
    size_t len; 
    char buff[MAX_DIGITS];

    i = MAX_ROWS;
    
    st = LazyCaterer(i -1);
    
    /* 
    ** Si calcola banalmente il logaritmo discreto del valor massimo, 
    ** per dimensionare l'ampiezza di ogni numero mostrato.
    */
    itoa(st + i, buff, 10);
    len = strlen(buff);
    
    printf("Triangolo di Floyd inverso, con %d righe "
           "(%d cifre per cella):\n\n", i, len);
    
    while (i > 0)
    {
        for (k = 0; k < i; k++)
        {
            printf("%*d ", len, (st + k));
        }
        puts("");
        --i;
        st -= i;
    }
}
Ecco uno snapshot del relativo output:

Y:\>RFloyd.exe
Triangolo di Floyd inverso, con 13 righe (2 cifre per cella):

79 80 81 82 83 84 85 86 87 88 89 90 91
67 68 69 70 71 72 73 74 75 76 77 78
56 57 58 59 60 61 62 63 64 65 66
46 47 48 49 50 51 52 53 54 55
37 38 39 40 41 42 43 44 45
29 30 31 32 33 34 35 36
22 23 24 25 26 27 28
16 17 18 19 20 21
11 12 13 14 15
 7  8  9 10
 4  5  6
 2  3
 1

Y:\>
Il codice è sostanzialmente autoillustrante.
La dimensione del triangolo è artificiosamente fissata a tempo di compilazione, tramite una semplice #define, ma il codice è predisposto per assegnare a runtime tale valore alla variabile di induzione del loop principale.
Si tratta chiaramente di un invito: non vedo infatti modo migliore per concludere questa entry, se non l'immancabile l'accettazione e convalida della dimensione desiderata per il triangolo tramite input utente è lasciata come semplice esercizio per il lettore interessato...

Naturalmente, la soluzione in J è decisamente più concisa:
   floyd=: [: rplc&(' 0';'  ')"1@":@(* $ $ +/\@,) >:/~@:i.
   floyd 7 
 1                  
 2  3               
 4  5  6            
 7  8  9 10         
11 12 13 14 15      
16 17 18 19 20 21   
22 23 24 25 26 27 28

Alcuni link (già riportati nel testo):
Formula di Gauss e relativo aneddoto
Numeri triangolari
Numeri poligonali centrali
Succinta biografia di Robert Floyd

aggiornamento da 03-12-2015 a 15:00 di M.A.W. 1968

Categorie
Programmazione , Scienza

Commenti