以前刚接触ACM时做11页,有挺多题不懂的。最近据某人说校纳新赛和杭电11页差不多,于是顺便又回来补上,收获不少,对递推有了更深的理解.
#include<cstdio>
#define MAXN 52
__int64 arr[MAXN];
int main()
{
int n,i;
arr[1]=3,arr[2]=6,arr[3]=6;
for(i=4; i<MAXN; ++i)
arr[i]=arr[i-1]+2*arr[i-2];
/*
arr[i]=arr[i-1]+2*arr[i-2];
在arr[i]时,可以由arr[i-1]和arr[i-2]得到,
arr[i-1]: 由于arr[i-1]和arr[1]不一样,所以arr[i]只能选择一种(arr[i]和arr[i-1]相邻且要和arr[0]不同)
arr[i-2]: 这时arr[i-1]不是最后一个,所以这个位置可以选两种颜色(只要和arr[i-2]不同就行了),
选好后arr[i]就只能选一种。
*/
while(scanf("%d",&n)==1){
printf("%I64d\n",arr[n]);
}
return 0;
}
2046 ( 骨牌铺方格
#include<cstdio>
#define MAXN 52
__int64 f[MAXN];
int main()
{
int i,n;
f[0]=0, f[1]=1, f[2]=2;
for(i=3; i<MAXN; ++i)
f[i] = f[i-1]+f[i-2];
/*
f[i] = f[i-1]+f[i-2];
f[i-1]: 只能加一块竖着放的
f[i-2]: 两块横着叠在一起
两种都是只有一种情况
*/
while(scanf("%d",&n)!=EOF){
printf("%I64d\n",f[n]);
}
return 0;
}
2047
( 阿牛的EOF牛肉串 )
/*
对于一串字符,分为两种情况:
(1) 不以O结尾的, 如EF,那么它接下来有三种情况: EFF、EFE、EFO
注意,有两个是不以O结尾的,一个是以O结尾的
(2) 以O结尾的,如EO,那么它接下来只有两种情况, EOF、EOE。
且这两种情况都不以O结尾
那么可以推导出,对于某一次的情况,它以O结尾的个数是,上一次不以O结尾的个数
不以O结尾的个数是上一次 “不以O结尾的”的两倍 加上上次 “以O结尾的”的两倍。
可以得出递推方程
f1[i] = f2[i-1]; // f1保存以O结尾的个数
f2[i] = f1[i-1]*2+f2[i-1]*2; // f2保存不以O结尾的个数
得出了这两个,总数也自然就求出来了
f[i] = f1[i]+f2[i]; // f保存总数
*/
#include<cstdio>
#define MAXN 52
__int64 f[MAXN],f1[MAXN],f2[MAXN];
int main()
{
int n,i;
f1[1]=1,f2[1]=2,f[1]=3;
// f1为以 O 结尾的个数,f2为以E、F结尾的个数
for(i=2; i<=40; ++i){
f1[i] = f2[i-1];
f2[i] = f1[i-1]*2+f2[i-1]*2;
f[i] = f1[i]+f2[i];
}
while(scanf("%d",&n)==1){
printf("%I64d\n",f[n]);
}
return 0;
}
错排公式(1462,2048,2049):
某人写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。
分析思路:
1、当N=1和2时,易得解~,假设F(N-1)和F(N-2)已经得到,重点分析下面的情况:
2、当有N封信的时候,前面N-1封信可以有N-1或者 N-2封错装
3、前者,对于每种错装,可从N-1封信中任意取一封和第N封错装,故=F(N-1)*(N-1)
4、后者简单,只能是没装错的那封和第N封交换信封,没装错的那封可以是前面N-1封中的任意一个,故= F(N-2) * (N-1)
基本形式:d[1]=0; d[2]=1
递归式:d[n]= (n-1)*( d[n-1] + d[n-2])
/*
错排公式
全部抽错的概率,即全部排错的情况个数除与的全排列个数
*/
#include<cstdio>
#define MAXN 52
__int64 f[MAXN],f1[MAXN],f2[MAXN];
double ans[MAXN];
int main()
{
int C,n,i;
f[1]=0,f[2]=1;
__int64 sum=2;
ans[2]=0.5;
for(i=3; i<=20; ++i){
sum *= i;
f[i] = (i-1)*(f[i-1]+f[i-2]);
ans[i] = f[i]*1.0/sum;
}
scanf("%d",&C);
while(C--){
scanf("%d",&n);
printf("%.2f%%\n",ans[n]*100);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
递推梯形公式,递推梯形公式的matlab程序,附带运行结果
递推公式求通项的几种方法 递推公式求通项的几种方法 递推公式求通项的几种方法
关于勒让德多项式递推公式推导的几种不同方法,非常实用,希望能对对考研、考博的同学们有所帮助
用递推公式计算定积分matlab版.doc
高中数学必修数列的递推公式PPT课件.pptx
用于求解递推公式的matlab程序,自己编的,不错
该文章网络下载,较好地推导了德多项式递推公式,是一份很好的参考资料!
在一般的数学统计过程中,为了求得方差,需要预先知道所有的数据项,然后通过求均值,再通过遍历所有数据项计算平方和的方式求得方差。 但是在大数据、流式处理的场景,是无法预先知道...方差递推公式的计算过程如下:
递推公式的伟大意义——?常见的编程实现方法?(优缺点?)有了公式,人工计算的方法?
用递推公式计算定积分(matlab版).pdf用递推公式计算定积分(matlab版).pdf用递推公式计算定积分(matlab版).pdf用递推公式计算定积分(matlab版).pdf用递推公式计算定积分(matlab版).pdf
20届高考数学一轮复习讲义(提高版) 专题4.3 利用递推公式求数列通项(解析版).docx
有一类试题,每相邻两项数之间的变化有一定的规律性,我们可将这种规律归纳成如下简捷的递推关系式:F(n)=G(F(n-1)) 这就在数的序列中,建立起后项和前项之间的关系。然后从初始条件(或最终结果)入手,一步步地按...
线性代数递推公式法(行列式例题).pdf
数列通项公式与递推公式.ppt
Mie理论递推公式计算散射相位函数,给出完整的推到公式
总结了大半年,控制系统各种传递函数双线性变换离散化后的递推公式。相信能帮助大家
2014届高中三年级数学一轮复习-专家讲坛-由递推公式求通项的7种方法及破解数列中的4类探索性问题-理.doc
教育资料
数列递推公式的九种方法.doc
根据最小二乘法的递推公式 ,由 ,逐次递推可得。程序中选取矩阵来存放x的值。通过循环程序计算出 , , 的值