ACM——逆推法（倒着想）（1）
母牛的故事
Time Limit:
MS (Java/Others)&&&&Memory Limit:
K (Java/Others)
Total Submission(s): 81436&&&&Accepted Submission(s): 40432
Problem Description
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0&n&55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。
Sample Input
Sample Output
6这道题我没做出来，这道题和蓝桥杯细胞繁衍的那道很是类似，但细胞繁衍那道似乎更难，细胞繁衍那道为什么不是递推式呢？递推式成立是有条件的，也就是说有的东西他就是符合递推式的。而有的，是不符合的，HH.这道题我没做出来，为什么呢？我就在想啊，每一年都有新出生的小牛，每一年都有还不具备生育能力的小牛，每一年都有具有生育能力的小牛，变量一下就变多了，感觉哈难受，思路一下就没有了，陷入的困境和我做细胞繁殖那道题时一模一样，很是高兴，因为这是类似的题，那么我就可以类似的想出一个解决此类问题的方法。
#include &stdio.h&int main(){&&& int j,n,a[60];&&& scanf(&%d&,&n);&&& while(n!=0)&&& {&&&&&&& a[1]=1;&&&&&&& a[2]=2;&&&&&&& a[3]=3;&&&&&&& for(j=4;j&=n;j++)&&&&&&&&&&& a[j]=a[j-1]+a[j-3];&&&&&&& printf(&%d/n&,a[n]);&&&&&&& scanf(&%d&,&n);&&& }}
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：36618次
积分：2924
积分：2924
排名：第13651名
原创：266篇
转载：25篇
评论：15条
(1)(1)(6)(28)(71)(65)(20)(1)(20)(35)(43)(1)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'第三节&&&层层递进——递推法与迭代法
层层递进——递推法与迭代法
1.熟悉递推法和迭代法的思路；
2.能够用递推法和迭代法解决数列问题。
在数学中我们常常会遇到这样的问题：已知第
一项(或几项)，要求能得出后面项的值，这就
是用了一种叫“递推”的方法。
【学习任务9】有个爱好幻想的人，想知道一年内一对兔子能繁殖多少对小兔子。于是，他围了一个栅栏，把一对刚出生并且是雌雄成对的小兔子养在里面。假设小兔子生下后第二个月就能繁殖，以后每月生产一次且每次都是生一雌一雄两只兔子，那么一年后将有多少对兔子?假设没有兔子死亡。
这是一道有趣的数学题，也就是著名的意大利数学家斐波那契在《算盘书》中记载的“兔子问题”。
【问题分析】
第1个月，有一对小兔子；
第2个月，小兔子长成了大兔子；
第3个月，大兔子；生下一对小兔子，这时，有2对兔子了；
第4个月，大兔子又生了一对小兔子，小兔子也长成大兔子了，栅栏里有3对兔子；
第5个月，原来大兔子又生了一对小兔子，而第3个月出生的兔子已成熟，也生了一对小兔子，这时共有5对兔子；
以此类推，我们可以用如图10-2来表示(B为一对小兔子，A为一对大兔子)：
&数量&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&B&&&&&&&&&&&&&&&&&&&&&&&&&
1&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&A&&
&&&&&&&&&&&&&&&&&&&&&&&1&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&A&&&&&
B&&&&&&&&&&&&&&&&&&&&&
2&&&&&&&&&&&&&&&&
第3个月&&&&
&&&&&&&&&&&&&&&
A&&&&&&&&&&&&&&&&
3&&&&&&&&&&&&&&&&
&&&&&&&&&&&
B&&&&&&&&&&
5&&&&&&&&&&&&&&&&
8&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&图&
&兔子繁殖说明图
从图解分析来看，很容易得出兔子繁殖的规律：
&1，1，2，3，5，8，13，21，34，55，89，144，……
&由此可知，一对刚出生的兔子，经过一年可以繁殖成144对兔子。观察上面的数列不难发现，从第3项开始，每个数都是紧邻的前面两个数的和，这样的数列就是有名的斐波那契数列。
斐波那契数列的规律是：数列中的第1及第2个数是1，从第3个数起，该数是其前面2个数之和。我们可以编写程序输出此数列的前20项。
【程序清单】
REM L10 -12A
FOR i = 3 TO
&&&&&&PRINT
【运行结果】
1&&&&&&&&&&&
1&&&&&&&&&&&
&2&&&&&&&&&&&&
3&&&&&&&&&&&&
8&&&&&&&&&&&
13&&&&&&&&&&
21&&&&&&&&&&
34&&&&&&&&&&
89&&&&&&&&&
144&&&&&&&&
233&&&&&&&&
377&&&&&&&&
987&&&&&&&
1597&&&&&&
2584&&&&&&
4181&&&&&&
实际上，斐波那契数列中的各项存在如下递推关系：
Ｆn=Ｆn-1＋Ｆn-2
这种后项由前面的项按一定的数学关系来求得的方法，叫递推。解决递推问题必须具备两个条件：
（1）初始条件；
（2）递推关系（或递推公式）。
在上例中，初始条件为：f1=1,f2=1；递推公式为：f3=f2+f1，用f1,f2,f3代表三个数，在每一次循环中它们代表不同的数。在程序运行过程中，这些变量不断地以新值取代原值，这种不断以新值取代原值得操作称为“迭代”。程序中的f1,f2,f3称为迭代变量，它们的值在不断地变化被迭代的。对于递推问题一般可以用迭代方法来处理，但有时不用迭代方法也很简洁。如上面的例子，由于我们知道了它的递推关系，就可以这样来设计程序：
【程序清单】
PRINT f(1),
FOR i = 3 TO
= f(i - 1) + f(i - 2)
&&&&&PRINT
【学习任务10】有一堆游戏棒，第一个参加游戏的人取走了一半多一根，第二个游戏者再将剩下的取走一半多一根，以此类推，以后的游戏者均取走前一次剩下的一半多一根，到第10个人来取时，发现只剩下一根了。问：游戏开始前这堆游戏棒共有多少根?
【问题分析】
&&&&平时，我们比较习惯用顺推的方法来解决问题，但对本题类型的问题，不妨用反向思维来考虑。根据题意：
&&&&第10个人来取时&&&&&&&&
&&&&推定第9个人来取时&&&&&
&&&&推定第8个人来取时&&&&&
&&&&推定第7个人来取时&&&&&
即(10+1)*2
&&&&推定第6个人来取时&&&&&
即(22+1)*2
&&&&推定第5个人来取时&&&&&
即(46+1)*2
&&&&推定第4个人来取时&&&&&
有190根，即(97+1)*2
&&&&推定第3个人来取时&&&&&
有382根，即(190+1)*2
&&&&推定第2个人来取时&&&&&
有766根，即(382+1)*2
&&&&推定第1个人来取时&&&&&
有1534根，即(766+1)*2
&&&&根据以上的推导过程，可以设计出这样的算法：
&&&&（0）将1赋给S作为初值，S是迭代变量；
&&&&（1）通过循环完成逆推的过程，迭代公式(S+1)*2，其中S是在不断变化的；
&&&&（2）输出9遍循环后的S值。
【程序清单】
REM L10_13A
FOR I = 9 TO 1 STEP
S = (S + 1) * 2
【运行结果】
我们是否也可以采用顺推的方法来解决？我们还是先来分析一下：
&&&&设S为总游戏捧数，A为每次取走后的所剩游戏棒数。让S从0开始进行搜索，每次逐步递增1，直到找出经过9次取游戏棒后剩下的游戏捧数为1时结束。
&&&&每次取走游戏棒数为A／2+1
&&&&每次取走后的剩下的游戏棒数为A-(A／2+1)，于是得出递推公式为：
&&&&A=A-A／2-1
&&&&取9次后剩下的游戏棒数A=1就终止。这时的S应该是最初的总游戏棒数。
&&&&因此在上述的内循环外，还要有一个外循环来给S计数，当S计数的值满足按条件取9次后剩下A=l为止。
S的初值可以取0，终值到底取多少为好是个未知数，所以不能用计数循环，只能用条件循环，直到满足A=1终止。
特别要注意的：在这个条件循环中用S=S+1来为S计数，决不能再用S作为迭代变量。应该用 A来作迭代变量，每次在操作内循环之前，把S赋给A。由此可见，同一问题的顺推与逆推除了递推公式不同外，迭代变量也有所改变。
【程序清单】
S + 1: A = S
I = 1 TO 9
= A - A / 2 - 1
LOOP UNTIL A = 1
&&上面分别介绍了两种递推方法：顺推和逆推。无论是哪一种递推方法，最关键的是要找到递推公式。只要找到了递推公式，程序就很容易实现。
【学习任务11】数列问题：有一数列
A(N)的前几项为0，1，2，6，16，44，120，328，…，已知后一项和前两项有某种关系，试编程求出前N项的和，并将这N个数及其和打印输出。
【问题分析】
问题的关键是找出数列A(N)的规律，然后将A(1)，A(2)…A(N)相加即可。
&&&&由题意知：A(N)与A(N—1)、A(N—2)之间存在关系
&&&&A(1)=0
&&&&A(2)=1
&&&&A(3)=2*(A(2)+A(1))=2*(1+0)=2
&&&&A(4)=2*(A(3)+A(2))=2*(2+1)=6
&&&&A(5)=2*(A(4)+A(3))=2*(6+2)=16
根据分析，很显然有A(N)=2*(A(N-1)+A(N-2))(N≥3)
【程序清单】
＂输入要求数列的项数N=＂；N
A(1) = 0: A(2) =
S = A(1) +
FOR I = 3 TO
= 2 * A(I - 1) + 2 * A(I - 2)
= S + A(I)
＂输出前＂；N；＂项，各项的值：＂
FOR I = 1 TO
＂前＂；N；＂项之和是I:＂；S
【运行结果】
&&&&输入要求数列的项数N=? 10
&&&&输出前10项，各项的值：
&&&&0&&&&&&
&&&&44&&&&
2448&&&&&&&
前10项之和是3861
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。【图文】第3章
递推_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
大小：1.20MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢uestcoj 890 Card Trick(dp+逆推)
题目链接：
啊哈哈，点我点我
思路：从终点向前递推。
首先p[I]表示从第i个点到终点的概率。则分为两种情况进行考虑。
【1】已经翻到的点则它必定会到终点，则概率为1.
【2】不知道的点则要进行枚举。那么p[i]=sum(p[i&#43;j])/13(2=<j<=13).那么这个问题就解决了。。
为什么要逆推，因为从前往后走，要用到后面的状态。
哎，自己的dp好弱啊，一个暑假好像都没怎么做。。哎，加油啊！！！
Card Trick
Time Limit: MS (/Others)
Memory Limit: KB (Java/Others)
I am learning magic tricks to impress my girlfriend Alice. My latest trick is a probabilistic one, i.e. it does work in most cases, but not in every case. To perform the trick, I first shuffle a set of many playing
cards and put them all in one line with faces up on the table. Then Alice secretly selects one of the first ten cards (i.e. she chooses x0,
a secret number between 1 and 10 inclusive)
and skips cards repeatedly as follows: after having selected a card at position xi with
a number c(xi) on
its face, she will select the card at position xi&#43;1=xi&#43;c(xi).
Jack (J), Queen (Q),
and King (K) count as 10,
Ace (A) counts as 11.
You may assume that there are at least ten cards on the table.
Alice stops this procedure as soon as there is no card at position xi&#43;c(xi).
I then perform the same procedure from a randomly selected starting position that may be different from the position selected by Alice. It turns out that often, I end up at the same position. Alice is very impressed by this trick.
However, I am more interested in the underlying math. Given my randomly selected starting position and the card faces of every selected card (including my final one), can you compute the probability that Alice chose
a starting position ending up on the same final card? You may assume that her starting position is randomly chosen with uniform probability (between 1 and 10 inclusive).
I forgot to note the cards that I skipped, so these cards are unknown. You may assume that the card face of every single of the unknown cards is independent of the other card faces and random with uniform probability out of the possible card faces (i.e. 2-10, J, Q, K,
Illustration of first sample input: my starting position is 2,
so I start selecting that card. Then I keep skipping cards depending on the card's face. This process iterates until there are not enough cards to skip (in this sample: Q).
The final Q card is followed by 0 to 9 unknown
cards, since Q counts as 10.
For each test case:
A line containing two integers n (1≤n≤100) and m (1≤m≤10)
where n is
the number of selected cards and m is
the 1-based
position of my first selected card.A line with n tokens
that specify the n selected
card faces (in order, including the final card). Each card face is given either as an integer x (2≤x≤10)
or as a single character (J, Q, K,
or A as specified above).
For each test case, print one line containing the probability that Alice chooses a starting position that leads to the same final card. Your output should have an absolute error of at most 10?7.
Sample input and output
Sample Input
Sample Output
2 2 2 2 2 2
2 2 2 2 2 2 2
Northwestern European Regional Contest 2013
UESTC Online Judge
Copyright (C) 2014 Ruins He(@lyhypacm), Jianjin Fan(@pfctgeorge)
and Yun Li(@mzry1992). Project
Any Problem, Please Report On Issues Page Or Discuss With Us In Mailing
Currently online registered users: 6
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
const int maxn=2000;
int main()
char str[maxn];
while(~scanf("%d%d",&n,&m))
memset(p,0,sizeof(p));
int start=m;
for(int i=1;i<=n;i++)
scanf("%s",str);
p[start]=1;
if(str[0]=&#39;2&#39;&&str[0]=1;i--)
if(p[i]==0)
for(int j=2;j<=11;j++)
temp=(j==10?4:1);
p[i]+=temp*p[i+j];
p[i]=p[i]/13;
ans+=p[i];
printf("%.10f\n",ans/10);【图文】第七讲_递推法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第七讲_递推法
大小：370.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢