使用递归实现买汽水(华为面试题)

今天老范问了我一个问题问题:一个人买汽水,一块钱一瓶汽水,三个瓶盖可以换一瓶汽水,两个空瓶可以换一瓶汽水问20块钱可以买多少汽水?注意:使用递归这一题乍一看,哎哟,这么简单,能买几瓶?恩。。五瓶!为啥啊?多了我喝不完啊!老范说,喝不完关你屁事,又不是给你喝哦哦哦,那没事儿了,我想想。在知道自己的人生安全得到了保障之后,我冷静下来仔细思考了如何用递归实现这个问题

大家好,又见面了,我是你们的朋友全栈君。

今天老范问了我一个问题
问题:
一个人买汽水,一块钱一瓶汽水,三个瓶盖可以换一瓶汽水,两个空瓶可以换一瓶汽水
问20块钱可以买多少汽水?
注意:使用递归

这一题乍一看,哎哟,这么简单,能买几瓶?恩。。
五瓶!
为啥啊?

多了我喝不完啊!

老范说,喝不完关你屁事,又不是给你喝

哦哦哦,那没事儿了,我想想。
在知道自己的人生安全得到了保障之后,我冷静下来仔细思考了如何用递归实现这个问题

首先想了想什么是递归

  1. 方法内调用自己的方法的现象称为递归调用
  2. 递归现象允许程序执行到某个阶段时整体调用重新来过

以及递归的注意事项:

  1. 方法内部调用自己的方法不能100%成立,否则就是死循环
  2. 递归层数尽量少,因为会消耗内存,运行效率低

不能100%成立也就是说,要有终止条件,达成某个条件,就要跳出递归调用

瓶盖和空瓶子换饮料,这是一个怎么样的过程?了解了这个过程,才能分析出这中间哪些变量在发生变化,转换,以及变化到哪个程度,就不满足继续递归的条件了,也就是满足终止条件了。

1块钱和2块钱的置换过程
(这是用processon画的https://www.processon.com/很好用)
(推荐一波,processon速打钱来!!!!!)
drink表示购买和置换的饮料
cup表示瓶盖
bottle表示空瓶子
首先分析每一个成员变量,

  • 1drink=1cup+1bottle;
  • 3cup=1drink;
  • 2bottle=1drink;

**所以置换的过程就是cup-3,drink+1 或者bottle-2,drink+1的过程。
所以递归调用的条件就是每一轮置换后,cup>=3||bottle>=2, &&drinks<1也就是跳出递归的条件是:每一轮置换后cup<3&&bottle<2 &&drinks<1**

因为在这个过程中,三个元素drink, cup, bottle都有连续的变化,所以递归调用时要将三个参数都传就去。
定义方法体
`public static int Soda(int drink, int cup, int bottle){

}
`
除了第一轮之外,每一轮的drink=cup/3+bottle/2, cup=cup%3, bottle=bottle%2
所以我本来是这么写的(错的):

    public static int Soda(int drinks,int caps,int bottles){

        if(caps<3&&bottles<2&&drinks<1){
            return drinks;
        }else{
            caps+=drinks;bottles+=drinks;
            drinks=caps/3+bottles/2;
            caps%=3;  bottles%=2;
            return Soda(drinks,caps,bottles)+drinks;
        }
    }

得出来是93,我惊呆了,拿给老范,老范说,不不不还有更多,应该是113。

113,那就是说,我缺少20个,正好是第一轮拿钱买的20个。我分析了一下,发现这个代码在第一次递归过程中,return Soda(drinks,caps,bottles)+drinks 这后面跟的drinks已经被第二次置换的drinks替换掉了,导致少了第一次花20块大洋买的drinks。

所以得调整顺序
将drinks=caps/3+bottles/2的过程放在return内部
return Soda(caps/3+bottles/2,caps,bottles)+drinks;
然后崩了,因为caps%=3;bottles%=2已经发生了,所以caps/3+bottles/2已经小于1了,直接满足了终止条件跳出了循环

将这两句调换顺序并放在if前,这样在每次递归时,首先将caps和bottles置换掉,之后再加上就不会影响drinks的置换数量。

  1. caps%=3; bottles%=2;
  2. caps+=drinks;bottles+=drinks;

然后我还发现,终止条件caps<3&&bottles<2&&drinks<1有点啰嗦,因为caps+=drinks;bottles+=drinks;只要drinks<1,就表示caps和drinks肯定满足终止条件。

最终代码:

public static int Soda(int drinks,int caps,int bottles){
        caps%=3;  bottles%=2;
        caps+=drinks;  bottles+=drinks;
        if(caps<3&&bottles<2){
            return drinks;
        }
        else{
            return Soda(caps/3+bottles/2,caps,bottles)+drinks;
        }
    }

得出113瓶。。。。
久久不能释怀,感觉错过了一个亿 v_v

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/127468.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 小程序功能页面配置怎么填_设置企业级应用在哪

    小程序功能页面配置怎么填_设置企业级应用在哪企业微信自建应用流程

    2022年10月21日
  • linuxdocker常用命令_查看docker

    linuxdocker常用命令_查看docker1、docker服务相关命令启动docker服务:systemctlstartdocker停止docker服务:systemctlstopdocker重启docker服务:systemctlrestartdocker查看docker服务状态:systemctlstatusdocker设置开机启动docker服务:systemctlenabledocker2、docker镜像相关命令查看镜像:dockerimages查看所有镜像:dockerimages-a从网络中

  • 后台 管理 系统

    后台 管理 系统课程/视频管理系统:https://item.taobao.com/item.htm?spm=a2oq0.12575281.0.0.50111deb1nO3pa&ft=t&id=643539140484教务管理系统:https://item.taobao.com/item.htm?spm=a2oq0.12575281.0.0.50111deb1nO3pa&ft=t&id=643539140484成绩管理系统:https://item.taobao.com/item.h

  • xshell连不上虚拟机linux的解决办法_虚拟机linux大概什么配置

    xshell连不上虚拟机linux的解决办法_虚拟机linux大概什么配置刚上手linux,我用的是VMareWorkstation虚拟机,装的是Ubuntu操作系统,就遇到虚拟机不能上网问题,以及xshell连接虚拟机失败。网上找了好多相关问题的解决方案,在懵懵懂懂中终于解决了上述问题。记录一下,以供参考1.首先window+r输入cmd进入命令行输入:ipconfig可以看到如下:重点关注:本机…

  • springmvc笔记_SpringMVC优点

    springmvc笔记_SpringMVC优点MVC简介普通的web项目每次都要进行手动的把jar包导进去,否则会报500,classnotfound[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VstjHhuz-1609824493673)(C:\Users\王东梁\AppData\Roaming\Typora\typora-user-images\image-20210104132339761.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L9AgS48A-16

    2022年10月15日
  • 各类手机开发平台介绍(转载)[通俗易懂]

    各类手机开发平台介绍(转载)[通俗易懂]近来无事,把手机开发平台的学习指南、教程和资料总结一下,方便大家参考。手机客户端软件开发最大的困难就是平台不统一,手机开发平台太多。手机可分为智能手机开发和featherphone手机。开发平台可分为开放式平台和封闭式平台,开放式平台包括symbian、windowsmobile、linux、iPhone、Android、BlackBerry、j2me、brew等,支持手机应用程序通过OT…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号