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

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

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

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

10.10.2012, 22:24. Просмотров 775. Ответов 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], и опять получается, что сравниваю со свеми подряд, включая тот минимальный в правом вверхнем углу.
вот собсно и проблемка: я не знаю как пропускать предидущие елементы
тут у меня только одна идея: создать масив в котором будут записыватся индексы уже прошедших елементов.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.10.2012, 22:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка элементов матрицы "треугольником" (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Класс "Матрицы: сортировка и другие преобразования" - C++
Я знаю, что такие вопросы обычно не приветствуются, но, всё же, извините за эту наглость. Не могу разобраться с условием : -...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - 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;, после замены столбца...

Дан массив из "n" элементов.Выполнить добавление элементов "k" в конец массива - C++
Вот начало,а дальше не знаю как { setlocale(LC_ALL, &quot;Russian&quot;); int n; // кол-во элементов массива cout &lt;&lt; &quot;Введите размер...

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

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.10.2012, 23:14
Ответ Создать тему
Опции темы

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