公因数と空間の時間の思想を交換します

問題1.整数Nが与えられると、Nの階乗N!最後に0はいくつありますか?例:N=10,N!=3628800,N!の末尾に0が2つあります.
問題2.Nを求めます!のバイナリ表示で最下位1の位置を示します.
問題3.丑数問題では,因子2,3,5のみを含む数を丑数と呼ぶ.関数を書いて、1つの数値n(n>0)を入力することを要求して、小さいから大きいn番目の丑数の値を求めます.
問題4.質量数の問題、1つの関数を書くことを要求して、数値n(n>0)を入力して、nの質量数の個数より小さくないことを求めます.(注意:質問3と質問4の質問は本質的に同じです.)
 
まず問題1と2を分析し,この2つの問題は階乗に関するものであり,このような問題は質量因数分解法で処理したほうがよい.N!因数分解を行う:N!=2^X*3^Y*5^Z*T.
問題1はNを求めることです!の因数分解におけるZの値は、2*5=10であり、X>=Zである.
問題2はNを求めることです!を選択します.
まず、ある数の因子tの指数を求めるアルゴリズムを与えます.

int indexOfT(int num,int t)
{
	int count = 0;
	int j;
	for(int i=1;i<=num;i++)
	{
		j=i;
		while(j%t==0)
		{
			count++;
			j/=t;
		}
	}
	return count;
}

上記の2つの問題は、この関数をループして結果を求めることができます.しかし、このような効率は高くなく、Nに対して!因数分解の指数を求めて、1つの公式があって、例えばZ:Z=[N/5]+[N/5^2]+[N/5^3]....
式中[N/5]はN以下の数のうち5の倍数寄与を1つ5、[N/5^2]はN以下の数のうち5^2の倍数寄与を1つ5……コードは以下の通りである.

count = 0;
while(n)
{
	n/=5;
	count +=n;
}

今からブス数の問題を見てみましょう.
n番目の醜数を繰り返して問題を解決することができます.

bool IsUgly(int number)
{
    while(number % 2 == 0)
        number /= 2;
    while(number % 3 == 0)
        number /= 3;
    while(number % 5 == 0)
        number /= 5;
 
    return (number == 1) ? true : false;
}

int GetUglyNumber_Solution1(int index)
{
    if(index <= 0)
        return 0;
 
    int number = 0;
    int uglyFound = 0;
    while(uglyFound < index)
    {
        ++number;
 
        if(IsUgly(number))
        {
            ++uglyFound;
        }
    }
 
    return number;
}

このコードは効率が低く,ここでは空間的に時間を変えることでアルゴリズムの時間的複雑さを低減できる.しかし、空間を変えるだけでは十分ではありません.ブス数の定義を分析すると、ブス数は別のブス数に2、3、5を乗じた結果(1を除く)であるべきであることがわかります.そのため、ブス数を順番に格納する配列を作成することができます.その後、配列にない最小のブス数を後方に生成し続け、このブス数は、前のブス数に2、3、5を乗じた結果に違いないが、この数はt 2、t 3、t 5でマークすることができる(もちろんマークは動的).コードは次のとおりです.

int min(int a,int b)
{
	return a<b?a:b;
}
int GetUglyNumber_Solution2(int index)
{
	if (index<=0)
		return 0;
	int* ugly=new int[index];
	int count=1;
	ugly[0]=1;
	int t2,t3,t5;
	t2=t3=t5=0;
	int a2,a3,a5,minNum;
	while (index>count)
	{
		count++;
		a2=2*ugly[t2];
		a3=3*ugly[t3];
		a5=5*ugly[t5];
		minNum=min(a2,min(a3,a5));
		ugly[count-1]=minNum;
		if (a2<=minNum)
			t2++;
		if (a3<=minNum)
			t3++;
		if (a5<=minNum)
			t5++;
	}
	int result=ugly[count-1];
	delete [] ugly;
	return result;
}

最後に質量数の問題を見てみましょう.
nの素数を求めるには,2<=i<=sqrt(n)をループテストするだけで,nを除去できるかどうか.効率を向上させるために、ふるいを導入することができます.もちろん、ふるいのサイズはカスタマイズできます.以下のコードで定義するふるいのサイズは6です.

bool isPrime(int number)
{
	if(number<=0) return false;
	int n=sqrt(number);
	for (int i=2;i<=n;i++)
		if (number%i==0) return false;
	return true;
}

int NumOfPrime(int index)
{
	if (index<0) 
		return -1;
	if (index==0) 
		return 0;
	int count=0;
	int i;
	if (index>6)
	{
		count = 4;
		int shaizi[6]={0,1,1,1,0,1};
		i=-1;
		for (int j=7;j<=index;j++)
		{
			i++;
			if (i==6) 
				i=0;
			if (shaizi[i]==0&&isPrime(j))
				count++;
		}
	}
	else
	{
		for (i=1;i<=index;i++)
			if (isPrime(i))
				count++;
	}
	return count;
}

このプログラムは,空間を用いて時間を入れ替える方式で,求めた結果を毎回保存し,その後求めた値を行ったときに前回保存した記録を検索することで,迅速に見つけることができ,求めたnが記録の中で最大のNより大きくなると,Nに基づいて残りのステップを計算し続けることもできる.スペースを節約するために、特別なポイントを保存すればいいので、プログラムは走るほど速くなります.
しかし、この考えは、一般的な考え方とは異なり、アルゴリズムの設計ではなく、思想であり、カンニングの味さえあると言える.
ここでは具体的な手順を示しません.