combinazioni, matematica e programmazione

[Oromis92]

ecco un bel problema che mi si è posto mentre lavoravo sulle combinazioni...
un programma del genere

#!/usr/bin/perl -w

print "Quante iterazioni? ";
$iterations = <>;

for ($seed = "a", $c=0; $c<$iterations; $c++, $seed++){
print $seed . "\n";
}

stampa tutte le combinazioni possibili dell'alfabeto.
e qui arriva il problema:
se io voglio stampare tutto le combinazioni dell'alfabeto a una lettera (praticamente l'alfabeto) devo generare 26 combinazioni. nulla di strano.
se devo generare tutte le combinazioni di una lettera E di due lettere
devo generare 702 numeri.
quindi, mi sono chiesto, la serie 26 - 702- etc... come posso trovare una regola per svilupparla ?

e con un po di intuizioni e lavoro carta-e-penna ho trovato la soluzione. anzi, due.
dato "p" come numero di elementi nell'alfabeto (in questo caso 26) le due serie X e Y (identiche) si possono generare come segue:

X_(i+1) = p * (X_i + 1) 

Y_(i+1) = (p ^ i) + Y_(i-1)

queste serie sono identiche. dimostrandolo per prove, con un programma del genere:

$p = #inserire valore
@X = (0);
@Y = (0);
for $i (1..100) {

$uno = $p*($X[$i-1]+1);
$due = ($p**$i)+$Y[$i-1];

push @X,$uno;
push @Y,$due;

print "$uno - $due\n";

}

si vede come i risultati, a prescindere da "p" siano identici.

il problema sta nella dimostrazione matematica che le serie siano identiche. in teoria basterebbe sviluppare questa equazione fino a raggiungere un risultato tipo 1=1

p * (X_i + 1) = (p ^ i) + X_(i-1)

ma in pratica non riesco a svilupparla

nessun aiutino ? :conigliomg:

 

[stoner]

Quando si ha a che fare con le serie si dimostrano per induzione. Prima dimostri che la regola è valida per un numero finito di valori. Che ne so, provi per uno, due e tre.

Poi assumi che sia valida per N generico. Da questa assunzione, cerchi di dimostrare che sia valida anche per N+1.

Se riesci a raggiungere un'identità allora l'equazione è corretta.
Comunque le equazioni sono scritte male.

$uno = $p*($X[$i-1]+1);
$due = ($p**$i)+$Y[$i-1];

Da qui si capisce che

x(i) = p*(x(i-1)+1) che è diverso da X_(i+1) = p * (X_i + 1) (cosa che hai scritto tu)
y(i) = p^i + y(i-1)  che è diverso da Y_(i+1) = (p ^ i) + Y_(i-1)

infatti le prime prove che ho fatto non coincidevano.
Quindi

p*(x(i-1)+1) = p^i + y(i-1)

in questo caso, assumo p = 3, i = 1 e ottengo
3*(0 + 1) = 3^1 + 0
3 = 3

Assumi che sia valida l'ugualianza p*(x(n-1)+1) = p^n + y(n-1), e provo a dimostrare che sia valida anche per N+1 sfruttando questo fatto

p*(x(n)+1) = p^(n+1) + y(n)
Questo è quello da dimostrare. (Se ho tempo lo faccio domani, quello che ho fatto prima non so se funziona).

 

[stoner]

Ok, l'ho dimostrato (comunque mi sono accorto che alla fine avevi sbagliato soltanto a scrive l'equazione della Y, quella della X è uguale).
Noi dobbiamo dimostrare che p*(x(n) + 1) = p^(n+1) + y(n) partendo d'ipotesi induttiva che p*(x(n-1)+1) = p^n + y(n-1)
dobbiamo riuscire ad arrivare ad una identità, quindi:

p*(x(n) + 1) = p^(n+1) + y(n)
=> p*x(n) + p = (p^n)*p + y(n)

noi sappiamo che y(n) = p^n + y(n-1) e che x(n) = p*x(n-1) + p, quindi sostituendo si ha che:

p*[p*x(n-1) + p] + p = (p^n)*p + p^n + y(n-1)

Dall'ipotesi induttiva sappiamo che p^n + y(n-1) = p*x(n-1) + p, quindi sostituendo si ha che:
p*[p*x(n-1) + p] + p = (p^n)*p + p*x(n-1) + p
=>
p*[p*x(n-1) + p] = (p^n)*p + p*x(n-1)
=>
p*[p*x(n-1) + p] - (p^n)*p - p*x(n-1) = 0
p* { p*x(n-1) + p - p^n - x(n-1) } = 0

Ora sappiamo che p*x(n-1) + p = p^n + y(n-1) (sempre dall'ipotesi iniziale). Ciò implica che:
p* { p^n + y(n-1) - p^n - x(n-1) } = 0
=>
p*[ y(n-1) - x(n-1)] = 0
=>
y(n-1) - x(n-1) = 0 => y(n-1) = x(n-1) (che è quello che volevamo dimostrare)

 

[Oromis92]

Grandissimo! finalmente...

unomg:

 

[RedSkull]

wow stoner hai qualche numero per il super enalotto ? xD

 

[V1R5]

wow stoner hai qualche numero per il super enalotto ? xD

Se risponde il numero che penso io lo frusto a vita.

 

[orakool]

wow stoner hai qualche numero per il super enalotto ? xD

Se risponde il numero che penso io lo frusto a vita.

 

[imported_lepa]

Quale, il 23?

 

[stoner]

ahah.. mi sono giocato il 23 e il 32 al superenalotto in due schedine differenti, come superstar, e non è uscito. ROTFL
In compenso è uscito il 20 (ci sono andato vicino D

Comunque, state sicuri, che se avessi dei numeri per il superenalotto non li darei a voi :conigliomg:

pazzo non ha ancora vinto nessuno e si è arrivati a 127.500.000 € :incredimg:

 

[imported_lepa]

In realtà è perchè io non ho ancora giocato....
Quando lo farò vincerò

 

[stoner]

[ot]
Se vinci ricordati di me
[/ot]

 

[imported_lepa]

[ot]Sì, mi ricorderò..... e riderò al pensiero del fatto che tu ci abbia buttato soldi.....[/ot]

 

[stoner]

[ot]oddio, 4 € non ho mica dovuto rubare per guadagnarli. Io so che la probabilità di vincere è molto bassa, infatti gioco solo se le cifre sono tali da giustificare anche una spesa minima di 4 €.
[/ot]

 

[imported_lepa]

[ot]Allora riderò pensando a tutti gli italiani e quanti soldi ci hanno buttato..ok? [/ot]

 

[RedSkull]

In realtà è perchè io non ho ancora giocato....
Quando lo farò vincerò