啊哈，算法 之原語的力量

現在引入程式設計珠玑第二章第二個問題

請将一個具有n個元素的一維向量向左旋轉i個位置．假如n = 8 ,i = 3 ,那麼向量abcdefgh旋轉之後得到的向量defghabc簡單編碼使用有一個具有n個元素的中間向量分n步完成此作業．你可以僅僅使用幾十個位元組的微小記憶體，花費與n成正比例的時間完成該向量的旋轉？

我看到這道題目時沒有看他的要求，這還不好辦，申請i個輔助空間，将剩下的n-i個數向前移動，然後将輔助空間裡面的資料連接配接上不就可以了．

作者分析到＂這個方案引入了i個輔助空間，顯然當數字很大的時候浪費了很多空間，而另外一個不同的方法中，我們可以定義一個函數來将x向左旋轉一個位置（時間上和n成正比）；然後調用n次，但這又很浪費時間＂

作者提出了三中解決方法：

１　就用一個中間變量存放x[0],然後将x[i]移到x[0],x[2*i]移到x[i，依次類推（将x中的所有下标對n取摸），直到我們有回到x[0]為止，不過在這時候我們從中間變量中提取元素，然後結束該過程．如果該過程不能夠移動所有的元素，那麼我們從x[1]開始重複上面過程，知道所有的元素被交換到．

以下是我完成大代碼，（我還沒有看作者後面的原來代碼，以後補上）

#include " stdio.h "

#include " stdlib.h "

#include " string.h "

#define  SIZE 10

char *  circumgyrate( char   *  number, int  circle)

{

  int  lenChar  =  strlen (number),count  =   0  , i  =   0  , time  =   0  ;

  char  temp ;

  while  ( count  <  lenChar  &&  i  <=  circle  -   1 )

    {

  temp  =  number[i];

  time  =   0  ;

   while  ( ((time + 1 ) * circle)  %  lenChar  !=  i  &&  count  <  lenChar )

  {

            count  ++  ;  

   number[time * circle  %  lenChar]  =  number[(time + 1 ) * circle % lenChar];

   time  ++  ;

  }

        count  ++  ;

  number[time * circle  % lenChar]  =  temp ;

  i  ++  ; 

 }

    return  number ;

}

int  main()

{

  char *  testChar;

  int  number ;

  int  circleNum ;

 printf( " please input the number char you input: " );

 scanf( " %d " , & number);

 testChar  =  ( char * )malloc( sizeof ( char ) * (number + 1 ));

 printf( " please input the chars: " );

 scanf( " %s " ,testChar);

 printf( " please input the number of circle you want: " );

 scanf( " %d " , & circleNum);

    printf( " the chars %s circle %d is: " ,testChar,circleNum);

 printf( " %s " ,circumgyrate(testChar,circleNum));

  return   0  ;

}

輸出結果：

please input the number char you input:20

please input the chars:1234567890abcdefghij

please input the number of circle you want:7

the chars 1234567890abcdefghij circle 7 is:

890abcdefghij1234567

２旋轉向量實際上就是将向量ab的倆個部分交換為向量ba，這裡a代表前i個元素，假設a比b短，我們将b分為b1,b2，使b２的長度和a的一樣長，交換b2和a，将ab1b2變化為b2b1a，現在就隻要交換b2,b1的倆部分，由于新問題和原來的問題一樣的，是以我們以遞歸的方式解決

代碼(自己寫的,書上的稍後補上)

#include " stdio.h "

#include " stdlib.h "

#include " string.h "

char *  reversed( char   *  number, int  frontNum , int  len, int  startLoc )

{

    int  i ;

    if  ( frontNum   ==  len  -  frontNum )

   {

          for  (i  =  startLoc ; i  <  startLoc  +  frontNum; i  ++  )

   {

    number[i]  ^=  number[ i  +  frontNum];

             number[ i  +  frontNum]  ^=  number[i];

             number[i]  ^=  number[ i  +  frontNum];

   }

    return  number ;

   }

    else   if  ( frontNum  <  len  -  frontNum )

   {

     for  (  i  =  startLoc ; i  <  startLoc  +  frontNum ; i  ++  )

    {

            number[i]  ^=  number[ len  -  frontNum  +  i];

   number[len  -  frontNum  +  i ]  ^=  number[i];

            number[i]  ^=  number[ len  -  frontNum  +  i];

    }

     return  reversed ( number ,frontNum ,len  -  frontNum ,startLoc);

   }

    else  

   {

          for  ( i  =  startLoc ; i  <  startLoc  +  len  -  frontNum ; i  ++  )

   {

            number[i]  ^=  number[frontNum  +  i];

           number[frontNum  +  i]  ^=  number[i];

            number[i]  ^=  number[frontNum  +  i];

   }

        return  reversed ( number , 2 * frontNum  -  len ,frontNum ,startLoc  +  len  -  frontNum);

   }

}

int  main()

{

  char   *  testChar ;

  int  number ;

  int  circleNum ;

 printf( " please input the number char you input: " );

 scanf( " %d " , & number);

 testChar  =  ( char * )malloc( sizeof ( char ) * (number + 1 ));

 printf( " please input the chars: " );

 scanf( " %s " ,testChar);

 printf( " please input the number of circle you want: " );

 scanf( " %d " , & circleNum);

    printf( " the chars %s circle %d is: " ,testChar,circleNum);

 printf( " %s " ,reversed(testChar,circleNum,number, 0 ));

  return   0  ;

}

運作結果:

please input the number char you input:20

please input the chars:1234567890abcdefghij

please input the number of circle you want:7

the chars 1234567890abcdefghij circle 7 is:

890abcdefghij1234567

3 這個算法我覺得真的是很棒的一個算法,将這個問題看做是把數組ab轉換成數組ba,我們先從ab開始,轉置a,然後轉置b,然後将a的轉置和b的轉置一起轉置得到ba

程式 如下(自己寫的):

#include " stdio.h "

#include " stdlib.h "

#include " string.h "

char *  testChar;

void  reversed(  int  startLoc , int  endLoc)

{

  for  (  int  i  =  startLoc ; i  <=  (endLoc  +  startLoc) / 2   && i  !=  endLoc  -  i  +  startLoc ; i  ++  )

 {

  testChar [i]  ^=  testChar[endLoc  -  i  +  startLoc];

  testChar[endLoc  -  i  +  startLoc]  ^=  testChar [i] ;

  testChar [i]  ^=  testChar[endLoc  -  i  +  startLoc];

 }

}

int  main()

{

  int  number ;

  int  circleNum ;

 printf( " please input the number char you input: " );

 scanf( " %d " , & number);

 testChar  =  ( char * )malloc( sizeof ( char ) * (number + 1 ));

 printf( " please input the chars: " );

 scanf( " %s " ,testChar);

 printf( " please input the number of circle you want: " );

 scanf( " %d " , & circleNum);

    printf( " the chars %s circle %d is: " ,testChar,circleNum);

 reversed(  0  , circleNum  -   1  ) ;

 reversed (circleNum ,number  -   1  );

 reversed (  0  ,number  -   1  ) ;

 printf( " %s " ,testChar);

  return   0  ;

}

運作結果:

please input the number char you input:20

please input the chars:1234567890abcdefghij

please input the number of circle you want:7

the chars 1234567890abcdefghij circle 7 is:

890abcdefghij1234567