UVa 3 n+1問題

UVa 3 n+1問題
1.       問題の説明
番号:100.
簡単な説明:1以上の整数に対して、現在数が偶数である場合、次の数は現在数を2で除算し、現在数が奇数である場合、次の数は現在数を3に1加算し、1まで計算する.では、形成する数列の長いをcycle-lengthと呼ぶ.
問題の入力は:1つの区間を与える[a,b]
問題の出力は、所与の区間(端点を含む)から数のcycle-lengthの最大のcycle-lengthを出力.
詳細については、ここを参照することができる.
2.       もんだいぶんせき
            2.1直観分析
最も直感的な方法は、当然、蛮力法(brute-force)を用いる、与えられた区間の各数をcycle-lengthとして求め、従ってcycle-lengthの中で最大のものを見つければよい.
            2.2最適化
最適化は分析の基礎に基づいている.
まず簡単な例を実験します.
例えば、所与の区間がB[1,10]、すなわち1,2,3,4,5,6,7,8,9,10である
簡単な分析から分かるように、通常大きな数は大きなcycle-lengthを有するので、まずA=9(なぜ10を取らないのか、9は1回の処理後に28に変更され、10より大きい)を取って、与えられた法則に従って以下のように行うことができる.
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
上の赤いマークの部分は、所定の区間内にあり、それらのcycle-lengthは明らかに現在の数9より小さいcycle-lengthであるため、これらの数は所定の区間内から除去され、現在のcycle-lengthを記憶することができ、
1回の操作後、与えられた区間は3,6になる
この区間が空になるまでこの方法に従って、停止し、その中で最大のcycle-lengthが求められる.
            2.3算出アルゴリズム
アルゴリズムの説明は2.2の最適化部分の分析と同じで、具体的なアルゴリズムの説明は3.
3.       アルゴリズムの説明
アルゴリズム疑似コード(クラスC)は以下のように記述される.
function getMCL
B[left, right];//指定区間
mcl = 0;//mclはmax-cycle-lengthを指す
while !B.empty()
{
A = getCandidate(B);//この関数はB区間で現在最も適切に処理されている要素を見つけるために使用されます.
//一般的に最大の奇数です.つまり、cycle-lengthの要素が大きいと予想されます.
                     ccl = 1;//cclとはcurrent-cycle-lengthのこと
                     while (A!=1)
              {
                     ccl++;
                     A = (A%2)?(3*A+1):(A/2);
if find(B,A)/この関数は、B区間内に中間結果Aが存在するか否かを判断するために用いられる
                            pop(B,A);//有れば除く
              }
              mcl = (mcl       }
       return mcl;
 
4.       具体的な実装

#include "iostream"
using namespace std;

int getCandidate(int B[], int base, int n)
{
	int i;
	for (i = n-1; i>=0; i--)
	{
		if (((base+i) % 2)&&(B[i]==0))
			return i;
	}
	for (i = n-1; i>=0; i--)
	{
		if (!B[i])
			return i;
	}
	return -1;
}
int nadd2(int left, int right)
{
	int Blength = right - left + 1;
	int length = Blength;
	int *B = new int[length];
	for (int i=0; i<length; i++)
		B[i] = 0;
	int mcl = 0;
	while (length > 0)
	{
		int ccl = 1;
		int pos = getCandidate(B, left, Blength);
		if (pos==-1)
			break;
		B[pos] = 1;
		length--;
		int A = pos+left;
		while (A!=1)
		{
			ccl ++;
			A = (A%2)?(3*A+1):(A/2);
			int Apos;
			if ((A-left>Blength)||(B[A-left])||(A<left))
				Apos = -1;
			else
				Apos = A-left;
				
			//B[Apos] = 1;
			if (Apos!=-1)
			{
				B[Apos] = 1;
				length --;
			}
		}
		mcl = (mcl<ccl)?ccl:mcl;
	}
	delete[] B;
	return mcl;
}
int main()
{
	int left, right;
	while(cin>>left>>right)
		cout<<left<<" "<<right<<" "<<nadd2(left,right)<<endl;
	return 0;
}

 
 


5.       複雑性解析
主な消費時間部分は二層循環部分であり、外層循環の回数は主に内層循環の区間内の命中率に依存する.統計学的分析は行われていないが、candidateの選択が適切であれば、内層サイクルごとに50%以上のヒット率がある.
区間内数Aの内層サイクル数(すなわち、Aから規則的に1に変化するcycle-length)がXであり、平均ヒット率がpであると仮定すると、時間複雑度は、
T(n)=X*T(n*(1-p)/Xが平均cycle-length
6.       コメント
実装過程では、最初はC++のvectorが使用するが、実行時の実際の消費時間は配列を使用する蛮力法よりも長く、コンパイラがvectorというデータ構造を維持する際に消費する時間が比較的大きいため、特にvectorのearse法を使用して特定の要素を削除する場合に分析される.最後に最も基本的な配列を用いて実現する、削除状態をマークで示す.
したがって、実際のアルゴリズム実装においても、データ構造の選択は非常に重要である、いわゆるプログラム=アルゴリズム+データ構造である.
改善できる点は、getCandidate関数のアルゴリズム、すなわち、cycle-lengthが長い要素をどのように推定するか、また、内層ループが区間内で削除状態としてマークする要素に現れると、内層ループが終了する.