微軟面試題之以遞增順序列印2^i*3^j*5^k

以遞增順序列印出2^i*3^j*5^k的前n項。假設目前已經求出第x項,那麼第x+1項一定是由前x項中的某項乘2，或乘3，或乘5，得到的大于第x項中最小的那個數，于是我們立即得到一個n^2的算法，代碼如下

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e4+10;
LL a[MAX];
int main() {
    LL p1,p2,p3;
    LL n,val;
    while(scanf("%lld",&n)==1) {
        LL v=0;
        a[0]=1;
        for(int i=1;i<n;i++) {
        	LL x=1e18;
        	for(int j=0;j<=i;j++) {
        		LL t1=a[j]*2,t2=a[j]*3,t3=a[j]*5;
        		if(t1>a[i-1])x=min(x,t1);
        		if(t2>a[i-1])x=min(x,t2);
        		if(t3>a[i-1])x=min(x,t3);
        	}
        	a[i]=x;
        }
        for(LL i=0;i<n;i++) {
            printf("%lld\n",a[i]);
        }
    }
    return 0;
}
           

下面來進行代碼的優化，假設第x是由含前x-1項中的某一項a[p1]和2相乘得到的，要使第x+1項大于第x項，和2相乘的項必定大于a[p1],同理和3或5相乘的項必定大于a[p2]或a[p3],是以我們可以在得出第x項的時候,如果是*2得到第x項那麼p1後移(保證下一次和2乘的數比這次的大),同理p2,p3的後移也一樣，又由于第n項<=2^n<3^n<5^n,而且每次都有後移，是以p1,p2,p3總的後移次數不會超過3n，是以我們得到了一個O(n)的算法,代碼如下

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e4+10;
LL a[MAX];
int main() {
    LL p1,p2,p3;
    LL n,val;
    while(scanf("%lld",&n)==1) {
        LL v=1;
      	p1=p2=p3=0; a[0]=1;
 		for(LL i=1;i<=n;i++) {
            while(true) {
                val=min(a[p1]*2,min(a[p2]*3,a[p3]*5));
                if(a[p1]*2==val) p1++;
                else if(a[p2]*3==val) p2++;
                else p3++;
                if(val>v) break;
            }
            a[i]=val;
            v=val;
        }
        for(LL i=0;i<n;i++) {
            printf("%lld\n",a[i]);
        }
    }
    return 0;
}