Numeri di telefono

[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

 

[Noixe]

Ecco la mia soluzione:

#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;
}