Комбинаторные алгоритмы для программистов



             

Сортировки - часть 3


Алгоритм реализован на Turbo C++. //#include <graphics.h> #include <stdlib.h> //#include <string.h> #include <stdio.h> #include <conio.h> //#include <math.h> #include <dos.h> #include <values.h> #include <iostream.h>

const n=4,//кол-во строк m=4; //столбцов

int m1[n][m]; //исходный массив struct mas{int i,i1;}; //i-индекс сравниваемой строки с i1 строкой mas a[n*2]; //массив типа mas, где будут лежать сестры, пример) a[1].i и a[1].i1 - сестры

void main() {clrscr(); int i,j; randomize(); for( i=0;i<n;i++) for( j=0;j<m;j++) m1[i][j]=random(2); //случайным образом в массив заносим цифры

for(i=0;i<n;i++) {printf("\n %d) ",i); for(int j=0;j<m;j++) printf(" %d",m1[i][j]); //распечатываем этот массив } int min, p; //индекс минимального элемента после s-го элемента i-ой строки //сортировка строк массива по возрастанию for(i=0;i<n;i++)//i-сортировка i-ой строки { for(int s=0;s<m-1;s++) {min=m1[i][s+1]; for(int j=s;j<m;j++) if(m1[i][j]<=min){min=m1[i][j];p=j;} //запоминаем минимальный элемент в ряде после s-го элемента if(m1[i][s]>=min) {m1[i][p]=m1[i][s];m1[i][s]=min;} //меняем местами s-й и p-й элемент,если s-й>p-го(минимального) }

}

printf("\n"); for(i=0;i<n;i++) {printf("\n %d) ",i); for(int j=0;j<m;j++) printf(" %d",m1[i][j]); //выводим отсортированный массив } int s=0 //сколько элементов в i-й строке совпадают с эл-ми i1 строки, k=0; //сколько строк совпали int i1; for(i=0;i<n-1;i++) //верхняя строка i for( i1=i+1;i1<n;i1++) //нижняя строка i1 {s=0; for(int j=0;j<m;j++) //сравнение идет по j-му столбцу // ! ! if(m1[i][j]==m1[i1][j])s++; //если соответствующие элементы в //i-й и i1-й строки совпадают, то кол-во совпавших увеличивается на 1 if(s==m){a[k].i=i;a[k].i1=i1;k++;} //если все элементы i-й и i1-й строки совпали, то они сестры }

printf("\nСестры :"); for(i=0;i<k;i++) printf("\n %d и %d",a[i].i,a[i].i1); //распечатываем a[i].i-ю и a[i].i1-ю сестру getch(); }




Содержание  Назад  Вперед