青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

C++研究

C++細節深度探索及軟件工程

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
  37 隨筆 :: 0 文章 :: 74 評論 :: 0 Trackbacks

算法要求:試設計一個算法,將數組A[0..n-1]中的元素循環右移K位,并要求只用一個元素大小的存儲

空間。元素移動或交換的次數為O(n)


【分析】:本題的應用環境很廣泛,在實用中有很重要意義,如:實現高階乘除法,在游戲選關和各種

特效中經常用到。目前手機等移動設備應用開發方興未艾,對此常用算法做一個深入的探討很有必要。

作者: 天津大學計算機系    常興龍  MSN:cxl82116@msn.com 

    本題的難點在于同時對空間復雜度與時間復雜度都做了很高的要求,但就本題來講,仍有很多種解

法。這里,探討常見的三種解法:
               1.由于每個元素,跟與它相距r×k位形成了一個“循環”,因此算法保證每次都有一至

二個元素正確歸位,設一個計數變量,當計數變量到達n時,算法結束
               2.對1解法求精,1解中可能使一個元素多于一次的移動,但如果找到n與k的最大公約數

,就可以解決此問題,從而保證每個元素只移動一次。
               3.第三種思想有一定的技巧,直觀理解比較困難,但手有有一副撲克牌,就能清楚地看

到整個過程(把整個排列看成是一個環形)。它的算法是:先逆轉前n-k個元素,再逆轉后K個元素,再

把整個序列逆轉。

void EMove(int A[n] , int k)
{
    
for(int i = 0 ; i < n;) //i為到位的元素個數,做為算法出口
    {
    
/**//* t是需要到位的元素的靜態指針 s 指向下一個K步到達的位置 ,
        r初值為1 ,在每一循環圈中置初值一次,做為步進值
*/

        s 
= ( t + r * k ) % n ;  
        A[t]
<-->A[s]; //用A[t]為緩沖空間 , 使此鏈上一個記錄到位,到位位置的記錄緩存到緩沖區中
        r++ ; i++;
        s 
= ( t +*k) %n;
        
if(s == t) //使兩個記錄到位,一圈結束
        {
            t
++;    //選擇親的起始點
            r=1;
            i
++;
        }
//if
    }
//for
}

[解二]
void EMove(int A[n] , int k)
{
    
for ( int i = 1; i <= k; i++ )
        
if ( n%== 0 && k%==0 ) p = j; 
        
/**//*上面為求最大公約數的O(n)寫法之一,還可以這么寫:
            int p= int();  //這也是一個C++新奇的寫法,int = 0,稍用一下構造函數
            while( n !=0 && k !=0)
            {
            n>k ? n%=k:k%=n;
            }
            p = n==0?k:n;
            p為n與k的最大公約數
            比較性能:注釋中的log(N)性能更好,但是破壞原來數據,
            如果保留原數據,輾轉一下,得不償失,這也是棄用的理由
        
*/

        
for ( i = 0 ; i < p ; i++//最大公約數,實質為保證每個元素都到位的子圈數目
        //極限情況,若 n與k最大公約為1,則一圈就能成功,無需另先起點
            j = i;
            m 
= ( i + k ) % n;
            temp 
= A[i]; //緩存
            while( m != i)
            
{
                
//利用A[j],交換 temp 與A[m]的值
                
//A[j]為本次要到位的元素
                
//A[m]存本次己位的元素
                
//temp 緩存下次要到位的元素
                A[j] = temp ; 
                temp 
= A[m] ; 
                A[m] 
= A[j] ; 
                
//前進一步
                j = m ;
                m 
= ( j + k ) % n ;
                
            }
//while
        }
//for
}
//Emove

[解三]
void Emove ( int A[n] , int k )
{
    
for ( i=0 ; i < ( n - k ) / 2 ; i++ )
    
{
        A[i]
<-->A[ n-k-1-i];
        
    }
//逆轉前n-k
    for( i = n - k ; i < ( 2*- k) /2 ; i++)
    
{
        A[n
-k+i]<-->A[k-1+i];
    }
 //逆轉后K項
    for ( i = 0 ; i < n/2 ; i++ )
    
{
        A[i]
<-->A[n-1-i];
    }
//逆轉整個鏈
}



補充:

[1]反轉鏈的下標確定方法,可以通俗的描寫

從 『鏈開始下標』到 (『鏈終止下標』-『鏈開始下標』)/2 ,反復做

     交換 『鏈開始下標+i』,『鏈終止下標-i』

[2]定義符號<-->為

Swap( int & i , int & j )
{
    
int temp = i ;
    i 
= j ; 
    j 
= temp
}


關于交換算法,還有一種線性代數矩陣的寫法

//交換x,y
Swap( int & x , int & y )
{
    
    x
=x+y;
    y
=x-y;
    x
=x-y;
}


【思考】如果把本題擴充一下,改為把A中的一個子序列擴右移K位(其余要求不變)的算法?(進一步

要求能夠處理K>子序列長度的情況?)(下次提供答案)

posted on 2007-05-15 10:03 常興龍 閱讀(2529) 評論(6)  編輯 收藏 引用 所屬分類: Algorithm

評論

# re: 精煉循環右移[未登錄] 2007-07-06 16:53 yong
第三種有意思,呵呵,怎么推出來的,琢磨琢磨...  回復  更多評論
  

# re: 精煉循環右移 2008-08-29 20:08 李銳
我也要好好看看,謝謝了  回復  更多評論
  

# re: 精煉循環右移 2010-04-18 20:52 zy天
A[n-k+i]<-->A[k-1+i];
應該是A[n-k+1]<-->A[k-1+i]  回復  更多評論
  

# re: 精煉循環右移 2010-04-28 22:28 tengzhao201
//最高效的循環右移算法??!
//這個是遞歸的寫法
//author:tengzhao201 QQ:715572192
//time:2010-4-24
//時間復雜度為O(n),空間復雜度O(1),交換點在中間時比逆序法快一倍!??!
//提速要點:由于取模運算的效率很低,去掉了取模運算后效率得到大提升;swap函數效率低,引入了temp變量
void TZshift1(int* arr,int N,int K)
{
K=K%N;

if(0==K)return;

int temp,qq,pp=0;
pp=0;qq=K;
for(int i=0;i<N-K;i++,pp++,qq++)
{
//swap(arr[i%K],arr[i+K]);//問題的關鍵在于找到原來的第i個元素現在在哪里,通過觀察可以發現在arr[i%K]的位置,下面的代碼實現了arr[i%K]和arr[i+K]的互換
if(K==pp)pp=0;
temp=arr[pp];
arr[pp]=arr[qq];
arr[qq]=temp;
}

TZshift1(arr,K,K-pp);
}

//最高效的循環右移算法??!
//非遞歸的寫法
//author:tengzhao201 QQ:715572192
//time:2010-4-24
//時間復雜度為O(n),空間復雜度O(1),交換點在中間時比逆序法快一倍!??!
//提速要點:采用非遞歸算法
void TZshift2(int* arr,int N,int K)
{
K=K%N;
if(0==K)
return;

//int count=0;
int temp,qq,pp=0;

while(K>0)
{
pp=0;qq=K;
for(int i=0;i<N-K;i++,pp++,qq++)
{
//swap(arr[i%K],arr[i+K]);//問題的關鍵在于找到原來的第i個元素現在在哪里,通過觀察可以發現在arr[i%K]的位置,下面的代碼實現了arr[i%K]和arr[i+K]的互換

if(K==pp)pp=0;
temp=arr[pp];
arr[pp]=arr[qq];
arr[qq]=temp;
//count+=2;
}
N=K;
if(0==pp)
return;
K-=pp;
//TZshift(arr,K,K-pp);
}
//cout<<"In tatal,has used "<<count<<" steps."<<endl;
}  回復  更多評論
  

# re: 精煉循環右移 2010-04-29 10:46 tengzhao201
http://download.csdn.net/source/2296222  回復  更多評論
  

# re: 精煉循環右移 2010-04-29 10:47 tengzhao201
最高效循環右移課程設計下載地址:
http://download.csdn.net/source/2296222  回復  更多評論
  

> hi的博客
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美电影打屁股sp| 欧美私人网站| 欧美色图首页| 一区二区三区免费看| 亚洲人成人一区二区三区| 蜜臀av国产精品久久久久| 伊人成人在线视频| 欧美激情综合色| 欧美人成网站| 久久激五月天综合精品| 久久久久久久精| 亚洲精品一区二区在线观看| 亚洲日韩中文字幕在线播放| 最新国产乱人伦偷精品免费网站| 亚洲精品国产精品乱码不99按摩| 国产婷婷成人久久av免费高清 | 亚洲在线观看免费视频| 欧美精品色网| 欧美激情第4页| 国产一区二区三区在线观看免费| 欧美国产视频在线观看| 国产亚洲欧美日韩精品| 午夜免费在线观看精品视频| av成人免费| 欧美人在线观看| 日韩视频在线观看免费| 亚洲尤物在线视频观看| 国产精品成人在线观看| 99热在线精品观看| 欧美亚洲午夜视频在线观看| 国产日韩专区在线| 欧美在线视频免费播放| 久久久久久久久久看片| 樱桃国产成人精品视频| 久久免费视频这里只有精品| 麻豆亚洲精品| 国产一区二区| 欧美伊人久久大香线蕉综合69| 亚洲国产欧洲综合997久久| 久久综合九色九九| 亚洲精品日韩欧美| 亚洲欧美日本国产有色| 国产日韩欧美另类| 麻豆成人综合网| 中文国产亚洲喷潮| 另类图片国产| 午夜一区在线| 日韩午夜剧场| 欧美午夜精品久久久久免费视 | 久久精彩视频| 亚洲欧洲日夜超级视频| 国产深夜精品| 国产精品久久| 欧美日韩国产限制| 性久久久久久久久久久久| 欧美成人精品一区二区三区| 亚洲国产免费| 久久精品一区二区三区不卡牛牛| 在线亚洲伦理| 91久久黄色| 国产在线观看一区| 国产精品毛片一区二区三区| 欧美日韩一区二区三区在线视频| 欧美成人高清| 欧美日韩精品一二三区| 欧美视频久久| 妖精视频成人观看www| 久久久精品tv| 久久久久国产精品麻豆ai换脸| 国产精品亚洲片夜色在线| 欧美一区亚洲二区| 久久成人精品| 久久久久久亚洲精品中文字幕| 国产手机视频精品| 毛片av中文字幕一区二区| 久久精品国产96久久久香蕉| 亚洲精品一区二区在线| 亚洲一区bb| 国产亚洲人成a一在线v站| 午夜精品一区二区三区四区 | 国产亚洲va综合人人澡精品| 亚洲一区视频| 一区二区欧美精品| 欧美日韩高清在线观看| 在线观看亚洲视频啊啊啊啊| 日韩午夜激情| 国产精品美女久久久久aⅴ国产馆| 亚洲美女福利视频网站| 精品999日本| 亚洲一区三区在线观看| 国产日韩欧美91| 免费不卡亚洲欧美| 亚洲美女在线观看| 欧美一区午夜精品| 亚洲人成高清| 国产日韩欧美三级| 欧美精品日日鲁夜夜添| 香蕉久久夜色精品国产| 亚洲人成欧美中文字幕| 亚洲欧美日韩一区二区| 在线成人免费观看| 欧美图区在线视频| 久久国产精品久久久| 99re6热在线精品视频播放速度| 久久国产欧美| 一本大道久久精品懂色aⅴ | 亚洲日韩欧美视频| 久久久噜噜噜| 亚洲一区二区三区在线视频| 亚洲国产精品va| 国产欧美日本| 欧美日韩黄色大片| 另类尿喷潮videofree | 一区二区三区四区五区精品| 久久综合婷婷| 欧美一级网站| 一区二区精品国产| 亚洲第一精品夜夜躁人人爽| 国产日韩精品一区观看| 欧美日韩中文在线| 欧美紧缚bdsm在线视频| 玖玖玖免费嫩草在线影院一区| 午夜亚洲精品| 亚洲制服av| 亚洲婷婷国产精品电影人久久 | 亚洲欧美成人一区二区三区| 午夜天堂精品久久久久| 最新国产精品拍自在线播放| 黄色综合网站| 国内精品久久久久久久果冻传媒| 国产精品色一区二区三区| 欧美极品一区二区三区| 欧美激情综合色综合啪啪| 欧美国产国产综合| 欧美成熟视频| 欧美欧美全黄| 欧美精品免费在线观看| 欧美激情精品久久久久久免费印度| 狂野欧美激情性xxxx| 久久一区激情| 免费日韩av片| 欧美精品一区二| 欧美日韩亚洲综合一区| 欧美午夜一区二区福利视频| 欧美性大战xxxxx久久久| 欧美色另类天堂2015| 国产精品va| 国产亚洲精品一区二555| 国产一区二区精品丝袜| 亚洲第一网站免费视频| 亚洲精品国精品久久99热| 亚洲每日更新| 亚洲一区二区少妇| 欧美在线啊v一区| 久久久久久久精| 欧美激情在线| 日韩一二三在线视频播| 亚洲一区免费| 久久婷婷久久| 欧美精品激情在线| 国产精品久久综合| 黄色欧美日韩| 在线亚洲自拍| 欧美在线视频二区| 欧美77777| 一区二区激情视频| 久久激情视频免费观看| 欧美a级片网| 国产精品日韩精品| 亚洲福利一区| 欧美一级播放| 亚洲福利专区| 亚洲欧美日韩国产综合在线| 久久亚洲午夜电影| 国产精品美腿一区在线看| 在线日韩av| 午夜精品一区二区三区电影天堂 | 亚洲乱码精品一二三四区日韩在线| 一区二区三区高清| 久久日韩粉嫩一区二区三区| 亚洲国产清纯| 久久成人资源| 国产精品都在这里| 亚洲激情亚洲| 久久久久看片| 亚洲视频一二| 欧美黄色视屏| 在线日韩欧美| 久久亚洲国产成人| 亚洲一区二区免费在线| 欧美大片免费看| 极品日韩久久| 久久国产主播| 一区二区三区精品在线 | 羞羞视频在线观看欧美| 欧美精品一区二区久久婷婷| 精品成人乱色一区二区| 欧美一乱一性一交一视频| 亚洲理论在线观看| 欧美成人精品|