プログラミング珠玉(二)文字列左回転

2286 ワード

プログラミング珠玉第二章の内容は、作者の意味が分からない内容がある.次はベクトル左旋と変位語の問題です.
一、n元ベクトルを左にi個の位置に回転させる.例えば、N＝8、i＝3のとき、ベクトルabcdefghabcはdefghabcに回転する.このテーマのプログラミングの美しさにも2.17節配列のループシフトと3.1節文字列シフトに含まれる問題がある.まとめてみると、5つの解法がありますが、プログラミング珠玉には2つのよく分からないアルゴリズムがあり、簡単に3つのアルゴリズムを紹介します.
第1のアルゴリズムは比較的に直接で、1つを書くことができて毎回左に1位移動して、3回移動して完成することができて、アルゴリズムの複雑度はi*Nです.ここではもう一つの誤りがあり,i>Nの場合もあると考えられるが,この場合,N回のループ移動後にベクトルが元のままに還元されることに気づくので,i=i%Nに対して先に対応することができ,これではiは大きくなく,アルゴリズム複素度はO(N 2)である.
第2のアルゴリズムは空間的に時間を変える方法を利用することができる.また、i=i%Nをiに対して処理した後、iサイズの空間を開き、文字列の前のi個の値を保存する.そして、文字列をi番目からi番目に直接移動し、空間i文字を後ろに補充すればよい.
第3のアルゴリズムは、反転により、文字列をabの2文字列に分けてaを反転〜aし、bを反転して〜bを得、abを〜a〜bに変えて〜a〜b全体を反転すればbaを得ることができる.このアルゴリズムはまた、abc文字列中のc列とa列の位置を切り替える必要があるなど、いくつかの要求に対して、a、b、c列をそれぞれ反転して全体を反転すればよい.このように時間的複雑度はNのみに関係してO(N)となる.次は3つのアルゴリズムのコードです.

#include <iostream>
using namespace std;

void leftShift1(char *a, int len, int i);
void leftShift2(char *a, int len, int i);
void leftShift3(char *a, int len, int i);
void reverse(char *a, int s, int e);

int main()
{
        char a[] = "abcdefgh";
        leftShift3(a, 8, 3);
        printf("%s
", a);
        return 0;
}

void leftShift1(char *a, int len, int i)
{
        i=i%len;
        while(i--)
        {
                char temp = a[0];
                for(int j=0; j<len; j++)
                        a[j] = a[j+1];
                a[len-1] = temp;
        }
}

void leftShift2(char *a, int len, int i)
{
        char *temp = new char[i]();
        memcpy(temp, a, i);
        memcpy(a, &a[i], len-i);
        memcpy(&a[len-i], temp, i);
}


void leftShift3(char *a, int len, int i)
{
        reverse(a, 0, i-1);
        reverse(a, i, len-1);
        reverse(a, 0, len-1);
}
void reverse(char *a, int s, int e)
{
        while(s<e)
        {
                char temp = a[s];
                a[s] = a[e];
                a[e] = temp;
                s++;
                e--;
        }
}

Floyd最短パスアルゴリズム

並列調査セット(等価クラス)ADT学習分析