Blue Flower

Scrivere un programma che consenta di disporre otto regine su una scacchiera di 8x8 celle senza che nessuna metta sotto scacco un'altra.
Soluzione:

Gli algoritmi di backtracking, sono algoritmi che trovano la soluzione di specifici problemi, senza seguire una regola computazionale fissa; essi procedono per tentativi.

Generalmente si decompone il procedimento in vari obiettivi parziali come nel caso degli algoritmi di ricerca , inoltre si fa uso di funzioni ricorsive, cioè, funzioni che invocano loro stesse; nel caso il tentativo effettuato non sia andato a buon fine.

Il problema delle otto regine è un classico esempio di uso dei metodi per tentativi.

Fu studiato, ma non completamente risolto da Gauss nel 1850, anche perchè la caratteristica di questi problemi è che 'sfuggono' a soluzioni analitiche.

In breve: otto regine devono essere disposte su una scacchiera di 8x8 celle senza che nessuna metta sotto scacco un'altra.

Scegliamo una opportuna rappresentazione dei dati, poiché è noto dalle regole degli scacchi che una regina può mangiare tutti i pezzi che si trovano nella sua colonna, nella sua riga o su una delle sue diagonali, si deduce che ogni colonna potrà contenere una ed una sola regina. 
Dovendo operare con 8 regine, 8 righe ed 8 colonne, è pressoché obbligatorio dichiarare la costante 

const int n = 8;

Per controllare se una regina non si trova sotto scacco di altre già precedentemente piazzate si elabora la seguente funzione

bool sicura(int regina, int riga){ 
for (int i = 0; i < regina; i++){ 
   // ricava la posizione della regina nella riga iesima 
   int xriga = T[i]; 
   //stessa riga o stessa diagonale 
   if (xriga == riga || xriga == riga - (regina - i) || 
   xriga == riga + (regina - i)) 
   return false; } 
return true; 
}//fine sicura() 


int regina è una variabile che identifica la k-esima regina delle 8 totali
int riga è il valore della riga dove si è deciso di piazzare la regina.
Se la regina si trova sotto scacco viene restituito false altrimenti true e il pezzo viene considerato in una posizione sicura.
Il programma procede per colonne su ognuna delle quali viene disposta una regina, la riga viene individuata dalla seguente funzione:

void tenta(int k){ 
   if (k < n){ 
      for (int i = 0; i < n; i++) 
         if (sicura(k, i)){ T[k] = i; tenta(k + 1); }//fine if 
}else{ 
   for (int i = 0; i < n; i++) cout << T[i] ; 
   cout << endl; 
}//fine else 
}//fine tenta() 

Viene usato il vettore T[k] che memorizza la colonna dove si trova la k-esima regina, poi per tentativi si esplorano tutte le righe dalla 0 alla 7 ( n-1 ) dove sia possibile posizionare il pezzo. 
Se il pezzo finisce in una posizione sicura, si passa alla regina successiva con l'istruzione

tenta(k + 1);

ovviamente ci sarà una regina per ogni colonna ( n=8 ) l'intera procedura viene avviata dal main() con l'istruzione

tenta(0);

e con 0 si intende la regina con indice 0 in colonna 0. 
Per ogni colonna saranno possibili diverse combinazioni qui rappresentiamo solo le prime 10 soluzioni
0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4
0 6 3 5 7 1 4 2
0 6 4 7 1 3 5 2
1 3 5 7 2 0 6 4
1 4 6 0 2 7 5 3
1 4 6 3 0 7 5 2
1 5 0 6 3 7 2 4
se consideriamo la prima soluzione che parte dalla colonna 0:



Una soluzione ovvia, sarebbe stata quella di rappresentare la scacchiera con una matrice quadrata; ma un esame più attento rivela che questa rappresentazione rende più difficile controllare la disponibilità delle posizioni. Considerando che questa operazione è quella più frequentemente eseguita è stato necessario scegliere una rappresentazione che permetta di verificare le posizioni nel modo più semplice possibile.

#include < iostream > 
using namespace std; 
const int n = 8; 
int T[n];//vettore rappresentativo delle 8 righe 

// Controlla se la posizione è sicura 
bool sicura(int regina, int riga){ 
   // Controlla se ogni regina precedente alla attuale 
   // non si trovi sulla stessa riga o su una delle diagonali 

   for (int i = 0; i < regina; i++){ 
   // ricava la posizione della regina nella riga iesima 
   int xriga = T[i]; 
   // stessa riga o stessa diagonale 
   if (xriga==riga || 
       xriga == riga - (regina - i) || 
       xriga == riga + (regina - i)) 
    return false; 

return true; 
}//fine sicura() 

void tenta(int k){ 
if (k < n){ 
   for (int i = 0; i < n; i++) 
   // prima di inserire la k-esima regina in una riga 
   // controlla se la posizione scelta è sicura 

      if (sicura(k, i)){ 
      T[k] = i; 
      tenta(k + 1);// posiziona un'altra regina 
    }//fine if 
}else{ 
// le n=8 regine sono posizionate (stampa) 
   for (int i = 0; i < n; i++) cout << T[i] << " "; 
   cout << endl; 
}//fine else 
}//fine tenta 

main(){ 
   tenta(0);//regina iniziale in colonna 0 
}

Scrivere un programma che inserito un numero intero, scriva a schermo se il numero è primo o no. Nel caso il numero non sia primo il programma deve stampare la sua fattorizzazione. Ad esempio 12=2*2*3.
Soluzione:


Prima si valuta se il numero è primo tramite la funzione

bool numeroprimo(int n)

All'interno di tale funzione il programma scrive a schermo se il numero è primo o no. Se il numero non è primo viene mandata in esecuzione la funzione

void dec(int n)

che ne stamperà la fattorizzazione.
Nella funzione dec(n) il valore n del numero n viene posto nella variabile temporanea p (p=n) il contatore i viene incrementato da 2 a p/2. 
Se i è un divisore di p, i viene stampato e il successivo valore di p vale p/i. 
Se i è un divisore di p, dopo la sua stampa i viene decrementato (e poi successivamente incrementato). 
Senza questo ultimo accorgimento potremmo non accorgerci che p possa essere più volte divisibile per i. 


#include < iostream >
using namespace std; 
bool numeroprimo(int n){ 
bool p=true; 
for(int i=2;i < n/2;i++) 
    if(n%i==0)p=false; 
       if(p)cout << "numero primo\n"; else cout << "NON primo\n"; 
return p; 

void dec(int n){ 
int p,i; 
bool primo; 
p=n; 
i=2; 
primo=true; 
do{ 
   if(p%i==0){ 
      if(primo==true)cout << i; 
      else cout << "*" << i; 
      p=p/i; i--; 
      primo=false; 

i++; 
}while(i < n/2); }//fine dec 
main(){ 
int n,i,p; 
bool primo=true; 
cout << "ins.num:";cin >> n; 
primo=numeroprimo(n); 
if(!primo)dec(n); 
}

Scrivi un programma di battaglia navale che si svolga fra un giocatore e il PC che si svolga su una matrice di 10x10 celle e che preveda per ciascuna parte l'utilizzo della seguente flotta:
1 nave da 4 celle
2 navi da 3 celle
2 navi da 2 celle
1 nave da 1 cella 

Il programma simula lo svogimento di una battaglia navale fra un giocatore e il computer, la battaglia si svolge su una matrice di 10x10 celle. 
La numerazione delle coordinate delle celle è coerente con il sistema di indicizzazione della matrice stessa; per cui la cella in alto a sinistra sarà indicata con coordinate 0,0 quella in basso a destra con coordinate 9,9. 
L'inserimento di coordinate maggiori di 9 o minori di 0 causa istantanemanete l'interruzione della partita..

Il gioco si svolge (per ciascun giocatore) con

1 nave da 4 celle 
2 navi da 3 celle 
2 navi da 2 celle 
1 nave da 1 cella 

Il principale problema che si pone, riguarda la collocazione delle navi entro i limiti della matrice 10x10, seguito dalla necessità di non far intersecare fra di loro le navi collocate sulla scacchiera 10x10. 

La collocazione delle navi avviene in due modi: in modo random sul lato del PC e tramite il caricamento da tastiera sul lato dell'utente.
Il PC usa una matrice M[int][int]  per disporre le sue navi 
Questa matrice di interi viene prima di tutto inizializzata con tutte le celle a 0 dalla funzione
iniz(char T[n][n],int M[n][n],int H[n][n],int HPC[n][n])
che si occupa di resettare anche tutte le altre matrici di interi presenti.
In questa struttura sarà indicata col valore 1, la cella occupata da una nave; con il valore 0 una cella libera.. 
Il caricamento della matrice M del PC viene eseguito dalla funzione
set(int M[n][n])
che si occupa di collocare in modo random tutte le 6 navi. Ovviamente, si fa ampio uso dei generatori di numeri casuali 
srand(); rand(); con particolare attenzione a rispettare i limiti dell'array e a non collocare navi su celle già occupate; la prima nave, quella da 4 celle, è l'unica a non avere questo problema.
Si usano dei cicli do-while per ritentare la disposizione di una nave qualora essa risulti in collisione con un'altra nave già disposta. La matrice 
T[char][char]
è solo rappresentativa dei tiri del giocatore, viene inizializzata riempiendo le celle col carattere '=' questo carattere commuta nel simbolo 'X' quando l'utente colpisce la nave del PC.  Questa gestione avviene nel ciclo do-while principale all'interno del main() dove appaiono le istruzioni:
if(M[i][j]==1){T[i][j]='X';M[i][j]=0;conta++;} 
    else T[i][j]='0';
 
è evidente che la matrice T è in relazione con la matrice M; quando una nave del PC viene colpita la corrispondente cella in M viene azzerata e la stessa cella viene indicata con la lettera X sulla struttura T. 
In fase di avvio si nota l'istruzione carica(H); che è una vera e propria procedura per collocare le navi sulla scacchiera del giocatore in modo manuale. 
Il giocatore deve indicare la cella iniziale dove disporre la nave e l'orientamento della stessa; usando convenzionalmente lo 0 per il senso orizzontale e l'1 per il senso verticale. In ogni caso la cella iniziale rappresenta la cella più a sinistra nel caso orizzontale, mentre viene intesa come la cella più in alto nel caso del senso verticale..
In questa procedura si notano dei cicli do-while in abbinamento con la variabile booleana 'valido' che ha il compito di verificare che la nave sia nei limiti della scacchiera e che non ci siano intersezioni con le altre navi.
La matrice H dell'utente viene utilizzata (inevitabilmente) durante l'esecuzione del tiro del PC
bool lancioPC(int H[n][n],int HPC[n][n]);
All'interno di questa funzione, H viene confrontata con una sua omologa HPC che il PC usa per capire se il suo tiro è andato a segno oppure no. 
La funzione lancioPC restituisce un valore booleano true se il PC ha colpito una nave del giocatore o false in caso contrario. Il programma è impostato in modo tale da eseguire un beep del suo speaker nel caso sia stata colpita una nave del giocatore. Simultaneamente sulla matrice H, dove il giocatore ha messo le sue navi e che viene stampata a video scomparirà il simbolo '1' corrispondente alla cella colpita dal PC col suo tiro. 

Si può notare che il PC, nell'esecuzioni dei suoi tiri, non segue una particolare politica; esso si limita a tirare in modo casuale nell'insieme di celle non non ha ancora tirato. Viene lasciato come sviluppo futuro l'implementazione di una strategia di combattimento più efficace da parte del PC.
Nel main() si nota la presenza di due variabili intere:
conta e contaPC ovviamente inizializzate a 0, che valutano la vittoria del giocatore o del PC al raggiungimento dela 15sima cella colpita; infatti la somma delle celle per le suddette navi disposte sulla singola scacchiera del giocatore o del PC è appunto 15. 
Si fa notare che il codice commentato nella funzione print() :
/* for(i=0;i < n;i++){//stampa M 
              for(j=0;j < n;j++) cout << M[i][j]; 
               cout << endl; 
}*/
 

permette di visualizzare oltre alla struttura H e T anche la matrice M della disposizione delle navi 'pensata' dal PC. Invece la funzione 
void p(int H[n][n]) 
è una procedura di stampa di servizio usata soltanto durante l'esecuzione della funzione carica(int H[n][n]) che in via preliminare permette all'utente di collocare le sue navi sulla sua scacchiera. 

#include<iostream> 
#include<time.h>
#include<stdlib.h> 
const int n=10; 
using namespace std; 
bool lancioPC(int H[n][n],int HPC[n][n]);//tira il PC 
void p(int H[n][n]);//funzione di stampa ausiliaria 
void print(char T[n][n],int M[n][n],int H[n][n]);//stampa
//reset di T ed M H ed HPC 
void iniz(char T[n][n],int M[n][n],int H[n][n],int HPC[n][n]); 
void set(int M[n][n]);//matrice del computer 
void carica(int H[n][n]);//matrice del giocatore 

main(){ 
bool exit=false, colpito=false; 
int i,j; 
char T[n][n],ch; 
int M[n][n],H[n][n],HPC[n][n],conta=0,contaPC=0; 
//inizializz. e caricamento navi lato giocatore 
iniz(T,M,H,HPC); 
set(M); 
carica(H); 
//inizio gioco
do{ 
system("CLS"); 
print(T,M,H); 
cout << "riga:";cin >> i; 
cout << "colonna:";cin >> j; 
if(i >= 0 && j >= 0 && i < n && j < n)
   if(M[i][j]==1){T[i][j]='X';M[i][j]=0;conta++;} 
   else T[i][j]='0'; 
else exit=true; 
colpito=lancioPC(H,HPC); 
if(colpito){contaPC++; cout << "\a" << flush;} 
if(conta==15){cout << "HAI VINTO!!!";print(T,M,H);break;}
if(contaPC==15){cout << "ha vinto il PC";print(T,M,H);break;}
}while(exit!=true); 
} //fine main 
void p(int H[n][n]){ 
int i,j; 
for(i=0;i < n;i++){//stampa T 
for(j=0;j < n;j++)cout << H[i][j]; 
cout << endl; 
}
}//fine p 

void print(char T[n][n],int M[n][n],int H[n][n]){ 
int i,j; 
for(i=0;i < n;i++){//stampa T 
for(j=0;j < n;j++) cout << T[i][j]; 
cout << endl; 

/* for(i=0;i < n;i++){//stampa M 
for(j=0;j < n;j++) cout << M[i][j]; 
cout << endl; 
}*/ 

cout << "----------" << endl; 
for(i=0;i < n;i++){//stampa H 
for(j=0;j < n;j++) cout << H[i][j]; 
cout << endl; } 
}//fine print
 


void iniz(
char T[n][n],int M[n][n],int H[n][n],int HPC[n][n]){ 
int i,j; 
for(i=0;i < n;i++)//iniz.T 
   for(j=0;j < n;j++) T[i][j]='='; 

for(i=0;i < n;i++)//iniz.M 
   for(j=0;j < n;j++) M[i][j]=0; 

for(i=0;i < n;i++)//iniz.H 
   for(j=0;j < n;j++) H[i][j]=0; 

for(i=0;i < n;i++)//iniz.HPC 
   for(j=0;j < n;j++) HPC[i][j]=0; 
}//fine iniz 

void set(int M[n][n]){ 
bool occupato=false; 
int row,col,i,j,s; 
srand(time(0));
//caricamento nave da 4 
s=rand()%2; 
row=rand()%7; 
col=rand()%7; 
if(s==0)for(j=col;j < col+4;j++)M[row][j]=1; 
else for(i=row; i < row+4;i++)M[i][col]=1; 
//caricamento 2 navi da 3 
for(i=0;i < 2;i++){ 
do{ 
occupato =false; 
s=rand()%2; 
row=rand()%8; 
col=rand()%8; 
if(M[row][col]!=0)occupato=true; 
else{ 
   if(s==0){ if(M[row][col+1]!=0 || M[row][col+2]!=0)occupato=true; 
   else { M[row][col]=1;M[row][col+1]=1;M[row][col+2]=1;} 
}else{ 
if(M[row+1][col]!=0 || M[row+2][col]!=0)occupato=true; 
else { M[row][col]=1;M[row+1][col]=1;M[row+2][col]=1;} 


}while(occupato==true); }//fine for 
//caricamento 2 navi da 2 
for(i=0;i < 2;i++){ 
do{ 
occupato =false; 
s=rand()%2; 
row=rand()%8; 
col=rand()%8; 
if(M[row][col]!=0)occupato=true; 
else{ 
if(s==0){ 
   if(M[row][col+1]!=0)occupato=true; else {    M[row][col]=1;M[row][col+1]=1;} 
}else{ 
   if(M[row+1][col]!=0)occupato=true; 
else { M[row][col]=1;M[row+1][col]=1;} 


}while(occupato==true); }//fine for 

//caricamento una nave da 1 
do{ 
occupato =false; 
row=rand()%10; 
col=rand()%10; 
if(M[row][col]!=0)occupato=true; 
else M[row][col]=1; 
}while(occupato==true); //fine caricamento una nave da 1 
}//fine set(M) 

void carica(int H[n][n]){ 
//'valido' controlla che la nave sia nei limiti della matrice 
//e che non vada a collidere con altre navi 

bool occupato=false, 
valido=false; 
int row,col,i,j,s; 
do{//caricamento nave da 4 
valido=false; 
cout<<"riga iniz.nave da 4:";cin>>row; 
cout<<"colonna iniz.nave da 4:";cin>>col; 
cout<<"orientamento (0/1):";cin>>s; 
if(row >= 0 && col >= 0 && row < n && col < n){ 
if(s==0 && col+4 < n){ 
   for(j=col;j < col+4;j++)H[row][j]=1; 
   valido=true;system("CLS");p(H); 

if(s==1 && row+4 < n){ 
for(i=row;i < row+4;i++)H[i][col]=1; 
system("CLS");valido=true;p(H); 

}else valido=false; 
}while(valido!=true); 
//fine caricamento nave da 4 
for(i=0;i < 2;i++){//caricamento 2 navi da 3 
do{ 
valido=false; 
cout<<"riga iniz.nave da 3:";cin>>row; 
cout<<"colonna iniz.nave da 3:";cin>>col; 
cout<<"orientamento (0/1):";cin>>s; 
if(row >= 0 && col >= 0 && row < n && col < n){ 
   if(H[row][col]==0){ 
   if(s==0 && col+2 < n && H[row][col+1]==0 && H[row][col+2]==0){
      for(j=col;j < col+3;j++)H[row][j]=1; 
      system("CLS");
      valido=true;p(H); 
   } 
   if(s==1 && row+2 < n && H[row+1][col]==0 && H[row+2][col]==0){
   for(j=row;j < row+3;j++)H[j][col]=1; 
   system("CLS");
   valido=true;p(H); 
   } 
}else valido=false; 
}else valido=false; 
}while(valido==false); 
}//fine caricamento 2 navi da 3 

for(i=0;i<2;i++){//caricamento 2 navi da 2 
do{ 
valido=false; 
cout<<"riga iniz.nave da 2:";cin>>row; 
cout<<"colonna iniz.nave da 2:";cin>>col; 
cout<<"orientamento (0/1):";cin>>s; 
if(row >= 0 && col >= 0 && row < n && col < n){ 
if(H[row][col]==0){ 
if(s==0 && col+1 < n && H[row][col+1]==0){ 
   for(j=col;j < col+2;j++)H[row][j]=1; 
   system("CLS");
   valido=true;p(H); 
   } 
if(s==1 && row+1 < n && H[row+1][col]==0){ 
   for(j=row;j < row+2;j++)H[j][col]=1; 
   system("CLS");valido=true;p(H); 
   } 
}else valido=false; 
}else valido=false; 
}while(valido==false); 
}//fine caricamento 2 navi da 2 

do{//caricamento una nave da 1 
valido=false; 
cout<<"riga nave da 1:"; cin>>row; 
cout<<"colonna nave da 1:";cin>>col; 
if(H[row][col]!=0)valido=false; 
else {H[row][col]=1;valido=true;} 
}while(valido==false); //fine caricamento una nave da 1 
}//fine carica(H) 

bool lancioPC(int H[n][n],int HPC[n][n]){ 
bool valido=false; 
int row,col; 
bool trovato=false; 
srand(time(0)); 
do{ 
   valido=false; 
   row=rand()%10; 
   col=rand()%10; 
   if(HPC[row][col]==1)valido=false; 
   else {valido=true;HPC[row][col]=1;} 
   if(valido) 
      if(H[row][col]==1){ H[row][col]=0;trovato=true;} }while(valido==false); 
return trovato; 
}//fine lancioPC 

Scrivi un programma che acquisisca un numero intero da tastiera, lo passi ad una funzione che dovrà ritornarlo al programma chiamante sotto forma di un vettore ad 8 posizioni rappresentativo del numero binario corrispondente all'intero ricevuto (conversione decimale-binario) e poi dovrà stamparlo.
Soluzione:

#include<iostream>
using namespace std; 
const int n=10; 
void decbin(int j,int L[n]);//prototipo 
main(){ 
int i,q, T[n]={0,0,0,0,0,0,0,0,0,0}; 
bool h=false; 
//acquisizione del numero intero decimale da tastieracout<<"Inserisci numero intero:";cin>>q;
if(q>511)cout<<"Conversione impossibile"; 
else{ 
decbin(q,T);//invocazione della funzione
//converte in binario il numero iniziale 
//stampo T dalla prima cifra !=0 partendo da sn
for(i=0;i<n;i++) 
    if(T[i]||h){ 
        cout<<T[i]; 
        h=true; 
        } 
cout<<" versione binaria di "<<q; 
}//fine else se q<511 
}//fine main 

void decbin(int j,int L[n]){ 
int i=1,pos; 
if(j<0) j=j*(-1); 
do{ 
    L[n-i]=j%2; 
    j=j/2; 
    i++; 
}while(j!=0); 
}//fine decbin 

Qui si è deciso per una funzione void 'decbin' che riceve come parametri il numero da convertire 'q' passato per valore e il vettore 'T' che comunque viene passato per indirizzo; lo dimostra il fatto che pur non ritornando alcun valore specifico la 'decbin
' modifica implicitamente il vettore T (i vettori vengono sempre e comunque passati per riferimento alle funzioni) .
L'algoritmo per la stampa di T è condizionato dall'esigenza di non stampare gli zeri superflui che si trovano nella parte sinistra di T.
La variabile binaria h è inizializzata a false, il ciclo for inizia la sua scansione partendo da sinistra nel vettore l'elemento attuale del vettore può essere stampato solo se T[i]=1 oppure se h=true; la prima ricorrenza uguale a 1 trovata nel vettore viene stampata, in quel momento h viene posta a true e da lì in poi tutti i numeri successivi contenuti nel vettore vengono stampati, 
sia che siano 0 o 1.

Scrivi un programma per ridurre ai minimi termini una frazione. 
Numeratore e denominatore devono essere passati per indirizzo ad una funzione che li modificherà, la funzione deve restituire il numeratore e il denominatore che descrivono la frazione ridotta ai minimi termini.
Soluzione:

#include<iostream>
using namespace std; 
void fun(int &n,int &d);//prototipo 
main(){ 
int num=350,den=45;//n=num d=den, i contatore 
fun(num,den); 
cout<<num<<"/"<<den<<endl;
cout<<(float)num/den;
}//fine main
void fun(int &n,int &d){ 
int i=2; 
int min;//il più basso fra num e den
do{
   if(n>d)min=d; 
   else min=n; 
     if((n%i==0)&&(d%i==0)){ 
          n=n/i; 
          d=d/i; 
     }else i++; 
}while(i<=min); 
}//fine fun