Question

数据结构（c语言完成） 已知数列的递归表达式 Fn＝2F(n-1)+3F(n-2)+F(n-3) F0

数据结构（c语言完成）
已知数列的递归表达式
Fn＝2F(n-1)+3F(n-2)+F(n-3) F0＝F1＝0，F2＝1。
要求精确计算数列的第n项，例如 n＝200/500的实际结果
（可以追加悬赏值）

Answer 1

C语言程序：

#include <stdio.h>

void main()
{
	double f0 = 0, f1 = 0, f2 = 1, f3;
	int i, n;

	scanf("%d", &n);

	if(n==1 || n==2)
	{
		printf("%d", 0);
		return;
	}
	if(n==3)
	{
		printf("%d", 1);
		return;
	}

	for(i=4; i<=n; i++)
	{
		f3 = 2 * f2 + 3 * f1 + f0;
		f0 = f1;
		f1 = f2;
		f2 = f3;
	}

	
	printf("%.0lf\n", f3);
}

运行测试：

Answer 2

#include "stdio.h"
#define M 82
int main(int argc,char *argv[]){
	int s[4][M]={0,},i,j,k,N;
	printf("Input N(int 0<=N<=1000)...\nN=");
	if(scanf("%d",&N)!=1 || N<0 || N>1000){
		printf("Input error, exit...\n");
		return 0;
	}
	s[0][M-1]=s[1][M-1]=0,s[2][M-1]=1;
	for(k=i=3;i<=N;i++,k++){
		for(j=0;j<M;j++)
			s[k%=4][j]=(s[(k+3)%4][j]<<1)+3*s[(k+2)%4][j]+s[(k+1)%4][j];
		for(j--;j>0;j--)
			if(s[k][j]>999999)
				s[k][j-1]+=s[k][j]/1000000,s[k][j]%=1000000;
	}
	N>2 ? k-- : k=N;
	for(i=0;s[k][i]==0 && i<M;i++);
	printf("F(%d)=\n%d",N,s[k][i]);
	for(i++;i<M;i++)
		printf("%06d",s[k][i]);
	printf("\n");
	return 0;
}

追答

1. 数字太大，只能用“大数处理”办法，设计了一个长度为82的int数组，每个元素存放一个用十进制表示的1000000进制的数进行计算(就是说每个元素最大的最后计数是999999，超过时就要向前“进位”)，输出时连接起来作为一个几百位长的十进制数。这就是s[4][82]中82的来历。

2. s[4][82]中的4是只取数列当前的前4个值。k的值用k%=4和k++来保证其值在0、1、2、3间循环，而核心计算表达式(s[(k+3)%4][j]<<1)+3*s[(k+2)%4][j]+s[(k+1)%4][j]中的(k+3)%4、(k+2)%4、(k+1)%4则保证F(k)与F(k-1)、F(k-2)和F(k-3)的正确逻辑关系，如若当前k==0，则k-1是3，k-2是2，k-3是1等。这样就既保证了运算的方便，又保证了最后结果在s[k]中(无论k是几)。

3. for(j--;j>0;j--)循环用来处理1000000进制进位处理，这一看就明白了。

4. for(i=0;s[k][i]==0 && i<M;i++);的作用是在N较小时删除前导0。

5. printf("F(%d)=\n%d",N,s[k][i]);输出第一个6位数，不足6位时不输出前面的0；而for(i++;i<M;i++)循环是输出后续的6位数，由“%06d”保证把其中的前导0全部输出来。
   

追问

更改82数值为n，就可以至多输出n*6位数对吧。感谢您的解答，我先采纳，如果有不懂的可能会继续问您。

Answer 3

#include<stdio.h>
#include<stdlib.h>
double fn(double n)
{
int i;
double f0=0,f1=0,f2=1,f3;

if(0==n)
{
return 0;
}
else if(1==n)
{
return 0;
}
else if(2==n)
{
return 1;
}
else if(n>=3)
{
for(i=3;i<=n;i++)
{
f3=2*f2+3*f1+f0;
f0=f1;
f1=f2;
f2=f3;
}
return f3;
}
else
{
return -1;
}
}
int main()
{
double n,r;
char t[1024]={'\0'};

while(1)
{
printf("请输入整数n，输入exit退出循环：");
gets(t);
if(!strcmp(t,"exit"))
{
break;
}
n=atof(t);
if(-1!=(r=fn(n)))
{
printf("fn(%lf)=%lf。\n",n,r);
}
else
{
printf("不能计算fn(%lf)的值。\n",n);
}
}
system("PAUSE");
return EXIT_SUCCESS;
}