Laborator MD 5-6 [PDF]

Zitiervorschau

Ministerul Educaţiei al Republicii Moldova Universitatea Tehnică a Moldovei

Catedra: Automatica și Tehnologii Informaționale

RAPORT Lucrare de laborator Nr.4 la Matematica Discreta Tema:Algoritmi de determinare a dr.minim(maxim)

A efectuat:

st. gr. TI

A verificat:

lect.univ. Ceban G.

Chişinău 2015 Scopul lucrării:  Studierea algoritmilor de determinare a drumurilor minime într-un graf.

 Elaborarea programelor de determinare a drumului minim într-un graf ponderat.

Enuntul problemei: 1. Elaboraţi procedura introducerii unui graf ponderat; 2. Elaboraţi procedurile determinării drumului minim; 3. Realizaţi un program cu următoarele funcţii:  introducerea grafului ponderat cu posibilităţi de analiză sintactică şi semantică şi de corectare a informaţiei;  determinarea drumului minim;  extragerea informaţiei la display şi printer (valoarea drumului minim şi succesiunea vârfurilor care formează acest drum).

Listingul programului: #include #include #include typedef struct list { int info; struct list *adr; }list; list* pushList(list *prev_el, list *&head_el, int inf); list** saveList(int n, list **adi_list); void viewList(int n, list **adi_list); int** matInitiala(int **mat_ini, int n, int &k, list **adi_list); void drFord(int v_fin, int **mat_ini, int mat_res[100][100], int k, int val_init, int &lun_dr, int &nr_lin, int n); void algBK(int **mat_ini, int val_init, int v_start, int mat_res[100][100], int n, int k, int &lun_dr, int &nr_lin); void afisDrFord(int mat_res[100][100], int nr_lin); void afisDrBK(int mat_res[100][100], int nr_lin); int matDr(int n, int m, int **mat_ini); void cleanMem(int n, list **adi_list); int main() { list **adi_list; int n, k, v_pon, v_fin, val_init, lun_dr, nr_lin, v_start, opt, ex_max; int **mat_ini, mat_res[100][100]; FILE *fp; printf("Introduceti numarul de virfuri: "); scanf("%d", &n); adi_list = saveList(n, adi_list); mat_ini = matInitiala(mat_ini, n, k, adi_list); ex_max = matDr(n, k, mat_ini); system("cls"); do {

1

printf("***********************************************\n"); printf("* Alg.Ford si Alg. Bellman Kalaba *\n"); printf("***********************************************\n"); printf("* 1.Afisarea listei de adiacenta *\n"); printf("* 2.Afisarea drumului minim(F) *\n"); printf("* 3.Afisarea drumului maxim(F) *\n"); printf("* 4.Afisarea drumului minim(B-K) *\n"); printf("* 5.Afisarea drumului maxim(B-K) *\n"); printf("* 0.Iesire *\n"); printf("* *\n"); printf("***********************************************\n"); printf("Introduceti optiunea dorita: "); fflush(stdin); opt = getche(); switch(opt) { case '1': printf("\n"); viewList(n, adi_list); printf("Pentru a reveni apasa-ti orice tasta..."); getch(); system("cls"); break; case '2': printf("\nIntroduce-ti virful pina in care trebuie calculat dr.minim: "); scanf("%d", &v_fin); val_init = 2147483600; drFord(v_fin, mat_ini, mat_res, k, val_init, lun_dr, nr_lin, n); printf("\nLungimea drumului = %d\n", lun_dr); printf("\n"); afisDrFord(mat_res, nr_lin); printf("Pentru a reveni apasa-ti orice tasta..."); getch(); system("cls"); break; case '3': if(ex_max == 0) { printf("\nDrum maxim nu exista, pentru ca graful este cu circuite!"); printf("Pentru a reveni apasa-ti orice tasta..."); getch(); system("cls"); break; } printf("\nIntroduce-ti virful pina in care trebuie calculat dr.maxim: "); scanf("%d", &v_fin); val_init = -2147483600; drFord(v_fin, mat_ini, mat_res, k, val_init, lun_dr, nr_lin, n); printf("\nLungimea drumului = %d\n", lun_dr); printf("\n"); afisDrFord(mat_res, nr_lin); printf("Pentru a reveni apasa-ti orice tasta..."); getch(); system("cls"); break; case '4':

2

printf("\nIntroduce-ti virful din care trebuie calculat dr.minim: "); scanf("%d", &v_start); val_init = 2147483600; algBK(mat_ini, val_init, v_start, mat_res, n, k, lun_dr, nr_lin); printf("\nLungimea drumului = %d\n", lun_dr); printf("\n"); afisDrBK(mat_res, nr_lin); printf("Pentru a reveni apasa-ti orice tasta..."); getch(); system("cls"); break; case '5': if(ex_max == 0) { printf("\nDrum maxim nu exista, pentru ca graful este cu circuite!"); printf("Pentru a reveni apasa-ti orice tasta..."); getch(); system("cls"); break; } printf("\nIntroduce-ti virful din care trebuie calculat dr.maxim: "); scanf("%d", &v_start); val_init = -2147483600; algBK(mat_ini, val_init, v_start, mat_res, n, k, lun_dr, nr_lin); printf("\nLungimea drumului = %d\n", lun_dr); printf("\n"); afisDrBK(mat_res, nr_lin); printf("Pentru a reveni apasa-ti orice tasta..."); getch(); system("cls"); break; default: system("cls"); } }while(opt != '0'); return 0; } //Functia pentru adaugarea unui element intr-o lista cu parcurgerea de la inceput spre sfirsit list* pushList(list *prev_el, list *&head_el, int inf) { list *tmp = (list *)malloc(sizeof(list)); tmp->info = inf; tmp->adr = 0; if(prev_el == 0) head_el = tmp; else prev_el->adr = tmp; prev_el = tmp; return prev_el; } //Functia pentru introducerea listei de adiacenta list** saveList(int n, list **adi_list) { int i, inf;

3

list *prev_el, *head_el; adi_list = (list **)malloc(n * sizeof(list *)); for(i = 0; i < n; i++) { prev_el = head_el = 0; printf("%d |", i + 1); do { scanf("%d", &inf); prev_el = pushList(prev_el, head_el, inf); }while(inf != 0); adi_list[i] = head_el; } return adi_list; } //Functia pentru afisarea listei de adiacenta void viewList(int n, list **adi_list) { int i; list *curr_el; for(i = 0; i < n; i++) { curr_el = adi_list[i]; printf("%d |", i + 1); while(curr_el != 0) { printf("%d ", curr_el->info); curr_el = curr_el->adr; } printf("\n"); } } //Functia pentru generarea matricei initiale cu care mai apoi vom lucra int** matInitiala(int **mat_ini, int n, int &k, list **adi_list) { int i, v_pon; list *curr_el; k = 0; mat_ini = (int **)malloc(k * sizeof(int *)); printf("Introduceti ponderile: \n"); for(i = 0; i < n; i++) { curr_el = adi_list[i]; while(curr_el->info != 0) { printf("P[%d, %d] = ", i + 1, curr_el->info); scanf("%d", &v_pon); mat_ini = (int **)realloc(mat_ini, (k + 1) * sizeof(int *)); mat_ini[k] = (int *)malloc(4 * sizeof(int)); mat_ini[k][0] = i + 1; mat_ini[k][1] = curr_el->info; mat_ini[k][2] = v_pon; curr_el = curr_el->adr; k++; }

4

} return mat_ini; } //Functia pentru gasirea drumurilor minime si maxime(Alg.B-K) void algBK(int **mat_ini, int val_init, int v_start, int mat_res[100][100], int n, int k, int &lun_dr, int &nr_lin) { int i, j, ii, con, n_v, min, max, nr_dr, nr_el, nr_ap, pos_v, aux; int mat_luc[100][n]; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(i == j) mat_luc[i][j] = 0; else{ for(ii = 0; ii < k; ii++) { con = 0; if(mat_ini[ii][0] == i + 1 && mat_ini[ii][1] == j + 1) { mat_luc[i][j] = mat_ini[ii][2]; con = 1; break; } } if(con == 0) mat_luc[i][j] = val_init; } } } n_v = n; for(i = 0; i < n; i++) mat_luc[n_v][i] = mat_luc[i][n - 1]; con = 0; if(val_init > 0) { do { n_v++; for(j = 0; j < n - 1; j++) { min = val_init; for(i = 0; i < n; i++) if(i != j) if(mat_luc[j][i] != val_init && mat_luc[n_v - 1][i] != val_init) if(min > mat_luc[j][i] + mat_luc[n_v - 1][i]) min = mat_luc[j][i] + mat_luc[n_v - 1][i]; mat_luc[n_v][j] = min; } mat_luc[n_v][n - 1] = 0; con = 1; for(i = 0; i < n; i++) if(mat_luc[n_v - 1][i] != mat_luc[n_v][i])

5

{ con = 0; break; } }while(con != 1); }else{ do { n_v++; for(j = 0; j < n - 1; j++) { max = val_init; for(i = 0; i < n; i++) if(i != j) if(mat_luc[j][i] != val_init && mat_luc[n_v - 1][i] != val_init) if(max < mat_luc[j][i] + mat_luc[n_v - 1][i]) max = mat_luc[j][i] + mat_luc[n_v - 1] [i]; mat_luc[n_v][j] = max; } mat_luc[n_v][n - 1] = 0; con = 1; for(i = 0; i < n; i++) if(mat_luc[n_v - 1][i] != mat_luc[n_v][i]) { con = 0; break; } }while(con != 1); } lun_dr = mat_luc[n_v][v_start - 1]; nr_dr = 0; nr_el = 1; nr_lin = 0; mat_res[nr_dr][1] = v_start; do { do { nr_ap = 0; pos_v = -1; for(i = 0; i < n; i++) if(i != v_start - 1) if(mat_luc[n_v][v_start - 1] - mat_luc[v_start - 1][i] == mat_luc[n_v][i]) { nr_ap++; if(pos_v == -1) pos_v = i; } if(v_start != n) if(nr_ap > 1) { nr_el++; mat_res[nr_dr][nr_el] = pos_v + 1; mat_res[nr_dr][0] = nr_el;

6

do { nr_lin++; for(j = 0; j 1) { nr_el++; mat_res[nr_dr][nr_el] = mat_ini[pos_v][0]; mat_res[nr_dr][0] = nr_el; do { nr_lin++; for(j = 0; j < mat_res[nr_dr][0]; j++) mat_res[nr_lin][j] = mat_res[nr_dr][j]; aux = pos_v - 1; for(i = aux; i >= 0; i--) { if(v_fin == mat_ini[i][1] && mat_ini[i] [3] == 1) break; } pos_v = i; mat_res[nr_lin][mat_res[nr_dr][0]] = mat_ini[pos_v][0]; nr_ap--; }while(nr_ap != 1); v_fin = mat_res[nr_dr][mat_res[nr_dr][0]]; }else{ nr_el++; mat_res[nr_dr][nr_el] = mat_ini[pos_v][0]; mat_res[nr_dr][0] = nr_el; v_fin = mat_ini[pos_v][0]; } }while(v_fin != 1); nr_dr++; nr_el = mat_res[nr_dr][0]; v_fin = mat_res[nr_dr][nr_el]; }while(nr_dr != nr_lin + 1); } //Functia pentru afisarea drumurilor gasite cu ajutorul Alg.Ford void afisDrFord(int mat_res[100][100], int nr_lin) { int i, j; for(i = 0; i = 1; j--) printf("%d ", mat_res[i][j]); printf("\n"); } } //Functia pentru generarea matricei drumurilor int matDr(int n, int m, int **mat_ini)

9

{ int i, j, k; int mat_dr[n][n]; for(i = 0; i < n; i++) for(j = 0; j < n; j++) mat_dr[i][j] = 0; for (i = 0; i < m; i++) { mat_dr[mat_ini[i][0] - 1][mat_ini[i][1] - 1] = 1; } for (k = 0; k < n; k++) for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (mat_dr[i][j] == 0) mat_dr[i][j] = mat_dr[i][k] * mat_dr[k][j]; for (i = 0; i < n; i++) if(mat_dr[i][i] == 1) return 0; return 1; } //Eliberarea memoriei dinamice ocupate de toate elementele programului void cleanMem(int n, list **adi_list) { int i; list *curr_el, *prev_el; for(i = 0; i < n; i++) { curr_el = adi_list[i]; while(curr_el != 0) { //prev_el = curr_el; prev_el = curr_el->adr; free(curr_el); curr_el = prev_el; } } free(adi_list); }

Concluzie: In acest laborator a fost efectuat un porgram care calculeaza drumul minim(maxim) folosind Alg. (F) si Alg(B-K). Programul ne permite afisarea lungimii drumului si tuturor drumurilor posibile care corespund criteriului ales(dr.minim sau maxim). In final rezultatele pot fi vizualizate atit la display cit si scoase la printer rezultatele fiind automat salvate intr-un fisier de tip text.

10