浅谈对于等比数列相关递推式的化简及相关问题题解

2018/01/10 17:21
阅读数 56

##一、简单的与等比数列相关函数的化简 ###对于递推式f(n)=mf(n-1)+k: 1.显然,存在一个实数c使其化成f(n)+c=m(f(n-1)+c)的形式,展开后我们有:f(n)=mf(n-1)+(m-1)*c; 2.显然其中(m-1)*c=k,进而可得c=k/(m-1); 3.那么构造等比数列就很简单了:我们建立一个新的数列A,使A(n)=f(n)+c,那么显然数列A为等比数列,公比为m;

##二、相关题目 ###1.[洛谷P1760]通天之汉诺塔 ####Description

-在你的帮助下,小A成功收集到了宝贵的数据,他终于来到了传说中连接通天路的通天山。但是这距离通天路仍然有一段距离,但是小A突然发现他没有地图!!!但是幸运的是,他在山脚下发现了一个宝箱。根据经验判断(小A有经验吗?),地图应该就在其中!在宝箱上,有三根柱子以及在一根柱子上的n个圆盘。小A在经过很长时间判断后,觉得这就是hanoi塔!(这都要琢磨)。但是移动是需要时间的,所以小A必须要通过制造延寿药水来完成这项任务。现在,他请你告诉他需要多少步完成,以便他造足够的延寿药水.。时限1s。 -输入格式:一个数n,表示有n个圆盘(n<=1500) -输出格式:一个数s,表示需要s步。

####Solution 1.显然这是一个高精计算的的普通汉诺塔,递推肯定是不能用的,那么我们来看递推式:f(n)=2f(n-1)+1; 2.在递推式两侧同时加上实数a=1,可得f(n)+1=2(f(n-1)+1); 3.建立等比数列A,使A(n)=f(n)+1,因为只有一块圆盘时需要移动的步数为1,数列的公比为2,所以A(1)=2,A(n)=2^(n-1)*2=2^n; 4.高精度计算数列A,输出f(n)=A(n)-1;

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[10000005]={0,1,0},len=1,x;     //因为步数可能会很大所以记录步数的数组a开得大一些,注意A(1)=1;
void g(){
	x=0;
	for(int i=1;i<=len;i++)a[i]*=2;   //计算
	for(int i=1;i<=len;i++)
	{
		a[i]+=x;
		x=a[i]/10;                          //进位;
		a[i]%=10;
	}
	if(x>0){
		len++;
		a[len]=x;                       //维护长度;
	}
}

int main(){
	int n,i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;++i) g();
	a[1]-=1;                                   //末尾减一,不用担心不够减:wjh大佬的证明:显然2的正整数次幂中末位不会出现奇数,所以不会出现5,且2的正整数次幂的末位>=2;
	for(i=len;i>0;--i)printf("%d",a[i]);
	printf("\n");
	return 0;
}

###2.[noip1999]Hanoi双塔问题 ####Description

-给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的。 现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘; (2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序; -任务:设Fn为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n(n<=200),输出Fn。

####Solution 1.双塔其实可以看做每个圆盘拆成两片,显然:对于普通汉诺塔递推式f(n)=2f(n-1)+1,双塔步数F(n)=2f(n); 2.那么可以得到F(n)=2F(n)+2:在递推式两侧同时加上实数a=2,可得F(n)+2=2(F(n-1)+2); 3.建立等比数列A,使A(n)=F(n)+2,因为只有一块圆盘时需要移动的步数为2,数列A的公比为2,所以A(n)=2^n+1; 4.高精度计算数列A,输出F(n)=A(n)-2;

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[2000]={0,2,0},len=1,x;          //因为步数n<=200所以记录步数的数组不必开很大,注意A(1)=2;
void g(){
	x=0;
	for(int i=1;i<=len;i++)a[i]*=2;   //计算;
	for(int i=1;i<=len;i++){
		a[i]+=x;
		x=a[i]/10;            
		a[i]%=10;                        //进位;
	}
	if(x>0){
		len++;
		a[len]=x;                         //维护长度;
	}
}

int main(){
	int n,i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;++i) g();
	a[1]-=2;                                 //F(n)=A(n)-2,不用担心不够减,证明同上;
	for(i=len;i>0;--i)printf("%d",a[i]);
	printf("\n");
	return 0;
}
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部