采蘑菇问题-白红宇

采蘑菇问题

阅读量：7071 次

发布时间：2019-06-28

本文共 2126 字，大约阅读时间需要 7 分钟。

查了下采蘑菇问题，用c写的相当困难，把自己绕进去了。

最后发现问题出在：采蘑菇的小姑娘起始位置是在数组之外的，而非数组的起始位置。所以在数组下标上折腾了好久。

采蘑菇问题描述引用以下博客：

【描述】

萌萌走出山路后，来到一片草地，发现过了草地有巨型蘑菇，于是他准备采摘一些。但是他对保护花草却很重视，他不忍心踩死花草，但为了蘑菇，他只能尽量少踩死几株。现在，草地上也像一条路，上面有n个点，第N个点就是巨型蘑菇所在地（上面没草），每个点上都有i株小草或j株蘑菇（也就是说有蘑菇就没有草），他每次最多跨越k步。

现在请为他选择一条路，在踩死尽量少的小草下，去采蘑菇。

P.S：默认出发点为：1，结束点为：N；

【输入格式】

第一行2个数：

n（表示这条路的长度），k（每次最多跨越数）

接下来第二行，n个数：

a[0],a[1],a[2],a[3]…a[n-1]（就是相应株数的小草，例如：

0 0 1 2 0【这是说第3个点有1株草，第4个点有2株草】)

（注意，如果小姑娘第一跳跨数为1,说明跳到了位置a[0]，

小姑娘的起始位置位于数组外）

【输出格式】

一个数，最少踩到的小草株数：m

【输入样例】

5 2

0 1 1 2 0

【输出样例】

（只踩到了第3株）

【数据范围】

N,k<=10000;

A[i]<=100;

第一次写的，虽然实现了功能，但是有些瑕疵：

#include
     
      #include
      
       int input[]={
   1,0,3};int startP=-1;//-1表示从数组外开始往数组内跳int inplen=3;int minSUM=0xff;int step=2;void FUN1(int inp[],int start,int sum){
   //sum是数组中start位的值+start前面跳的值;        int i=1;        for(;i<=step;i++){                if((start+i+1)>inplen){
   //表示数组遍历完毕后跳出结束                        if(sum

输出：

xu@xu-ThinkPad-X61:~$ gcc caimogu2.c

xu@xu-ThinkPad-X61:~$ ./a.out

start = -1 cur = 0 sum =1

start = 0 cur = 1 sum =1

start = 1 cur = 2 sum =4

start = 0 cur = 2 sum =4

start = -1 cur = 1 sum =0

start = 1 cur = 2 sum =3

minSUM = 0

问题：

1：累加器sum作为参数传递进去，想实现记录每次踩到小草的个数;由于sum不仅与当前递归有关，而且与下一次递归也有联系，容易出错;尽量用返回值的方法，避免思路不清;

2：递归貌似从后往前累加的，我这个方法sum其实是从前往后加的，不是我的初衷。

3：综合说来我的代码前期函数功能没有定义清晰，细节上的处理还是不够流畅;

请教高人后，在原来基础上修改了代码，这下对递归的认识清晰很多，下面看看改进版的：

#include
     
      #include
      
       int step=2;int inplen=5;int FUN(int inp[],int start){        if(start > (inplen -1))                return 0;        int tmp=0;        int min=0xffff;        int k=1;        for(;k<=step;k++){                tmp=FUN(inp,start+k);                if(tmp

输出：

xu@xu-ThinkPad-X61:~$ gcc caimogu.c

xu@xu-ThinkPad-X61:~$ ./a.out

start 4 = 0

start 3 = 2

start 3 = 0

start 2 = 3

start 4 = 0

start 2 = 2

start 1 = 2

start 4 = 0

start 3 = 2