피폴라치 수열=>다양한 방법의 비교(분치, 귀속, 동적 기획/추이)

피폴라치 수열은 아주 좋은 예이다. 첫 번째 항목과 두 번째 항목은 모두 1이고, 이후의 모든 항목은 앞의 두 항목의 합이다.
이렇게 하면 피폴라치 수열에는 여러 가지 해법이 있을 수 있다.
우선 반복 사용:

// for  
#include
#include
#include
#include
using namespace std;
long long work(int n){
if(n==1||n==2){
	return 1;
}
else{
	return work(n-1)+work(n-2);
}
}
int main()
{int n;
//freopen("fei.in","r",stdin);
//freopen("fei.out","w",stdout);
scanf("%d",&n);
printf("%lld",work(n));
return 0;	
}

일반적인 귀속 방법에는 많은 중복 계산이 존재한다.효율은 자연히 매우 낮다.예를 들어 f(n-1)를 계산할 때 이미 f(n-2)를 계산해 냈지만 귀환은 f(n-2)를 다시 한 번 계산해야 한다.
그래서 분치, 한 단락 한 단락의 계산을 채택하여 중복 계산을 줄인다.
2점:

// for  
#include
double n;
int k;
long long s,a;
long long sishewuru(double g){
	if(g>=(int)g+0.5){
		return g+1;
	}
	else return g;
}
long long er(long long q){
if(q==1||q==2){
	return 1;
}
else{
	return er(q-1)+er(q-2);
}
}
long long wang(long long p){
	if(p==sishewuru(n/2)){
		return s;
	}
	if(p==sishewuru(n/2)-1){
		return a;
	}
	else return wang(p-1)+wang(p-2);
}
int main()
{//freopen("fei.in","r",stdin);
//freopen("fei.out","w",stdout);
scanf("%lf",&n);
s=er(sishewuru(n/2));
a=er(sishewuru(n/2)-1);
long long o=wang(n);
printf("%lld",o);
return 0;
}

2분의 효율도 극히 제한적이다. 일반적인 귀환은 40 정도까지 계산하면 이미 극한이고 2분은 75 정도까지 계산할 수 있다.
그래서 문제를 한층 더 나누어 그로 하여금 더욱 적게 반복하게 했다.
3점:

// for  
#include
double n;
int k;
long long s,a;
long long f,d;
long long sishewuru(double g){
	if(g>=(int)g+0.5){
		return g+1;
	}
	else return g;
}
long long er(long long q){
if(q==1||q==2){
	return 1;
}
else{
	return er(q-1)+er(q-2);
}
}
long long wang(long long p){
	if(p==sishewuru(n/3)){
		return s;
	}
	if(p==sishewuru(n/3)-1){
		return a;
	}
	else return wang(p-1)+wang(p-2);
}
long long ring(long long i){
	if(i==sishewuru(2*n/3)){
		return f;
	}
	if(i==sishewuru(2*n/3-1)){
		return d;
	}
	else return ring(i-1)+ring(i-2);
}
int main()
{//freopen("fei.in","r",stdin);
//freopen("fei.out","w",stdout);
scanf("%lf",&n);
s=er(sishewuru(n/3));
a=er(sishewuru(n/3)-1);
f=wang(sishewuru(2*n/3));
d=wang(sishewuru(2*n/3)-1);
long long o=ring(n);
printf("%lld",o);
return 0;
}

3점은 단시간 내에 110항 정도를 계산할 수 있다.다음은 과감한 6점.

// for  
#include
double n;
int k;
long long s,a;
long long f,d;
long long w,q,e,r,t,y;
long long sishewuru(double g){
	if(g>=(int)g+0.5){
		return g+1;
	}
	else return g;
}
long long er(long long q){
if(q==1||q==2){
	return 1;
}
else{
	return er(q-1)+er(q-2);
}
}
long long wang(long long p){
	if(p==sishewuru(n/6)){
		return s;
	}
	if(p==sishewuru(n/6)-1){
		return a;
	}
	else return wang(p-1)+wang(p-2);
}
long long dao(long long x){
	if(x==sishewuru(n/3)){
		return f;
	}
	if(x==sishewuru(n/3-1)){
		return d;
	}
	else return dao(x-1)+dao(x-2);
}
long long yu(int v){
	if(v==sishewuru(n/2)){
		return w;
	}
	if(v==sishewuru(n/2-1)){
		return q;
	}
	else return yu(v-1)+yu(v-2);
}
long long nb(int m){
	if(m==sishewuru(2*n/3)){
		return r;
	}
	if(m==sishewuru(2*n/3-1)){
		return e;
	}
	else return nb(m-1)+nb(m-2);
}
long long ring(long long i){
	if(i==sishewuru(5*n/6)){
		return y;
	}
	if(i==sishewuru(5*n/6-1)){
		return t;
	}
	else return ring(i-1)+ring(i-2);
}
int main()
{//freopen("fei.in","r",stdin);
//freopen("fei.out","w",stdout);
scanf("%lf",&n);
s=er(sishewuru(n/6));
a=er(sishewuru(n/6)-1);
f=wang(sishewuru(n/3));
d=wang(sishewuru(n/3)-1);
w=dao(sishewuru(n/2));
q=dao(sishewuru(n/2-1));
r=yu(sishewuru(2*n/3));
e=yu(sishewuru(2*n/3-1));
y=nb(sishewuru(5*n/6));
t=nb(sishewuru(5*n/6-1));
long long o=ring(n);
printf("%lld",o);
return 0;
}

6분 측정에 의하면 단시간 내에 200개 정도를 계산할 수 있고 210개 항목까지 계산할 수 있을 것이다.
이를 통해 일반적인 귀속은 40 정도, 2분에서 75 정도, 3분 110 정도, 6분 200 정도까지 갈 수 있음을 알 수 있다. 짧은 시간에 계산할 수 있는 항목수(n)와 그것이 몇 단락(r)으로 나뉘는지 정비례할 수 있다.
대략 40 정도를 계수로 한다.n=k*r.
그러나 이런 방법도 극히 제한되어 있기 때문에 뒤로 계산하려면 끊임없이 단락을 확대해야 하기 때문에 매우 번거롭다.
그래서 점차적인 추측을 직접 이용하여 동태적인 기획으로 계산하면 효율이 크게 강화될 것이다.

// / for  
#include
long long a[10000];
int main()
{int n;
//freopen("fei.in","r",stdin);
//freopen("fei.out","w",stdout);
scanf("%d",&n);
a[1]=a[2]=1;
for(int i=3;i<=n;i++){
	a[i]=a[i-1]+a[i-2];
}
	printf("%lld",a[n]);
	return 0;
}

나는 10000개의 정형수조를 정의했는데 이런 방법으로 10000개를 계산하는 것은 조금도 힘들지 않다는 것을 알 수 있다.이렇게 보면 이런 방법은 속도와 효율이 매우 높다.
피폴라치의 수열은 다르기 때문에 해법이 아직 매우 많으니, 여기에는 더 이상 열거하지 않겠다.