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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
#1

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

10.10.2012, 22:24. Просмотров 757. Ответов 8
Метки нет (Все метки)

Здраствуйте. Есть матртца размера 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++
const n=10; Var i, j: Integer; y:Integer; m: array of integer; Begin For i:=1 to n do begin m:=random(100); write(m:4); ...

Заменить столбцы, от первого до последнего, матрицы "x" на столбец матрицы "у" - C++
Добрый день! Необходимо заменить столбцы, от первого до последнего, матрицы &quot;x&quot; на столбец матрицы &quot;у&quot;, после замены столбца...

Уменьшение значений элементов матрицы(перегрузка операции "--") - C++
Задача Перегрузите операцию &quot;--&quot; позволяющую уменьшать переменную типа матрица на 1. В результате каждылемент матрицы должен...

Отсортировать каждый столбец матрицы по возрастанию элементов методом "пузырька" - C++
Здравствуйте!!! помогите, пожалуйста, написать программу на С++. дана матрица размерностью n на n, содержащая целые числа. отсортировать...

Задана матрица размером NxM. Определить количество "особых" элементов матрицы - C++
Помогите написать программу. Задана матрица размером NxM. Определить количество &quot;особых&quot; элементов матрицы, считая элемент &quot;особым&quot;, если...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:29     Сортировка элементов матрицы "треугольником" #2
Разбейте задачу на подзадачи.
1. обнуление главной диагонали
2. реализация функции, которая выдергивает из матрицы верхний или нижний треугольник данных и помещает его в обычный одномерный массив.
3. реализация функции сортировки обычного одномерного массива
4. реализация функции, которая вставляет уже отсортированный одномерный массив обратно в матрицу
lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 22:36  [ТС]     Сортировка элементов матрицы "треугольником" #3
хм... ну, тогда решение задачи дествительно выглядит проще. но вот накладные расходы: функции, дополнительная память под масивы. хотя... для таких програм как эта, "накладные" расходы почти незаметно повлияют на ее работу. но тем не менее повлияют
ну ладно, спасибо. попробую так, потом если получится, может быть даже както оптимизирую.
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:38     Сортировка элементов матрицы "треугольником" #4
lowercase, борьба за такты?)
не торопитесь с оптимизацией. Вначале просто пишите правильный рабочий код
lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 22:56  [ТС]     Сортировка элементов матрицы "треугольником" #5
I.M., не то чтобы борьба за такты. просто, понимаете, у меня на 1 лабу по Си 2 пары дается. а я получается самый шустрый и 1 лабу делаю за 1 пару. вобще все задания, что в методичке, для меня кажутся детскими, вот мне препод и дал задачку потяжелее, чтобы я помучался. хотя он и ничего против, походу, иметь не будет, если я сделаю через функции, но мне кажется, что соль задачи была, в том, чтобы сделать это через циклы.
вот так то
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:59     Сортировка элементов матрицы "треугольником" #6
lowercase, программы пишутся для людей, а не для компьютеров.
Вы бы в каком коде предпочли разбираться? где все сделано аккуратно через функции (классы и тд)
или где все сплошным текстом, с кучей вложенных циклов и условий
Вы бы смогли сходу сказать, что делает первый код и что делает второй код, не зная условия задания?
lowercase
212 / 201 / 34
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 23:05  [ТС]     Сортировка элементов матрицы "треугольником" #7
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++
Народ помогите! Половину алгоритма вроде написал, а дальше не могу:wall: Как в столбце найти &quot;особый&quot; элемент и завести для него счетчик? ...

Определить количество "особых" элементов матрицы - C++
Здравствуйте, господа! Тут такая тема, дана матрица a, нужно определить кол-во 'особых' элементов матрицы, считая элемент 'особым', если...

Задача на "закрашивание" некоторых элементов матрицы - C++
Имеется матрица чисел 0 и 1 - это некое изображение 0 - белый 1 - черный цвета. Если единицы образуют собой какую нибудь замкнутую область...

Подсчитать сколько элементов массива в каждой новой строке матрицы имеет значение "-1" - C++
Всем привет такая проблема: из двумерного массива сделал матрицу типа: 1-1 0 0-1-1 1 1 1 нужно подсчитать сколько элементов...


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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 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     Сортировка элементов матрицы "треугольником"
Ответ Создать тему
Опции темы

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