算法与程序设计之贪心算法_贪心算法小论文

实例问题

首先我们先来看一个算法题，由这个题来理解贪心算法
题目描述：
一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳的更远，每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就代表袋鼠下一跳最多能够跳5米，如果为0，就会陷进去无法继续跳跃，河流一共N米宽，袋鼠初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1；

分析

问题要求是最少多少跳可以到达对岸？典型的最优解问题，在求解最优解问题的时候，贪心算法往往是我们的一个思路，但并不是所有的最优解问题都可以用贪心算法，这有一定的判断条件。

先给出一个数组 [2 3 1 1 1]
从2开始先后跳，题目要求用最少的跳数。我们只要保证每次跳都能尽可能的远，这样得到的跳数才能尽可能的小，思路是对的，但是如果从前面开始分析的话。
给出的数组中如果每次都跳当前桩子的最大值，并不能得到最小的跳数。
既然思路是对的，我们换个方向，从后往前分析，从后面找能跳到对岸的最远距离的桩子第一次找是 4 号下标（下标从0开始），能跳到对岸，且里对岸最远，然后以4号下标作为对岸，往前找能跳到4号下标的且离4号最远的桩子，这时候是1号下标的3，依次类推，因为每次都是找到最大距离，所以经历的跳数是最少的。

根据分析给出代码

int fun(int *arr,i