プログラミング珠玉--swap section

3367 ワード
プログラミング アルゴリズム
プログラミング珠玉第2編は主に3つの思想を提出した.
1. 二分検索(binary search)
2. パーティションを交換します.(swap section)
3. 署名する.        (signature)
 
二分検索はよく知っていますが、サインはいい考えだと思います.差は多くないでしょう.hashMapに相当するでしょう.このセクションで私が主に注目しているのは、パーティションを交換するアルゴリズムです.
 
問題の説明は、長さnの文字列iの位置を回転させることです.例えば、文字列「abcdefgh」、n=8、i=3であり、回転して「defghabc」を得る.
最も考えやすいのは、もちろん前のi文字を保存し、後ろのn-i文字を前に移動し、保存したi文字列をn-i文字の後ろに貼り付けることです.時間的複雑度はO(n),空間的複雑度はO(i)であり,せん断された文字を格納するために余分なi空間が必要である.空間の複雑さをO(1)に下げる方法はありますか?
 
本の中でGries and Millsの総括報告書に言及した..ネットで探してきました.レポートには、次の3つのアルゴリズムが記載されています.
1. Dolphine swap.
Dolphine swapの基本的な考え方は、x[0]を先に保存し、x[i]をx[0]に、x[2 i]をx[i]に...iとnが互いに質的であれば,1サイクルですべての文字列を配置し,最後にtを最後の空席に埋め込むことができる.iとnが互いに質を持たない場合はgcdサイクルが必要である.
void dolphine( char* s, int pos ){
	int n=strlen(s);
	int r = gcd( n, pos );
	int i=0;
	for( i=0; i<r; i++ ){
		char t=s[i];
		int j=i;
		while(1){
			int k = j+pos;
			if( k >= n )
				k -= n;
			if( k == i )
				break;
			s[j] = s[k];
			j =k ;
		}
		s[j] = t;
	}
}

//    gcd   
int gcd( int a, int b ){
	while( a != b ){
		if( a>b )
			a -= b;
		else
			b -= a;
	}
	return a;
}

 
2. Successive swap
in−iの場合、交換後は後のn−i文字列を操作することになる.
void successiveSwap( char*s, int pos ){
	if( pos == 0 || pos == strlen(s) )
		return;
	int i, p;
	i = p = pos;
	j = strlen(s)-i;
	while( i!=j ){
		if( i<j ){
	//swap（ char*s, int a, int b, int m)      s[a...a+m-1] s[b...b+m-1]    
			swap( s, p-i, p+j-i, i );
			j -= i;
		}else{
			swap( s, p-i, p, j );
			i -= j;
		}
	}
	swap( p-i, p, i );
} 

3. Reversal swap
Reversal swapが一番簡単です.a=s[0...i-1],b=s[i...n-1]とし,a=「abcd」,b=「kgthe」とし,
a = reverse(a) = "dcba",
b = reverse(b) = "ehtgk"
reserse(ab)=「kgheabcd」は、私たちが望んでいる結果ではないでしょうか.
  
void reversalSwap( char* s, int pos ){
	reverse( s, 0, pos-1 );
	reverse( s, pos, strlen(s)-1 );
	reverse( s, 0, strlen(s)-1 );
	}

 
Bentleyは後述の練習問題でこの3つのアルゴリズムを比較した結果、比較的大きな配列を考慮すると、この配列は1ページを超えるメモリを占有し、回転距離の増加に伴いdolphineアルゴリズムはページの交換を絶えず招くため、アルゴリズムの時間オーバーヘッドが大きくなる.一方,SuccessiveSwapは比較的良好なlocalityを持つため,時間オーバーヘッドは3つのアルゴリズムの中で最も安定である.ReversalsiveSwapも比較的安定しているが,2回の交換が行われているため,時間はSuccessiveSwapより上である.
添付ファイルはGries and Millsの＜swap section＞
 
この日から「プログラミング珠玉」とこのまとめを見始めましたが、前に出したコードに問題があることに気づき、修正しました.そして第2章で提起した他の2つの問題も面白くて、記録する価値があると思います.
 
いわゆる二分検索は,我々が一般的に考えているような順序付けされた配列を与えて検索するものではないが,思想は一致している.たとえば、99個の0から100の数を指定して、この範囲内でこのデータのセットに含まれていない数を見つけます(99個の数しかありません.重複していない場合は、少なくとも2つの数がこの配列に含まれていません).二分検索の考え方を用いて、データを順番に処理し、例えば50より大きい数を片側に、より小さいものを他方に置く.少なくとも片方のデータが50個未満であれば、必ずこちらの数の中に存在しない数を見つけて、順番に類推することができます.
 
同位語を探して、同位語が同じ計算結果を持つように計算方法を設計します.本の中で与えられた考えは語のアルファベットを並べ替えて、対応する結果を得ることです.次に、すべての単語の計算結果を並べ替えて、同位語が一緒に並べられるようにします.
チェーンテーブル逆シーケンス出力の3つのアルゴリズム
【アルゴリズム】最小生成ツリーのprim