分治アルゴリズム——二分検索法

30889 ワード
アルゴリズム(新しい)
分治アルゴリズム——二分検索法
ウィキペディアにおける分治アルゴリズムの解釈は以下の通りである.
コンピュータ科学において,分治法は多重分岐再帰に基づく重要なアルゴリズムモデルを構築するものである.字面上の解釈は「分而治之」であり、1つの複雑な問題を2つ以上の同じまたは類似のサブ問題に分け、最後のサブ問題が簡単に直接解くことができるまで、元の問題の解、すなわちサブ問題の解の合併である.
このテクニックは,並べ替えアルゴリズム(集計並べ替え,高速並べ替え),フーリエ変換(高速フーリエ変換)のような多くの効率的なアルゴリズムの基礎である.
一方,分治法アルゴリズムの理解と設計には一定の時間がかかる.帰納法で理論を証明するように、再帰を推進するためには、既存の問題に取って代わる比較的概括的または複雑な問題が必要になることが多い.問題を適切に要約するシステム的な方法はない.
分治法という名前は、ソートされた列のいずれかを検索するための折半検索アルゴリズム(数値解析で類似したルート計算アルゴリズム)など、問題を1つの細い問題だけに簡略化するために使用される場合もあります.これらのアルゴリズムは一般的な分治アルゴリズムよりも効率的に実行できる.ここで,アルゴリズムが末尾再帰を用いれば簡単なループに変換できる.しかし、この一般化の下で、再帰またはループを使用するすべてのアルゴリズムは、「分治アルゴリズム」と見なされる.したがって、一部の著者らは、「分治法」という名前は、少なくとも2つのサブ問題を持つアルゴリズムにのみ使用されるべきであると考えている.サブ問題の1つだけが減治法という名前を提案されたことがある.
分治アルゴリズムは通常数学的帰納法で検証される.その計算コストの多くは再帰関係式を解くことで判定される.
分治アルゴリズムは1種のとても重要なアルゴリズムで、その字面の上の意味は“分而治之”で、1つの複雑な問題を2つ以上の同じ問題あるいは類似のサブ問題に分解して、左後のサブ問題まで簡単に解くことができて、もとは問題の解はサブ問題の解の合併で、分治の技巧は多くの効率的なアルゴリズムの基礎で、たとえば、高速ソート、集計ソート、高速フーリエ変換などです.
私たちは一つのテーマを通じて分治アルゴリズムの重要なアルゴリズムである二分ルックアップ法(折半ルックアップ法、以下二分法と略称する)を理解する.
まず、ウィキペディアで二分法をどのように説明しているかを見てみましょう.
コンピュータ科学において、二分ルックアップアルゴリズム(英語:binary search algorithm)は、折半ルックアップアルゴリズム(英語:half-interval search algorithm)、対数ルックアップアルゴリズム(英語:logarithmic search algorithm)[2]とも呼ばれ、ある特定の要素を秩序配列でルックアップする検索アルゴリズムである.検索プロセスは配列の中間要素から始まり、中間要素がちょうど検索する要素である場合、検索プロセスは終了します.特定の要素が中間要素より大きいか小さい場合は、配列が中間要素より大きいか小さいかの半分で検索され、最初と同じように中間要素から比較されます.ステップ配列が空の場合は、見つからないことを意味します.この検索アルゴリズムは、比較のたびに検索範囲を半分に縮小します.
二分ルックアップアルゴリズムの場合の複雑さは対数時間である.二分ルックアップアルゴリズムは定数空間を用い,任意のサイズの入力データに対してもアルゴリズムが用いる空間は同じである.入力データの数が少ない場合を除き、二分ルックアップアルゴリズムは線形検索よりも速いが、配列は事前にソートされなければならない.特定の、迅速な検索のために設計されたデータ構造がより効果的であるにもかかわらず(ハッシュテーブルなど)、二分検索アルゴリズムの応用面はより広い.
二分検索アルゴリズムには多くの中変種がある.例えば、分散積層は、複数の配列における同じ数値の探索を向上させることができる.分散積層は計算幾何学と他の分野の多くの探索問題を効果的に解決した.インデックス検索は、二分検索アルゴリズムを境界のないリストに拡張します.二叉探索ツリーとBツリーのデータ構造は二分探索アルゴリズムに基づいている.
二分法はその後多くのデータ構造とアルゴリズムにおいて重要な役割を果たした.
二分法を盗むテンプレートの問題を見てみましょう.
入力データ
入力ファイルの最初の行はNで、N個の要素があることを表し、2番目の行はN個の数で、このN個の数は小さいから大きいまで並べ替えられ、3番目の行はMで検索する数を表す(N<=10000).
出力データ
1つの数、すなわち、その数が見つかった場合、出力位置、そうでなければ出力-1.
サンプル入力
3
2 4 6
4
サンプル出力
2
この問題を解決するには、再帰的な二分アルゴリズムと非再帰的な二分アルゴリズムを採用する2つの考え方があります.
再帰的二分法
まず入力したN個の数字を配列numberに格納し、その後、検索時に辞書を引くように、まず最も中間のデータの最も中間の番号をmidに設定します.この列の開始位置はhead、終了位置はtailです.mid=(head+tail)/2で、配列の中間値と見つける必要がある値の関係は次の3つあります.
number[mid]==Mであれば、この位置が要求される数字で、mid+1を出力すればよい
number[mid]number[mid]>Mでは、この数字の位置を少し後ろにして、mid=tail、headを変わらず、二分法を続けます
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#define R register 
#define LL long long 
#define pi 3.14159265358979323
using namespace std;

inline void search(int head, int tail, int M, int number[]){
	if(tail > head){
		int mid = (head + tail) / 2;
		if(number[mid] == M){
			printf("%d", mid + 1);
			return ;
		}
		else{
			if(number[mid] < M){
				search(mid, tail, M, number);
			}
			else{
				search(head, mid, M, number);
			}
		}
	}
	else{
		printf("-1");
	}
}

int main(){
	int N, M, number[10100];
	scanf("%d", &N);
	for(R int i = 0; i < N; ++ i){
		scanf("%d", &number[i]);
	}
	scanf("%d", &M);
	search(0, N, M, number);
	return 0;
}

非再帰的二分法
非再帰的な二分法は,以前の再帰形式の二分法とこの問題を処理する考え方は同じであるが,再帰的な二分法を用いる効率は再帰的な二分法を用いるよりも再帰的な二分法を用いる方が低いためである.
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#define R register 
#define LL long long 
#define pi 3.14159265358979323
using namespace std;

inline void search(int head, int tail, int M, int number[]){
	while(head < tail){
		int mid = (head + tail) / 2;
		if(number[mid] == M){
			printf("%d", mid + 1);
			return; 
		}
		else if(number[mid] < M){
			head = mid;
		}
		else{
			tail = mid;
		}
	}
	printf("-1");
}

int main(){
	int N, M, number[10100];
	scanf("%d", &N);
	for(R int i = 0; i < N; ++ i){
		scanf("%d", &number[i]);
	}
	scanf("%d", &M);
	search(0, N, M, number);
	return 0;
}

二分法でできる問題をもう一度見てみましょう.
タイトルの説明
最小の自然数Nを見つけて、N!10進数でQ個の0を含む.
入力データ
1つの数字Q(0<=Q<=10^8).
出力データ
No solutionが出力されない場合、Nが出力されます
サンプル入力
2
サンプル出力n
10
Qのデータ範囲、つまりNを観察!の末尾0はすでに1千万個を超え、すでにlong longの範囲を超えているので、Nを採用すれば!末尾0の数を求めることは明らかに不可能であり,式により末尾0の数を求めることができる.
f(N!) = N/5 + N/(5^2) + N/(5^3) + … + N/(5^n)
このような公式を通じて私はNを得ることができます!中末尾0の個数
具体的に末尾0の数を求めるコードは以下の通りです.
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#define R register 
#define LL long long 
#define pi 3.14159265358979323
using namespace std;

int main(){
	int N;
	scanf("%d", &N);
	int total = 0;
	int number = 5;
	while(number <= N){
		total += N / number;
		number *= 5;
	} 
	printf("%d", total);
	return 0;
}

このコードでNが109の場合、N!末尾0の数は:24999999で、少なくともNが1億の場合、末尾0の数が必要な範囲を超えていることを決定し、1から109の数字がこの条件に合致していることを2分で検索することができます.我々が必要とするのは最小のNがこの条件を満たすことができる数であるため、この数Nは必ず5の倍数であり、最後に求めた数を判断する必要があり、もしこの数が5の倍数でなければ、この数を5の倍数に減らす必要があり、コードは以下の通りである.
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#define R register 
#define LL long long 
#define pi 3.14159265358979323
using namespace std;

inline int count(int number){
	int total = 0;
	int number_1 = 5;
	while(number_1 <= number){
		total += number / number_1;
		number_1 *= 5;
	}
	return total;
}

int main(){
	int Q;
	scanf("%d", &Q);
	int head = 1, tail = 1e9;
	while(head < tail){
		int mid = (head + tail) / 2;
		int ans = count(mid);
		if(ans == Q){
			if(ans % 5 != 0){
				mid -= mid % 5;
			}
			printf("%d", mid);
			return 0;
		}
		else if(ans < Q){
			head = mid;
		}
		else if(ans > Q){
			tail = mid;
		}
	}
	printf("no solution");
	return 0;
}
C言語プログラミング(五)選択制御構造
Poj 2112[最大ストリーム][二分図の多重整合]