啊哈，算法 之原语的力量

现在引入编程珠玑第二章第二个问题

请将一个具有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