sinq Temat założony przez niniejszego użytkownika |
Transponowanie Macierzy w sposób niekonwencjonalny. » 2016-12-05 18:52:11 Witam wszystkich. Jestem początkującym programistą więc dla kogoś z doświadczeniem problem może wydać się trywialny. Ostatnio na laboratoriach z programowania prowadzący rzucił w nas takim oto przykładem: "Napisz funkcję która zamienia wiersze i kolumny, dowolnej tablicy dwuwymiarowej. Nie można tworzyć zmiennych globalnych, ani tworzyć tablicy pomocniczej." Ogólnie należy to zrobić najkrótszym i najmniej obciążającym (?) sprzęt sposobem. Do tej pory poznaliśmy -Tablice, -deklaracje zmiennych, -liczby pseudolosowe, -funkcje, -pętle, -instrukcje warunkowe... to chyba wszystko. Rzecz jasna z żadnych metod ponad tych które znamy nie możemy korzystać. Postanowiłem jednak pójść wyżej i spróbować 'transponować' tablicę. Udało mi się to zrobić dla 'macierzy' kwadratowej. #include <stdlib.h> #include <stdio.h> #include <time.h>
int transponuj( float A[], const int n, const int m, int chk ) { int i, j = 0, k = m; float bufor; if( m == n ) { for( j = 0; j < n; j++ ) { for( i = 0; i < k && k > 1; i++ ) { if( k - 1 - i == 0 ) break; bufor = A[ m -( k - 1 ) + i + j * m ]; A[ m -( k - 1 ) + i + j * m ] = A[ m *( m -( k - 1 ) + i ) + j ]; A[ m *( m -( k - 1 ) + i ) + j ] = bufor; } k--; } } else { printf( "Tego jeszcze nie umiem :'(\n Sprobuj macierz kwadratowa :)\n" ); system( "Pause" ); return 0; } return 4; }
int main( void ) { srand( time( NULL ) ); const int n = 10, m = 10; const float min = - 1.5, max = 1.5; int i, chk = 0; float A[ n * m ]; for( i = 0; i < n * m; i++ ) A[ i ] =( max - min ) * rand() / RAND_MAX + min; chk = transponuj( A, n, m, chk ); wyswietl( A, n, m, chk ); return 0; }
Ale nie mogę znaleźć rozwiązania dla tablicy gdy m != n . Walczyłem z tym dobrych kilka godzin. Zapisałem ponad 3 kartki A4 i nie wiem jak to przepchnąć. Moje pytanie: Czy istnieje sposób by to zrobić, czy szukam rozwiązania na próżno? Próbowałem znaleźć rozwiązanie mojego problemu na forum i w goglach ale nic nie znalazłem, problem jest chyba niekonwencjonalny, biorąc pod uwagę założenia. |
|
Monika90 |
» 2016-12-05 20:22:00 Jeżeli naprawdę Cię to interesuje to zacznij tutaj https://en.wikipedia.org/wiki/In-place_matrix_transpositionAle jest też inne rozwiązanie tego problemu, zamiast przestawiać elementy w pamięci można udawać że wiersze to są kolumny, a kolumny to wiersze, co demonstruje ten program w C++ #include <utility> #include <memory> #include <random> #include <iostream>
template < class T > struct matrix { int width; int height; int horizontal_stride; int vertical_stride; std::unique_ptr < T[] > data; matrix( int width, int height ) : width( width ) , height( height ) , horizontal_stride( 1 ) , vertical_stride( width ) , data( std::make_unique < T[] >( width * height ) ) { } };
template < class T, class Generator > void fill( matrix < T >& m, Generator g ) { for( int i = 0; i < m.height * m.width; ++i ) m.data[ i ] = g(); }
template < class T > void print( std::ostream & out, const matrix < T >& m ) { for( int y = 0; y < m.height; ++y ) { for( int x = 0; x < m.width; ++x ) out << m.data[ y * m.vertical_stride + x * m.horizontal_stride ] << ' '; out << '\n'; } }
template < class T > void transpose( matrix < T >& m ) { std::swap( m.width, m.height ); std::swap( m.horizontal_stride, m.vertical_stride ); }
int main() { std::mt19937 urbg( 2016 ); std::uniform_int_distribution < int > d( 0, 9 ); matrix < int > m( 7, 4 ); fill( m,[ & ] { return d( urbg ); } ); print( std::cout, m ); transpose( m ); print( std::cout, m ); }
|
|
sinq Temat założony przez niniejszego użytkownika |
Swap » 2016-12-05 21:02:27 Prawie nic nie zrozumiałem z tego rozwiązania (kod) Monika90. W przyszłości pewnie to sprawdzę tak więc dziękuję bardzo :) Dopiero zaczynam poznawać C. Widziałem że użyłaś funkcji swap(). Zapomniałem dodać że nawet tego nie pozwalają nam używać. Każą nam wymyślać algorytmy od podstaw. Z tego co napisałaś rozumiem że dla dużych tablic pamięć zaczyna 'płonąć'? :) Czego oni nas uczą :P Nadal jestem ciekawy czy istneje sposób 'transponowania' dla m != n przy użyciu tych zagadnień które wymieniłem. Dziękuję za zainteresowanie. |
|
mateczek |
» 2016-12-06 06:12:54 Monika90 tutaj pisze w c++. Nie w C Idea programu wiąże się z odmiennym sposobem liczenia indeksu dla macierzy zwykłej i transponowanej #include <iostream> using namespace std; int main() { int dane[ 9 ] = { 1, 1, 1, 2, 2, 2, 3, 3, 3 }; for( int wiersze = 0; wiersze < 3; wiersze++ ) { for( int kolumny = 0; kolumny < 3; kolumny++ ) { int index = wiersze * 3 + kolumny; cout << dane[ index ] << " "; } cout << endl; } cout << endl; for( int wiersze = 0; wiersze < 3; wiersze++ ) { for( int kolumny = 0; kolumny < 3; kolumny++ ) { int index = wiersze + kolumny * 3; cout << dane[ index ] << " "; } cout << endl; } }
powyżej masz samą esencję takowej transpozycji, ale możesz jeszcze zajrzeć tutaj. Tam jest tam kod całej klasy http://cpp0x.pl/forum/temat/?id=22546&p=2 |
|
« 1 » |