阿里巴巴笔试中的 两道编程题

两道编程题：

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