Programmazione:Circoli viziosi

ovveroUn’eterna ghirlanda brillante

Eugenio Omodeo

Trieste, 21.04.2020

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Programmazione:Circoli viziosi

ovveroUn’eterna ghirlanda brillante

Eugenio Omodeo

Trieste, 21.04.2020

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Bello o conturbante ?

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Il paradosso del mentitore ( Epimenide di Creta, 600 a.C. )

Lettera di San Paolo a Tito I, 12-13:

“[11]A questi tali bisogna chiudere la bocca, perchemettono in scompiglio intere famiglie, insegnando peramore di un guadagno disonesto cose che non si devonoinsegnare. [12]Uno dei loro, proprio un loro profeta, giaaveva detto: �I Cretesi son sempre bugiardi, malebestie, ventri pigri�. [13]Questa testimonianza e vera.Percio correggili con fermezza,”

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Il paradosso del mentitore ( Epimenide di Creta, 600 a.C. )

Lettera di San Paolo a Tito I, 12-13:

“[11]A questi tali bisogna chiudere la bocca, perchemettono in scompiglio intere famiglie, insegnando peramore di un guadagno disonesto cose che non si devonoinsegnare. [12]Uno dei loro, proprio un loro profeta, giaaveva detto: �I Cretesi son sempre bugiardi, malebestie, ventri pigri�. [13]Questa testimonianza e vera.Percio correggili con fermezza,”

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Test ricorsivo di palindromicita1 in Java

private

public static boolean palindroma( String s ) {return s.length() 6 1 ||(

s.charAt( 0 ) == s.charAt( s.length() - 1 ) &&palindroma( s.substring( 1, s.length() - 1 ) )

);

}

La stringa vuota e le stringhe di lunghezza 1 sono il caso base. Seuna stringa non e vuota, richiediamo che abbia il primo carattereuguale all’ultimo e che, mutilata di questi due caratteri, rimangapalindroma.

1Esempi: “narici di Ciran”, “Avevi visioni d’un evo dove nudi noi si viveva”.

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Test ricorsivo di palindromicita1 in Java

privatepublic static boolean palindroma( String s ) {return s.length() 6 1 ||(

s.charAt( 0 ) == s.charAt( s.length() - 1 ) &&palindroma( s.substring( 1, s.length() - 1 ) )

);

}

La stringa vuota e le stringhe di lunghezza 1 sono il caso base. Seuna stringa non e vuota, richiediamo che abbia il primo carattereuguale all’ultimo e che, mutilata di questi due caratteri, rimangapalindroma.

1Esempi: “narici di Ciran”, “Avevi visioni d’un evo dove nudi noi si viveva”.

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Ricorsione mutua ( Es. istruzioni / espressioni )

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Ricorsione mutua, in Java

public static boolean pari( int p ) {assert p > 0;

return p == 0 || dispari( p - 1 );}

public static boolean dispari( int d ) {assert d > 0;

return d != 0 && pari( d - 1 );}

( Anche questi metodi andrebbero ‘privatizzati’ )

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Simulazione del test ricorsivo di disparita

L’esecuzione diSystem.out.println( dispari( 2 ) );

‘scatena’ le invocazioni

I dispari( 2 )

I pari( 1 )

I dispari( 0 )

che forniscono (da sotto in su) i risultati

I false

I false

I false ( questo verra stampato a video )

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Simulazione del test ricorsivo di parita

L’esecuzione diSystem.out.println( pari( 2 ) );

‘scatena’ le invocazioni

I pari( 2 )

I dispari( 1 )

I pari( 0 )

che forniscono (da sotto in su) i risultati

I true

I true

I true ( questo verra stampato a video )

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Due esercizi sulla ricorsione

I Implementate in modo ricorsivo il confronto lessicografico frastringhe.

I Implementate come metodo ricorsivo che abbia il suo casobase nei numeri primi la scomposizione dei numeri interinonnegativi come somme di quattro quadrati.

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Un esempietto liberamente riadattato da Peano

public static long fatt( int n ){

return ( n == 0 ) ? 1 : n * fatt( n - 1 );

}

Queste definizioni rigorose sono adottate nei trattatiscolastici del prof. Catania.

(Giuseppe Peano, “Le definizioni in matematica”, 1921)

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

Esempietto analogo: numeri di Fibonacci ( 1170–1240 ca. )

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

E poi i numeri del triangolo di Tartaglia ( 1499 ca.–1557 )

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

E poi i numeri del triangolo di Tartaglia ( 1499 ca.–1557 )

Il coefficiente binomiale(nk

)esprime in quanti modi

posso prelevare k elementi da un insieme di n elementi.

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante

E poi i numeri del triangolo di Tartaglia ( 1499 ca.–1557 )

Il coefficiente binomiale(nk

)esprime in quanti modi

posso prelevare k elementi da un insieme di n elementi.

Eugenio Omodeo Programmazione:Circoli viziosiovvero Un’eterna ghirlanda brillante