[C++] Piastrelle

Giovanni vuole piastrellare il suo bagno. Il suo bagno è grande lxN e lui vorrebbe piastrellarlo con piastrelle grandi 1×2 e 1X1. Giovanni vuole decidere come piastrellare il suo bagno. Stampa a Giovanni tutte le possibili piastrellature del bagno, in modo da aiutarlo a scegliere.

Input
Il ﬁle ‘input.txt’ è costituito da un unico numero N, la dimensione del bagno.

Output
In questo ﬁle devono comparire tante righe quante sono le possibili piastrellature del bagno. Ogni piastrellatura possibile deve essere stampata in questo modo. Se la piastrella è da 1X1, stampare [O] (senza virgolette). Se la piastrella è da 1X2, stampare [OOOO], senza virgolette. Le piastrellature devono essere stampate in ordine lessicograﬁco in base alla grandezza delle piastrelle.

Assunzioni 1 ≤ N ≤ 25

input.txt output.txt
4 [O][O][O][O]
[O][O][OOO]
[O][OOO][O]
[OOO][O][O]
[OOO][OOO]

Noi andremo, con una funzione ricorsiva, a scrivere riga per riga le piastrellature.
Se ci fate caso questo problema si basa sui numeri di Fibonacci; per risolvere il numero di Fibonacci ci sono due principali algoritmi: uno basato sulla ricorsione (molto lento) e uno molto veloce iterativo.
Risolvere questo problema iterativamente però è molto difficile, e considerato che in questo caso il massimo è 25 (numero relativamente basso) la soluzione ricorsiva non da problemi.

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <cassert>

#define p1 "[O]"
#define p2 "[OOOO]"

using namespace std;

int n;
ifstream in;
ofstream out;

void stampaPiastr(int n, string storia){
// stampa, una per riga, tutte le possibili diverse piastrallature del bagno 1xn.
// ciascuma prefissata dalla stringa <storia>

assert (n>=0);

    if (n==0) { // caso base
       out << storia <<"n";}
    else if (n==1) { // saso base
       out << storia+p1<<"n";}
    else {
       stampaPiastr(n-1, storia+p1);
       stampaPiastr(n-2, storia+p2);
    }
}

int main() {
in.open ("input.txt");
out.open ("output.txt");

in >> n;

stampaPiastr(n,"");

    return 0;
}

#include <cstdlib>

#include <iostream>

#include <fstream>

#include <string>

#include <cassert>

#define p1 "[O]"

#define p2 "[OOOO]"

using namespace std;

int n;

ifstream in;

ofstream out;

void stampaPiastr(int n, string storia){

// stampa, una per riga, tutte le possibili diverse piastrallature del bagno 1xn.

// ciascuma prefissata dalla stringa <storia>

assert (n>=0);

if (n==0) { // caso base

out << storia <<"n";}

else if (n==1) { // saso base

out << storia+p1<<"n";}

else {

stampaPiastr(n-1, storia+p1);

stampaPiastr(n-2, storia+p2);

}

int main() {

in.open ("input.txt");

out.open ("output.txt");

in >> n;

stampaPiastr(n,"");

return 0;

}

1984 è realtà ... e non solo in Cina

Firefox pulsante chiudi scheda a sinistra

VirtualBox: cartelle condivise su guest Linux

Ubuntu M10: alla scoperta del tablet

Effetto spada laser con Kdenlive [videoguida]