递归使用-换汽水问题

假如有这么一个问题,1瓶汽水1块钱,2个空瓶可以兑换一瓶汽水,问n块钱可以兑换多少瓶汽水?

考虑整个过程就是用空瓶不断兑换汽水的过程。又因为空瓶小于2个的时候就不能兑换汽水了,考虑将当前瓶数n可以分为n-1和1,同样将n-1分为n-2和1,依次类推。因此要想求得瓶数为n的时候可以兑换的汽水数,我们只需求得1个空瓶兑换的基本情况,再依次回溯,最终求得瓶数为n时的情况。所以采用递归的解法,

在每一个栈帧中,都是求当前空瓶数能兑换的汽水数,传入的参数为空瓶数,则可以兑换的汽水数为空瓶数对2求商,而递推传入下一个栈帧的参数值为兑换的汽水数(即空瓶数)加上余数(不能兑换的数量)。在递推到基础问题时,回溯返回给上一层调用函数。

其python实现代码为

def bottlechange(n):

    drinknum=n//2                     #空瓶兑换汽水数,同时也是当下对应的空瓶数

   totalemptybottle=drinknum+n%2     #空瓶总数

   

    if totalemptybottle<2:             #基础条件

        return drinknum

   

return drinknum+bottlechange(totalemptybottle)                           

 

def buy(money):

    num =money+bottlechange(money)         #递归空瓶可以兑换的汽水瓶数,初始空瓶数为money

    return num

def bottlechange(n):

    if n<2:             #基础条件

        return 0

    drinknum=n//2                     #空瓶兑换汽水数,同时也是当下对应的空瓶数

   totalemptybottle=drinknum+n%2     #空瓶总数

   

    returndrinknum+bottlechange(totalemptybottle)

用空瓶个数作为参数进行递归时,当空瓶小于2个的时候,就应该停止迭代了,直接返回此时的兑换数。

测试用例

>>> buy(15)

29

>>> buy(2)

3

>>> buy(1)

1

再比如买汽水的规则,1块钱可以买1瓶汽水,2个空瓶可以换一瓶汽水,3个瓶盖可以换一瓶汽水,问:20块可以买到多少瓶汽水?

分析:该问题的一个求解过程实际上就是用空瓶和瓶盖不断去兑换汽水的过程。这个过程有明显的递归性,可以使用递归的方法求解。它的出口条件是空瓶总数小于2且瓶盖总数小于3,因为这个条件下是无法兑换汽水的。

def bottlecapchange(bottle=0,cap=0):

    drinknum=bottle // 2+cap // 3 #空瓶和瓶盖兑换汽水瓶数

   totalemptybottle=drinknum+bottle % 2     #空瓶总数

    totalcap=drinknum+cap % 3              #瓶盖总数

   

    if totalemptybottle < 2 andtotalcap <3 :

        return drinknum

    else:

        return drinknum+bottlecapchange(bottle=totalemptybottle,cap=totalcap)

       

def buy(money):

    num =money+bottlecapchange(money,money)  #递归空瓶、瓶盖可以兑换的汽水瓶数

    return num

每次迭代过程中需要先算出当前可用的瓶盖和空瓶数。

测试用例

>>> buy(2)

5

>>> buy(1)

1

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • One 1 the [ðə, ði:] art.这,那 ad.[用于比较级;最高级前] 2 be [bi:,bi]...
    梁培林阅读 9,416评论 0 10
  • Scala 是一种有趣的语言。它一方面吸收继承了多种语言中的优秀特性,一方面又没有抛弃 Java 这个强大的平台,...
    MaLiang阅读 1,541评论 0 2
  • 8月22日-----字符串相关 2-3 个性化消息: 将用户的姓名存到一个变量中,并向该用户显示一条消息。显示的消...
    future_d180阅读 1,003评论 0 1
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,428评论 0 2
  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,486评论 0 10