Andrea Pannitti Blog

Scambio di due variabili senza la variabile di appoggio

2011-01-05T00:55:00.000-08:00

Il metodo classico per lo scambio di due variabili, denotiamole con a e b, prevede l'utilizzo di una terza variabile di appoggio, chiamiamola c, e consiste, sostanzialmente, nell'eseguire in successione le seguenti assegnazioni:

c = a

a = b

b = c

In questo topic, sarà mostrato un metodo alternativo che effettuerà il suddetto scambio senza l'utilizzo della terza variable di appoggio c.

L'idea di tale metodo per variabili numeriche è da attribuirsi al caro amico Giovanni Valentino ed è stato poi, successivamente, da me esteso al caso alfanumerico. Nel prosieguo, quindi, distingueremo i due casi analizzandoli separatamente.

Caso numerico

Dette a e b le variabili numeriche da scambiare, possiamo effettuare lo scambio effettuando in successione le seguenti operazioni:

a = a + b

b = a - b

a = a - b

Come si potrà verificare, tale metodo funziona correttamente per qualsiasi valore numerico che si attribuisce alle variabili a e b.

Passiamo quindi ad esaminare il caso alfanumerico.

Caso alfanumerico

Per esaminare tale caso, al fine di aumentare la chiarezza espositiva e la comprensione in termini pratici dello stesso, faremo riferimento alla sintassi di uno specifico linguaggio di programmazione, sebbene il procedimento possa essere applicato utilizzando qualsiasi altro linguaggio.

Per quanto detto, la sintassi che utilizzeremo è quella del linguaggio Java.

Le operazioni da eseguire, ricalcano le orme del caso numerico e si discostano da questo solo per alcuni dettagli.

Più precisamente, dette a e b le variabili alfanumeriche da scambiare, le operazioni da compiere sono le seguenti:

a = a + b;

// b = a.substring(0, 0 + a.length() - b.length()); Equivale a:

b = a.substring(0, a.length() - b.length());

//a = a.substring(b.length(), b.length() + a.length() - b.length()); Equivale a:

//a = a.substring(b.length(), a.length()); Equivale a:

a = a.substring(b.length());

Anche in questo caso, si potrà facilmente constatare, che il metodo funziona per qualsiasi stringa attribuita alle variabili a e b.

Concludiamo tale topic, osservando che: sebbene il metodo illustrato ottimizza l'utilizzo dello spazio di memoria, esso ha, come rovescio della medaglia, l'aumento del tempo computazionale dovuto alle operazioni che devono essere eseguite.

In definitiva, il suddetto metodo, è equivalente a quello tradizionale e la scelta dell'uno o dell'altro, dipende esclusivamente dal tipo di ottimizzazione che si desidera: più spazio e meno tempo nel caso tradizionale, meno spazio e più tempo per il metodo illustrato. Ovviamente, però, essendo tali ottimizzazioni veramente minime, soprattutto in considerazione della potenza raggiunta dagli attuali computers, la scelta del metodo, in realtà, dipende da fattori dovuti esclusivamente al gusto personale.

Algoritmo per la generazione di un calendario di calcio

2009-05-22T00:40:00.000-07:00

In questo topic illustrerò un algoritmo, sin'ora inedito, per la generazione di un calendario di calcio.

L'ideatore di tale algoritmo è Giuseppe Di Falco, un bravo professore di matematica dell'ITC che ho frequentato negli anni ottanta.

Prima di passare alla descrizione vera e propria dell'algoritmo, cercherò di spiegare meglio qual'è il problema che si intende risolvere.

Dato un numero n di squadre, si desidera visualizzare un calendario, suddiviso in n giornate, in cui ciascuna delle n squadre incontra una ed una sola volta tutte le altre.

Ogni giornata sarà costituita da n/2 partite e, nel caso in cui n sia dispari, una squadra riposerà.

Al termine del girone, costituito dall'insieme delle giornate, tutte le squadre dovranno aver sfidato una ed una sola volta tutte le altre ed inoltre, sempre nel caso che il numero di squadre sia dispari, tutte dovranno aver riposato una ed una sola volta.

Ovviamente, il nome delle squadre non è importante: potremo riferirci a ciascuna di esse identificandole con un numero compreso tra 1 e n.

A questo punto, vediamo come funziona l'algoritmo in questione, riferendoci, per fissare le idee, ad un caso specifico.

Per comodità, prendiamo in esame prima il caso in cui n è dispari; quindi, a titolo di esempio, supponiamo n=5.

Scriviamo in verticale i nomi (nel nostro caso, come abbiamo detto, le identifichiamo con numeri) delle squadre:

1
2
3
4
5

Immaginando la suddetta lista come una "striscia" pieghevole, la spezziamo in due "ruotando" in senso antiorario la seconda metà in modo tale che essa assuma la seguente forma:

5
14
23

Quella che abbiamo ottenuto costituisce la prima giornata del calendario: la prima squadra gioca contro la quarta, la seconda contro la terza e la quinta riposa.

Ora, tenendo fissa la forma della nostra stricia, facciamo "slittare" in senso antiorario i nomi delle squadre che la compongono.
Così facendo, essa assumerà la seguente conformazione:

4
53
12

Questa costituisce la seconda giornata del nostro calendario.

Ripetendo tale operazione altre n-2 volte otterremo il girone di "andata" del nostro calendario. Non sarà necessario generare il girone di "ritorno" in quanto esso è identico a quello di andata con il solo scambio dei ruoli tra le squadre che giocano "in casa" e quelle che giocano "fuori casa".

In definitiva, quindi, l'output che otterremo sarà il seguente:

Giornata 1:
1 - 4
2 - 3
Riposa la squadra: 5

Giornata 2:
5 - 3
1 - 2
Riposa la squadra: 4

Giornata 3:
4 - 2
5 - 1
Riposa la squadra: 3

Giornata 4:
3 - 1
4 - 5
Riposa la squadra: 2

Giornata 5:
2 - 5
3 - 4
Riposa la squadra: 1

A questo punto, dovremmo esaminare il caso in cui n è pari. Possiamo notare, però, che se "fissiamo" l'ultima squadra, facendola giocare con la squadra che dovrebbe riposare nel caso n-1, otterremmo in modo del tutto automatico proprio il calendario che desideriamo.

Allora, per fissare le idee, supponiamo n=6. Per quanto detto, il calendario che otterremo sarà il seguente:

Giornata 1:
6 - 5
1 - 4
2 - 3

Giornata 2:
6 - 4
5 - 3
1 - 2

Giornata 3:
6 - 3
4 - 2
5 - 1

Giornata 4:
6 - 2
3 - 1
4 - 5

Giornata 5:
6 - 1
2 - 5
3 - 4

Ovviamente, in ogni caso, il numero totale delle giornate (del solo girone di andata), sarà: n - 1 + (n%2).

Per finire, vediamo un'implementazione in Java, rilasciata sotto Licenza GPL 3, come tutto il codice del software presente in questo blog, del suddetto algoritmo.

/**

* @author Andrea Pannitti

public class CalendarioDiCalcio {

/**

* @param args

public static void main(String[] args) {

int n;

//Controllo sul parametro di input

try {

n=Integer.parseInt(args[0]);

if (n<1 || n>99) {

System.out.println("Attenzione: il parametro di input deve essere un numero intero compreso tra 1 e 99!");

return;

}

catch (Exception e) {

System.out.println("Attenzione: il parametro di input deve essere un numero intero compreso tra 1 e 99!");

return;

}

//Inizializzazione della stringa delle squadre

String StringaSquadre = "";

for (int i=1; i<=n; i++)

StringaSquadre+=(" " + String.valueOf(i)).substring((" " + String.valueOf(i)).length()-2);

//Genera il calendario

for (int i=1; i<=n-1+(n%2); i++) {

System.out.println("Giornata " + i +":");

if (n%2==0)

System.out.println(StringaSquadre.substring((n - 1)* 2) + " - " + StringaSquadre.substring((n - 2) * 2, (n - 1) * 2));

for (int j=0; j<(int)((n-1)/2); j++) {

System.out.println(StringaSquadre.substring(j * 2, (j + 1)* 2) + " - " + StringaSquadre.substring((n - j - 3 + (n%2)) * 2, (n - j - 2 + (n%2)) * 2));

}

if (n%2==1)

System.out.println("Riposa la squadra: " + StringaSquadre.substring((n - 1) * 2));

//Ruota la stringa delle squadre

StringaSquadre = StringaSquadre.substring((n - 2 + (n%2)) * 2, (n - 1 + (n%2)) * 2) + StringaSquadre;

StringaSquadre = StringaSquadre.substring(0, (n - 1 + (n%2)) * 2) + StringaSquadre.substring(n * 2, (n + 1 - (n%2)) * 2);

System.out.println();

}

CRC Reverser Java Version

2008-01-26T10:11:00.000-08:00

In una sfida di un gioco da Hackers a cui partecipo, il problema da risolvere era trovare una parola chiave a partire dal suo codice hash CRC32.
Allora, cercando su Internet, ho trovato un interessante blog di Bas Westerbaan. Da tale blog è possibile scaricare un programma scritto in python che trova tutte le parole che hanno un determinato codice hash CRC32.
Con questo programma ho risolto il mio problema... ma ora la prossima sfida per me era di tradurre tale programma da Python in Java, il mio linguaggio di programmazione preferito insieme a C# e Visual Basic.
Così, ho appreso le basi del linguaggio python ed ho tradotto tale programma.

Potete scaricare la versione Java di tale programma da qui.

Questo programma, come quello di Bas Westerbaan, è rilasciato sotto licenza GPL 2.

Come Usare il programma: java CrcReverser hash (in decimale o esadecimale con h prefisso, senza hash viene inizializzato automaticamente con 4157704578).

Esempio: java CrcReverser 4157704578 oppure java CrcReverser hf7d18982

Aggiornamento: Potete scaricare la nuova versione con interfaccia utente grafica da qui. Il codice sorgente è qui.

English
In a Hacker's Game challenge which I play, the problem to solve was to find a keyword from its CRC32 hash code.
Then, looking on the Internet, I found an interesting blog of Bas Westerbaan. From this blog is possible to download a program written in python that finds all the words with a specifc CRC32 hash code.
With this program I solved my problem... but now the next challenge for me was to translate this program from Python to Java, my favorite programming language with C# and Visual Basic.
So, I learned the basics of python language and I translated this program.

You can download the Java version of this program from here.

This program, like that of Bas Westerbaan, is released under GPL 2 license.

How to use the program: java CrcReverser hash (in decimal or hexadecimal with h prefix, without hash the default is 4157704578).

Exemple: java CrcReverser 4157704578 or java CrcReverser hf7d18982

Update: You can download the new version with GUI from here. The source code is here.

Algoritmo per lo sviluppo di sistemi integrali per il Totocalcio

2006-05-07T07:31:00.000-07:00

Questo è il mio primo blog.

L'idea di questo post nasce da una passione innata che ho per la matematica applicata ai giochi a pronostico, come il Totocalcio, il Superenalotto o il Lotto.

Di seguito proporrò un algoritmo che ho concepito per lo sviluppo di un sistema integrale per il totocalcio.

Allora, vediamo come funziona l'algoritmo anzidetto.

Fondamentalmente si tratta, definito il pronostico, di determinare in modo diretto qual'è la i-esima colonna dello sviluppo integrale.

Come Fare?

L'idea è quella di sfruttare la matematica relativa ai cambiamenti di base: la stessa che si utilizza quando si vuole passare dal sistema di numerazione decimale a quello binario, ottale, esadecimale o qualsiasi altro.

Perchè ciò?

Per spiegarlo consideriamo un semplice sistema di 3 doppie:

1x
1x
1x

Lo sviluppo di tale sistema è il seguente:

1111xxxx
11xx11xx
1x1x1x1x

Cosa accadrebbe se trasformassimo gli 1 in 0 e le x in 1?
Lo sviluppo assumerebbe la seguente forma:

00001111
00110011
01010101

Leggendo in verticale le colonne, come numeri binari, ci accorgeremmo che, nel sistema decimale, esse coincidono con i numeri:

01234567

Quindi, per determinare la i-esima colonna del sistema ci basta trasformare il numero decimale i-1 in binario e modificare gli zeri in uno e gli uno in x.

Quanto detto ci fa comprendere meglio il legame dello sviluppo del sistema (di sole doppie) con l'aritmetica binaria.

Quella illustrata, però, è la situazione più semplice in cui il pronostico è omogeneo e costituito da tutte doppie.

Ma cosa accadrebbe nel caso in cui il pronostico non fosse più costituito da sole doppie? Questa è sicuramente una complicazione in quanto desideriamo passare ad un sistema di numerazione che non è più a base omogenea ma bensì a base variabile.

Tale ostacolo, però, può essere facilmente superato seguendo l'algoritmo che andiamo di seguito a descrivere.

Per descrivere meglio tale algoritmo, ci riferiremo ancora una volta ad un esempio concreto.

Allo scopo, consideriamo il seguente sistema:

1
1x
1x2
1x

Lo sviluppo di tale sistema è il seguente:

111111111111
111111xxxxxx
11xx2211xx22
1x1x1x1x1x1x

000000000111
123456789012

Il sistema di numerazione in cui dovremmo trasformare i numeri (da 0 a 11) avrà la seguente base:

1232
(ogni posizione equivale alla lungezza del pronostico per quella posizione)

Supponiamo di voler individuare la sesta colonna (la numero 5 numerandole da 0 a 11) in tale sistema di numerazione.

Allora Procediamo nel seguente modo:

Dividiamo il numero della colonna che vogliamo determinare per l'ultimo elemento della base:

5:2=2 con resto 1

Dividiamo il risultato ottenuto per il penultimo elemento della base:

2:3=0 con resto 2

Dividiamo il risultato ottenuto per il secondo elemento della base:

0:2=0 con resto 0

Dividiamo il risultato ottenuto per il primo elemento della base:

0:1=0 con resto 0

Considerando all'inverso tali resti, otteniamo la colonna:

0021

Aggiungendo 1 ad ogni posizione si avrebbe:

1132

Da cui, sostituendo il rispettivo simbolo del pronostico, si ottiene la colonna:

112x

Quindi abbiamo visto che la funzione effettua la seguente trasformazione:

5 -> 0021

Equivalente a:

6 -> 112x

Denominando Dec2Col tale funzione, in Linguaggio C# essa può essere scritta nel seguente modo:

string Dec2Col(int NCol, string Base)

{
int NPartite = Base.Length;
string Col="";

NCol--;
for (int i=NPartite-1; i>=0; i--)
{
Col = Pronostico[i].Substring(NCol % Convert.ToInt32(Base.Substring(i,1)), 1) + Col;
NCol /= Convert.ToInt32(Base.Substring(i,1));
}

return Col;
}

Quindi, lo sviluppo completo del sistema può essere effettuato eseguendo un ciclo che ad ogni passo richiama la suddetta funzione e ne stampa il risultato, come mostrato dal seguente codice:

// Sviluppa il sistema
for (int i=1; i<=NCol; i++)

Console.WriteLine(Dec2Col(i, Base));

Aggiornamento

Vorrei far osservare che, tra i pregi di tale algoritmo, vi è indubbiamente quello della sua immediata parallelizzazione.

Inoltre, per dar seguito al commento di Claudio, riporto di seguito il codice d'esempio completo, rilasciato sotto Licenza GPL 3, che ho scritto in Visual Basic .NET:

Module Program

Dim Pronostico(13) As String

Sub Main()

Dim NCol As Long

Dim Base As String

Pronostico = new String(){"1", "1", "1x", "x", "1", "1", "1x2", "x", "1x2", "1", "x", "1", "1x", "1x2"}

NCol = 1 : Base = ""

For i=0 To Pronostico.Length - 1

NCol *= Pronostico(i).Length

Base += Pronostico(i).Length.ToString

Console.WriteLine("Colonne da sviluppare: " + NCol.ToString)

For i=1 To NCol

Console.WriteLine(Dec2Col(i, Base))

Console.Write("Premi un tasto per continuare . . . ")

Console.ReadKey(True)

End Sub

Function Dec2Col(NCol As Long, Base As String) as String

Dim NPartite As Integer = Base.Length

Dim Col As String = ""

NCol -= 1

For i = NPartite - 1 To 0 Step -1

Col = Mid(Pronostico(i), (NCol Mod Integer.Parse(Mid(Base, i + 1, 1))) + 1, 1) + Col

NCol = Int(NCol / (Integer.Parse(Mid(Base, i + 1, 1), 1)))

Return Col

End Function

End Module

Nonché, quello scritto in C#:

using System;

namespace TotoC

{

class Program

{

static String[] Pronostico;

public static void Main(string[] args) {

int NCol;

String Base = "";

Pronostico = new String[] {"1", "1", "1x", "x", "1", "1", "1x2", "x", "1x2", "1", "x", "1", "1x", "1x2"};

NCol = 1;

for (int i=0; i

NCol *= Pronostico[i].Length;

Base += Pronostico[i].Length;

}

Console.WriteLine("Colonne da sviluppare: " + NCol);

// Sviluppa il sistema

for (int i=1; i<=NCol; i++)

Console.WriteLine(Dec2Col(i, Base));

Console.Write("Premi un tasto per continuare . . . ");

Console.ReadKey(true);

}

public static String Dec2Col(int NCol, String Base) {

int NPartite = Base.Length;

String Col = "";

NCol--;

for (int i=NPartite-1; i>=0; i--)

{

Col = Pronostico[i].Substring(NCol % Convert.ToInt32(Base.Substring(i,1)), 1) + Col;

NCol /= Convert.ToInt32(Base.Substring(i,1));

}

return Col;

}

E quello in Java:

public class Toto {

static String[] Pronostico;

public static void main(String[] args) {

int NCol;

String Base = "";

Pronostico = new String[] {"1", "1", "1x", "x", "1", "1", "1x2", "x", "1x2", "1", "x", "1", "1x", "1x2"};

NCol = 1;

for (int i=0; i

NCol *= Pronostico[i].length();

Base += Pronostico[i].length();

}

System.out.println("Colonne da sviluppare: " + NCol);

// Sviluppa il sistema

for (int i=1; i<=NCol; i++)

System.out.println(Dec2Col(i, Base));

System.out.println("Premi un tasto per continuare . . . ");

}

public static String Dec2Col(int NCol, String Base) {

int NPartite = Base.length();

String Col = "";

NCol--;

for (int i=NPartite-1; i>=0; i--)

{

Col = Pronostico[i].substring(NCol % Integer.parseInt(Base.substring(i,i+1)), (NCol % Integer.parseInt(Base.substring(i,i+1)))+1) + Col;

NCol /= Integer.parseInt(Base.substring(i,i+1));

}

return Col;

}