问题一:取数游戏程序文件 choice.pas可执行文件 choice.exe输入文件 choice.in输出文件 choice.out时间限制 3s问题描述：我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。如果你能算出一共有多少种取法，那么你会被天神Lijiganjun奖励。输入格式：输入文件“choice.in”中仅包含一个数n（1< n < 50）。输出格式：输出文件“choice.out”中仅包含一个数———你的答案。样例：CHOICE.IN CHOICE.OUT5 13哪位哥哥能写出来啊？小弟感激不尽~~~

我顶~~

我用的是动态规划
本题的答案ans=？
n=1时
ans（1）=2
要1的时候是1种，
不要1的时候是1种
n=2时
ans（2）=3
要2的时候是1种，条件是“不要1”
不要2的时候是2种，条件是“要1”或者“不要1”
所以
* ：ans(n)=ans(n,不要n)+ans(n,要n)
①：ans(n,要n)=ans(n-1,不要n-1)
②：ans(n,不要n)=ans(n-1,不要n-1)+ans(n-1,要n-1))
综合成方程就是6L的
动态转移方程如下
F[i,1]=F[i-1,0]（①）
F[i,0]=F[i-1,0]+F[i-1,1]（②）
初始值F[1,1]=1 F[1,0]=1
以下是原程序
program choice; {dp}
var
n:integer;     {1<n<50}
ans:integer;
a:array[1..50,0..1]of integer;
i,j,k:integer;
begin
assign(input,'choice.in');
reset(input);
read(n);
close(input);
a[1,1]:=1;a[1,0]:=1;
for i:=2 to n do begin
a[i,1]:=a[i-1,0];
a[i,0]:=a[i-1,1]+a[i-1,0];
end;
ans:=a[n,0]+a[n,1];
assign(output,'choice.out');
rewrite(output);
writeln(ans);
close(output);
end.


6，7L正解

今天来了两次，第一次来以为是6 7L说的用DP，而非斐波拉契数列自己照着“DP”做了以下，才发现根本就没有DP，那所谓DP只是普通递推！！！求出来也就是斐波拉契数列！
3 9L正解！！！！！！！！！！问题是，怎么存储这么大的数，qword都不够的，高精度？望指教。。。。还有3l的 mod10000 什么意思？

忘补充了，我做的范围是1《n《100的。。。怎么解决捏？？？？

是否要求最优解才算动规，还是由子问题求解也算？？ 。。。。。

动规虽然方便 但新手不容易会

DP的状态转移方程本质上是一个递推公式。
6、7L的状态转移方程，其实仔细观察，会发现它的结果依赖于f[i-1,0]与f[i-2,0]，即可以转化为以下形式：
F[i,0]=F[i-1,0]+F[i-1,1]=F[i-1,0]+F[i-2,0]
去掉第二维，既得
F[i]=F[i-1]+F[i-2]
很熟悉吧，斐波那契无处不在。只不过：边界条件F[-1]=1 F[0]=1，取和的时候取f[n]即可。
这样就可以直接用斐波那契数列的通项公式了。

太大高精度吧- -

排列组合……

#include<stdio.h>
int amount=0;
int board[100][100];
void cover(int tr,int tc,int dr,int dc,int size)
{
int s,t;
if(size<2) return;
amount++; //所使用的三格板数目
t=amount;
s=size/2; //子问题棋盘大小
if((dr<(tr+s))&&(dc<(tc+s)))
{
cover(tr,tc,dr,dc,s);
board[tr+s-1][tc+s]=t; //覆盖1号三格板
board[tr+s][tc+s-1]=t;
board[tr+s][tc+s]=t;
cover(tr,tc+s,tr+s-1,tc+s,s); //覆盖其余部分
cover(tr+s,tc,tr+s,tc+s-1,s);
cover(tr+s,tc+s,tr+s,tc+s,s);
}
else if((dr<(tr+s))&&(dc>=(tc+s)))
{
cover(tr,tc+s,dr,dc,s);
board[tr+s-1][tc+s-1]=t; //覆盖2号三格板
board[tr+s][tc+s-1]=t;
board[tr+s][tc+s]=t;
cover(tr,tc,tr+s-1,tc+s-1,s); //覆盖其余部分
cover(tr+s,tc,tr+s,tc+s-1,s);
cover(tr+s,tc+s,tr+s,tc+s,s);
}
else if((dr>=(tr+s))&&(dc<(tc+s)))
{
cover(tr+s,tc,dr,dc,s);
board[tr+s-1][tc+s-1]=t; //覆盖3号三格板
board[tr+s-1][tc+s]=t;
board[tr+s][tc+s]=t;
cover(tr,tc,tr+s-1,tc+s-1,s); //覆盖其余部分
cover(tr,tc+s,tr+s-1,tc+s,s);
cover(tr+s,tc+s,tr+s,tc+s,s);
}
else if((dr>=(tr+s))&&(dc>=(tc+s)))
{
cover(tr+s,tc+s,dr,dc,s);
board[tr+s-1][tc+s-1]=t; //覆盖4号三格板
board[tr+s-1][tc+s]=t;
board[tr+s][tc+s-1]=t;
cover(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余部分
cover(tr,tc+s,tr+s-1,tc+s,s);
cover(tr+s,tc,tr+s,tc+s-1,s);
}
}
void outputboard(int size){
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
printf("%d ",board[i][j]);
printf("\n");}
}
void main(){
int size=1,x,y,k;
printf("请输入k的值\n");
scanf("%d",&k);
for(int i=1;i<=k;i++)
size=size*2;
printf("请输入残缺模块所在的行和列，以空格相隔\n");
scanf("%d %d",&x,&y);
if(x<k&&y<k)
cover(0,0,x,y,size);
else
printf("输入行和列有误\n");
outputboard(size);
}