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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.71
_д_м_и_т_р_и_й_
0 / 0 / 0
Регистрация: 11.02.2011
Сообщений: 35
#1

Определить, может ли при перестановке строк одной матрицы получится вторая - C++

15.08.2011, 17:07. Просмотров 4367. Ответов 21
Метки нет (Все метки)

Даны две матрицы одинаковых размеров. Определить, может ли при перестановке строк одной матрицы получится вторая. Помогите пожалуйста реализовать данную программу на Си, потому что сам я пока не могу сделать. Заранее всем спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.08.2011, 17:07
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определить, может ли при перестановке строк одной матрицы получится вторая (C++):

Может ли получится список тождественный исходному при перемешивании методом random.shuffle() - Python
Может ли при случайном перемешивании массива 1, 2, 3, 4, 5 при помощи метода random.shuffle() получиться массив 1, 2, 3, 4, 5? Нет, не...

Может ли при каких либо условиях вторая квадратичная форма равняться нулю? - Геометрия
может ли при каких либо условиях вторая квадратичная форма равняться нулю, если да то при каких условиях, и что это означает?

Сделать, чтобы при переходе с одной формы на другую, первая исчезала, а вторая оставалась - Delphi
Подскажите код чтобы при переходе с одной формы на другую. Чтобы первая исчезала ,а вторая оставалась.

При нажатии на кнопку одной формы, у меня должна выскочить вторая...как это написать в процедуре... - Delphi
При нажатии на кнопку одной формы, у меня должна выскочить вторая...как это написать в процедуре??? очень нужно помогите

Получить новую матрицу из произведений минимумов строк одной матрицы и максимумов столбцов другой матрицы - Pascal ABC
Пусть даны две вещественные матрицы порядка n. Получите новую мат- рицу следующим способом (для нахождения минимального элемента и...

Создать матрицы А[n,m] и B[n,m]. Определить суммы строк каждой матрицы.Переставить строки по возрастанию сумм строк в каждой матрице. - Pascal
Создать матрицы А и B. Определить суммы строк каждой матрицы. Переставить строки по возрастанию сумм строк в каждой матрице. ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
paskal
441 / 290 / 26
Регистрация: 15.08.2011
Сообщений: 853
15.08.2011, 18:02 #16
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Берём строку, сравниваем с каждой из строк 2-й матрицы, если есть такая же, переходим к другой строке, в итоге либо перебрав все строки 1-й матрицы поймём что они есть во 2-й либо какая та строка не будет содержаться - тогда матрицы не эквивалентны,
Это решение не полное. Во 2-й матрице могут попасться 2 одинаковые строки, тогда перестановки не существует, а ваш алгоритм скажет что существует.
Нужно создать вспомогательный одномерный массив, длина которого равна числу строк матриц. Перебирать поиском строки с 0-й по последнюю и если совпадение есть, записывать номер совпавшей строки во вспомогательный массив. Потом отсортировать его и проверить на последовательность 0,1,2...N-1. Если хоть раз совпадения не получилось, можно закончить с отрицательным ответом.
PointsEqual
ниначмуроФ
834 / 518 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
15.08.2011, 19:57 #17
можно отсортировать сначала строки матрицы, а потом по-элементно сравнить:
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
 
using namespace std;
 
/****************************
 Даны две матрицы одинаковых размеров.
 Определить, может ли при перестановке строк одной матрицы получится вторая
****************************/
 
 
 
 
const size_t SIZE = 3;
 
int** CreateMatrix(size_t nRow, size_t nCol)
{
    int** matrix = new int*[nRow];
    for (int i = 0; i < nRow; ++i)
    {
        matrix[i] = new int[nCol];
    }
 
    return matrix;
}
 
 
void ShowMatrix(int** matrix, size_t nRow, size_t nCol)
{
    for (int i = 0; i < nRow; ++i)
    {
        for (int j = 0; j < nCol; ++j)
        {
            cout << matrix[i][j] << "  ";
        }
        cout << endl;
    }
}
 
 
void InitMatrix(int** matrix, size_t nRow, size_t nCol)
{
    for (int i = 0; i < nRow; ++i)
        for (int j = 0; j < nCol; ++j)
            matrix[i][j] = 0;
}
 
 
void SwapPtr(int*& p1, int*& p2)
{
    int* tmp = p1;
    p1 = p2;
    p2 = tmp;
}
 
 
void SortRowsMatrix(int** matrix, size_t size)
{
    for (int i = 0; i < size; ++i)
    {
        for (int j = size-1; j > i; --j)
        {
            if (*matrix[j-1] > *matrix[j])
            {
                SwapPtr(matrix[j-1] , matrix[j]);
            }
        }
    }
}
 
 
bool IsEqual(int** matrix1, int** matrix2, size_t nRow, size_t nCol )
{
    for (int i = 0; i < nRow; ++i)
    {
        for (int j = 0; j < nCol; ++j)
        {
            if (matrix1[i][j] != matrix2[i][j])
                return false;
        }
    }
    return true;
}
 
 
int main()
{
    int** matrix = CreateMatrix(SIZE, SIZE);
    InitMatrix(matrix, SIZE, SIZE);
 
    matrix[0][0] = 600;
    matrix[0][1] = 2;
    matrix[0][2] = 3;
 
    matrix[1][0] = 8;
    matrix[1][1] = 7;
    matrix[1][2] = 6;
 
    matrix[2][0] = 345;
    matrix[2][1] = 78;
    matrix[2][2] = 23;
 
    SortRowsMatrix(matrix, SIZE);
    ShowMatrix(matrix, SIZE, SIZE);
 
    ////////////////////////////////////////////
    cout << endl;
    ////////////////////////////////////////////
 
    int** matrix2 = CreateMatrix(SIZE, SIZE);
    InitMatrix(matrix2, SIZE, SIZE);
 
    matrix2[0][0] = 345;
    matrix2[0][1] = 78;
    matrix2[0][2] = 23;
 
    matrix2[1][0] = 600;
    matrix2[1][1] = 2;
    matrix2[1][2] = 3;
 
    matrix2[2][0] = 8;
    matrix2[2][1] = 7;
    matrix2[2][2] = 6;
 
    ShowMatrix(matrix2, SIZE, SIZE);
 
    cout << endl;
 
 
    SortRowsMatrix(matrix2, SIZE);
    ShowMatrix(matrix2, SIZE, SIZE);
 
 
    IsEqual(matrix, matrix2, SIZE, SIZE) ? (cout << "Equal") : (cout << "NotEqual");
 
  //delete all matrix
 
 
    return 0;
}
-=ЮрА=-
Заблокирован
Автор FAQ
15.08.2011, 22:01 #18
Цитата Сообщение от PointsEqual Посмотреть сообщение
можно отсортировать сначала строки матрицы, а потом по-элементно сравнить:
- которыйраз встрчаю сортировки - они удлинняют время выполнения алгоритма, на мой взгляд нужно работать сразу с матрицами, притом есть ряд задач где исходная матрица должна оставаться таковой (даже если она не отсортированная)!

Добавлено через 2 минуты
Цитата Сообщение от paskal Посмотреть сообщение
Это решение не полное. Во 2-й матрице могут попасться 2 одинаковые строки, тогда перестановки не существует, а ваш алгоритм скажет что существует.
- С учётом этого изменил в своём алгоритме всего 1-но условие(а именно - если рядов несколько, то число найденных элементов превысит число столбцов), вот код на С...
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdio.h>
#include <conio.h>
 
void getmatr(int rows, int cols, int ** matr, char * name); 
bool scanrow(int rows, int cols, int ** matr, int * row);
void showrow(int cols, int *row);
 
int main()
{
    int rows, cols;
    int ** matr1, **matr2;
    bool is_row = false;
    char ch;
    do
    {
        printf("Enter num of rows: ");
        scanf("%d",&rows);
        printf("Enter num of cols: ");
        scanf("%d",&cols);
 
        matr1 = new int *[rows];
        matr2 = new int *[rows];
 
        for(int i = 0; i < rows; i++)
        {
            matr1[i] = new int[cols];
            matr2[i] = new int[cols];
        }
        printf("Enter matrix A\r\n");
        getmatr(rows, cols, matr1, "A");
 
        printf("Enter matrix B\r\n");
        getmatr(rows, cols, matr2, "B");
    
        printf("\tMatrix A\r\n");
        for(i = 0; i < rows; i++)
            showrow(cols, matr1[i]);
        printf("\tMatrix B\r\n");
        for(i = 0; i < rows; i++)
            showrow(cols, matr2[i]);
        for(i = 0; i < rows; i++)
        {
            if(!(is_row = scanrow(rows, cols, matr1, matr2[i])))
                break;
        }
        delete [] matr1;
        delete [] matr2;
 
        if(is_row && i == rows)
            printf("rows in matr2 is can be sorted in rows of matr1\r\n");
        else
            printf("matr1 not equal matr2\r\n");
        printf("[Y/N] Y - enter new matrixes\r\n");
        ch = getch();
    }
    while('Y' == ch || 'y' == ch);
    return 0;
}
 
void getmatr(int rows, int cols, int ** matr, char * name)
{
    for(int i = 0,j; i < rows; i++)
    {
        for(j = 0; j < cols; j++)
        {
            printf("%s[%02d][%02d] = ",name,i + 1, j + 1);
            scanf("%d",&matr[i][j]);
        }
    }
}
 
bool scanrow(int rows, int cols, int ** matr, int * row)
{
    bool ret = false;
    for(int i = 0,j, n; i < rows; i++)
    {
        n = 0;
        for(j = 0; j < cols; j++)
        {
            if(matr[i][j] == row[j])
                n++;
            else
                break;
        }
        if(cols < n)
            break;
    }
    if(n == cols)
        ret = true;
    return ret;
}
 
void showrow(int cols, int *row)
{
    for(int j = 0; j < cols; j++)
        printf("%d ",row[j]);
    printf("\r\n");
}
Листинг выполнения программы рассмотрел все случаи присутствия нескольких одинаковых строк)

Enter num of rows: 3
Enter num of cols: 3
Enter matrix A
A[01][01] = 1
A[01][02] = 2
A[01][03] = 3
A[02][01] = 4
A[02][02] = 5
A[02][03] = 6
A[03][01] = 7
A[03][02] = 8
A[03][03] = 9
Enter matrix B
B[01][01] = 4
B[01][02] = 5
B[01][03] = 6
B[02][01] = 7
B[02][02] = 8
B[02][03] = 9
B[03][01] = 1
B[03][02] = 2
B[03][03] = 3
Matrix A
1 2 3
4 5 6
7 8 9
Matrix B
4 5 6
7 8 9
1 2 3
matr1 not equal matr2
[Y/N] Y - enter new matrixes
Enter num of rows: 3
Enter num of cols: 3
Enter matrix A
A[01][01] = 1
A[01][02] = 2
A[01][03] = 3
A[02][01] = 1
A[02][02] = 2
A[02][03] = 3
A[03][01] = 4
A[03][02] = 5
A[03][03] = 6
Enter matrix B
B[01][01] = 4
B[01][02] = 5
B[01][03] = 6
B[02][01] = 1
B[02][02] = 2
B[02][03] = 3
B[03][01] = 7
B[03][02] = 8
B[03][03] = 9
Matrix A
1 2 3
1 2 3
4 5 6
Matrix B
4 5 6
1 2 3
7 8 9
matr1 not equal matr2
[Y/N] Y - enter new matrixes
Enter num of rows: 3
Enter num of cols: 3
Enter matrix A
A[01][01] = 1
A[01][02] = 2
A[01][03] = 3
A[02][01] = 1
A[02][02] = 2
A[02][03] = 3
A[03][01] = 4
A[03][02] = 5
A[03][03] = 6
Enter matrix B
B[01][01] = 1
B[01][02] = 2
B[01][03] = 3
B[02][01] = 1
B[02][02] = 2
B[02][03] = 3
B[03][01] = 4
B[03][02] = 5
B[03][03] = 6
Matrix A
1 2 3
1 2 3
4 5 6
Matrix B
1 2 3
1 2 3
4 5 6
matr1 not equal matr2
[Y/N] Y - enter new matrixes
grizlik78
Эксперт С++
1908 / 1440 / 111
Регистрация: 29.05.2011
Сообщений: 2,996
15.08.2011, 22:33 #19
-=ЮрА=-, а почему во всех случаях в выводе результат "matr1 not equal matr2"? Это так и должно быть?
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
16.08.2011, 08:28 #20
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
вот код на С...
C++
1
2
3
4
5
        matr1 = new int *[rows];
        matr2 = new int *[rows];
 
        delete [] matr1;
        delete [] matr2;
Когда это операторы new и delete стали входить в состав языка Си???
-=ЮрА=-
Заблокирован
Автор FAQ
16.08.2011, 09:58 #21
Цитата Сообщение от Olga_ Посмотреть сообщение
Когда это операторы new и delete стали входить в состав языка Си???
- когда это писал ориентировался на то что в большинстве случаев память учат выделять оператором new, я конечно мог malloc и realloc ввести или ещё чего нибудь поизвращеннёй, но задачи это бы не упростило
-=ЮрА=-
Заблокирован
Автор FAQ
16.08.2011, 10:20 #22
Цитата Сообщение от grizlik78 Посмотреть сообщение
-=ЮрА=-, а почему во всех случаях в выводе результат "matr1 not equal matr2"? Это так и должно быть?
Нет, я не додумал ввести 1-о условие (обнулять счётчик нужно лишь в том случае если он меньше числа столбцов, иначе нужно смотреть дальше есть ли похожие строки)
C++
1
2
if(n < cols)
            n = 0;
, прототип scanrow с учётом этого условия должен быть таким
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool scanrow(int rows, int cols, int ** matr, int * row)
{
    bool ret = false;
    for(int i = 0,j, n; i < rows; i++)
    {
        if(n < cols)
            n = 0;
        for(j = 0; j < cols; j++)
        {
            if(matr[i][j] == row[j])
                n++;
            else
                break;
        }
        if(cols < n)
            break;
    }
    if(n == cols)
        ret = true;
    return ret;
}
Скриншот работы прилагаю
Миниатюры
Определить, может ли при перестановке строк одной матрицы получится вторая  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.08.2011, 10:20
Привет! Вот еще темы с ответами:

Определить может ли конь перейти с одной шахматной доски на другую - Turbo Pascal
Даны координаты (как целые от 1 до 8) двух различных полей шахматной доски. Если конь за один ход может перейти с одной доски на другую то...

Почему в IDE может не получится после компиляции исполняемый файл? - C Linux
В статье про установку CodeBlocks написано, что если при его установке поставить галку в строке MinGW то он (MinGW) установится сразу...

Найти последовательность слов из которых может получится заданное слово - JavaScript
Даны заданное слово и непустая последовательность слов (одномерный символьный массив): между словами запятые или пробелы, в конце точка. В...

Какова вероятность, что на карточка вынутых по одной получится 325? - Теория вероятностей
Какова вероятность, что на трех карточкаx, вынутых по одной и положенных в порядке их появления получим число 325, если всего карточек...


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

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

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