2011-2014-蓝桥杯预赛递归算法题目及部分答案.pdf

2014 预赛第三题 标题：李白打酒 话说大诗人李白，一生好饮。幸好他从不开车。 一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边 边 唱： 无事街上走，提壶去打酒。 逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次 遇到的是花，他正好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为 a，遇花 记为 b 。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有 多少呢？请你计算出所有可能方案的个数（包含题目给出的）。 注意：通过浏览器提交答案。答案是个整数。不要书写任何多 余的内容。 #include <cstdio> using namespace std; int sum = 0; char str[100]; int Fun(int now, int i, int a, int b) { if(now < 0 || i > 16 || (now == 0 && i < 16)) return 0; if(now == 0) { if(i == 16 && a == 5 && b == 10) { sum++; for(int j = 0; j < 15; j++) putchar(str[j]); putchar(10); } } str[i - 1] = 'a'; Fun(now * 2, i + 1, a + 1, b); str[i - 1] = 'b'; Fun(now - 1, i + 1, a, b + 1); } int main() { str[15] = '\0'; Fun(2, 1, 0, 0); printf("sum = %d\n", sum); return 0; } 2013 预赛 3: 第 39 级台阶（满分 8 分） 小明刚刚看完 电影《第 39 级台阶》，离开电影院的时候，他数了数 礼堂前的台阶数，恰好是 39 级! 站在台阶前，他突然又想着一个 问题： 如果我每一步只能迈上 1 个或 2 个台阶。先迈左脚，然后左右交 替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完 39 级 台阶，有多少种不同的上法呢？ 请你利用计算机的优势，帮助小明寻找答案。 解答： /有左右脚的限制，即第一步必须左脚，然后左右交替，最后一步 必须是右脚。即必须走偶数步。 #include<iostream.h> //有左右脚的限制。 const int N=39; int f(int m,int n) { if(m==0||n==0) return 1; return(f(m-1,n)+f(m,n-1));//递归的关键在此，大规模逐渐转化 为小规模。 } int main() { int x=N/2,y; //x 表示走两步的次数，y 表示走一步的次数。 int i,sum=0; for(i=x;x>=0;x-=2) //为了保持偶数步，必须 x 每次递减 2， 而不是 1 ；(x 要 x>=0,不能 x>0) ，x=0 是针对偶数台阶。 { y=N-2*x; sum+=f(x,y); //求组合数; } cout<<"共有 "<<sum<<"种走法。"<<endl; return 0; } /种走法。 2012