一個算法題目

phy0077

a1, a2, ... , an, b1, b2, ... , bn,
a2 與 b1 互換

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

    你打印結(jié)果看看， 你的描述看上去也有錯誤。
這個題目很復(fù)雜

peidright

回復(fù) 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

回復(fù)  phy0077
舉個例子

         a1 a2 a3 a4  b1 b2 b3 b4

i=1 第一輪： a1 b1 a3 a4  a2 b2 b3  ...
peidright 發(fā)表于 2010-03-21 10:43

    暈，說的是一套，舉得例子又是另一套

peidright

回復(fù) 10# phy0077

想了一下，這道題目從原理上，似乎很簡單，但是用程序?qū)懗鰜�，需要找�?guī)律。

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

Ai 是這樣一個2n階矩陣，滿足 互換2n向量中幾個元素的位置。

現(xiàn)在已經(jīng)知道，有2n 這樣的矩陣肯定可以滿足這樣的變換，現(xiàn)在要把這2n個矩陣兩兩組合，形成 n個矩陣，為了方便寫程序，這n個矩陣有
這樣的特性：
強一點的： 最好還是單個元素與單個元素之間的變換（看起來不可能）

弱一點的： 這n個矩陣，某種意義上是相似的，而且矩陣與矩陣之間，包含在這些矩陣之間的元素，是相同的。

。。。最終可能的表達式，。�，F(xiàn)賴心把矩陣畫出來。。。

peidright

回復(fù) 13# phy0077 [/b］

暈，我上面O(2N)的方法都有問題，要重新思考了

cjaizss

隨便翻看了一篇論文,里面介紹的算法貌似也并非O(1)空間復(fù)雜度.

shang2010

logN次執(zhí)行？

yug1129

如果數(shù)據(jù)是從文件中讀入的，可以用兩個文件指針，分別打開輸入文件，并將第二個指針定位在b1，然后從兩個指針交替地讀數(shù)據(jù)再輸出，輸出序列即為a1, b1, ...., 。

wqf2

這個時間和空間復(fù)雜度是可以做到的。

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. }
   

復(fù)制代碼