Здравствуйте, nikov, Вы писали:

N>Дана прямоугольная матрица из целых чисел размера M×N, расположенная в памяти построчно в виде непрерывного линейного массива. Написать программу, которая транспонирует эту матрицу in place, используя дополнительную память не более O(max(M,N)).

В чем собственно трудность?
Если поменять функцию доступа к элементам то вообще никакой работы не надо производить

get(i,j)=mtx(i*M+j)
get_tr=get(j,i)

Вариант без затрат по памяти

#include <stdio.h>

int step(int i,int m,int n) { return (i%n)*m+(i/n); }
int need(int i,int m,int n) {
    int j,k;
    for(j=1;j<i-1;j++) {
        k=j;
        do {
            k=step(k,m,n);
            if (i==k) return 0;
        } while(k!=j);
    }
    return 1;
}
void tr(int *x,int m,int n) {
    int i,j,k,w,v,mn=m*n;
    for(i=1;i<mn;i++) {
        if (!need(i,m,n)) continue;
        j=step(k=i,m,n); w=x[k];
        while(i!=j) {
            v=w; w=x[j]; x[j]=v; 
            k=j; j=step(k,m,n);
        }
        x[i]=w;
    }
}

void show(int *x,int m,int n,int dm,int dn) {
    int i,j;
    for(i=0;i<m;i++) {
        for(j=0;j<n;j++) {
            printf("%3d",x[i*dm+j*dn]);
        }
        printf("\n");
    }
}
int main(int argc,char** argv) {
    enum { M=3, N=7 };
    int i,x[M*N];
    for(i=0;i<M*N;i++) x[i]=i;
    show(x,M,N,N,1);printf("\n");
    show(x,N,M,1,N);printf("\n");
    tr(x,M,N);
    show(x,N,M,M,1);printf("\n");
    return 0;
}

N>Бонус: написать программу, которая поворачивает блок целых чисел размера M×N×K in place вокруг псевдо-диагонали, состоящей из элементов с индексами (0,0,0), (1,1,1), (2,2,2), ..., чтобы получился блок K×M×N, используя дополнительную память не более O(max(M,N,K)).

Меняем функцию доступа

get_rot(i,j,k)=get(k,i,j)

Со сдвигом индексов примерно так же как и с транспонированием, только длиннее.

N>Можно ли улучшить эти алгоритмы, чтобы использовать дополнительную память не более O(log(max(M,N))) и O(log(max(M,N,K))), соответственно?
До, но работать будут медленнее.

Здравствуйте, nikov, Вы писали:

N>Дана прямоугольная матрица из целых чисел размера M×N, расположенная в памяти построчно в виде непрерывного линейного массива. Написать программу, которая транспонирует эту матрицу in place, используя дополнительную память не более O(max(M,N)).

В чем собственно трудность?
Если поменять функцию доступа к элементам то вообще никакой работы не надо производить

get(i,j)=mtx(i*M+j)
get_tr=get(j,i)

Вариант без затрат по памяти

#include <stdio.h>

int step(int i,int m,int n) { return (i%n)*m+(i/n); }
int need(int i,int m,int n) {
    int k=i;
    do {
        k=step(k,m,n);
        if (k<i) return 0;
    } while(k!=i);
    return 1;
}
void tr(int *x,int m,int n) {
    int i,j,k,w,v,mn=m*n;
    for(i=1;i<mn;i++) {
        if (!need(i,m,n)) continue;
        j=step(k=i,m,n); w=x[k];
        while(i!=j) {
            v=w; w=x[j]; x[j]=v; 
            j=step(k=j,m,n);
        }
        x[i]=w;
    }
}

void show(int *x,int m,int n,int dm,int dn) {
    int i,j;
    for(i=0;i<m;i++) {
        for(j=0;j<n;j++) {
            printf("%3d",x[i*dm+j*dn]);
        }
        printf("\n");
    }
}
int main(int argc,char** argv) {
    enum { M=3, N=7 };
    int i,x[M*N];
    for(i=0;i<M*N;i++) x[i]=i;
    show(x,M,N,N,1);printf("\n");
    show(x,N,M,1,N);printf("\n");
    tr(x,M,N);
    show(x,N,M,M,1);printf("\n");
    return 0;
}

N>Бонус: написать программу, которая поворачивает блок целых чисел размера M×N×K in place вокруг псевдо-диагонали, состоящей из элементов с индексами (0,0,0), (1,1,1), (2,2,2), ..., чтобы получился блок K×M×N, используя дополнительную память не более O(max(M,N,K)).

Меняем функцию доступа

get_rot(i,j,k)=get(k,i,j)

Со сдвигом индексов примерно так же как и с транспонированием, только длиннее.

N>Можно ли улучшить эти алгоритмы, чтобы использовать дополнительную память не более O(log(max(M,N))) и O(log(max(M,N,K))), соответственно?
До, но работать будут медленнее.