МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра АСУ
Розрахункова робота з дисципліни: "Алгоритми та структури даних " Завдання 10. (Гето) Комендант фортеці виходить з центрального приміщення і перевіряє як солдати чергують на постах. При цьому він, проходячи всі пости, не проходить двічі по жодній ділянці маршруту і кожен пост відвідує лише один раз. Який маршрут коменданта?
Текст програми #include <stdio.h> #include <math.h> #include <stdlib.h> #include <conio.h> #define MAX 16 int funck(int mas[][MAX],int i,int j) { int k=0,m; int **mas1=(int **) malloc(MAX*sizeof(int)); mas1[0]=(int*) malloc(MAX* MAX* sizeof(int)); for (i=1;i<MAX;i++) { mas1[i]=mas[0]+i*MAX; } for (i=0;i<MAX;i++) { // printf("%d ",mas1[i][j]); for (j=0;j<MAX;j++) { mas1[i][j]=mas[i][j]; // printf("%d ",mas1[i][j]); } printf ("\n"); } i=0; j=0; while (k!=15) { j=0; while (i!=j) { if (mas1[i][j]==1) mas1[i][j]=3; j++; } k++; mas1[i][j]=2; //mas1[j][i]=2; printf (" %d",k); // if (i==15) return 0; i++; } printf ("\n"); for (i=0;i<MAX;i++) { for (j=0;j<MAX;j++) { printf("%d ",mas1[i][j]); } printf ("\n"); } return k; } int main(void) { clrscr(); int mas[MAX][MAX]; int nr,buf, nc,k, j,nom,i; mas[0][0]=0; mas[0][1]=1; mas[0][2]=0; mas[0][3]=0; mas[0][4]=0; mas[0][5]=0; mas[0][6]=0; mas[0][7]=0; mas[0][8]=0; mas[0][9]=0; mas[0][10]=0; mas[0][11]=0; mas[0][12]=0; mas[0][13]=0; mas[0][14]=0; mas[0][15]=0; mas[1][0]=1; mas[1][1]=0; mas[1][2]=1; mas[1][3]=0; mas[1][4]=0; mas[1][5]=1; mas[1][6]=1; mas[1][7]=1; mas[1][8]=0; mas[1][9]=0; mas[1][10]=0; mas[1][11]=0; mas[1][12]=0; mas[1][13]=0; mas[1][14]=0; mas[1][15]=0; mas[1][16]=0; mas[1][17]=0; mas[2][0]=0; mas[2][1]=1; mas[2][2]=0; mas[2][3]=1; mas[2][4]=0; mas[2][5]=0; mas[2][6]=0; mas[2][7]=1; mas[2][8]=1; mas[2][9]=0; mas[2][10]=0; mas[2][11]=0; mas[2][12]=0; mas[2][13]=0; mas[2][14]=0; mas[2][15]=0; mas[3][0]=0; mas[3][1]=0; mas[3][2]=1; mas[3][3]=0; mas[3][4]=1; mas[3][5]=0; mas[3][6]=0; mas[3][7]=0; mas[3][8]=1; mas[3][9]=1; mas[3][10]=0; mas[3][11]=0; mas[3][12]=0; mas[3][13]=0; mas[3][14]=0; mas[3][15]=0; mas[4][0]=0; mas[4][1]=0; mas[4][2]=0; mas[4][3]=1; mas[4][4]=0; mas[4][5]=1; mas[4][6]=0; mas[4][7]=0; mas[4][8]=0; mas[4][9]=1; mas[4][10]=1; mas[4][11]=0; mas[4][12]=0; mas[4][13]=0; mas[4][14]=0; mas[4][15]=0; mas[4][16]=0; mas[4][17]=0; mas[5][0]=0; mas[5][1]=1; mas[5][2]=0; mas[5][3]=0; mas[5][4]=1; mas[5][5]=0; mas[5][6]=1; mas[5][7]=0; mas[5][8]=0; mas[5][9]=0; mas[5][10]=1; mas[5][11]=0; mas[5][12]=0; mas[5][13]=0; mas[5][14]=0; mas[5][15]=0; mas[6][0]=0; mas[6][1]=1; mas[6][2]=0; mas[6][3]=0; mas[6][4]=0; mas[6][5]=1; mas[6][6]=0; mas[6][7]=1; mas[6][8]=0; mas[6][9]=0; mas[6][10]=1; mas[6][11]=1; mas[6][12]=0; mas[6][13]=0; mas[6][14]=0; mas[6][15]=0; mas[7][0]=0; mas[7][1]=1; mas[7][2]=1; mas[7][3]=0; mas[7][4]=0; mas[7][5]=0; mas[7][6]=1; mas[7][7]=0; mas[7][8]=0; mas[7][9]=0; mas[7][10]=0; mas[7][11]=0; mas[7][12]=1; mas[7][13]=0; mas[7][14]=0; mas[7][15]=0; mas[8][0]=0; mas[8][1]=0; mas[8][2]=1; mas[8][3]=1; mas[8][4]=0; mas[8][5]=0; mas[8][6]=0; mas[8][7]=1; mas[8][8]=0; mas[8][9]=1; mas[8][10]=0; mas[8][11]=0; mas[8][12]=0; mas[8][13]=1; mas[8][14]=0; mas[8][15]=0; mas[9][0]=0; mas[9][1]=0; mas[9][2]=0; mas[9][3]=1; mas[9][4]=1; mas[9][5]=0; mas[9][6]=0; mas[9][7]=0; mas[9][8]=1; mas[9][9]=0; mas[9][10]=1; mas[9][11]=0; mas[9][12]=0; mas[9][13]=0; mas[9][14]=1; mas[9][15]=0; mas[10][0]=0; mas[10][1]=0; mas[10][2]=0; mas[10][3]=0; mas[10][4]=1; mas[10][5]=1; mas[10][6]=1; mas[10][7]=0; mas[10][8]=0; mas[10][9]=1; mas[10][10]=0; mas[10][11]=1; mas[10][12]=0; mas[10][13]=0; mas[10][14]=0; mas[10][15]=1; mas[11][0]=0; mas[11][1]=0; mas[11][2]=0; mas[11][3]=0; mas[11][4]=0; mas[11][5]=0; mas[11][6]=1; mas[11][7]=0; mas[11][8]=0; mas[11][9]=0; mas[11][10]=1; mas[11][11]=0; mas[11][12]=1; mas[11][13]=0; mas[11][14]=0; mas[11][15]=1; mas[12][0]=0 ; mas[12][1]=0; mas[12][2]=0; mas[12][3]=0; mas[12][4]=0; mas[12][5]=0; mas[12][6]=0; mas[12][7]=1; mas[12][8]=0; mas[12][9]=0; mas[12][10]=0; mas[12][11]=1; mas[12][12]=0; mas[12][13]=1; mas[12][14]=0; mas[12][15]=0; mas[13][0]=0; mas[13][1]=0; mas[13][2]=0; mas[13][3]=0; mas[13][4]=0; mas[13][5]=0; mas[13][6]=0; mas[13][7]=0; mas[13][8]=1; mas[13][9]=0; mas[13][10]=0; mas[13][11]=0; mas[13][12]=1; mas[13][13]=0; mas[13][14]=1; mas[13][15]=0; mas[14][0]=0; mas[14][1]=0; mas[14][2]=0; mas[14][3]=0; mas[14][4]=0; mas[14][5]=0; mas[14][6]=0; mas[14][7]=0; mas[14][8]=0; mas[14][9]=1; mas[14][10]=0; mas[14][11]=0; mas[14][12]=0; mas[14][13]=1; mas[14][14]=0; mas[14][15]=1; mas[15][0]=0; mas[15][1]=0; mas[15][2]=0; mas[15][3]=0; mas[15][4]=0; mas[15][5]=0; mas[15][6]=0; mas[15][7]=0; mas[15][8]=0; mas[15][9]=0; mas[15][10]=1; mas[15][11]=1; mas[15][12]=0; mas[15][13]=0; mas[15][14]=1; mas[15][15]=0; for (i=0;i<MAX;i++) { for (j=0;j<MAX;j++) { printf("%d ",mas[i][j]); } printf ("\n"); } funck(mas,0,0); //printf("%d", k=per(mas)); return 0; } Результат:
Висновок: у даній розрахунковій роботі я розглянув і реалізував алгоритм розв’язування практичної задачі із проходження по одному шляху один раз.Я малюнок розглянув як граф,і записав його як матрицю суміжностей.Потім я проходив по матриці по суміжних прямих ребрах по одному разу,і якщо я на цій точці є перший раз то ставив 2,а на суміжні ставив 3,і так робив поки не пройшов по всій матриці.