Форум программистов, компьютерный форум CyberForum.ru

Сортировка элементов матрицы "треугольником" - C++

Восстановить пароль Регистрация
 
lowercase
 Аватар для lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 22:24     Сортировка элементов матрицы "треугольником" #1
Здраствуйте. Есть матртца размера N, нужно на главной диагонали сделать нули, а елементы которые остались побоках диагонали отсортировать "треугольником"(если повенуть матрицу на 45% против часовой стрелки то над диагональю будет треугольник) чобы на верху треугольника был елемент с найменьшим значением, потом в каждом новом ряду елементы возрастали слева на право. Вобще сортировка вроде похожа на зизагом но не то
Например есть матрица:
0 1 5 4
3 2 7 6
3 0 1 4
1 3 4 2
должно быть вот так:
0 5 4 1
3 0 6 4
1 3 0 7
0 3 4 0
у меня программа сортирует но только в рамках одного "строчки" треугольника, то есть, вместо должного получается вот так:
0 1 5 4
4 0 4 6
3 3 0 7
1 3 0 0
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#define N 4
 
void print_matrix(int x[N][N]){
    int i, j;
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            printf("%d%s", x[i][j], j == N - 1 ? "\n" : " ");
}
void swap(int* x, int* y){
    int t = *x;
    *x= *y;
    *y = t;
}
int main(){
    int x[N][N] = {
        { 0, 1, 5, 4 },
        { 3, 2, 7, 6 },
        { 3, 0, 1, 4 },
        { 1, 3, 4, 2 },
    };
    print_matrix(x);
    int i, j, k, ci, cj;
    for(i = 0; i < N; i++)
        x[i][i] = 0;
    printf("\n");
 
    for(k = 0; k < N; k++)
        for(i = 0, j = N - k; i < k && j < N; i++, j++)
            for(ci = i, cj = j; ci < k && cj < N; ci++, cj++){
                if(x[ci][cj] < x[i][j])
                    swap(&x[ci][cj], &x[i][j]);
 
                if(x[cj][ci] > x[j][i])
                    swap(&x[cj][ci], &x[j][i]);
            }
 
    print_matrix(x);
    getch();
}
Помогите отсортировать матрицу, или каким нибудь советом, по поводу того, как это можно сделать.

Добавлено через 21 минуту
только что определил диапазоны индексов масива для циклов:
i,j,k уже было, вот они:
k = (0, n - 1)
i = (0, k)
j = (n - k, n);
при чем i и j должны меняся синхронно.
дальше таким образом нужно сравнивать каждый елемент x[i][j] с остальными елементами, x[ci][cj](как при обычной сортировке), диапазон ci = (0, n - 1), для каждого ci, cj = (ci + 1, n)
итого получаю такую струтуру циклов:
C
1
2
3
4
5
6
7
8
9
for(k = 0; k < N; k++)
    for(i = 0, j = N - k; i < k && j < N; i++, j++)
        for(ci = 0; ci < N - 1; ci++)
            for(cj = ci + 1; cj < N; cj++){
                if(x[ci][cj] < x[i][j])
                    swap(&x[ci][cj], &x[i][j]);
                if(x[cj][ci] > x[j][i])
                    swap(&x[cj][ci], &x[j][i]);
        }
но тут вот вчем загвоздка: независимо от того где я нахожусь(i, j), сравниваются также элементы которые уже были отсортированы и стоят на нужных местах. то есть, например, я сначало в правый верхний угол (x[0][3]) записал минимальный елемент. далее, по алгоритму я выбераю, например, елемент x[0][2], и опять получается, что сравниваю со свеми подряд, включая тот минимальный в правом вверхнем углу.
вот собсно и проблемка: я не знаю как пропускать предидущие елементы
тут у меня только одна идея: создать масив в котором будут записыватся индексы уже прошедших елементов.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.10.2012, 22:24     Сортировка элементов матрицы "треугольником"
Посмотрите здесь:

C++ Уменьшение значений элементов матрицы(перегрузка операции "--")
C++ Определить количество "особых" элементов матрицы
отсортировать каждый столбец матрицы по возрастанию элементов методом "пузырька" C++
В одномерном массиве состоящим из "N" вещественных элементов вычислить сумму элемента массива с не четными "N" C++
C++ Определить количество "особых" элементов матрицы
C++ Подсчитать сколько элементов массива в каждой новой строке матрицы имеет значение "-1"
C++ Задача на "закрашивание" некоторых элементов матрицы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:29     Сортировка элементов матрицы "треугольником" #2
Разбейте задачу на подзадачи.
1. обнуление главной диагонали
2. реализация функции, которая выдергивает из матрицы верхний или нижний треугольник данных и помещает его в обычный одномерный массив.
3. реализация функции сортировки обычного одномерного массива
4. реализация функции, которая вставляет уже отсортированный одномерный массив обратно в матрицу
lowercase
 Аватар для lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 22:36  [ТС]     Сортировка элементов матрицы "треугольником" #3
хм... ну, тогда решение задачи дествительно выглядит проще. но вот накладные расходы: функции, дополнительная память под масивы. хотя... для таких програм как эта, "накладные" расходы почти незаметно повлияют на ее работу. но тем не менее повлияют
ну ладно, спасибо. попробую так, потом если получится, может быть даже както оптимизирую.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:38     Сортировка элементов матрицы "треугольником" #4
lowercase, борьба за такты?)
не торопитесь с оптимизацией. Вначале просто пишите правильный рабочий код
lowercase
 Аватар для lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 22:56  [ТС]     Сортировка элементов матрицы "треугольником" #5
I.M., не то чтобы борьба за такты. просто, понимаете, у меня на 1 лабу по Си 2 пары дается. а я получается самый шустрый и 1 лабу делаю за 1 пару. вобще все задания, что в методичке, для меня кажутся детскими, вот мне препод и дал задачку потяжелее, чтобы я помучался. хотя он и ничего против, походу, иметь не будет, если я сделаю через функции, но мне кажется, что соль задачи была, в том, чтобы сделать это через циклы.
вот так то
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:59     Сортировка элементов матрицы "треугольником" #6
lowercase, программы пишутся для людей, а не для компьютеров.
Вы бы в каком коде предпочли разбираться? где все сделано аккуратно через функции (классы и тд)
или где все сплошным текстом, с кучей вложенных циклов и условий
Вы бы смогли сходу сказать, что делает первый код и что делает второй код, не зная условия задания?
lowercase
 Аватар для lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 23:05  [ТС]     Сортировка элементов матрицы "треугольником" #7
I.M., естественно, я предпочел бы акуратно сделанный через функции код. более того, я зачастую так и делаю. сначало реализирую маленькие задачки в виде функций потом все это дело составляю воедино. так как это всего лишь лаба, то мне, чесно говоря, всеравно как делать. через циклы это скорее уже на смыкалку, дабы поразкинуть мозгами, чего скорее всего и требовал препод.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 23:14     Сортировка элементов матрицы "треугольником" #8
lowercase, не думаю, что он требовал писать запутанный и непонятный код)
хотя ваш препод - вам виднее.
для усложнения собственной жизни можете все это дело в класс обернуть, сделать динамический массив внутри, предусмотреть ввод чисел руками, из файла и рандомное заполнение. можно дать выбор, какую диагональ занулять. можно дать выбор сортировки по возрастанию и убыванию. много чего можно придумать)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.10.2012, 23:14     Сортировка элементов матрицы "треугольником"
Еще ссылки по теме:

Класс "Матрицы: сортировка и другие преобразования" C++
Задана матрица размером NxM. Определить количество "особых" элементов матрицы C++
C++ Сортировка элементов массива ("метод пузырьков")
C++ Дан массив из "n" элементов.Выполнить добавление элементов "k" в конец массива

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.10.2012, 23:14     Сортировка элементов матрицы "треугольником" #9
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#define N 4
 
void print_matrix(int x[N][N]){
    int i, j;
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            printf("%d%s", x[i][j], j == N - 1 ? "\n" : " ");
}
void swap(int* x, int* y){
    int t = *x;
    *x= *y;
    *y = t;
}
int main(){
    int x[N][N] = {
        { 0, 1, 5, 4 },
        { 3, 2, 7, 6 },
        { 3, 0, 1, 4 },
        { 1, 3, 4, 2 },
    };
    print_matrix(x);
    int i, j, a, b, ci, cj;
    for(i = 0; i < N; i++)
        x[i][i] = 0;
    printf("\n");
 
    for(j=N-1; j>0; j--)
        for(i=0; i<N-j; i++)
        {
            ci=i; cj=j+i;
            for(a=i+1; a<N-j; a++)
                if(x[a][j+a]<x[ci][cj])
                {
                    ci=a; cj=j+a;
                }
            for(b=j-1; b>0; b--)
                for(a=0; a<N-b; a++)
                    if(x[a][b+a]<x[ci][cj])
                    {
                        ci=a; cj=b+a;
                    }           
            swap(&x[ci][cj], &x[i][j+i]);
                
 
        }        
 
    print_matrix(x);
    getch();
    return 0;
}
Yandex
Объявления
10.10.2012, 23:14     Сортировка элементов матрицы "треугольником"
Ответ Создать тему
Опции темы

Текущее время: 00:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru