编程珠玑随笔

第二章：基本的算法(1)

   下面就从编程珠玑的第二章算法讲起，首先请看问题描述:

将一个n元一维向量向左旋转i个位置。例如：当n=8时且i=3时，向量abcdefgh旋转为defghabc。

简单的代码可以使用一个n元的中间变量在n步内完成工作，下面介绍一些更简便的算法。

1:杂技算法:

　　移动x[0]到临时变量t,然后移动x[i]到x[0],x[2i]到x[i],依次类推(将x中的所有下标对n取模),直到返回到取x[0]值的元素，此时改为从t取值然后终止过程，当i为3时n为12时,元素安如下顺序进行移动：

 

(此代码用到了求最大公约数的算法)

 

#include<iostream>

using namespace std;

//求最大公约数
//欧几里得算法
int gcd(int a, int b)
{
    while( a!= b)
    {
        if(a>b) 
        {    
         a-=b;
        }
        
        else 
        {
            b-=a;
        }
    }
    return a
        ;
}

//杂技算法
void Rotate1(char* a,int lenth,int rotateLen)
{
    int gcdNum = gcd(lenth,rotateLen);//字符串的长度和旋转次数的最大公约数是所需的置换数
    
    for(int i=0; i<gcdNum; i++)
    {
        char temp = a[i];
        int first = i;
        while(true)
        {
            int second = (first+rotateLen)% lenth;
            
            if(second == i) break;
            
            a[first] = a[second];
            
            first = second;
        }
        a[first] = temp;
    }
}


int main()
{
    char a[9] = "abcdefgh";
    Rotate1(a,8,3);
    cout<<a<<endl;
    return 0;
}

 

 

2:求逆算法

 

求解过程：我们将问题看做是把数组ab转换成数组ba

将a[n]看做是向量BC组成，最终的结果需要时CB，过程如下：将BC各分别取逆B^-1C^-1，再对整个式子取逆，得到CB

 

#include<iostream>

using namespace std;

void Revert(char* str,int start,int end)//求逆算法
{
    while(start<end)
    {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }
}

void Rotate1(char* a,int start,int end)
{
    Revert(a,0,2);
    Revert(a,3,7);
    Revert(a,0,7);
}


int main()
{
    char a[9] = "abcdefgh";
    Rotate1(a,0,7);
    cout<<a;
}

这样 实现了两种旋转的算法，好了今天就到这了。