两个有趣的算法问题

      一共是两道题,第一道是上学期的matlab考试的时候碰到的,另外一道是师弟发的一道数学题的学习笔记,于是找了个时间想了一下,结合网上找到的资料参考。用的是matlab语言。

1.一只青蛙,每次可以选择跳1级或者跳2级,问跳n级一共有多少种方法?

算法分析:
      这道题当时我在考场上没有想出来,因为我没想到会考matlab实现算法的题目,问了一下编程组的同学,得到的答案是可以用二叉树,但是,至少目前我还没在matlab里面见过指针,C++的指针还不是很熟练(ps:现在熟练多了),于是只能换个思路了。
      从递归的角度去思考,关键还是怎么得到递推公式,首先跳1级只有1种方法,跳2级有2种方法,接着考虑以前做过的奥数题模型——蜗牛爬井,关键在于分析最后一天的情况,在这里我们也是分析最后几个台阶的情况。青蛙最后会在倒数第2级或者最后1级,因此接近递归出口时的方法是有f(n-1)+f(n-2)种,换言之f(n)=f(n-1)+f(n-2)

1
2
3
4
5
6
7
8
function answer=test(Number)
if Number==1
answer=1;
elseif Number==2
answer=2;
else
answer=test(Number-1)+test(Number-2);
end

2.M个相同的苹果放到N个相同的篮子中,问有多少种分法?

算法分析:
      这里我参考了网上的资料,写出一个比较独特的递归方法。为了具体一点,这里我举8个苹果放到3个篮子里。
      8个苹果3个篮子=8苹果2篮子+5个苹果2篮子+2苹果2篮子=(8苹果1篮子+6苹果1篮子)+(3苹果1篮子+1苹果1篮子)+(1苹果1篮子+1苹果1篮子)=5+3+2=10

1
2
3
4
5
6
7
8
9
function answer=test(apple,basket)
answer=0;
if(basket<=1)
answer=1;
return;
end
for i=apple:-basket:0
answer=answer+test(i,basket-1);
end

文章目录
|