Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
213 / 202 / 85
Регистрация: 09.05.2012
Сообщений: 494
1

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

10.10.2012, 22:24. Показов 1826. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.10.2012, 22:24
Ответы с готовыми решениями:

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

Сортировка "Двумерных" векторов (матрицы) для Чайников
Приветствую, мне чужие коды на эту тему показались муторными, решил написать свою сортировку....

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

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов), которые разделяются...

8
573 / 556 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:29 2
Разбейте задачу на подзадачи.
1. обнуление главной диагонали
2. реализация функции, которая выдергивает из матрицы верхний или нижний треугольник данных и помещает его в обычный одномерный массив.
3. реализация функции сортировки обычного одномерного массива
4. реализация функции, которая вставляет уже отсортированный одномерный массив обратно в матрицу
1
213 / 202 / 85
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 22:36  [ТС] 3
хм... ну, тогда решение задачи дествительно выглядит проще. но вот накладные расходы: функции, дополнительная память под масивы. хотя... для таких програм как эта, "накладные" расходы почти незаметно повлияют на ее работу. но тем не менее повлияют
ну ладно, спасибо. попробую так, потом если получится, может быть даже както оптимизирую.
0
573 / 556 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:38 4
lowercase, борьба за такты?)
не торопитесь с оптимизацией. Вначале просто пишите правильный рабочий код
0
213 / 202 / 85
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 22:56  [ТС] 5
I.M., не то чтобы борьба за такты. просто, понимаете, у меня на 1 лабу по Си 2 пары дается. а я получается самый шустрый и 1 лабу делаю за 1 пару. вобще все задания, что в методичке, для меня кажутся детскими, вот мне препод и дал задачку потяжелее, чтобы я помучался. хотя он и ничего против, походу, иметь не будет, если я сделаю через функции, но мне кажется, что соль задачи была, в том, чтобы сделать это через циклы.
вот так то
0
573 / 556 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 22:59 6
lowercase, программы пишутся для людей, а не для компьютеров.
Вы бы в каком коде предпочли разбираться? где все сделано аккуратно через функции (классы и тд)
или где все сплошным текстом, с кучей вложенных циклов и условий
Вы бы смогли сходу сказать, что делает первый код и что делает второй код, не зная условия задания?
0
213 / 202 / 85
Регистрация: 09.05.2012
Сообщений: 494
10.10.2012, 23:05  [ТС] 7
I.M., естественно, я предпочел бы акуратно сделанный через функции код. более того, я зачастую так и делаю. сначало реализирую маленькие задачки в виде функций потом все это дело составляю воедино. так как это всего лишь лаба, то мне, чесно говоря, всеравно как делать. через циклы это скорее уже на смыкалку, дабы поразкинуть мозгами, чего скорее всего и требовал препод.
0
573 / 556 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
10.10.2012, 23:14 8
lowercase, не думаю, что он требовал писать запутанный и непонятный код)
хотя ваш препод - вам виднее.
для усложнения собственной жизни можете все это дело в класс обернуть, сделать динамический массив внутри, предусмотреть ввод чисел руками, из файла и рандомное заполнение. можно дать выбор, какую диагональ занулять. можно дать выбор сортировки по возрастанию и убыванию. много чего можно придумать)
0
Эксперт С++
4720 / 2541 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.10.2012, 23:14

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование)
Разработать программу с использованием наследования классов, реализующую классы: − воин;...

Сортировка элементов массива ("метод пузырьков")
const n=10; Var i, j: Integer; y:Integer; m: array of integer; Begin For i:=1 to n do begin...

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

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


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru