Newsgroup: it.hobby.enigmi
Titolo: Numeri di 9 cifre

E' tornato Silvio..... Urra'.
Quanti sono i numeri di 9 cifre, una volta cancellati tutti
quelli con la stessa cifra ripetuta 3 o piu' volte
consecutivamente ? 
:) dario

 :) dario
-
.
.
.
S
P
O
I
L
E
R
.
.
.
-
Prima provo a dare la soluzione, poi, se e' giusta, spiego come:
837000000.
Dade :)

Spoiler
Io ne ho contati 848844693.....
sandro.san
--

Mi correggo, c'e' qualcosa che non mi torna...

.
.
.
.
.
.
.
.
.
.
.
999999999-99999999-56839329
   =843160671
Questo e' giusto (credo)
sandro.san


.
.
Ciao
Dario, ciao Silvio!
.
.
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
I numeri di 9 cifre sono
900.000.000 da 100.000.000 a 999.999.999 compresi.
Quelli che hanno almeno
tre cifre consecutive uguali li ho contati con la brute force, tagliando
qualche ramo secco qua e la', perche' a ragionarci su c'e' da prendere
delle belle cantonate! Essi sono 56.124.180 (ho contato questi perche' si
fa prima).
La mia risposta e' dunque 843.875.820
.
.
Ciao a tutti  :o)
Livio
.
.
PS: Si', si' sto leggendo che non siete d'accordo...
--------------------------------
Inviato via 
http://usenet.iol.it
 

 fa prima).
Non mi trovo, mentre invece sarei portato a dare ragione a sandro.san
Vediamo come ci sono arrivato:
Chiamiamo tripli i numeri con almeno tre cifre consecutive uguali.
Sia f(n) il numero di tripli di n cifre. Stiamo cercando f(9).
Possiamo procedere per induzione, partendo da
f(1)=0
f(2)=0
f(3)=9
vediamo un numero di 4 o più cifre, ad esempio 7
abcdefX
Sarà triplo se:
a)  abcdef è triplo
b)  abcdef finisce con due X
Nel caso b) per evitare di contare alcuni numeri due volte devo accertarmi
che abcd non sia triplo e finisca con una cifra diversa da X.
Ricapitoliamo:
ognuno degli f(6) tripli abcdef è il prefisso di 10 diversi tripli abcdefX
ognuno dei (9000-f(4)) non tripli "abcd" è il prefisso di 9 diversi tripli
abcdXXX (d<>X)
La formula ricorsiva allora è:
f(n+3) = 10*f(n+2) + 9*(9*10^(n-1)-f(n))
n         f(n)
1            0
2            0
3            9
4          171
5        2.520
6       33.219
7      411.651
8    4.903.830
9   56.839.329
Metodo alternativo:
Ogni numero di 9 cifre può essere rappresentato da una stringa di 8 bit,
ognuno dei quali indica se una cifra è uguale alla precedente:
122345556 ==>
*01000110
La codifica non è biunivoca e i numeri tripli sono caratterizzati dall'avere
almeno due "1" ripetuti. Ad ogni codifica binaria corrispondono 9*9^s
numeri, con s=numero di bit "0" della codifica. Questo perché la cifra
iniziale può essere una delle 9 cifre non nulle, e ad ogni "0" possiamo
scegliere in 9 modi diversi come cambiare cifra, mentre con gli "1" dobbiamo
ripetere forzatamente la precedente. E' facile scrivere un programma che
genera tutte le 256 stringhe, controlla che ci sia almeno una sequenza "11"
e moltiplica per il *peso* 9*9^s.
Con questa codifica possiamo testare numeri molto grandi, che altrimenti
richiederebbero tempi biblici.
Comunque con la funzione ricorsiva si fa decisamente prima.
Ciao, Silv:o)

Ciao a tutti e bentornato a Silvio!
Con la brute force ho trovato conferma ai risultati di sandro.san e Silvio. 
Tre minuti per scrivere il programma (senza ottimizzazioni), un'oretta e 
mezza di elaborazione e il risultato č: 843.160.671.
Ciao
Giorgio
_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at 
http://www.hotmail.com
.
-- 
Posted from [194.185.19.122] by way of 
f183.law8.hotmail.com
 [216.33.241.183] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Silvio.
.
.
.
.
.
Va bene,
va bene, razza di pignoli: 8.4x10^8
843.160.671 ciao  :o)
Livio


 richiederebbero tempi biblici.
Confermo!! Ho utilizzato la "forza bruta" su STR(n) in un ciclo testando la tripla ripetizione delle 10 cifre convertite
singolarmente in stringa.
Pur sapendo che VB lavora moooolto più velocemente sui numeri che sulle stringhe ho lanciato speranzoso  il programma
alla sera....e il mattino dopo ho resettato il computer!!
Non ditemi che dovrei passare al C, vi risponderi che non ci capisco un' H !! :-)
Ciao
LW
P.S.
Ma sti computer non dovevano fare milioni di operazioni al secondo!! :-)


Ciao, non mi permetterei mai,
ma la tentazione (e l'amore per il fortran)
e' troppo forte...
Tempo di elaborazione: 90 secondi scarsi.
 program dario
  integer*4 tot, ral
  tot=0
     do i1=1,9
     do i2=0,9
     do i3=0,9
     do i4=0,9
     do i5=0,9
     do i6=0,9
     do i7=0,9
     do i8=0,9
     do i9=0,9
 if ((i5.eq.i6.and.i6.eq.i7).or.(i6.eq.i7.and.i7.eq.i8)
     +.or.(i7.eq.i8.and.i8.eq.i9).or.(i1.eq.i2.and.i2.eq.i3).or.
     +(i2.eq.i3.and.i3.eq.i4).or.(i3.eq.i4.and.i4.eq.i5).or.
     +(i4.eq.i5.and.i5.eq.i6))  tot= tot +1
     end do
     end do
     end do
     end do
     end do
     end do
     end do
     write(*,*) i1,i2,i3,i4,i5,i6,i7,i8,i9  , tot
     end do
     end do
   end
sandro.san


.
.
Levando tanto di cappello alla soluzione analitica di Silvio Sergio,
ma leggendo di tempi biblici di coloro che hanno usato la forza bruta,
vorrei spezzare una lancia in favore di quest'ultima (come al solito)
con un paio di considerazioni:
1) La pretesa superiorita' del linguaggio "C" e' soltanto piu' una
leggenda metropolitana. A parita' di controlli, l'avvento del Pentium
con il suo parallelismo e il suo coprocessore ha eliminato la maggior
parte dei vantaggi del "C".
2) Usando strutture nidificate, al posto di laboriose formule logiche,
e' possibile anche nei linguaggi ad alto livello ottenere formidabili
accelerazioni. Ecco nel seguito il programma in VB5 che risolve il
problema di Dario in meno di 25 secondi, senza alcuna potatura di
rami secchi.
Ciao a tutti  :o)
Livio
'-----------------------------------------------------------
Private Sub Command2_Click()
TEMPO = Timer
Dim A As Byte, B As Byte, C As Byte, D As Byte, E As Byte, F As Byte, G As
Byte, H As Byte, I As Byte, N As Long
For A = 1 To 9
 For B = 0 To 9
  Text1 = Str(A) + Str(B)
  Text2 = Str(N)   'Stampa di monitoring
  DoEvents
  For C = 0 To 9
   For D = 0 To 9
    For E = 0 To 9
     For F = 0 To 9
      For G = 0 To 9
       For H = 0 To 9
        For I = 0 To 9
        If B = C Then
            If A = B Then GoTo Conta   'A=B=C
            If C = D Then GoTo Conta   'B=C=D
        End If
        If D = E Then
            If C = D Then GoTo Conta   'C=D=E
            If E = F Then GoTo Conta   'D=E=F
        End If
        If F = G Then
            If E = F Then GoTo Conta   'E=F=G
            If G = H Then GoTo Conta   'F=G=H
        End If
        If G = H Then
          If H = I Then GoTo Conta     'G=H=I
        End If
Prossimo:
Next: Next: Next: Next: Next: Next: Next: Next: Next
Text1 = "END: " + Str(Timer - TEMPO) 'Stampa tempo impiegato
Text2 = "N=" + Str(N)    'Stampa risultato finale
Exit Sub
Conta:
    N = N + 1   'Conteggi num. con 3 cifre cons. uguali
    GoTo Prossimo
End Sub
'-----------------------------------------------------------
'Risultato: N = 56839329
'S.O.: Windows98 R4.10.2222A
'Linguaggio: Microsoft VisualBasic 5.0
'uP: Pentium Intel 733
'Tempo impiegato: 24.44"
'-----------------------------------------------------------
-- 
Posted from 
mail-1.tiscalinet.it
 [195.130.225.147] 


 ha scritto nel messaggio news:9blvqr$543$1...@canarie.caspur.it...


Ciao,
mi sa che per adesso vince Livio,
pero' non sono ancora riuscito
a far girare il suo programma in VB,
per cui, bho.
Ottimizzando il mio gira in 35' circa.
Sandro.for
--

 parte dei vantaggi del "C".
Questa frase mi punge nell'orgoglio! :-)))
Da programmatore C (di nascita) e VB (di adozione) ho provato a fare un
confronto diretto tra la velocità di esecuzione dell'algoritmo in
discussione realizzato con due programmi sostanzialmente identici scritti
nei due linguaggi.
Questa è la versione in C:
#include <stdio.h>
int cifra(long x, int n);
int buono(long x);
void main()
{
 long c = 0, i;
 for (i = 100000000; i <= 999999999; i++)
  if (buono(i))
   c++;
 printf("%d\n", c);
}
int buono(long x)
{
 int i, c;
 for (i = 0; i < 7; i++)
  if ((c = cifra(x, i)) == cifra(x, i+1) && c == cifra(x, i + 2))
   return 0;
 return 1;
}
int cifra(long x, int n)    // estrae l'n-esima cifra dal numero x
{
 while (n--)
  x /= 10;
 return x % 10;
}
*************************************
Questa è la versione corrispondente in VB:
Private Sub Command1_Click()
    Dim c As Long, i As Long
    c = 0
    For i = 100000000 To 999999999
        If buono(i) Then c = c + 1
    Next
    Print c
End Sub
Private Function buono(ByVal x As Long) As Boolean
    Dim i As Integer, c As Integer
    For i = 0 To 6
        c = cifra(x, i)
        If c = cifra(x, i + 1) And c = cifra(x, i + 2) Then
            buono = False
            Exit Function
        End If
    Next
    buono = True
End Function
Private Function cifra(ByVal x As Long, ByVal n As Integer)
    Do While n
        x = x \ 10
        n = n - 1
    Loop
    cifra = x Mod 10
End Function
*************************
Per quanto abbia usato tutte le ottimizzazioni disponibili per realizzare
l'exe in VB 6.0, il tempo di esecuzione è di circa 5 volte maggiore del
corrispondente programma in C. Insomma il C ha ancora qualche marcia in più
rispetto al VB. :-)
Non voglio entrare nel merito della bontà del mio algoritmo rispetto a
quello di Livio. Non era mia intenzione scrivere un algoritmo ottimizzato (e
infatti svolge molto lavoro inutile) quanto scrivere codice abbastanza
elegante e senza rischi di errori.
... e poi un programma che utilizza 9 For annidati e 2 GoTo non so nemmeno
come definirlo!!! :-))))))))))))))))
Ciao :-)
Giorgio

 ha scritto nel messaggio news:9bmlvj$gnm$1...@canarie.caspur.it...

Quello di Livio a me gira che è una meraviglia!!
37 secondi! ( P3 500 MHz )
Non ho parole... e non mi capita spesso! :-)
Ciao
LW


In termine di velocità una meraviglia è la parola giusta!
Come dicevo a sandro.san, non credevo ai miei occhi quando ho visto il fantastico tempo reallizzato dal programma di
Livio.
Sul mio P3 500 MHz dopo 37'' aveva concluso i calcoli!
Anch'io pensavo che 9 For annidati fossero una bestemmia, invece...
Ciao
LW

 vorrei spezzare una lancia in favore di quest'ultima (come al solito)
Livio, io sono del partito dei "forzabrutisti preventivi" nel senso che se
in due minuti posso buttar giù un algoritmo che mi fa il lavoro, intanto lo
faccio e poi penso a soluzioni eleganti, regolandomi col risultato trovato.
Però quando capisco che i tempi di esecuzione sono lunghi penso a qualche
trucco oppure rinuncio.
In questo caso si potrebbe pensare: la prima cifra la fisso (es: c0=1) e poi
moltiplico quanto trovato per 9 (per simmetria). Ma l'appetito vien
mangiando: perché fare un ciclo da 0 a 9 per la seconda cifra se sappiamo
che per 9 di questi 10 valori il lavoro da fare è il medesimo?  tanto vale
provare solo due volori, 1 o 2, sapendo che se la cifra è diversa dalla
precedente devo introdurre un fattore moltiplicativo 9.
Ecco un algoritmo che in una frazione di secondo produce il risultato
cercato.
---------------
Sub tripli()
  tot = 0
  b0 = 1: m0 = 1
  For c1 = 1 To 2: If c1 = c0 Then m1 = 0 Else m1 = 1
  For c2 = 1 To 2: If c2 = c1 Then m2 = 0 Else m2 = 1
  For c3 = 1 To 2: If c3 = c2 Then m3 = 0 Else m3 = 1
  For c4 = 1 To 2: If c4 = c3 Then m4 = 0 Else m4 = 1
  For c5 = 1 To 2: If c5 = c4 Then m5 = 0 Else m5 = 1
  For c6 = 1 To 2: If c6 = c5 Then m6 = 0 Else m6 = 1
  For c7 = 1 To 2: If c7 = c6 Then m7 = 0 Else m7 = 1
  For c8 = 1 To 2: If c8 = c7 Then m8 = 0 Else m8 = 1
    s = m0 + m1 + m2 + m3 + m4 + m5 + m6 + m7 + m8
    t = (m1+m2)*(m2+m3)*(m3+m4)*(m4+m5)*(m5+m6)*(m6+m7)*(m7+m8)
    If t = 0 Then tot = tot + 9^s
  Next: Next: Next: Next: Next: Next: Next: Next
  Print tot
End Sub
----------------
Ciao, Silv:o)


.
:o))))
I tabu' sono quegli argomenti per cui si litiga in famiglia, si 
rovinano le amicizie, vanno a rotoli gli affari. Esempi di tabu' 
sono l'opinione politica, la religione, il pisello di Cristo, 
il linguaggio "C" e il S.O. Linux.
:o))))
Giorgio, tu non hai scritto due programmi equivalenti, ma ne hai 
scritto uno in C e hai tradotto l'altro in VB. Tu pensi in C!!!
:o))))
A suo tempo, con le prime schede madre Intel Pentium 75, ho 
piantato sul bus ISA un convertitore DA per generare segnali 
analogici definiti in tempo reale dal software, come ad es. una 
sinusoide definita per campioni. Ho caricato il Dos6.22 e ho 
fatto esperimenti con il QuickBasic4.0 e il QuickC2.5, entrambi 
della Microsoft. Risultato inaspettato anche per me: leggero 
vantaggio per il compilato QB4 (10% medio).
:o))))
A pie' di pagina ho riscritto il programma, guadagnando ancora 
piu' di un secondo, ed eliminando i GOTO che tanto fanno 
inorridire i puristi (mica sono un programmatore, io!). 
Il risultato di 23 secondi e' confrontabile per Pentium da 
100 a 1000 MHz con una semplice proporzione. A riprova della 
mia tesi vi sfido a far meglio in "C"!!! (senza gli algoritmi 
di Silvio, neh!, ma esaminando ognuna delle combinazioni).
:o))))
Ciao a tutti  :o)
Livio
----------------------------------------------------------------------
Private Sub Command2_Click()
TEMPO = Timer
Dim A As Byte, B As Byte, C As Byte, D As Byte, E As Byte, F As Byte, 
G As Byte, H As Byte, I As Byte, N As Long
For A = 1 To 9
 For B = 0 To 9
  Text1 = Str(A) + Str(B)
  Text2 = Str(N)   'Stampa di monitoring
  DoEvents
  For C = 0 To 9
   For D = 0 To 9
    For E = 0 To 9
     For F = 0 To 9
      For G = 0 To 9
       For H = 0 To 9
        For I = 0 To 9
 
        If A = B And B = C Then
            N = N + 1
        ElseIf C = D And (B = C Or D = E) Then
            N = N + 1
        ElseIf E = F And (D = E Or F = G) Then
            N = N + 1
        ElseIf G = H And (F = G Or H = I) Then
            N = N + 1
        End If
 
Next: Next: Next: Next: Next: Next: Next: Next: Next
Text1 = "END: " + Str(Timer - TEMPO) 'Stampa tempo impiegato
Text2 = "N=" + Str(N)    'Stampa risultato finale
'-----------------------------------------------------------
'Risultato: N = 56839329
'S.O.: Windows98 R4.10.2222A
'Linguaggio: Microsoft VisualBasic 5.0
'uP: Pentium Intel 733
'Tempo impiegato: 23.2" (170"@100MHz)
'-----------------------------------------------------------
End Sub
-- 
Posted from 
mta21-acc.tin.it
 [212.216.176.74] 


 come definirlo!!! :-))))))))))))))))
Hmmmm... Io diffido di quelli che quando vedono un goto gli vengono le
convulsioni (e ne ho incontrati taaaaaaaanti nella mia vita professionale e
non). Se ripenso alle menate che mi fecero fare una volta per farmi eliminare un
goto da un programma (mi radoppiarono quasi la lunghezza del codice), mi tornano
gli incubi. Io appartengo al partito del QCVCV (6, 2, 2, 2, 2 - squallido
tentativo di riportare in argomento questo thread :)
--AG

:o))))
Ho riscritto il tuo programma in C. In effetti il miglioramento in termini
di prestazioni non è molto nei confronti della versione VB. Del resto non
c'è molto a cui aggrapparsi. Un gruppo di for annidati verrano tradotti in
codice macchina allo stesso modo in VB e in C. Ho solo verificato che in C
si ottiene un miglioramento di un 15% rispetto al VB se si dichiarano le
variabili dei for come long invece che come byte (come saprai, il
trattamento di un long in un sistema a 32 bit è più efficiente, anche se più
dispendioso, rispetto a gestire un byte o un intero su due byte; in VB
questa modifica non cambia di molto i tempi). C'è comunque da dire che se la
complessità del programma aumenta (chiamate di funzioni e altro), il C
dovrebbe riuscire a gestirlo in maniera più efficiente.
Concludendo vorrei dire che io non sto dalla parte del C per partito preso.
Lavoro sia in Visual Basic che in Visual C++ e normalmente decido di
affrontare in VB quei progetti che sarebbe un suicidio sviluppare in VC++ e
affronto in VC++ quei progetti che sarebbe un suicidio sviluppare in VB!
:-))))
Ciao :-)
Giorgio
P.S. Ma il mio problema (o meglio di Dario) delle bistecche (vedi thread "Le
bistecche") non vi interessa? Lo conoscete già? Io lo trovo carino, ma
sembra che abbia interessato poche persone.

 sembra che abbia interessato poche persone.
Scherzi? Ma con in giro la "mucca pazza"!?!?
Ciao
Gianni
--
Io voto Berlusconi perchè credo alla Befana