兩道編程題：
1請用最少的額外空間將一個M*N的矩陣旋轉90度，寫出算法描述和類c語言程序;
2完成如下函數，給定分子和分母，輸出其小數表示形式，循環節用[]表示，例如給出分子：13，分母19，輸出爲：0.[13]
參考解答：
只需要一個空間即可(下標變量i),考慮的是順時針旋轉
#include "iostream.h"
const int M=5;
const int N=3;
void main()
{
int a[M][N]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int c[N][M]={0};
int i;//只需一個空間i。
for(i=0;i
c[i%N][M-1-i/N]=a[i/N][i%N];//就這句話
for(i=0;i
{
if(i%N == 0)
cout<
cout<
}
cout<
for(i=0;i
{
if(i%M == 0)
cout<
cout<
}
cout<
}
最省空間的矩陣轉置
#include "stdafx.h"
#include
using namespace std; int main()
{
const int M = 5;
const int N = 3;
int a[M][N] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int* p = a[0];
//轉90度後的.矩陣設爲b[N][M],則 b[j] = *(p + i + j*N)
for(int i = 0; i < N; i++)
{
for(int j =0; j < M; j++)
{
cout<< *(p + i + j*N) <<",";
}
cout<
}
system("pause");
return 0;
}
這是一個Matrix Transposition In place(M!=N) 問題。1972年 MIT的一個教授給出了到目前爲止的最佳解法。不過好像沒有樓上這些人說的那麼簡單,其中還包含了一個定理。大家可以去搜論文，嘿嘿.
Key word:Matrix Transposition In place
transposition, matrix operations, permutation,primitive roots, number theory