Alagert уточни в каком именно виде и как хранится матрица, и в каком ее надо записать.

Матрица записана след образом:

Код

int * matrix =new int[m*n]; //for example for(int=0;i<m*n;i++) matrix[i]=i;

т.е была матрица: 1 2 3
4 5 6

записана в массив будет в виде : 1 2 3 4 5 6
после траспонирования: 1 4
2 5
3 6
в массиве будет: 1 4 2 5 3 6

Пасибо за вариант, ща буду его разбирать.

Это сообщение отредактировал(а) Alagert - 8.1.2006, 22:55

Алгоритм:
Исходная матрица - A (M,N) в векторе V (M*N)
Конечная матрица - B (N,M)
Возьмем элемент вектора V(K).
В исходной матрице его адрес:
A (K mod N, K div N)
В конечной матрице его адрес должен стать:
B (K div N, K mod N)
Т.е. в векторе V его адрес станет
V( N*(K mod N) + (K div N))

Итого:

Код

For K = 0 to M*N    If K > (N*(K mod N)+(K\N)) Then       ' Менять местами надо только один раз       ' Диагональные - вообще не надо       SWAP V(K), V(N*(K mod N)+(K\N))    End if Next

PS. Писано на коленке, проверьте.

Цитата(Akina @ 8.1.2006, 23:20)

Алгоритм: Исходная матрица - A (M,N) в векторе V (M*N) Конечная матрица - B (N,M) Возьмем элемент вектора V(K). В исходной матрице его адрес: A (K mod N, K div N) В конечной матрице его адрес должен стать: B (K div N, K mod N) Т.е. в векторе V его адрес станет V( N*(K mod N) + (K div N)) Итого: Код For K = 0 to M*N    If K > (N*(K mod N)+(K\N)) Then       ' Менять местами надо только один раз       ' Диагональные - вообще не надо       SWAP V(K), V(N*(K mod N)+(K\N))    End if Next PS. Писано на коленке, проверьте.

Работает, если исправить кое что:
1) возьмем V(K), в исходной матр это будет A(K/N, k mod N)
2) в траспонированной B(K mod N, K/N)
3) перестановка в векторе V(M*(K mod N) + K/N)

Вот вроде так. В твоем варианте получается, что траспонирование матр никак не зависит от ее второй размерности.

2 Mal Hack
В коде, который ты привел ошибка: ты выходишь за границы массива, когда меняешь элементы. И ты принял, что матр квадратная.

Ща еще потестирую.
ВСЕМ БОЛЬШОЕ СПАСИБО!

На тот случай если алгоритм Akina не сработал привожу полную рабочую программу.

Код

program MatrixTransp; {$APPTYPE CONSOLE} uses   SysUtils; var   N: Integer; // по вертикали   M: Integer; // по горизонтали   a: array of Integer; // наш массив   maxmodul: Integer; // максимальный модуль для пометки элемента массива   temp_a, temp_i, i, j: Integer; // временные переменные procedure InitArray; var   i, j: Integer; // счетчик begin {инициируем размерность матрицы и заполняем случайными числами от -50 до 50}   Write('Введите N ');   Read(N);   Write('Введите M ');   Read(M);   SetLength(a, M*N);   Randomize;   for i := 0 to M*N - 1 do     a[i] := Random(100) - 50; {Выведем матрицу}   for i:= 0 to N-1 do   begin     for j:= 0 to M-1 do       Write(a[i*M + j]: 4);     writeLn;   end; end; procedure FindMaxModule; {находим максимальное по модулю число и записываем его модуль в maxmodule} var   i: Integer; // счетчик begin   maxmodul := a[0];   for i := 0 to M*N - 1 do     if maxmodul < abs(a[i]) then       maxmodul :=  abs(a[i]); end; procedure Mark(i: Integer); {"помечаем" элемент массива, путем увеличения его по модулю на maxmodul + 1} begin   if a[i] >= 0 then     a[i] := a[i] + maxmodul + 1   else     a[i] := a[i] - maxmodul - 1; end; procedure Remark(i: Integer); {"размечаем" элемент массива, путем уменьшения его по модулю на maxmodul + 1} begin   if a[i] >= 0 then     a[i] := a[i] - maxmodul - 1   else     a[i] := a[i] + maxmodul + 1; end; function isMark(i: Integer): Boolean; {возвращает true, если элемент "помечен" и false в противном случае} begin   Result := abs(a[i]) > maxmodul; end; function TransPos(i: Integer): Integer; {получение номера в массиве, по которому лежит транспонированный эллемент} begin   Result := (i mod n) * m + (i div n); end; begin   InitArray;   FindMaxModule;   for i := 0 to N*M - 1 do   begin     if not isMark(i) then // если с элементом раньше не работали     begin       temp_i := i;       while not isMark(TransPos(temp_i)) do begin         {обмен значениями}         temp_a := a[TransPos(temp_i)];         a[TransPos(temp_i)] := a[temp_i];         a[temp_i] := temp_a;         {помечаем элемент}         Mark(temp_i);         temp_i := TransPos(temp_i);       end;     end;   end;   {размечаем все меченные элементы}   for i := 0 to N*M - 1 do   begin     if isMark(i) then       Remark(i);   end; // выведем транспонированную матрицу   writeLn;   for i:= 0 to M-1 do   begin     for j:= 0 to N-1 do       Write(a[i*N + j]: 4);     writeLn;   end;   readln;   readln; end.

Цитата

В исходной матрице его адрес: A (K mod N, K div N) В конечной матрице его адрес должен стать: B (K div N, K mod N) Т.е. в векторе V его адрес станет V( N*(K mod N) + (K div N))

проблема в том, что тот элемент, на место которого нужно поставить K-й, необязательно должен стать на его место...
пример:
исходная матрица - 2 строки, 3 столбца
0 1 2 3 4 5
переходит в
0 3 1 4 2 5

например, 1 становится на место 2, но не наоборот...

P.S. если не ошибся...

Почему не будет работать алгоритм Akina.
Потому что при транспонировании прямоугольной матрицы элементы не будут заменятся двунаправленно. Т.е. пусть у нас есть матрица:
┌─┬─┬─┐
│0│1│2│
├─┼─┼─┤
│3│4│5│
└─┴─┴─┘, она транспонируется в матрицу
┌─┬─┐
│0│3│
├─┼─┤
│1│4│
├─┼─┤
│2│5│
└─┴─┘, если все записать в строку, то получим, что была строка [0, 1, 2, 3, 4, 5], получили транспонированием строку [0, 3, 1, 4, 2, 5]. Т.е. преобразовния следующие
0 -> 0;
1 -> 2 -> 4 -> 3 -> 1;
5 -> 5;
В зависимости от размерности матрицы может быть разное количество таких цепочек.
при реализации этих преобразований нужно запомнить, с какими элементами производили преобразования, а с какими - нет. Для этого в моем решении вводится переменная maxmodul, которая хранит максимальный модуль из входной матрицы. Элемент, с которым происвели преобразование, помечаем путем увеличения его модуля на maxmodul + 1. В конце работы, для всех помеченных элементов модуль уменьшаем на maxmodul + 1.
Добавлено @ 02:08
maxim1000 немного раньше это написал. Да еще и с тем же примером, что и у меня

Цитата

Для этого в моем решении вводится переменная maxmodul, которая хранит максимальный модуль из входной матрицы. Элемент, с которым происвели преобразование, помечаем путем увеличения его модуля на maxmodul + 1.

это тоже, как мне кажется, не подходит - при больших значениях оно будет приводить к переполнению операций сложения...
на самом деле, это почти эквивалентно использованию старших битов значений...

maxim1000, можно и тип Real (или double) сделать. Я просто думал над пометкой без использования дополнительных массивов. Насчет переполнения я тоже думал, но ничего другого не придумал. Времени на это не было. И так программу накидал - должен был, а то лопухнулся с определениями. Ладно хоть Alagert не расскажет моему преподавателю по алгебре как лопухнулся. Во всяком случае, программа работает Если кто придумает как лучше помечать элементы - милости прошу. Только функции изменить и вперед!

Цитата

Если кто придумает как лучше помечать элементы - милости прошу

помечать элементы никак нельзя - нельзя заставить матрицу хранить больше информации, чем то, насколько она расчитана
в случае с double произойдет потеря точности...
так что получится ненастоящее транспонирование...
Добавлено @ 02:45
вот пришел в голову еще один способ:
(для начала сразу скажу - первый индекс - строка или количество строк, второй - столбец или количество столбцов)
наша задача - транспонировать матрицу m*n
мы точно знаем, какие элементы будут в конце массива - нужно просто взять последний столбец и вытащить его элементы в конец
дальше можно отбросить последние m элементы и обработать (n-1)*m матрицу, которая задана в оставшейся части массива...

Цитата(maxim1000 @ 9.1.2006, 03:40 )

помечать элементы никак нельзя

но у меня же получился один вариант
Можно, кстати, перевести в строковый тип и помечать добавлением какого-нибудь символа (или группы символов)
Добавлено @ 02:50

Цитата(maxim1000 @ 9.1.2006, 03:40 )

вот пришел в голову еще один способ:

, а те элементы, что в конце, ты куда денешь?
У этого способа та же проблема...

Код

void Transpose(int *Array,unsigned int RowCount,unsigned int ColumnCount) {   while(ColumnCount>1)   {     //draw last column into the tail of the array     //(begin from the bottom)     for(unsigned int c=0;c<RowCount;c++)     {//draw (ColumnCount-1,RowCount-1-c)-th element to the end       unsigned int index=ColumnCount-1+ColumnCount*(RowCount-1-c);       unsigned int target=ColumnCount*RowCount-1-c;       int temp=Array[index];       for(i=index;i<target;++i)         Array[i]=Array[i+1];       Array[target]=temp;     }     //proceed with smaller matrix     --ColumnCount;   } }

вот...
правда, тоже писалось на коленках
Добавлено @ 03:02

Цитата(Illuminaty @ 9.1.2006, 02:47 )

но у меня же получился один вариант

который решает задачу только для некоторых матриц (у которых не слишком большие элементы)

Цитата(Illuminaty @ 9.1.2006, 02:47 )

Можно, кстати, перевести в строковый тип и помечать добавлением какого-нибудь символа (или группы символов)

нельзя, т.к.это потребует дополнительных расходов памяти, пропорциональных размерностям матрицы

Цитата(Illuminaty @ 9.1.2006, 02:47 )

а те элементы, что в конце, ты куда денешь?

они сдвинутся
под "вытаскиванием" элементов я имел в виду такую операцию - берем элемент, все, которые после него, сдвигаем в сторону начала массива (занимая освободившееся место), а взятый элемент - в конец массива (ну или на каком-то расстоянии от конца)
Добавлено @ 03:08
пример с матрицей 2*3
1 2 3 4 5 6
1. вытаскиваем элементы последнего столбца (3 и 6) в конец массива (начиная с нижних)
1.1. вытаскиваем 6 - его вытаскивать не надо, так тут ничего и делать не надо
1.2. вытаскиваем 3:
3 запоминаем (одна временная переменная)
1 2 3 4 5 6 -> 1 2 4 5 (неважно что) 6 -> 1 2 4 5 3 6
Добавлено @ 03:11
а теперь сводим задачу (2*3) к задаче (2*2), уменьшая количество столбцов и размер массива (точнее, размер той части массива, с котороймы работаем), т.е. транспонируем матрицу 2*2: 1 2 4 5
по тому же алгоритму

А если менять цепочкой, а не линейно?

То есть берем i-ый элемент и ставим его на корректное место j.
После этого мы берем не (i+1) элемент(как не единожды предлагалось ранее), а элемент j (то есть тот, на котором должен стоять i).
Если же такого уже нет, то берем i+1.
При этом i+1 считается обработанным, если в обходе его цепочки мы натолкнемся на обработанный элемент.

Цепочка - это...

Пример:

Есть
123
456

(123456)

Хотим

14
25
36

(142536)


Отображение A->At такое:
1->1, 2->3, 3->5, 4->2, 5->4, 6->6

Цепочка - это вот такая ерунда: 1->1, 2->3->5->4->2 ну и прочее. Блин. Не могу сформулировать, но интуитивно надеюсь понятно.


Запускаем алгоритм:
1) Берем i=1. (123456 <- текущий массив)
2) 1->1. Единица уже была(только что), не меняем (123456)
3) Берем 2. Ставим её на 3. 3 запоминаем (122456)
4) Ставим 3 на 5. 5 запомиаем (122436)
5) Ставим 5 на 4. 4 запоминаем(122536)
6) Ставим 4 на 2. мы начинали с двойки, поэтому останавливаемсч(142536)

7) Берем 3. Мы её не будем трогать, так как цепочка 3->5->4->2 приводит к уже обработанной 2.(142536)
8) Берем 4. Не меняем, так как 4->2 приводит к обработанной 2(142536)
9) Берем 5. Не меняем, так как 5->4 приводит к обработанной 4(142536)
10) Берем 6. Не меняем, так как 6->6 приводит к обработываемой 6(142536)

Готово. 142536

Попробую обосновать инвариантом цикла,

Инвариант цикла -
цепочки всех элементов до текущего оттранспорированны.

Инициализация - текущего элемента нет.
Предшественников нет. (ну или даже 1-ый элемент всегда оттранспорирован)
Сохранения инварианта - мы меняем местами только те элементы, цепочки которых не содержат
предшествующих элементов. Иными словами если что-то было верно, то оно останется верным.
Если что-то было неверным, оно станет верным. Мы трогаем лишь элементы цепочки.
Завершение - Все цепочки оттранспорированны. => оттранспорированны ВСЕ элементы матрицы .

ЗЫ. Цепочка образует цикл, это всё очень имхо и это я не доказывал, но имхо это так. Все таки A=Att.
Добавлено @ 09:34
Тьфу блин, как же я это такой пост пропустил.
Идея с цепочками уже была у Illuminaty
Ну ладно. По крайне мере можете попниать обоснование.

Это сообщение отредактировал(а) Mayk - 9.1.2006, 09:38

maxim1000, круто! Проверил - действительно работает.
Только твоя функция немного неправильно работает, но это из-за

Цитата(maxim1000 @ 9.1.2006, 03:58 )

тоже писалось на коленках

.
Вот полностью работающая программа

Код

program MatrixTransp; {$APPTYPE CONSOLE} uses   SysUtils; var   N: Integer; // по вертикали   M: Integer; // по горизонтали   a: array of Integer; // наш массив   maxmodul: Integer; // максимальный модуль для пометки элемента массива   i, j: Integer; // временные переменные procedure InitArray; var   i, j: Integer; // счетчик begin {инициируем размерность матрицы и заполняем случайными числами от -50 до 50}   Write('Введите N ');   Read(N);   Write('Введите M ');   Read(M);   SetLength(a, M*N);   Randomize;   for i := 0 to M*N - 1 do     a[i] := Random(100) - 50; {Выведем матрицу}   for i:= 0 to N-1 do   begin     for j:= 0 to M-1 do       Write(a[i*M + j]: 4);     writeLn;   end; end; procedure Transpose; var   i, j, temp, c, k: Integer; begin   k := 0;   for j := M -1 downto 0 do     for i := N -1 downto 0 do     begin       temp := a[i*(j+1) + j];       for c := i*(j+1) + j to M*N - k - 2 do         a[c] := a[c+1];       a[M*N - k - 1] := temp;       k := k + 1;     end; end; begin   InitArray;   Transpose; // выведем транспонированную матрицу   writeLn;   for i:= 0 to M-1 do   begin     for j:= 0 to N-1 do       Write(a[i*N + j]: 4);     writeLn;   end;   readln;   readln; end.

Проверено - работает

Всем огромное спасибо! А я вот вчера в 1.30 уже сломался. Проверил вариант Akina и бухнулся спать.
Сейчас буду разбирать все ваши идеи.