Laborator 10

Problema

Scrieti un program recursiv care afiseaza toate modurile in care un numar natural pozitiv poate sa fie scris cu suma de 1, 2 si 3, indiferent de ordine.

Exemplu:

5 poate fi scris in 5 moduri:

1+1+1+1+1

1+1+1+2

1+2+2

1+1+3

2+3

Problema 1

Un participant la un joc de noroc porneste avand la start o suma de bani A. La fiecare tura a jocului, jucatorul poate pierde sau castiga o suma in valoare fixa B. Sa se gaseasca toate posibilele variante de desfasurare a jocului (secvente pierdere - castig), astfel incat dupa N runde, jucatorul sa aiba aceeasi suma de bani (A) ca la start. A, B si N se citesc de la tastatura.

Problema 2

Intre N orase exista o retea de drumuri care permite ca dintr-un oras sa se ajunga in oricare din celelalte. Intre 2 orase exista cel mult un drum direct, de lungime cunoscuta, iar timpul necesar pentru parcurgerea unui drum este proportional cu lungimea sa. Se cere sa se realizeze programul pentru determinarea traseului pe care se poate merge intre doua orase date, intr-un timp minim. Datele se citesc de la tastatura sau dintr-un fisier.

Problema 3

Se considera o suprafata caroiata de dimensiune N x N, in care fiecare patrat are una din culorile galben, rosu, albastru sau verde. Configuratia suprafetei se citeste de la tastatura (sau dintr-un fisier). Sa se determine si sa se tipareasca daca exista drumuri (minime) intre colturile opuse. Un drum trebuie sa cuprinda doar patrate de aceeasi culoare, deplasarea dintr-un patrat putandu-se face in oricare dintre cei maxim opt vecini.

Rezolvare problema:

#include <stdio.h> #include <stdlib.h> int n,nrSolutii,solutii[100]; void afisareSolutie(int nr) { int i; nrSolutii++; printf("Solutia nr %d: ",nrSolutii); printf("%d",solutii[1]); for(i=2;i<=nr;i++) printf("+%d",solutii[i]); printf("\n"); } void back(int i,int sumaPartiala) { int j; if(sumaPartiala==n) afisareSolutie(i-1); else for(j=1;j<=n-sumaPartiala;j++) if(j>=solutii[i-1]) if(j<4) { solutii[i]=j; back(i+1,sumaPartiala+j); } } int main() { printf("n=");scanf("%d",&n); nrSolutii=0; back(1,0); printf("Sunt %d solutii",nrSolutii); return 0; }

Rezolvare problema 1:

#include<stdlib.h>

#include<stdio.h>

int A ; // suma de bani initiala int B ; // suma de bani pe care o poate castiga respectiv pierde int N ; // numarul de runde int runde[100]; void afisare() { static int nrCazuri=1; int i; printf("\n\nCazul %d:",nrCazuri++); for(i=0;i<N;i++) { if(runde[i]==0) printf("\nPierde"); if(runde[i]==1) printf("\nCastiga"); } } void joc(int nrRundaCurenta,int sumaCurenta) { if(sumaCurenta>=B) { if(nrRundaCurenta==N) { if(sumaCurenta==A) afisare(); } else { runde[nrRundaCurenta]=0 ; //pierde suma B joc(nrRundaCurenta+1,sumaCurenta-B); runde[nrRundaCurenta]=1; //castiga suma B joc(nrRundaCurenta+1,sumaCurenta+B); } } } int main() {

printf("Hello world!\n");

printf("Suma initiala: ");scanf("%d",&A); printf("Blind-ul: ");scanf("%d",&B); printf("Numarul de runde: ");scanf("%d",&N); joc(0,A); return 0; }

Rezolvare problema 2:

#include<stdlib.h> #include<stdio.h> int cost[100][100] ; int drum[100] ; int n; int max=1000000; int orasInitial; int orasFinal; int vizitat[100] ; void citire() { FILE *f ; f=fopen("bac.txt","r"); if(f==NULL) { printf("Eroare la deschiderea fisierului de intrare"); exit(1); } fscanf(f,"%d",&n); int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) fscanf(f,"%d",&cost[i][j]); fclose(f); } void afisare(int pas) { int costTotal=0,i; printf("\n"); for(i=0;i<pas;i++) { costTotal=costTotal+cost[vizitat[i]][vizitat[i+1]]; printf("%d-",vizitat[i]); } printf("%d",vizitat[pas]); printf(" Costul total:%d",costTotal); if(costTotal<max) { max=costTotal; for(i=0;i<=pas;i++) drum[i]=vizitat[i]; } } void min() { int i=0; printf("\nMinim: "); while(drum[i]!=0) printf("%d-",drum[i++]); } int valid(int pas) { int i; for(i=0;i<pas;i++) if(vizitat[i]==vizitat[pas]) return 0; if(cost[vizitat[pas-1]][vizitat[pas]]==0) return 0; return 1; } void back(int pas) { if(vizitat[pas-1]==orasFinal) afisare(pas-1); else { int i; for(i=1;i<=n;i++) { vizitat[pas]=i; if(valid(pas)) back(pas+1); } } } int main() { printf("Hello world!\n"); citire(); orasInitial=4 ; orasFinal=2; vizitat[0]=orasInitial; back(1); min(); return 0; }

Rezolvare problema 3

Incercare:

#include<stdlib.h> #include<stdio.h> int tab[100][100]; int drum[100][100]; int vizitat[100][100]; int n; int pasi; int min[100]; int x[]={ 1, 1, 1, 0, 0, -1, -1, -1}; int y[]={-1, 0, 1, 1, -1, -1, 0, 1}; enum color { X, A, G, R, V }; void afisare() { int i,j; printf("\nSolutie!"); for(i=1;i<=n;i++) { printf("\n"); for(j=1;j<=n;j++) printf("%d ",drum[i][j]); } } void citeste() { FILE *f; f=fopen("bac.txt", "r"); fscanf(f,"%d",&n); printf("n=%d\n",n); int i, j; char aux ; fscanf(f,"%c",&aux); for(i=1;i<=n;i++) { printf("\n"); for(j=1;j<=n;j++) { fscanf(f,"%c",&aux); printf("%c",aux); switch(aux) { case 'A' : tab[i][j] = A ; break; case 'G' : tab[i][j] = G ; break; case 'R' : tab[i][j] = R ; break; case 'V' : tab[i][j] = V ; } } fscanf(f,"%c",&aux); } printf("\n"); for(i=1; i<=n; i++) { printf("\n"); for(j=1;j<=n ;j++) printf("%d",tab[i][j]); } } void back(int pas, int lin, int col) { drum[lin][col] = pas ; if((lin==1)&&(col==n)) { printf("\nExista minim! %d\n",pas); afisare(); printf("\n-------------------------------------------------------"); } else { int i; for(i=0; i<8; i++) { if((tab[lin+x[i]][col+y[i]] != 0) && (drum[lin+x[i]][col+y[i]] == 0) && (tab[lin+x[i]][col+y[i]] == tab[n][1])) { drum[lin+x[i]][col+y[i]] = pas+1; back(pas+1, lin+x[i], col+y[i]) ; drum[lin+x[i]][col+y[i]] = 0; } } } } int main() { printf("Hello world!); citeste(); back(1, n, 1); return 0; }