<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    so true

    心懷未來,開創(chuàng)未來!
    隨筆 - 160, 文章 - 0, 評(píng)論 - 40, 引用 - 0
    數(shù)據(jù)加載中……

    數(shù)組右移的方法

    【題目】有一個(gè)整數(shù)數(shù)組,現(xiàn)要求實(shí)現(xiàn)這個(gè)整數(shù)數(shù)組的循環(huán)右移。如:1,2,3,4,5 則循

    環(huán)右移兩位后結(jié)果是:4,5,1,2,3。

     

    方法一:(最最容易想到的辦法)

    void RightCircleShift_00(int buffer[],int shift)

    {

        int i,j,tt;

       

        for(i=0;i<shift;i++)

        {

           tt = buffer[ARRSIZE-1];

           for(j=ARRSIZE-1;j>0;j--)

               buffer[j] = buffer[j-1]; 

           buffer[0] = tt;

        }

    }

    這個(gè)辦法是用兩個(gè)循環(huán)來控制,內(nèi)循環(huán)每次向右移動(dòng)一位,外循環(huán)則用來限制移動(dòng)的位數(shù)。

    算法需要執(zhí)行 ARRSIZE * ShiftValue次,時(shí)間復(fù)雜度是O( N2 )。

     

    方法二:(由方法一得到的遞歸程序)

    void RightCircleShift_01(int buffer[],int shift)

    {

        int *p,tt;

       

        tt = *(buffer+ARRSIZE-1);

     

        for(p = buffer+ARRSIZE-1;p > buffer;p--)

           *p = *(p-1);

       

        *buffer = tt;

     

        shift--;

        if(shift > 0)

            RightCircleShift_00(buffer,shift);

    }

    這個(gè)程序跟方法一類似,區(qū)別就是它是用遞歸來實(shí)現(xiàn)的。同樣需要執(zhí)行ARRSIZE *

    ShiftValue次,時(shí)間復(fù)雜度也是O( N2 )。

     

    方法三: 

    void RightCircleShift_02(int buffer[],int shift)

    {

        int *title,*r,*p;

       

        if(shift == 0)

           return;

       

        shift = shift % ARRSIZE;

       

        title = (int *)malloc(sizeof(int)*shift);

        if( title == NULL )

           return;

       

        r = buffer + (ARRSIZE - shift);

        memcpy(title, r, shift * sizeof(int));

     

        p = buffer + shift;

        memmove(p, buffer, (ARRSIZE - shift) * sizeof(int));

        memcpy(buffer, title, shift * sizeof(int));

       

        free(title);

    }

    這個(gè)算法需要移動(dòng)位數(shù)大小的臨時(shí)輔助空間。如需移動(dòng)兩位,則申請(qǐng)兩個(gè)的空間,然后把從

    右邊起的兩個(gè)元素拷貝的臨時(shí)輔助空間,然后前面的元素向后移動(dòng)兩位,最后再把臨時(shí)空間

    里面的兩個(gè)元素拷貝到前面的兩位即可完成循環(huán)右移。需要執(zhí)行 ARRSIZE次,時(shí)間復(fù)雜度是

    O( N )。

     

    方法四:從內(nèi)存模型上出發(fā)。
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>

    void Rotate(int* beg, int* newBeg, int* end)
    {
    int numElems = end - newBeg;
    int* temp = (int*)malloc(sizeof(int)*(end - newBeg));
    memcpy(temp, newBeg, (end - newBeg)*sizeof(int));
    memmove(beg + numElems, beg, (newBeg - beg)*sizeof(int));
    memcpy(beg, temp, (end - newBeg)*sizeof(int));
    free(temp);
    }

    int main()
    {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    for(int i = 0; i < 10; ++i)
    {
    Rotate(a, a + 1, a + 10);
    for(int j = 0; j < 10; ++j)
    printf("%d ", a[j]);
    printf("\n");
    }
    }
    方法五:先把N個(gè)字符逆序,再把前M個(gè)字符逆序,最后再把這N - M個(gè)字符逆序,即得到最

    終結(jié)果。

    代碼實(shí)現(xiàn)如下:

    /******************************************************************
    * Copyright (c) 2005-2007 CUG-CS
    * All rights reserved
    *
    * 文件名稱:StringShift.c
    * 簡(jiǎn)要描述:字符串循環(huán)左移
    *
    * 當(dāng)前版本:1.0
    * 作    者:raincatss
    * 完成日期:2007-11-18
    * 開發(fā)環(huán)境:Windows XP Sp2 + VC6.0
    * 個(gè)人博客:http://raincatss.cublog.cn/
    ******************************************************************/


    #include <string.h>
    #include <assert.h>

    static void Swap(char *p, char *q);
    static void Reverse(char *str, int i, int n);

    void String_Shift_Reverse(char *str, int n)
    {
        int len;
       
        assert(NULL != str);
        len = strlen(str);
        if (n <=0 || n >= len) {
            return;
        }

        Reverse(str, 0, n - 1);
        Reverse(str, n, len - 1);
        Reverse(str, 0, len - 1);
    }

    static void Swap(char *p, char *q)
    {
        char tmp;

        tmp = *p;
        *p = *q;
        *q = tmp;
    }

    static void Reverse(char *str, int i, int n)
    {
        int l, r;

        for (l = i, r = n; l < r; l++, r--) {
            Swap(&str[l], &str[r]);
        }
    }
     


    #include <iostream>
    #include <algorithm>
    using namespace std;

    int main()
    {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    rotate(a, a + 10 - 4, a + 10);

    for(int i = 0; i < 10; ++i)
    cout << a[i] << ' ';
    }
    方法六:這是我給出的方法,我認(rèn)為是最最好的一種方法,簡(jiǎn)直了,無語(yǔ)了。。。。
    不過網(wǎng)上也有人想到了,呵呵。
    但是這個(gè)方法要求被處理的數(shù)組長(zhǎng)度或位移的位數(shù)中至少有一個(gè)奇數(shù)。
    #include <stdio.h>

    void move(int * ptr, int n, int m)
    {
     if(m<=0)
      return;
     if(!(n%2 || m%2))
     {
      move(ptr,n,m-1);
      move(ptr,n,1);
      return;
     }
     int pos=0;
     int i=0;
     while(++i<n)
     {
      pos=(pos+m)%n;
      int tmp=*ptr;
      *ptr=*(ptr+pos);
      *(ptr+pos)=tmp;  
     }
    }

    void main()
    {
     int a[]={1,2,3,4,5,6,7,8,9,10};
     move(a,10,7);
     for(int i=0;i<10;i++)
      printf("%d ",a[i]);
    }
    該方法對(duì)位移數(shù)m沒有任何要求,只要不為負(fù)數(shù)就可以。
    此外,交換兩個(gè)數(shù)據(jù)可以不用任何的臨時(shí)空間的,優(yōu)化后的代碼如下:
    void move(int * ptr, int n, int m)
    {
     if(m<=0)
      return;
     if(!(n%2 || m%2))
     {
      move(ptr,n,m-1);
      move(ptr,n,1);
      return;
     }
     int pos=0;
     int i=0;
     while(++i<n)
     {
      pos=(pos+m)%n;
      *ptr^=*(ptr+pos);
      *(ptr+pos)^=*ptr;
      *ptr^=*(ptr+pos);  
     }
    }
    再優(yōu)化:
    void move(int * ptr, int n, int m)
    {
     if(m<=0)
      return;
     if(!(n%2 || m%2))
     {
      move(ptr,n,m-1);
      move(ptr,n,1);
      return;
     }
     int pos=0;
     int i=0;
     while(++i<n)
     {
      pos=(pos+m)%n;
      *ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);  
     }
    }
    再用逗號(hào)表達(dá)式優(yōu)化:
    void move(int * ptr, int n, int m)
    {
     if(m<=0)
      return;
     if(!(n%2 || m%2))
     {
      move(ptr,n,m-1);
      move(ptr,n,1);
      return;
     }
     int pos=0;
     int i=0;
     while(pos=(pos+m)%n,++i<n)
      *ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
    }
    最后再優(yōu)化判斷是否為偶數(shù)的運(yùn)算:
    void move(int * ptr, int n, int m)
    {
     if(m<=0)
      return;
     if(!( n&1 || m&1 ))
     {
      move(ptr,n,m-1);
      move(ptr,n,1);
      return;
     }
     int pos=0;
     int i=0;
     while(pos=(pos+m)%n,++i<n)
      *ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
    }

    還有別人給出的一些方法:
    分析:
     
    最容易想到的方法有兩種:
    申請(qǐng)一個(gè)3個(gè)字節(jié)的空間,把“ABC”復(fù)制進(jìn)去,然后把剩下的字符從左到右依次移到相應(yīng)的位置,最后把“ABC”再?gòu)?fù)制到最后,釋放空間,算法結(jié)束。這樣時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(M)。
    只用一個(gè)字節(jié)的輔助空間,每次把字符串循環(huán)左移一位,共移M次。這樣時(shí)間復(fù)雜度為O(M·N),空間復(fù)雜度為O(1)。
    以上兩種方法雖然簡(jiǎn)單,但時(shí)間(或空間)復(fù)雜度令人不盡滿意,有沒有時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(1)的算法呢?下面我們來研究一下。

    方案一

    設(shè)字符串長(zhǎng)度為N,臨時(shí)變量為t,算法步驟如下:

    設(shè)i = 0
    j = i,保存s[j]到t
    把s[(j + N) % M]向前移N位到最終位置s[j % M]
    j += N
    如果j % M != i,則轉(zhuǎn)3;否則下一步
    i++
    如果i < gcd(M, N),則轉(zhuǎn)2;否則移動(dòng)完畢,算法結(jié)束
    實(shí)現(xiàn)代碼如下:

    /******************************************************************
    * Copyright (c) 2005-2007 CUG-CS
    * All rights reserved
    *
    * 文件名稱:StringShift.c
    * 簡(jiǎn)要描述:字符串循環(huán)左移
    *
    * 當(dāng)前版本:1.0
    * 作    者:raincatss
    * 完成日期:2007-11-18
    * 開發(fā)環(huán)境:Windows XP Sp2 + VC6.0
    * 個(gè)人博客:http://raincatss.cublog.cn/
    ******************************************************************/

    #include <stdio.h>
    #include <string.h>
    #include <assert.h>

    static int gcd(int m, int n);

    void StringShift(char *str, int n)
    {
        int i, j, len;
        char tmp;

        assert(NULL != str);
        len = strlen(str);
        if (n <= 0 || n >= len) {
            return;
        }
       
        for (i = 0; i < gcd(len, n); i++) {
            j = i;
            tmp = str[j];
            do {
                str[j] = str[(j + n) % len];
                j = (j + n) % len;
            } while (j != i);
            str[(j + len - n) % len] = tmp;
        }
    }

    static int gcd(int m, int n)
    {
        int tmp;

        while (n != 0) {
            tmp = m % n;
            m = n;
            n = tmp;
        }

        return m;
    }
     

    在do{}while()循環(huán)中,如果k每次加n后不與len取模,可以發(fā)現(xiàn)k - i最后等于M、N的最小公倍數(shù),這樣保證在循環(huán)過程中無重復(fù)下標(biāo)(為什么?請(qǐng)自己想一下)。之所以讓for()循環(huán)做gcd(M, N)次,是因?yàn)槊看蝑o{}while()循環(huán)做M * N / (N * gcd(M, N)) = M / gcd(M, N)次,for()循環(huán)做gcd(M, N)次正好可以保證移動(dòng)M次,即所有元素移動(dòng)一次。(如果誰(shuí)有此法的精確且清楚的數(shù)學(xué)證明,請(qǐng)發(fā)Email:raincatss#gmail.com)

    方案二

    把原字符串分成三部分ABlBr(Br與A長(zhǎng)度相同),循環(huán)左移后為BlBrA??梢韵劝袮與Br互換位置,變?yōu)锽rBlA,然后再把Br與Bl互換,由此可以遞歸求解。

    遞歸實(shí)現(xiàn)代碼如下:

    /******************************************************************
    * Copyright (c) 2005-2007 CUG-CS
    * All rights reserved
    *
    * 文件名稱:StringShift.c
    * 簡(jiǎn)要描述:字符串循環(huán)左移
    *
    * 當(dāng)前版本:1.0
    * 作    者:raincatss
    * 完成日期:2007-11-18
    * 開發(fā)環(huán)境:Windows XP Sp2 + VC6.0
    * 個(gè)人博客:http://raincatss.cublog.cn/
    ******************************************************************/

    #include <stdio.h>
    #include <assert.h>

    static void Swap(char *p, char *q);

    void StringShift(char *str, int len, int n)
    {
        int i;

        assert(NULL != str);
        if (len <= 0 || n <= 0 || n >= len) {
            return;
        }

        if (n < len - n) {
            for (i=0; i<n; i++) {
                Swap(&str[i], &str[len - n + i]);
            }
            StringShift(str, len - n, n);
        } else if (n > len - n) {
            for (i=len-1; i>n-1; i--) {
                Swap(&str[i], &str[i - n]);
            }
            StringShift(str + len - n, n, n + n - len);
        } else {
            for (i=0; i<n; i++) {
                Swap(&str[i], &str[n + i]);
            }
        }
    }

    static void Swap(char *p, char *q)
    {
        char tmp = *p;
        *p = *q;
        *q = tmp;
    }
     

    為提高效率,可以把遞歸轉(zhuǎn)換為迭代,實(shí)現(xiàn)代碼如下:

    /******************************************************************
    * Copyright (c) 2005-2007 CUG-CS
    * All rights reserved
    *
    * 文件名稱:StringShift.c
    * 簡(jiǎn)要描述:字符串循環(huán)左移
    *
    * 當(dāng)前版本:1.0
    * 作    者:raincatss
    * 完成日期:2007-11-18
    * 開發(fā)環(huán)境:Windows XP Sp2 + VC6.0
    * 個(gè)人博客:http://raincatss.cublog.cn/
    ******************************************************************/

    #include <stdio.h>
    #include <assert.h>

    static void Swap(char *p, char *q);

    void StringShift(char *str, int len, int n)
    {
        int i, tmp;
        char *s = str;

        assert(NULL != str);
        if (len <= 0 || n <= 0 || n >= len) {
            return;
        }

        while (n != len - n) {
            if (n < len - n) {
                for (i=0; i<n; i++) {
                    Swap(&s[i], &s[len - n + i]);
                }
                len -=n;
            } else {
                for (i=len-1; i>n-1; i--) {
                    Swap(&s[i], &s[i - n]);
                }
                s += len - n;
                tmp = n;
                n = n + n - len;
                len = tmp;
            }
        }
        for (i=0; i<n; i++) {
            Swap(&s[i], &s[n + i]);
        }
    }

    static void Swap(char *p, char *q)
    {
        char tmp = *p;
        *p = *q;
        *q = tmp;
    }
     

    posted on 2008-03-10 12:47 so true 閱讀(2308) 評(píng)論(0)  編輯  收藏 所屬分類: C&C++

    主站蜘蛛池模板: 亚洲国产成人精品无码区在线网站| 精品亚洲视频在线观看| 亚洲美女aⅴ久久久91| 今天免费中文字幕视频| 亚洲热妇无码AV在线播放| 91在线视频免费观看| 亚洲午夜无码久久久久| 国产成人无码区免费网站| 老司机午夜性生免费福利| 成人免费无码大片A毛片抽搐色欲| 亚洲成人在线免费观看| 亚欧色视频在线观看免费| 亚洲成AV人片久久| 国产美女在线精品免费观看| 亚洲中文字幕无码av在线| 扒开双腿猛进入爽爽免费视频 | 色视频色露露永久免费观看| 亚洲 日韩 色 图网站| 免费黄网在线观看| 色吊丝性永久免费看码| 亚洲大片在线观看| 无人在线观看免费高清视频| 国产a v无码专区亚洲av| 国产精品高清视亚洲精品| 精品国产一区二区三区免费看| 香蕉视频亚洲一级| 在线播放免费播放av片| 亚洲AV成人精品网站在线播放| 久久久久高潮毛片免费全部播放| 亚洲成a人片毛片在线| 日本不卡视频免费| 爽爽爽爽爽爽爽成人免费观看| 久久亚洲精品国产精品| 日韩成人免费视频播放| 中文字幕一区二区三区免费视频| 亚洲黄色片免费看| 又黄又爽的视频免费看| 免费人妻无码不卡中文字幕系| 亚洲性无码AV中文字幕| 自拍偷自拍亚洲精品情侣| 国产精品爱啪在线线免费观看|