Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: (ст)Сортировка двумерного массива, пользуясь суммой элементов.  (Прочитано 15868 раз)
0 Пользователей и 1 Гость смотрят эту тему.
be3
Гость
« : 20-12-2005 11:19 » 

Дана матрица А размером 20x20. Считая ее составленной из 100 квадратов размером 2х2 и переставляя эти квадраты преобразовать А так, что бы в результирующей матрице для всяких двух квадратов B и C выполнялось следующее условие: если сумму элементов B, меньше суммы элементов С, то B лежит либо выше, либо левее (когда B и C на одной горизонтали) квадрата С.

Проблема состоит в написании и собственно в разработке алгоритма. Т.е. если бы условие было сортировать не всю матрицу по возрастанию, а допустим по столбцам все было бы гораздо проще.

Вот код который имею на данный момент...
Код:
...

Мне предложили некоторое решение моей задачки, но к сожалению оно так и осталось непонятным. Может у кого будут некоторые соображения по этому поводу.


Задача берётся влоб.
Заметим, что если получилась какая-то матрица, удовлетворяющая требуемым условиям, то транспонированная к ней тоже будет удовлетворять этим условиям, поэтому как сортировать - не важно. Итак, едем...
Код:
...
« Последнее редактирование: 30-04-2007 14:59 от Алексей1153++ » Записан
be3
Гость
« Ответ #1 : 22-12-2005 07:48 » 

Решение готово

Код:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
const int n=6;
typedef int Matrix[n][n];
/*ввод матрици с клавиатуры*/
void EnterMatrix(Matrix Matr){
for(int i=0; i<n; i++){
for (int j=0; j<n; j++){
    printf("Matr[%d,%d]",i,j);
      scanf("%d", &Matr[i][j]);
      }}}

/*Генерация эелементов матрицы*/
void GenerateMatrix(Matrix Matr){
int max, min;
printf("Vvedite diapozon zna4eniy\n max=");
scanf("%d", &max);
printf("\n min=");
scanf("%d", &min);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
   Matr[i][j]=random(max-min)+min;
   }
/*Вывод матрицы*/
void PrintMatrix(Matrix Matr){
for (int i=0; i<n; i++){
for( int j=0; j<n; j++){
      printf ("%d ", Matr[i][j]);
      }
      printf ("\n");
      }};

int sum(Matrix &Matr, int pos) {
int row = pos / (n / 2);
int column = pos % (n / 2);
row *= 2;
column *= 2;
int sum=Matr[row][column]+Matr[row][column+1]+Matr[row+1][column]+Matr[row+1][column+1];
return sum;
}
void swap(Matrix &Matr, int i, int j, int k, int z) {
int a = Matr[i][j];
Matr[i][j] = Matr[k][z];
Matr[k][z] = a;
}
void swap(Matrix &Matr, int pos1, int pos2) {
int row1 = pos1 / (n / 2);
int column1 = pos1 % (n / 2);
int row2 = pos2 / (n / 2);
int column2 = pos2 % (n / 2);
row1 *= 2;
column1 *= 2;
row2 *= 2;
column2 *= 2;
swap(Matr, row1, column1, row2, column2);
swap(Matr, row1, column1 + 1, row2, column2 + 1);
swap(Matr, row1 + 1, column1, row2 + 1, column2);
swap(Matr, row1 + 1, column1 + 1, row2 + 1, column2 + 1);
}
/*Сортировка матрицы по условию задачи*/
void Sortirovka(Matrix &Matr){
int sum1, sum2;
char is=1;
int i;
int len = (n * n) / 4 ;
 while(is)
 {
is=0;
for (i=1; i<len; i++) {
sum1 = sum(Matr, i);
sum2 = sum(Matr, i - 1);
if ( sum1 < sum2 )
{
swap(Matr, i, i - 1);
is=1;
}
}
 }
}


main(){
int dey=0;
Matrix M;
char ask;

do{
/*Выбор действия*/
printf("Viberite neobhodimoe deystvie i najmite ukazannuu klavi6u\n");
printf ("(a)Vvesti matricu s klaviaturi\n");
printf ("(b)Sgenirirovat' matricu\n");
printf ("(c)Vivesti matricu na ekran\n");
printf ("(d)Sortirovka\n");
printf ("(e)Exit\n");
scanf("%c", &ask);
switch(ask){
case 'a':{
printf("Vvod matrici s klaviaturi\n");
EnterMatrix(M);
printf ("Polu4ivwaysja matrica\n");
PrintMatrix(M);
dey=1;
getch();
break;
};
case 'b':{
printf ("Generacija matrici\n");
GenerateMatrix(M);
printf ("Polu4ivwaysja matrica\n");
PrintMatrix(M);
dey=1;
getch();
break;
};
case 'c':{
if (dey==1){
printf ("Vivod matrici\n");
PrintMatrix(M);
} else break;
getch();
break;
};
case 'd':{
if (dey==1){
printf ("Sortirovka po usloviu zada4i\n");
Sortirovka(M);
PrintMatrix(M);
} else break;
getch();
break;
};
};
} while (ask!='e');
}
« Последнее редактирование: 20-12-2007 16:17 от Алексей1153++ » Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #2 : 24-12-2005 20:40 » 

В третьем томе книги Д.Кнута "Искуство программирования" описывается помоему 32 алгоритма сортировки массивов. Выбирай на любой вкус. Самый быстрый для данных хранимых в памяти компьютера считается алгоритм побитовой сортировки. Количество полных проходов в нем зависит от разрядности сортируемых данных. Алгоритм имеет большой минус. Нужно его настраивать на сортируемые данные. Второй по быстроте алгоритм "Quick Sort". Этот алгоритм довольно часто встречается в реализациях библиотек. смысл такой: Берется элемент массива и выгоняется на свое место в массиве. т.е. если массив сортируется по возрастаюшей, то элементы меньше по индексу будут меньше контрольного элемента. Выше по индексу будут больше контрольного элемента. Дальше массив разбивается на две части. Первая часть те элементы которые меньше контрольного элемента. Вторая часть те элементы которые больше контрольного элемента. Производится сортировка уже этих частей по тому же алгоритму.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 22-04-2006 14:02 » new

(комент)

статья по алгоритмам сортировки?
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines