公因数与空间换时间思想

Love The Way You Lie 2022-02-01 03:55 199阅读 0赞

问题1.给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N=10，N！=3628800，N！的末尾有两个0。

问题2.求N！的二进制表示中最低位1的位置。

问题3.丑数问题，把只包含因子2、3、5的数称作丑数。写一个函数，要求输入一个数值n（n>0），求从小到大的第n个丑数的值。

问题4.质数问题，要求写一个函数，输入数值n（n>0），求不小于n的质数的个数。（注意：问题3与问题4的问法其实在本质上是一样的。）

首先分析问题1和2，这两个个题目就是关于阶乘的，而对于这样的问题用质因数分解法比较好处理。将N!进行因式分解：N!=2^X\*3^Y\*5^Z\*T。

问题1即是求N!的因式分解中Z的值，因为2\*5=10，且X>=Z。

问题2即是求N!的因式分解中X的值。

首先给出一个求某数中因子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;
    }

上面两题都可以循环调用这个函数来求结果。但是这样效率不高，对于N!求因式分解的指数，有个公式，例如求解Z：Z=\[N/5\]+\[N/5^2\]+\[N/5^3\]…。

公式中\[N/5\]表示不大于N的数中5的倍数贡献一个5，,\[N/5^2\]表示不大于N的数中5^2的倍数再贡献一个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的结果，而这个数可以用t2、t3、t5进行标记（当然标记是动态的）。代码如下：

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的基础上继续算其余的步骤。为了节省空间，可以保存一些特殊的点就可以了，然后程序会越跑越快。

但是这个想法，与一般的思路不一样，不是算法的设计了，而是一种思想，甚至可以说有点作弊的味道。

这里就不给出具体程序了。