Calcolare quantità numeri senza ripetizione in un intervallo
Salve ragazzi,
vorrei capire quali calcoli devo fare per sapere esattamente quanti numeri ci sono in un intervallo le cui cifre non si ripetono!
Io ho pensato a qualcosa del genere:
se ad esempio devo calcolare quanti ce ne sono nell'intervallo [1056, 7954], ho pensato di fare questo calcolo:
$a = D(9, 4) = 10*9*8*7 = 5040$
$b = (a / 10) * (1 + (9 - 7)) = 1512$
$a - b = 3528$
Purtroppo il calcolo non basta. Infatti ho provato a far calcolare il numero con un mio programma e non corrisponde.
Qualche suggerimento?
vorrei capire quali calcoli devo fare per sapere esattamente quanti numeri ci sono in un intervallo le cui cifre non si ripetono!
Io ho pensato a qualcosa del genere:
se ad esempio devo calcolare quanti ce ne sono nell'intervallo [1056, 7954], ho pensato di fare questo calcolo:
$a = D(9, 4) = 10*9*8*7 = 5040$
$b = (a / 10) * (1 + (9 - 7)) = 1512$
$a - b = 3528$
Purtroppo il calcolo non basta. Infatti ho provato a far calcolare il numero con un mio programma e non corrisponde.
Qualche suggerimento?
Risposte
Nessuno è in grado?
"xsl":
Salve ragazzi,
vorrei capire quali calcoli devo fare per sapere esattamente quanti numeri ci sono in un intervallo le cui cifre non si ripetono!
Io ho pensato a qualcosa del genere:
se ad esempio devo calcolare quanti ce ne sono nell'intervallo [1056, 7954], ho pensato di fare questo calcolo:
$a = D(9, 4) = 10*9*8*7 = 5040$
$b = (a / 10) * (1 + (9 - 7)) = 1512$
$a - b = 3528$
Purtroppo il calcolo non basta. Infatti ho provato a far calcolare il numero con un mio programma e non corrisponde.
Qualche suggerimento?
Mi sembra alquanto difficile trovare una formula generale.
Dovremmo conoscere la distribuzione dei numeri le cui cifre non si ripetono per valutare quanti ce ne sono in un intervallo assegnato..
Io ho fatto questo calcolo, ma una generalizzazione la vedo difficile:
Come hai indicato i numeri di 4 cifre che non si ripetono sono $D(10, 4) = 10*9*8*7 = 5040$ (contando anche quelli che iniziano con 0)
A questi devo togliere quelli presenti tra 0000 e 1055 e quelli presenti tra 7955 e 9999.
Quelli presenti tra 0000 e 1055 sono: $1*9*8*7+1*1*3*7+1*1*1*3=528$
Quelli presenti tra 7955 e 9999 sono: $2*9*8*7+1*1*2*7+1*1*1*2=1024$
Dunque $5040-528-1024=3488$
Come vedi, il calcolo di quelli da togliere dipende dalle cifre degli estremi dell'intervallo che hai dato, perciò mi sembra di difficile generalizzazione.
"cenzo":
A questi devo togliere quelli presenti tra 0000 e 1055 e quelli presenti tra 7955 e 9999.
Quelli presenti tra 0000 e 1055 sono: $1*9*8*7+1*1*3*7+1*1*1*3=528$
Quelli presenti tra 7955 e 9999 sono: $2*9*8*7+1*1*2*7+1*1*1*2=1024$
Intanto grazie per la risposta. Ma non ho capito il calcolo che fai per togliere le cifre che non interessano
"xsl":
[quote="cenzo"]
A questi devo togliere quelli presenti tra 0000 e 1055 e quelli presenti tra 7955 e 9999.
Quelli presenti tra 0000 e 1055 sono: $1*9*8*7+1*1*3*7+1*1*1*3=528$
Quelli presenti tra 7955 e 9999 sono: $2*9*8*7+1*1*2*7+1*1*1*2=1024$
Intanto grazie per la risposta. Ma non ho capito il calcolo che fai per togliere le cifre che non interessano[/quote]
Si, lo spiego perchè è un po' contorto..
Iniziamo con quelli presenti tra 0000 e 1055
Se la prima cifra è 0 (1 sola possibilità) le altre 3 le posso scegliere in 9*8*7 modi, da cui $1*9*8*7$
Se la prima cifra è 1 (1 sola possibilità): la seconda cifra deve essere per forza 0 (se fosse ad esempio 2 supererei il numero 1055), dunque ho 1 sola possibilità (siamo ad $1*1$). La terza cifra deve essere diversa dalle prime due (dunque non può essere 0 nè 1) ma deve poi dare un numero minore di 1056. Ho allora suddiviso in due ulteriori casi: (a) la terza cifra è 2,3,4 (3 possibilità) e la quarta cifra una dei rimanenti 10-3=7 numeri (7 possibilità): ottengo così il secondo addendo $1*1*3*7$; (b) la terza cifra è 5 (1 possibilità), in tal caso la quarta cifra può essere 2,3,4 (non può essere 0,1,5 altrimenti duplico una cifra già presente; non può essere maggiore di 5 altrimenti supero il numero 1055), in definitiva 3 possibilità, da cui il terzo addendo $1*1*1*3$.
Per quelli presenti tra 7955 e 9999 il ragionamento è analogo, ma in tal caso bisogna avere necessariamente un numero maggiore di 7954.
Nel tuo messaggio non c'è una spiegazione..
"xsl":
Nel tuo messaggio non c'è una spiegazione..
Beh.. forse non è la spiegazione che ti aspettavi
EDIT: non è che il browser non ha renderizzato bene la pagina e non leggi quello che ho scritto? prova a ricaricarla
Si era un problema di browser.
Ma in generale devo sempre predisporre n-1 casi?
Per n intendo la lunghezza del numero.
Ma in generale devo sempre predisporre n-1 casi?
Per n intendo la lunghezza del numero.
Non mi piace molto come soluzione, perchè vedo troppa "manualità" nel calcolo.
Tenterei di trovare un algoritmo per trovare quanti numeri ci sono (non ripetuti) per qualsiasi N.
La differenza dei due numeri porterebbe alla soluzione.
Tenterei di trovare un algoritmo per trovare quanti numeri ci sono (non ripetuti) per qualsiasi N.
La differenza dei due numeri porterebbe alla soluzione.
"Umby":
Non mi piace molto come soluzione, perchè vedo troppa "manualità" nel calcolo.
Tenterei di trovare un algoritmo per trovare quanti numeri ci sono (non ripetuti) per qualsiasi N.
La differenza dei due numeri porterebbe alla soluzione.
Ok ma la differenza contiene anche quei numeri le cui cifre si ripetono..
"xsl":
Ok ma la differenza contiene anche quei numeri le cui cifre si ripetono..
Perchè ???
Mi spiego meglio:
se il numero 1056 è il 529esimo numero (partendo da 0000) con cifre che non si ripetono,
ed il numero 7954 è il 4016esimo numero.
La differenza tra i due (4016 - 529 = 3487) ti da proprio l'informazione che cercavi.
P.s. Differisce di una unità rispetto al calcolo di cenzo, in quanto ho conteggiato solo uno dei due estremi.
"Umby":
se il numero 1056 è il 529esimo numero (partendo da 0000) con cifre che non si ripetono,
ed il numero 7954 è il 4016esimo numero.
Questa informazione come la ricavi?
Umby evidentemente ha rapportato il tutto alle quattro cifre, ma non so se è quello richiesto dal testo del problema:
così non sono conteggiati i numeri di solo una o due cifre, né quelli di tre cifre contenenti uno zero.
se l'intervallo deve essere tra due numeri con lo stesso numero di cifre, la soluzione dovrebbe essere corretta, altrimenti penso che si possa "aggiustare" con poca difficoltà.
xsl, puoi chiarire il problema?
così non sono conteggiati i numeri di solo una o due cifre, né quelli di tre cifre contenenti uno zero.
se l'intervallo deve essere tra due numeri con lo stesso numero di cifre, la soluzione dovrebbe essere corretta, altrimenti penso che si possa "aggiustare" con poca difficoltà.
xsl, puoi chiarire il problema?
"adaBTTLS":
Umby evidentemente ha rapportato il tutto alle quattro cifre, ma non so se è quello richiesto dal testo del problema:
così non sono conteggiati i numeri di solo una o due cifre, né quelli di tre cifre contenenti uno zero.
se l'intervallo deve essere tra due numeri con lo stesso numero di cifre, la soluzione dovrebbe essere corretta, altrimenti penso che si possa "aggiustare" con poca difficoltà.
xsl, puoi chiarire il problema?
In generale io vorrei calcolare a priori quanti numeri ci sono in un intervallo le cui cifre non si ripetono;
la lunghezza degli estremi può variare fino ad un massimo di 10 e gli estremi devono avere medesima lunghezza.
Esempi:
[10, 35]
[102, 324]
e così via..fino a raggiungere la totale lunghezza di 10.
beh, allora il calcolo di Umby dovrebbe soddisfarti.
il totale dei numeri di $k$ cifre diverse, compresi quelli che iniziano per "zero", è:
$((10),(k))*k! = (10!)/((10-k)!)$
poi, Umby ha parlato di un calcolo troppo meccanico, per cui penso che per dire che
"il numero 1056 è il 529esimo numero (partendo da 0000) con cifre che non si ripetono, ed il numero 7954 è il 4016esimo numero",
basta "contare" i $(9!)/(6!)$ numeri inizianti per "zero" (numeri di tre cifre diverse da zero che non si ripetono), i numeri di due cifre diverse tra loro e diverse da zero ed uno che precedono 56, i numeri che precedono 7000 e i numeri che iniziano per sette e precedono 7954 ...
il totale dei numeri di $k$ cifre diverse, compresi quelli che iniziano per "zero", è:
$((10),(k))*k! = (10!)/((10-k)!)$
poi, Umby ha parlato di un calcolo troppo meccanico, per cui penso che per dire che
"il numero 1056 è il 529esimo numero (partendo da 0000) con cifre che non si ripetono, ed il numero 7954 è il 4016esimo numero",
basta "contare" i $(9!)/(6!)$ numeri inizianti per "zero" (numeri di tre cifre diverse da zero che non si ripetono), i numeri di due cifre diverse tra loro e diverse da zero ed uno che precedono 56, i numeri che precedono 7000 e i numeri che iniziano per sette e precedono 7954 ...
Ok. Mi pare di capire che un metodo generico non c'è!
A questo punto un informatico la risolverebbe in questo modo
n = 0
a = estremo sinistro
b = estremo destro
finchè a <= b {
se c non ha ripetizioni n = n +1;
a = a +1;
}
Io ho proposto un calcolo all'inizio, secondo te quel calcolo può essere un passo iniziale per giungere al calcolo esatto dei numeri (in un intervallo) che non contengono ripetizioni?
A questo punto un informatico la risolverebbe in questo modo
n = 0
a = estremo sinistro
b = estremo destro
finchè a <= b {
se c non ha ripetizioni n = n +1;
a = a +1;
}
Io ho proposto un calcolo all'inizio, secondo te quel calcolo può essere un passo iniziale per giungere al calcolo esatto dei numeri (in un intervallo) che non contengono ripetizioni?
"Umby":
Non mi piace molto come soluzione, perchè vedo troppa "manualità" nel calcolo.
Tenterei di trovare un algoritmo per trovare quanti numeri ci sono (non ripetuti) per qualsiasi N.
La differenza dei due numeri porterebbe alla soluzione.
Giusto, mi sembra un approccio più semplice
Proverei allora il seguente algoritmo per determinare quanti numeri (senza cifre ripetute) ci sono fino al numero N (escluso).
Supponiamo che N=7386
E' un numero di l=4 cifre
La prima è p=7; la seconda s=3; la terza t=8; la quarta q=6
Calcolo le correzioni p'=7; s'=3; t'=6; q'=5.
Ad esempio t'=t-2=8-2=6 Sottraggo 2 perchè il numero t=8 "contiene" due numeri precedenti più piccoli (7 e 3)
q'=q-1=6-1=5 poichè nei numeri fino al 6, tra i precedenti, c'è già il 3, quindi tolgo solo 1.
Per p' non ci sarà mai alcuna correzione (p'=p).
Per s' non necessita correzione in quanto 3 è più piccolo di 7.
Fatto questo primo passo posso calcolare:
numeri del tipo (0..6)XXX ne sono 7*9*8*7 cioè p'*9*8*7
numeri del tipo 7(0..2)XX ne sono 1*3*8*7 cioè s'*8*7
numeri del tipo 73(0,1,2,4,5,6)X ne sono 1*1*6*7 cioè t'*7
numeri del tipo 738X ne sono 1*1*1*5 cioè q'
In definitiva i numeri con cifre diverse da 0000 a N=7386 escluso, ne sono:
p'*9*8*7+s'*8*7+t'*7+q'
Che ve ne pare?
Sto provando a trovare una formula generale.
Dato il numero di $n$ cifre $N =a_1a_2...a_k...a_n$ dove $a_k$ è la $k"-esima"$ cifra ($n<=10$; $a_k=0..9$)
Nota: le cifre del numero N siano tutte diverse tra loro.
Come indicato al post precedente troviamo prima le "correzioni" $a'_1, a'_2,...,a'_k,...,a'_n$
Il conteggio dei numeri aventi cifre diverse da 00.. a N escluso è (generalizzando la formula del post precedente):
$sum_(k=1)^(n)a'_k*D_(10-k,n-k)$
(avendo indicato con $D$ le disposizioni).
Dato il numero di $n$ cifre $N =a_1a_2...a_k...a_n$ dove $a_k$ è la $k"-esima"$ cifra ($n<=10$; $a_k=0..9$)
Nota: le cifre del numero N siano tutte diverse tra loro.
Come indicato al post precedente troviamo prima le "correzioni" $a'_1, a'_2,...,a'_k,...,a'_n$
Il conteggio dei numeri aventi cifre diverse da 00.. a N escluso è (generalizzando la formula del post precedente):
$sum_(k=1)^(n)a'_k*D_(10-k,n-k)$
(avendo indicato con $D$ le disposizioni).
"adaBTTLS":
poi, Umby ha parlato di un calcolo troppo meccanico, per cui penso che per dire che
"il numero 1056 è il 529esimo numero (partendo da 0000) con cifre che non si ripetono, ed il numero 7954 è il 4016esimo numero",
basta "contare" i $(9!)/(6!)$ numeri inizianti per "zero" (numeri di tre cifre diverse da zero che non si ripetono), i numeri di due cifre diverse tra loro e diverse da zero ed uno che precedono 56, i numeri che precedono 7000 e i numeri che iniziano per sette e precedono 7954 ...
Mi fa piacere rivederti, dopo una lunga assenza.
Diciamo piu' che contare, la mia idea era quella di dare un peso alle varie cifre.
Cenzo ha già spiegato il ragionamento, dovrei solo aggiungere un paio di precisazioni.
La prima cifra ha un peso di 504, la seconda di 56, la terza 7, l'ultima 1.
"cenzo":
Che ve ne pare?
Per me è quasi perfetto.
Il tuo calcolo è molto simile al mio. Qualche piccola differenza dal tuo, che te le elenco, cosi' possiamo verificare quale dei due calcoli è esente da errori.
1) L'ultima cifra. (Nel tuo esempio il 6).
Questa cifra se è diversa dalle altre 3, devi incrementare di una unita' il risultato finale. Nel mio programmino di simulazione infatti, il 7386 mi restituisce come risultato 3744 contro il tuo 3743. Il perchè succede questo, penso che sia abbastanza logico. Se ti chiedevo di calcolare 7387 (anzichè 7386), considerato che il 7 è gia presente non dovevi considerare una unità in più. (Ho notato che hai escluso il numero stesso, ma cmq, c'e' qualcosa che non va)
2) Devi stoppare il calcolo appena incontri una prima cifra doppia.
Se ad esempio devi calcolare su 3357, devi:
3*504 + 3*56 + STOP (Questo perchè in presenza di cifre doppie, quello che viene dopo, poco interessa).
"Umby":
Il tuo calcolo è molto simile al mio. Qualche piccola differenza dal tuo, che te le elenco, cosi' possiamo verificare quale dei due calcoli è esente da errori.
1) L'ultima cifra. (Nel tuo esempio il 6).
Questa cifra se è diversa dalle altre 3, devi incrementare di una unita' il risultato finale. Nel mio programmino di simulazione infatti, il 7386 mi restituisce come risultato 3744 contro il tuo 3743. Il perchè succede questo, penso che sia abbastanza logico. Se ti chiedevo di calcolare 7387 (anzichè 7386), considerato che il 7 è gia presente non dovevi considerare una unità in più. (Ho notato che hai escluso il numero stesso, ma cmq, c'e' qualcosa che non va)
2) Devi stoppare il calcolo appena incontri una prima cifra doppia.
Se ad esempio devi calcolare su 3357, devi:
3*504 + 3*56 + STOP (Questo perchè in presenza di cifre doppie, quello che viene dopo, poco interessa).
Si, il mio calcolo non contempla la possibilità che nel numero in input N ci siano cifre ripetute (mi era sembrato di leggere che xsl escudesse tale possibilità).
Trovo giusta la tua correzione in tale caso (segnalata con lo STOP al punto 2).
Aggiungo una nota al post precedente in modo da segnalarlo. Grazie
Per l'ultima cifra, come hai notato, ho escluso il numero N stesso in modo da avere una formula più semplice, evitando di addizionare una unità in più solo per essa (e diversamente dalle altre cifre).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo