一个算法题目

phy0077

a1, a2, ... , an, b1, b2, ... , bn,
a2 与 b1 互换

形成
a1 b1 a3 ... an  ; a2,b2,.b3,....bn
把前 ...
peidright 发表于 2010-03-21 09:08

    你打印结果看看， 你的描述看上去也有错误。
这个题目很复杂

peidright

回复 11# phy0077
举个例子

             a1 a2 a3 a4 a5  b1 b2 b3 b4 b5

i=1 第一轮： a1 b1 a3 a4 a5  a2 b2 b3 b4 b5

i=2 第二轮： a1 b1 a2 a4 a5  a3 b2 b3 b4 b5

i=3 第三轮： a1 b1 a2 b2 a5  a3 a4 b3 b4 b5

          ： a1 b1 a2 b2 a3  a5 b3 a4 b4 b5

          ： a1 b1 a2 b2 a3  b3 a5 a4 b4 b5
            
             a1 b1 a2 b2 a3  b3 a4 b4 a5 b5

我这方法确实是错的，O(2n),我再算算

phy0077

回复  phy0077
举个例子

         a1 a2 a3 a4  b1 b2 b3 b4

i=1 第一轮： a1 b1 a3 a4  a2 b2 b3  ...
peidright 发表于 2010-03-21 10:43

    晕，说的是一套，举得例子又是另一套

peidright

回复 10# phy0077

想了一下，这道题目从原理上，似乎很简单，但是用程序写出来，需要找规律。

(a1,a2,a3,....,an,b1,b2,bn....)*A1A2A3***************A2n = (a1,b1,a2,b2,........,an,bn)

Ai 是这样一个2n阶矩阵，满足 互换2n向量中几个元素的位置。

现在已经知道，有2n 这样的矩阵肯定可以满足这样的变换，现在要把这2n个矩阵两两组合，形成 n个矩阵，为了方便写程序，这n个矩阵有
这样的特性：
强一点的： 最好还是单个元素与单个元素之间的变换（看起来不可能）

弱一点的： 这n个矩阵，某种意义上是相似的，而且矩阵与矩阵之间，包含在这些矩阵之间的元素，是相同的。

。。。最终可能的表达式，。。现赖心把矩阵画出来。。。

peidright

回复 13# phy0077 [/b］

晕，我上面O(2N)的方法都有问题，要重新思考了

cjaizss

随便翻看了一篇论文,里面介绍的算法貌似也并非O(1)空间复杂度.

shang2010

logN次执行？

yug1129

如果数据是从文件中读入的，可以用两个文件指针，分别打开输入文件，并将第二个指针定位在b1，然后从两个指针交替地读数据再输出，输出序列即为a1, b1, ...., 。

wqf2

这个时间和空间复杂度是可以做到的。

shang2010

1. 
   
2. #define N 10
   
3. 
   
4. inline int fun(int i)
   
5. {
   
6. return (i<N)?(i*2):((i-N)*2+1);
   
7. }
   

复制代码