Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Transponowanie Macierzy w sposób niekonwencjonalny.

Ostatnio zmodyfikowano 2016-12-06 06:12
Autor Wiadomość
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.
C/C++
#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; /*<-wymiary A*/
    const float min = - 1.5, max = 1.5; /*<-zakres*/
    int i, chk = 0;
    float A[ n * m ]; //Niech macierz dwuwymiarowa bedzie jednowymiarowa.
   
    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.
P-154552
Monika90
» 2016-12-05 20:22:00
Jeżeli naprawdę Cię to interesuje to zacznij tutaj https://en.wikipedia.org/wiki​/In-place_matrix_transposition

Ale 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++
C/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 );
}
P-154556
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.
P-154558
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
C/C++
#include <iostream>
using namespace std;
int main() {
    int dane[ 9 ] = { 1, 1, 1, 2, 2, 2, 3, 3, 3 }; //tablica 3x3
    // wyświetl zwykłą
    for( int wiersze = 0; wiersze < 3; wiersze++ ) {
        for( int kolumny = 0; kolumny < 3; kolumny++ ) {
            int index = wiersze * 3 + kolumny;
            cout << dane[ index ] << " ";
        }
        cout << endl;
    }
    //wyświetl transponowaną
    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
P-154575
« 1 »
  Strona 1 z 1