C语言解决空瓶换水问题:高效算法与实现

标题:C语言解决空瓶换水问题:高效算法与实现


一、问题描述

在一个饮料促销活动中,你可以通过空瓶换水的方式免费获得更多的水:3个空瓶可以换1瓶水。喝完这瓶水后,空瓶会再次变为空瓶。假设你最初拥有一定数量的空瓶,问你最终最多可以喝到多少瓶水?


二、输入输出格式

输入
  • 一个整数 ( n ),表示初始空瓶的数量。
  • 当输入 ( n = 0 ) 时,表示输入结束,不再处理数据。
输出
  • 一个整数,表示最多可以喝到的水瓶数。
输入约束
  • ( 0 \leq n \leq 10^9 )。

三、解决思路

  1. 用空瓶换水

    • 每3个空瓶可以换1瓶水。
    • 剩下的空瓶数量为当前空瓶数的模3结果。
  2. 重复换水

    • 不断将换来的新瓶子喝完并重新计算空瓶数,直到无法再换。
  3. 特殊情况

    • 如果剩下两个空瓶,可以假设向老板借一个空瓶换最后一瓶水(喝完归还),可以多喝一瓶水。

四、C语言实现代码

#include <stdio.h>int main() {int n; // 初始空瓶数量// 读取输入,直到输入为0while (scanf("%d", &n) != EOF && n != 0) {int total_drinks = 0; // 喝到的总水瓶数while (n >= 3) {int new_drinks = n / 3; // 换到的新水瓶数量total_drinks += new_drinks; // 累加到总水瓶数n = new_drinks + (n % 3); // 剩余空瓶数量}// 处理剩余的2个空瓶情况if (n == 2) {total_drinks += 1;}// 输出结果printf("%d\n", total_drinks);}return 0;
}

五、代码详解

1. 变量说明
  • n:表示初始空瓶数量。
  • total_drinks:记录总共可以喝到的水瓶数。
  • new_drinks:每次用空瓶换到的新水瓶数量。
2. 主循环逻辑
  • 当空瓶数大于等于3时:
    • 计算新水瓶数量 new_drinks = n / 3
    • 更新总喝水数 total_drinks += new_drinks
    • 更新剩余空瓶数 n = new_drinks + (n % 3)
3. 特殊处理
  • 如果剩余空瓶数为2,假设可以借1个空瓶,再喝1瓶水。

六、输入输出示例

输入
10
3
0
输出
5
1
解释
  1. 输入10
    • 第一次换水:10空瓶换3瓶水,剩余1个空瓶。
    • 第二次换水:喝完3瓶水再换1瓶水,剩余2个空瓶。
    • 最后借1瓶空瓶,再喝1瓶水,总计喝5瓶水。
  2. 输入3
    • 3空瓶换1瓶水,总计喝1瓶水。
  3. 输入0
    • 结束程序。

七、算法复杂度分析

  1. 时间复杂度:( O(\log_3 n) )
    • 每次循环将瓶子数量减少为原来的 ( \frac{1}{3} )。
  2. 空间复杂度:( O(1) )
    • 只使用常量级的变量进行计算。

八、边界情况分析

  1. 输入为 0
    • 输出为空,无计算。
  2. 输入为 1 或 2
    • 无法换水,输出为 0。
  3. 输入为大数(如 ( 10^9 ))
    • 算法效率高,能够在合理时间内计算结果。

九、总结

本程序采用了简单的循环与贪心算法,利用空瓶数除以3的方式模拟实际换水过程,具有以下特点:

  1. 代码简洁:逻辑清晰,易于理解。
  2. 性能优秀:支持大范围输入,处理效率高。
  3. 扩展性强:可轻松修改用于类似的物品兑换问题。

通过这段代码,你将掌握贪心算法的核心思想,以及如何用C语言实现高效的数值计算。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/480274.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

elasticsearch单节点模式部署

原文地址&#xff1a;elasticsearch单节点模式部署 – 无敌牛 欢迎参观我的个人博客&#xff1a;无敌牛 – 技术/著作/典籍/分享等 第一步&#xff1a;下载 官方下载地址&#xff1a;Download Elasticsearch | Elastic&#xff0c;可以 wget 直接下载。 命令&#xff1a;wg…

26页PDF | 数据中台能力框架及评估体系解读(限免下载)

一、前言 这份报告详细解读了数据中台的发展历程、核心概念、能力框架及成熟度评估体系。它从阿里巴巴的“大中台&#xff0c;小前台”战略出发&#xff0c;探讨了数据中台如何通过整合企业内部的数据资源和能力&#xff0c;加速业务迭代、降低成本&#xff0c;并推动业务增长…

音视频入门基础:MPEG2-TS专题(8)——TS Header中的适配域

注&#xff1a;本文有部分内容引用了维基百科&#xff1a;https://zh.wikipedia.org/wiki/MPEG2-TS 一、引言 当TS Header中的adaptation_field_control属性的值为10或11 时&#xff0c;TS Header包含adaptation field&#xff08;适配域&#xff09;&#xff1a; 根据《T-RE…

挑战用React封装100个组件【001】

项目地址 https://github.com/hismeyy/react-component-100 组件描述 组件适用于需要展示图文信息的场景&#xff0c;比如产品介绍、用户卡片或任何带有标题、描述和可选图片的内容展示 样式展示 代码展示 InfoCard.tsx import ./InfoCard.cssinterface InfoCardProps {ti…

百度智能云千帆部署流程---语音识别和合成

目录 一、前期准备 二、语音合成 三、语音识别 实现整个流程如下图&#xff0c;但是我们的工作量并不是很多&#xff0c;我们可以在官网找到示例代码 一、前期准备 这里我们使用到3个代码 API_KEY.py 填写我们的API xzarm_asr.py 语音识别 xzarm_tts.py 语音合…

33 基于单片机的智能窗帘控制系统

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机&#xff0c;采用DHT11温湿度传感器检测温湿度&#xff0c;滑动变阻器连接ADC0832数模转换器转换模拟,光敏传感器&#xff0c;采用GP2D12红外传感器&#xff0c;通过LCD1602显示屏显示…

抓包之OSI七层模型以及TCPIP四层模型

写在前面 本文看下OSI七层模型以及TCP/IP四层网络模型&#xff0c;并尝试使用wireshark进行验证。 1&#xff1a;OSI七层网络模型和TCP/IP四层模型 全称&#xff1a;open system interconnection。 需要注意OSI七层模型最终是没有落地的&#xff0c;最终落地的是与之类似的…

华为海思2025届校招笔试面试经验分享

目前如果秋招还没有offer的同学&#xff0c;可以赶紧投递下面这些公司&#xff0c;都在补招。争取大家年前就把后端offer拿下。如果大家在准备秋招补录取过程中有任何问题&#xff0c;都可以私信小编&#xff0c;免费提供帮助。如果还有部分准备备战春招的同学&#xff0c;也可…

05_JavaScript注释与常见输出方式

JavaScript注释与常见输出方式 JavaScript注释 源码中注释是不被引擎所解释的&#xff0c;它的作用是对代码进行解释。lavascript 提供两种注释的写法:一种是单行注释&#xff0c;用//起头:另一种是多行注释&#xff0c;放在/*和*/之间。 //这是单行注释/* 这是 多行 注释 *…

【动手学电机驱动】STM32-FOC(8)MCSDK Profiler 电机参数辨识

STM32-FOC&#xff08;1&#xff09;STM32 电机控制的软件开发环境 STM32-FOC&#xff08;2&#xff09;STM32 导入和创建项目 STM32-FOC&#xff08;3&#xff09;STM32 三路互补 PWM 输出 STM32-FOC&#xff08;4&#xff09;IHM03 电机控制套件介绍 STM32-FOC&#xff08;5&…

Django+Nginx+uwsgi网站Channels+redis+daphne多人在线聊天实现粘贴上传图片

在DjangoNginxuwsgi网站Channelsredisdaphne多人在线的基础上&#xff08;详见DjangoNginxuwsgi网站使用Channelsredisdaphne实现简单的多人在线聊天及消息存储功能-CSDN博客&#xff09;&#xff0c;实现在输入框粘贴或打开本地图片&#xff0c;上传到网站后返回图片路径&…

全新AI模型家族登场:完全可复现的开源语言模型OLMo 2

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

Java进阶七-网络编程,反射

一 网络编程 网络编程&#xff1a;在网络通信的协议下&#xff0c;不同计算机上运行的程序&#xff0c;进行的数据传输。 一 基础知识 1 常见的软件架构 CS&#xff1a;通过客户端访问服务器。 1&#xff1a;画面可以做的非常好&#xff0c;用户体验好。2&#xff1a;需要…

【C++进阶篇】像传承家族宝藏一样理解C++继承

文章目录 须知 &#x1f4ac; 欢迎讨论&#xff1a;如果你在学习过程中有任何问题或想法&#xff0c;欢迎在评论区留言&#xff0c;我们一起交流学习。你的支持是我继续创作的动力&#xff01; &#x1f44d; 点赞、收藏与分享&#xff1a;觉得这篇文章对你有帮助吗&#xff1…

Swin-T图像论文复现

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

扫雷-完整源码(C语言实现)

云边有个稻草人-CSDN博客 在学完C语言函数之后&#xff0c;我们就有能力去实现简易版扫雷游戏了&#xff08;成就感满满&#xff09;&#xff0c;下面是扫雷游戏的源码&#xff0c;快试一试效果如何吧&#xff01; 在test.c里面进行扫雷游戏的测试&#xff0c;game.h和game.c…

Spring Web MVC(详解中)

文章目录 Spring MVC&#xff08;中&#xff09;RESTFul风格设计RESTFul风格概述RESTFul风格特点RESTFul风格设计规范RESTFul风格好处RESTFul风格实战需求分析RESTFul风格接口设计后台接口实现 基于RESTFul风格练习&#xff08;前后端分离模式&#xff09;案例功能和接口分析功…

输入json 达到预览效果

下载 npm i vue-json-pretty2.4.0 <template><div class"newBranchesDialog"><t-base-dialogv-if"addDialogShow"title"Json数据配置"closeDialog"closeDialog":dialogVisible"addDialogShow":center"…

STL算法之基本算法<stl_algobase.h>

STL标准规格中没哟区分基本算法或复杂算法&#xff0c;然后SGI却把常用的一些算法定义于<stl_algobase.h>之中&#xff0c;其他算法定义于<stl_algo.h>之中。以下一一列举这些基本算法。 目录 运用实例 equal,fill,fill_n,iter_swap, lexicographical_compare,m…

dns 服务器简单介绍

dns 服务器分类&#xff1a; 根域名服务器顶级域名服务器权威域名服务器本地域名服务器 dns 的查询过程 国内优秀公共域名 腾讯&#xff1a;DNSPod-免费智能DNS解析服务商-电信_网通_教育网,智能DNS-烟台帝思普网络科技有限公司 119.29.29.29 和 182.254.118.118 阿里&#xf…