[Esercizio] Numeri di telefono

Noixe · 31-01-2011, 09:55

Mi è venuto in mente questo simpatico esercizio.

Quando bisogna leggere un numero di telefono, c'è chi lo fa cifra per cifra, chi legge due cifre per volta, chi magari ne legge prima tre e poi le rimanenti, etc... così mi sono chiesto:

1. Quanti sono tutti i modi possibili di leggere un numero di telefono?

2. Quale algoritmo è in grado di generarli tutti?

Ad esempio dato il numero 1234 i modi possibili sono 8:

1 234 (uno duecentotrentaquattro)
1 2 34 (uno due trentaquattro)
1 2 3 4 (uno due tre quattro)
1 23 4 (uno ventitre quattro)
12 34 (dodici trentaquattro)
12 3 4 (dodici tre quattro)
123 4 (centoventitre quattro)
1234 (milleduecentotrentaquattro)

Scrivere un algoritmo che data una stringa di numeri in input, generi i vari modi in cui le cifre possono essere raggruppate e lette.

Infine scrivere quanti sono i modi possibili di leggere un numero di n cifre.

Saluti

P.S.: Questo messaggio va interpretato come un piccolo contest e non come una richiesta di risoluzione dei compiti per casa

rеpne scasb · 31-01-2011, 14:15

■

zuper · 31-01-2011, 15:39

Quote:

Originariamente inviato da Noixe

Mi è venuto in mente questo simpatico esercizio.

Quando bisogna leggere un numero di telefono, c'è chi lo fa cifra per cifra, chi legge due cifre per volta, chi magari ne legge prima tre e poi le rimanenti, etc... così mi sono chiesto:

1. Quanti sono tutti i modi possibili di leggere un numero di telefono?

2. Quale algoritmo è in grado di generarli tutti?

Ad esempio dato il numero 1234 i modi possibili sono 8:

1 234 (uno duecentotrentaquattro)
1 2 34 (uno due trentaquattro)
1 2 3 4 (uno due tre quattro)
1 23 4 (uno ventitre quattro)
12 34 (dodici trentaquattro)
12 3 4 (dodici tre quattro)
123 4 (centoventitre quattro)
1234 (milleduecentotrentaquattro)

Scrivere un algoritmo che data una stringa di numeri in input, generi i vari modi in cui le cifre possono essere raggruppate e lette.

Infine scrivere quanti sono i modi possibili di leggere un numero di n cifre.

Saluti

P.S.: Questo messaggio va interpretato come un piccolo contest e non come una richiesta di risoluzione dei compiti per casa

http://it.wikipedia.org/wiki/Excusat...atio_manifesta

Noixe · 31-01-2011, 15:58

Quote:

Originariamente inviato da rеpne scasb

Se 'n' e' il numero di cifre di cui e' composto il numero telefonico, il numero dei modi possibili di leggerlo (secondo il tuo schema) e': 2^(n-1).

In effetti dallo schema si ricava facilmente, non avrei dovuto postarlo

Quote:

Originariamente inviato da rеpne scasb

Un "semplice" algoritmo ricorsivo, tenendo conto che se f(k,n) rappresentano le 'k' combinazioni di un numero telefonico di 'n' cifre, espresse in s(k,m) gruppi numerici, allora f(k+1) = 2 * f(k) e s(k+1,m+1) = 1+s(k,m) + s(k+1,m)

Umh... volevi dire f(k, n+1) = 2 * f(k, n) forse?
Mentre non ho ben capito cosa indicano i gruppi numerici s(k, m).
Intendi dire le combinazioni vere e proprie?
Quindi s(k, n+1) = s(k, n) + s(k, n-1) + ... + 1?

In ogni caso, richiedevo l'algoritmo funzionante

Noixe · 31-01-2011, 15:59

Quote:

Originariamente inviato da zuper

http://it.wikipedia.org/wiki/Excusat...atio_manifesta

LOL, l'algoritmo l'ho scritto già a suo tempo

Ecco l'output dell'algoritmo con un numero di 10 cifre (che di sicuro non ho scritto manualmente a differenza di quello postato inizialmente

)

Codice:

0 123456789
0 1 23456789
0 1 2 3456789
0 1 2 3 456789
0 1 2 3 4 56789
0 1 2 3 4 5 6789
0 1 2 3 4 5 6 789
0 1 2 3 4 5 6 7 89
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 78 9
0 1 2 3 4 5 67 89
0 1 2 3 4 5 67 8 9
0 1 2 3 4 5 678 9
0 1 2 3 4 56 789
0 1 2 3 4 56 7 89
0 1 2 3 4 56 7 8 9
0 1 2 3 4 56 78 9
0 1 2 3 4 567 89
0 1 2 3 4 567 8 9
0 1 2 3 4 5678 9
0 1 2 3 45 6789
0 1 2 3 45 6 789
0 1 2 3 45 6 7 89
0 1 2 3 45 6 7 8 9
0 1 2 3 45 6 78 9
0 1 2 3 45 67 89
0 1 2 3 45 67 8 9
0 1 2 3 45 678 9
0 1 2 3 456 789
0 1 2 3 456 7 89
0 1 2 3 456 7 8 9
0 1 2 3 456 78 9
0 1 2 3 4567 89
0 1 2 3 4567 8 9
0 1 2 3 45678 9
0 1 2 34 56789
0 1 2 34 5 6789
0 1 2 34 5 6 789
0 1 2 34 5 6 7 89
0 1 2 34 5 6 7 8 9
0 1 2 34 5 6 78 9
0 1 2 34 5 67 89
0 1 2 34 5 67 8 9
0 1 2 34 5 678 9
0 1 2 34 56 789
0 1 2 34 56 7 89
0 1 2 34 56 7 8 9
0 1 2 34 56 78 9
0 1 2 34 567 89
0 1 2 34 567 8 9
0 1 2 34 5678 9
0 1 2 345 6789
0 1 2 345 6 789
0 1 2 345 6 7 89
0 1 2 345 6 7 8 9
0 1 2 345 6 78 9
0 1 2 345 67 89
0 1 2 345 67 8 9
0 1 2 345 678 9
0 1 2 3456 789
0 1 2 3456 7 89
0 1 2 3456 7 8 9
0 1 2 3456 78 9
0 1 2 34567 89
0 1 2 34567 8 9
0 1 2 345678 9
0 1 23 456789
0 1 23 4 56789
0 1 23 4 5 6789
0 1 23 4 5 6 789
0 1 23 4 5 6 7 89
0 1 23 4 5 6 7 8 9
0 1 23 4 5 6 78 9
0 1 23 4 5 67 89
0 1 23 4 5 67 8 9
0 1 23 4 5 678 9
0 1 23 4 56 789
0 1 23 4 56 7 89
0 1 23 4 56 7 8 9
0 1 23 4 56 78 9
0 1 23 4 567 89
0 1 23 4 567 8 9
0 1 23 4 5678 9
0 1 23 45 6789
0 1 23 45 6 789
0 1 23 45 6 7 89
0 1 23 45 6 7 8 9
0 1 23 45 6 78 9
0 1 23 45 67 89
0 1 23 45 67 8 9
0 1 23 45 678 9
0 1 23 456 789
0 1 23 456 7 89
0 1 23 456 7 8 9
0 1 23 456 78 9
0 1 23 4567 89
0 1 23 4567 8 9
0 1 23 45678 9
0 1 234 56789
0 1 234 5 6789
0 1 234 5 6 789
0 1 234 5 6 7 89
0 1 234 5 6 7 8 9
0 1 234 5 6 78 9
0 1 234 5 67 89
0 1 234 5 67 8 9
0 1 234 5 678 9
0 1 234 56 789
0 1 234 56 7 89
0 1 234 56 7 8 9
0 1 234 56 78 9
0 1 234 567 89
0 1 234 567 8 9
0 1 234 5678 9
0 1 2345 6789
0 1 2345 6 789
0 1 2345 6 7 89
0 1 2345 6 7 8 9
0 1 2345 6 78 9
0 1 2345 67 89
0 1 2345 67 8 9
0 1 2345 678 9
0 1 23456 789
0 1 23456 7 89
0 1 23456 7 8 9
0 1 23456 78 9
0 1 234567 89
0 1 234567 8 9
0 1 2345678 9
0 12 3456789
0 12 3 456789
0 12 3 4 56789
0 12 3 4 5 6789
0 12 3 4 5 6 789
0 12 3 4 5 6 7 89
0 12 3 4 5 6 7 8 9
0 12 3 4 5 6 78 9
0 12 3 4 5 67 89
0 12 3 4 5 67 8 9
0 12 3 4 5 678 9
0 12 3 4 56 789
0 12 3 4 56 7 89
0 12 3 4 56 7 8 9
0 12 3 4 56 78 9
0 12 3 4 567 89
0 12 3 4 567 8 9
0 12 3 4 5678 9
0 12 3 45 6789
0 12 3 45 6 789
0 12 3 45 6 7 89
0 12 3 45 6 7 8 9
0 12 3 45 6 78 9
0 12 3 45 67 89
0 12 3 45 67 8 9
0 12 3 45 678 9
0 12 3 456 789
0 12 3 456 7 89
0 12 3 456 7 8 9
0 12 3 456 78 9
0 12 3 4567 89
0 12 3 4567 8 9
0 12 3 45678 9
0 12 34 56789
0 12 34 5 6789
0 12 34 5 6 789
0 12 34 5 6 7 89
0 12 34 5 6 7 8 9
0 12 34 5 6 78 9
0 12 34 5 67 89
0 12 34 5 67 8 9
0 12 34 5 678 9
0 12 34 56 789
0 12 34 56 7 89
0 12 34 56 7 8 9
0 12 34 56 78 9
0 12 34 567 89
0 12 34 567 8 9
0 12 34 5678 9
0 12 345 6789
0 12 345 6 789
0 12 345 6 7 89
0 12 345 6 7 8 9
0 12 345 6 78 9
0 12 345 67 89
0 12 345 67 8 9
0 12 345 678 9
0 12 3456 789
0 12 3456 7 89
0 12 3456 7 8 9
0 12 3456 78 9
0 12 34567 89
0 12 34567 8 9
0 12 345678 9
0 123 456789
0 123 4 56789
0 123 4 5 6789
0 123 4 5 6 789
0 123 4 5 6 7 89
0 123 4 5 6 7 8 9
0 123 4 5 6 78 9
0 123 4 5 67 89
0 123 4 5 67 8 9
0 123 4 5 678 9
0 123 4 56 789
0 123 4 56 7 89
0 123 4 56 7 8 9
0 123 4 56 78 9
0 123 4 567 89
0 123 4 567 8 9
0 123 4 5678 9
0 123 45 6789
0 123 45 6 789
0 123 45 6 7 89
0 123 45 6 7 8 9
0 123 45 6 78 9
0 123 45 67 89
0 123 45 67 8 9
0 123 45 678 9
0 123 456 789
0 123 456 7 89
0 123 456 7 8 9
0 123 456 78 9
0 123 4567 89
0 123 4567 8 9
0 123 45678 9
0 1234 56789
0 1234 5 6789
0 1234 5 6 789
0 1234 5 6 7 89
0 1234 5 6 7 8 9
0 1234 5 6 78 9
0 1234 5 67 89
0 1234 5 67 8 9
0 1234 5 678 9
0 1234 56 789
0 1234 56 7 89
0 1234 56 7 8 9
0 1234 56 78 9
0 1234 567 89
0 1234 567 8 9
0 1234 5678 9
0 12345 6789
0 12345 6 789
0 12345 6 7 89
0 12345 6 7 8 9
0 12345 6 78 9
0 12345 67 89
0 12345 67 8 9
0 12345 678 9
0 123456 789
0 123456 7 89
0 123456 7 8 9
0 123456 78 9
0 1234567 89
0 1234567 8 9
0 12345678 9
01 23456789
01 2 3456789
01 2 3 456789
01 2 3 4 56789
01 2 3 4 5 6789
01 2 3 4 5 6 789
01 2 3 4 5 6 7 89
01 2 3 4 5 6 7 8 9
01 2 3 4 5 6 78 9
01 2 3 4 5 67 89
01 2 3 4 5 67 8 9
01 2 3 4 5 678 9
01 2 3 4 56 789
01 2 3 4 56 7 89
01 2 3 4 56 7 8 9
01 2 3 4 56 78 9
01 2 3 4 567 89
01 2 3 4 567 8 9
01 2 3 4 5678 9
01 2 3 45 6789
01 2 3 45 6 789
01 2 3 45 6 7 89
01 2 3 45 6 7 8 9
01 2 3 45 6 78 9
01 2 3 45 67 89
01 2 3 45 67 8 9
01 2 3 45 678 9
01 2 3 456 789
01 2 3 456 7 89
01 2 3 456 7 8 9
01 2 3 456 78 9
01 2 3 4567 89
01 2 3 4567 8 9
01 2 3 45678 9
01 2 34 56789
01 2 34 5 6789
01 2 34 5 6 789
01 2 34 5 6 7 89
01 2 34 5 6 7 8 9
01 2 34 5 6 78 9
01 2 34 5 67 89
01 2 34 5 67 8 9
01 2 34 5 678 9
01 2 34 56 789
01 2 34 56 7 89
01 2 34 56 7 8 9
01 2 34 56 78 9
01 2 34 567 89
01 2 34 567 8 9
01 2 34 5678 9
01 2 345 6789
01 2 345 6 789
01 2 345 6 7 89
01 2 345 6 7 8 9
01 2 345 6 78 9
01 2 345 67 89
01 2 345 67 8 9
01 2 345 678 9
01 2 3456 789
01 2 3456 7 89
01 2 3456 7 8 9
01 2 3456 78 9
01 2 34567 89
01 2 34567 8 9
01 2 345678 9
01 23 456789
01 23 4 56789
01 23 4 5 6789
01 23 4 5 6 789
01 23 4 5 6 7 89
01 23 4 5 6 7 8 9
01 23 4 5 6 78 9
01 23 4 5 67 89
01 23 4 5 67 8 9
01 23 4 5 678 9
01 23 4 56 789
01 23 4 56 7 89
01 23 4 56 7 8 9
01 23 4 56 78 9
01 23 4 567 89
01 23 4 567 8 9
01 23 4 5678 9
01 23 45 6789
01 23 45 6 789
01 23 45 6 7 89
01 23 45 6 7 8 9
01 23 45 6 78 9
01 23 45 67 89
01 23 45 67 8 9
01 23 45 678 9
01 23 456 789
01 23 456 7 89
01 23 456 7 8 9
01 23 456 78 9
01 23 4567 89
01 23 4567 8 9
01 23 45678 9
01 234 56789
01 234 5 6789
01 234 5 6 789
01 234 5 6 7 89
01 234 5 6 7 8 9
01 234 5 6 78 9
01 234 5 67 89
01 234 5 67 8 9
01 234 5 678 9
01 234 56 789
01 234 56 7 89
01 234 56 7 8 9
01 234 56 78 9
01 234 567 89
01 234 567 8 9
01 234 5678 9
01 2345 6789
01 2345 6 789
01 2345 6 7 89
01 2345 6 7 8 9
01 2345 6 78 9
01 2345 67 89
01 2345 67 8 9
01 2345 678 9
01 23456 789
01 23456 7 89
01 23456 7 8 9
01 23456 78 9
01 234567 89
01 234567 8 9
01 2345678 9
012 3456789
012 3 456789
012 3 4 56789
012 3 4 5 6789
012 3 4 5 6 789
012 3 4 5 6 7 89
012 3 4 5 6 7 8 9
012 3 4 5 6 78 9
012 3 4 5 67 89
012 3 4 5 67 8 9
012 3 4 5 678 9
012 3 4 56 789
012 3 4 56 7 89
012 3 4 56 7 8 9
012 3 4 56 78 9
012 3 4 567 89
012 3 4 567 8 9
012 3 4 5678 9
012 3 45 6789
012 3 45 6 789
012 3 45 6 7 89
012 3 45 6 7 8 9
012 3 45 6 78 9
012 3 45 67 89
012 3 45 67 8 9
012 3 45 678 9
012 3 456 789
012 3 456 7 89
012 3 456 7 8 9
012 3 456 78 9
012 3 4567 89
012 3 4567 8 9
012 3 45678 9
012 34 56789
012 34 5 6789
012 34 5 6 789
012 34 5 6 7 89
012 34 5 6 7 8 9
012 34 5 6 78 9
012 34 5 67 89
012 34 5 67 8 9
012 34 5 678 9
012 34 56 789
012 34 56 7 89
012 34 56 7 8 9
012 34 56 78 9
012 34 567 89
012 34 567 8 9
012 34 5678 9
012 345 6789
012 345 6 789
012 345 6 7 89
012 345 6 7 8 9
012 345 6 78 9
012 345 67 89
012 345 67 8 9
012 345 678 9
012 3456 789
012 3456 7 89
012 3456 7 8 9
012 3456 78 9
012 34567 89
012 34567 8 9
012 345678 9
0123 456789
0123 4 56789
0123 4 5 6789
0123 4 5 6 789
0123 4 5 6 7 89
0123 4 5 6 7 8 9
0123 4 5 6 78 9
0123 4 5 67 89
0123 4 5 67 8 9
0123 4 5 678 9
0123 4 56 789
0123 4 56 7 89
0123 4 56 7 8 9
0123 4 56 78 9
0123 4 567 89
0123 4 567 8 9
0123 4 5678 9
0123 45 6789
0123 45 6 789
0123 45 6 7 89
0123 45 6 7 8 9
0123 45 6 78 9
0123 45 67 89
0123 45 67 8 9
0123 45 678 9
0123 456 789
0123 456 7 89
0123 456 7 8 9
0123 456 78 9
0123 4567 89
0123 4567 8 9
0123 45678 9
01234 56789
01234 5 6789
01234 5 6 789
01234 5 6 7 89
01234 5 6 7 8 9
01234 5 6 78 9
01234 5 67 89
01234 5 67 8 9
01234 5 678 9
01234 56 789
01234 56 7 89
01234 56 7 8 9
01234 56 78 9
01234 567 89
01234 567 8 9
01234 5678 9
012345 6789
012345 6 789
012345 6 7 89
012345 6 7 8 9
012345 6 78 9
012345 67 89
012345 67 8 9
012345 678 9
0123456 789
0123456 7 89
0123456 7 8 9
0123456 78 9
01234567 89
01234567 8 9
012345678 9
0123456789

rеpne scasb · 31-01-2011, 18:01

■

rеpne scasb · 31-01-2011, 18:06

■

Noixe · 31-01-2011, 18:57

Interessante anche questo metodo, ma come dicevo prima, l'obiettivo del messaggio era quello di scrivere un codice funzionante.

Ecco la mia soluzione in C++:

Codice:

#include <iostream>
#include <string>

using namespace std;

string CombNumTel(string s, string t = "") {

   for (int i = 0; i < s.size() - 1; i++) {
       string pre = s.substr(0, i + 1) + " ";
       string post = s.substr(i + 1);
       cout << t << pre << post << endl;
       CombNumTel(post, t + pre);
   };

   return s;
}


int main() {

   cout << CombNumTel("1234") << endl;

   return 0;
}

31-01-2011, 09:55	#1
Noixe Member Iscritto dal: Aug 2008 Messaggi: 51	[Esercizio] Numeri di telefono Mi è venuto in mente questo simpatico esercizio. Quando bisogna leggere un numero di telefono, c'è chi lo fa cifra per cifra, chi legge due cifre per volta, chi magari ne legge prima tre e poi le rimanenti, etc... così mi sono chiesto: 1. Quanti sono tutti i modi possibili di leggere un numero di telefono? 2. Quale algoritmo è in grado di generarli tutti? Ad esempio dato il numero 1234 i modi possibili sono 8: 1 234 (uno duecentotrentaquattro) 1 2 34 (uno due trentaquattro) 1 2 3 4 (uno due tre quattro) 1 23 4 (uno ventitre quattro) 12 34 (dodici trentaquattro) 12 3 4 (dodici tre quattro) 123 4 (centoventitre quattro) 1234 (milleduecentotrentaquattro) Scrivere un algoritmo che data una stringa di numeri in input, generi i vari modi in cui le cifre possono essere raggruppate e lette. Infine scrivere quanti sono i modi possibili di leggere un numero di n cifre. Saluti P.S.: Questo messaggio va interpretato come un piccolo contest e non come una richiesta di risoluzione dei compiti per casa Ultima modifica di Noixe : 31-01-2011 alle 10:03.

31-01-2011, 14:15	#2
rеpne scasb Senior Member Iscritto dal: May 2008 Messaggi: 533	■ Ultima modifica di rеpne scasb : 18-06-2012 alle 17:14.

31-01-2011, 18:01	#6
rеpne scasb Senior Member Iscritto dal: May 2008 Messaggi: 533	■ Ultima modifica di rеpne scasb : 18-06-2012 alle 17:14.

31-01-2011, 18:06	#7
rеpne scasb Senior Member Iscritto dal: May 2008 Messaggi: 533	■ Ultima modifica di rеpne scasb : 18-06-2012 alle 17:14.

Strumenti
Mostra una versione stampabile Invia questa pagina per email