上海住房和城乡建设部网站官网,wordpress有留言时邮件提醒,网站关键词查询网址,颜色广告青蛙过河 [递推法] 题目描述输入输出样例输入样例输出样例 递推解答A C 代码 题目描述
有一条河#xff0c;左边一个石墩( A A A区)上有编号为 1 #xff0c; 2 #xff0c; 3 #xff0c; 4 #xff0c; … #xff0c; n 1#xff0c;2#xff0c;3#xff0c;4左边一个石墩( A A A区)上有编号为 1 2 3 4 … n 1234…n 1234…n的 n n n只青蛙河中有 k k k个荷叶( C C C区)还有 h h h个石墩( D D D区)右边有一个石墩( B B B区)如下图所示。 n n n只青蛙要过河(从左岸石墩 A A A到右岸石墩 B B B)规则为
石墩上可以承受任意多只青蛙荷叶只能承受一只青蛙不论大小青蛙可以 A A A→ B B B可以从 A A A跳到 B B B下同 A A A→ C C C A A A→ D D D C C C→ B B B D D D→ B B B D D D→ C C C C C C→ D D D当一个石墩上有多只青蛙时则上面的青蛙只能跳到比它大1号的青蛙上面。
你的任务是对于给出的 h h h k k k计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?
输入输出样例
输入样例 2 2 2 3 3 3 河中间有 2 2 2个石礅 3 3 3个荷叶
输出样例 16 16 16 最多有 16 16 16只青蛙可以按照规则过河 递推解答
关键在这里 从具体到一般推导过程如下 f ( 0 , 0 ) 1 f(0,0)1 f(0,0)1 f ( 0 , k ) k 1 ; f(0,k)k1; f(0,k)k1; 如 k 3 k3 k3时有 4 4 4只青蛙可以过河 f ( 1 , k ) 2 ( k 1 ) ; f(1,k)2(k1); f(1,k)2(k1); 递推思想 f ( 2 , k ) 2 ( k 1 ) × 2 2 2 × ( k 1 ) ; f(2,k)2(k1)×22^2×(k1); f(2,k)2(k1)×222×(k1); …… 依此类推得递推式 F ( i , k ) F ( i − 1 , k ) × 2 2 i × ( k 1 ) ; F(i,k)F(i-1,k)×22^i×(k1); F(i,k)F(i−1,k)×22i×(k1); …… 因此结论为 f ( h , k ) 2 h × ( k 1 ) f(h,k)2^h×(k1) f(h,k)2h×(k1) A C 代码
#include bits/stdc.h
using namespace std;
long long h,k,ans1;
int main()
{cin h k;while (h--)ans*2;ans*(k1);cout ans;return 0;
}
