两个有趣的算法问题

Maths

      一共是两道题，第一道是上学期的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

文章目录
|