Sunday, May 07, 2006

Algoritmo per lo sviluppo di sistemi integrali per il Totocalcio


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


000000000111123456789012Il 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:

0021Aggiungendo 1 ad ogni posizione si avrebbe:

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

112xQuindi abbiamo visto che la funzione effettua la seguente trasformazione:

5 -> 0021Equivalente a:

6 -> 112xDenominando 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
Next
Console.WriteLine("Colonne da sviluppare: " + NCol.ToString)
For i=1 To NCol
Console.WriteLine(Dec2Col(i, Base))
Next
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)))
Next
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<Pronostico.Length; 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;
}
}
}




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<Pronostico.length; 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;
 }
}


Ed un elegante implementazione che ho scritto in Python:

numPartite = int(input('Quante partite? '))

p = []
nCol = 1
base = ''

for i in range(1, numPartite + 1):
    p.append(input('Partita n. ' + str(i) + ': '))
    nCol *= len(p[i-1])
    base += str(len(p[i-1]))

print('Colonne da sviluppare: ' + str(nCol))

def dec2col(p: list, nCol: int, base: str):
    nPartite = len(base)
    col = ''
    
    nCol -= 1
    for i in range(nPartite - 1, -1, -1):
        col = p[i][nCol % int(base[i:i+1])] + col
        nCol //= int(base[i:i+1])
    return col

for i in range(1, nCol + 1):
    print(dec2col(p, i, base))


9 Comments:

At 5:15 PM, Blogger Giovanni Conte said...

Non riesco a far funzionare l'algoritmo. Ad es. sostituendo il pronostico 2 ad 1, nella prima fissa, ritorna sempre 1.

 
At 2:56 AM, Anonymous Anonymous said...

Anche se è un post di qualche anno fa, spero possa darmi qualche dritta.
Nell'ottica di sviluppare un mio programma per il Superenalotto, mi sono imbattuto nel problema della riduzione. Il metodo di confrontare le colonne funziona ma non è sufficiente in quanto non è ottimizzato. Hai qualche suggerimento.

Ciao e grazie in anticipo,
Gianni

 
At 5:38 PM, Anonymous Anonymous said...

Ciao Andrea, complimenti per l'algoritmo che sviluppa un sistema.
Io l'ho fatto funzionare facendo un programma in V.B. e usando per provarlo lo stesso esempio che tu proponi. I guai sono cominciati appena ho dovuto fare un pronostico di 14 partite. NON MI FUNZIONA PIU' e non capisco dove sbaglio.
Il "C" non lo conosco e ho capito ben poco di quanto scrivi in questo linguaggio.
Potresti essere così gentile da rispondermi?
Se vuoi potrai scrivermi a : Clark_452000@yahoo.it

Grazie Claudio

 
At 7:23 AM, Anonymous Anonymous said...

interessante istruttivo ma con bug... i numeri di base da cui si deduce il binario o ternario (a seconda se é una doppia o una tripla) non possono essere sempre gli stessi ; cioe quelli che l'autore indica inizialmente con 0,1,2,3,4,5 ... dedotti dal sistema base esplicativo di 3 doppie. In buona sostanza dovrebbe essere intuitivo il fatto che ad ogni sistema in sviluppo non possono essere utilizzati numeri base che sono sempre gli stessi ..... ! se le 1 , x, 2 di colonna (variabile a seconda di come si imposta il sistema) si ricavano da un numero base che univocamente le determina il numero base deve essere variabile a seconda del sistema impostato !

1x - 111 xxx
1x2 - 1x2 1x2
-------------------
012 345

12 - 111 222
1x2 - 1x2 1x2
-------------------
012 345



si provi a dedurre l'ultima colonna dal valore 5 per il primo e secondo sistema : é impossibile .

E MAIL :
danilo.roncacci@inaassitalia.it

 
At 12:05 AM, Blogger Andrea Pannitti said...

Non c'è alcun bug; infatti, per rendertene conto, puoi effettuare la prova, ad esempio, modificando la riga del programma Java dove è definito il pronostico una volta con:

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

Ed una volta con:

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

In entrambi i casi vedrai che, compilando il programma, il sistema sviluppato è corretto!

Forse, quello che vuoi intendere, è che in entrambi i sistemi che hai proposto, l'ultima colonna è mappata, per entrambi, col valore 5 e a priori, senza conoscere il sistema a cui si riferisce, è impossibile dire a cosa corrisponde il valore 5 e ciò varrebbe anche per qualsiasi altro sistema il cui sviluppo è costituito da almeno sei colonne ma ciò non ha importanza in quanto l'algoritmo è studiato proprio per mappare le colonne di un sistema noto (ossia sai a priori se vuoi sviluppare il sistema {1x, 1x2} oppure {12, 1x2}) con la posizione che questa occupa nel suo sviluppo integrale; tant'è che, come puoi constatare, il codice dei programmi proposti funziona perfettamente!


Un saluto,
Andrea Pannitti

 
At 4:05 AM, Anonymous Anonymous said...

Andrea ... danilo ...... ma funziona si funziona ma il cambio di base numerica mi sorprende , cio si utilizza una base numerica fissa (edotta dal sistema di doppie quindi valori in binario ) poi hai mischiato scusa il termine oppure introdotto il cambio base e va bene ...calcolando la colonna i valori corrispondono l'ho anchi evinto. ma tu sai spiegare perche o percome ? ci sto provando ciao ?

 
At 10:06 AM, Blogger Unknown said...

Ciao Andrea.

Ho Provato in C assolutamente standard.
Ti posto il codice.
Ho usato

#define NP 13
char pron[NP][4]; // contiene "1X2" per 13 volte
char buffer[NP+1];

//---------------------------------------------------------------------------
void build(int n) {
int i;

for (i = 0; i < NP; i++) {
buffer[i] = pron[i][n%ln[i]];
n/=ln[i];
}
}

void Svil() {
int current;
for (current = 0; current < count; current++) {
build(current);
filtri();
}
}
//---------------------------------------------------------------------------

Spero che sia utile.

 
At 2:10 PM, Anonymous Anonymous said...

Molto interessante... Mi fate sentire veramente stupido. Andrea avresti per caso modo di scrivere anche l'algoritmo per i sistemi ridotti n-1 e n-2?

 
At 3:42 PM, Anonymous Paola said...

Buongiorno Andrea, grazie per la condivisone del codice. Sto provando con difficoltà a tradurre l’algoritimo in PHP. Non conosco i linguaggi che hai riportato. Potresti aiutarmi?
soluzioni.agrodolce@gmail.com

 

Post a Comment

<< Home