C语言经典算法之出售金鱼算法

这篇具有很好参考价值的文章主要介绍了C语言经典算法之出售金鱼算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

A.建议

B.简介

一 代码实现

二 时空复杂度

A.时间复杂度:

B.空间复杂度:

C.总结:

三 优缺点

A.优点:

B.缺点:

四 现实中的应用


前言

A.建议

1.学习算法最重要的是理解算法的每一步,而不是记住算法。

2.建议读者学习算法的时候,自己手动一步一步地运行算法。

B.简介

关于出售金鱼的算法问题,是一个经典的逆向思维数学题。原题描述是这样的:小明将一缸金鱼分5次卖出,每次卖出规则如下:

  1. 第一次卖出全部的一半加1/2条。
  2. 第二次卖出余下数量的三分之一加1/3条。
  3. 第三次卖出剩余数量的四分之一加1/4条。
  4. 第四次卖出剩余数量的五分之一加1/5条。
  5. 最后剩下11条未卖出。

要求编写程序计算出原来鱼缸里共有多少条金鱼。

一 代码实现

以下是一个使用C语言来解决这个问题的基本思路和伪代码:

#include <stdio.h>
#include <math.h>

double reverseCalculateFish(int remaining_fish) {
    int i;
    for (i = 5; i >= 1; --i) {
        double soldPortion = (remaining_fish + 1.0 / i) * i;
        // 将soldPortion向下取整为整数部分(即减去小数点后的部分)
        remaining_fish = (int)soldPortion - 1;
    }
    return remaining_fish * 2; // 因为第一次卖出的是总数的一半加1/2条
}

int main() {
    int initialFishCount;
    // 使用最后剩下的11条鱼作为起始条件进行逆向推算
    initialFishCount = reverseCalculateFish(11);
    printf("原来鱼缸中共有 %d 条金鱼。\n", initialFishCount);

    return 0;
}

上述代码中定义了一个reverseCalculateFish函数,它接收剩余金鱼的数量,并根据卖出规则反向计算上一次卖出前的数量。从已知的最后一次剩余11条开始,逐步向前推算,直到计算到最初的金鱼数量。

注意,在实际编程时,由于涉及浮点数运算和向下取整,可能需要对浮点数做适当的处理以确保正确地得到整数结果。在C语言中可以使用floor()函数或直接类型转换为整数实现这个过程。同时,由于题目中提到的数量关系可能会导致浮点误差,因此计算过程中应尽可能避免累积误差的影响。

二 时空复杂度

上述算法是一个简单的迭代过程,用于逆向计算最初鱼缸中的金鱼数量。由于该算法仅涉及基本的算术运算和循环结构,其时空复杂度相对较低。

A.时间复杂度:

该算法中有一个从5开始递减到1的循环结构,循环次数固定为5次,因此时间复杂度是O(1)。这意味着不论输入数据规模如何变化(此处指剩余鱼的数量),算法执行的时间都是常数级别的。

B.空间复杂度:

算法中只使用了几个固定的变量(如iremaining_fish和中间计算结果)来进行计算,并没有依赖于问题规模的数据结构存储额外信息。所以空间复杂度也是O(1),即算法使用的额外空间不随问题规模的增长而增长。

C.总结:

总结起来,此出售金鱼问题的解决方案具有很好的时空效率,时间和空间复杂度均为常数级O(1)。

三 优缺点

A.优点:

  1. 简洁性:该算法思路直接明了,采用逆向思维,通过循环逐次还原每次卖出前的鱼数量,不需要复杂的搜索或优化过程。
  2. 效率高:由于时间复杂度和空间复杂度都是O(1),这意味着无论原始鱼缸中有多少条金鱼,算法都能在固定时间内完成计算,且占用的空间非常有限。
  3. 易于实现:仅用到基本的数学运算和控制结构(如for循环),无需高级的数据结构或者复杂的算法逻辑。

B.缺点:

  1. 特定场景:此算法是针对题目中特定规则设计的,对于更复杂、规则不明确或者非线性的销售情况则不适用,缺乏通用性。
  2. 数值精度:虽然在简单情况下浮点数运算能够得到正确结果,但在涉及大量连续除法和加法的实际情况中,可能因浮点数精度限制导致误差积累。尽管这个问题可以通过使用整数算术结合恰当的转换来避免,但如果题目扩展为更复杂的分数或小数,则需要特别注意数值稳定性问题。
  3. 无错误处理:该算法假设输入数据总是合法且符合题目的条件,即最后剩余的金鱼数量已知且在经过5次售卖后能正确逆推出初始数量。如果实际应用中存在数据异常或者售卖规则变化,算法没有包含相应的错误检测和处理机制。

四 现实中的应用

“出售金鱼”问题所体现的算法本质上是一个逆向思维和逐步还原的过程,这种逻辑在现实中的应用是多样的:

  1. 资源分配与追踪: 在供应链管理、库存管理和项目管理等领域中,当需要追溯一个物品或资源经过一系列操作后最初的状态时,可以借鉴这个算法的思路。例如,通过记录每次消耗或分配的数量以及额外的变动值,逆向计算出原始总量。

  2. 财务分析与审计: 在财务分析中,如果知道公司资产在连续几个阶段后的余额及其各阶段的变化规则(如扣除一定比例费用并加上特定金额),可以采用类似的方法来反推初始资金数额。

  3. 编程教学与练习: 这种问题常被用作数学逻辑训练和编程教育的题目,用于锻炼学生的逆向思考能力和递归/迭代解决问题的能力。

  4. 数据分析与预测修正: 在数据处理过程中,有时需要根据当前结果回溯过去的情况,以校正模型参数或者调整预测模型。该算法提供了一种从已知结果出发进行反向推理的方法论基础。

  5. 游戏设计与开发: 游戏中经常涉及生命值、资源点数等属性的变化,玩家可能需要根据最后剩余的数值去推测之前某个状态下的属性值,此算法可以帮助游戏开发者实现这一功能。

虽然以上提到的应用场景不是直接对应于“出售金鱼”问题本身,但它们都体现了相同的问题解决策略——基于已知结果,按照给定规则逆向求解原初状态。文章来源地址https://www.toymoban.com/news/detail-843534.html

到了这里,关于C语言经典算法之出售金鱼算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】之多指针算法经典问题

    本文为 【数据结构与算法】多指针算法经典问题 相关介绍,下边将对 链表反转 (包含 迭代反转链表 、 递归反转 、 头插法反转 ), 双指针-快慢指针 (包含 寻找单向无环链表的中点 、 判断单向链表是否有环及找环入口 ), 双指针-左右指针 (包含 两数之和 、 二分查

    2024年02月03日
    浏览(18)
  • 数据结构(五)数据结构与算法中的经典题

    本文是在原本数据结构与算法闯关的基础上总结得来,加入了自己的理解和部分习题讲解。至此数据结构介绍已完结,后续会把数据结构算法题系列更完。 原活动链接 邀请码: JL57F5 根据要求完成题目 Q1. (单选)以下哪些数据结构支持随机访问? A. 数组 B. 单链表 C. 双向链表

    2024年01月20日
    浏览(23)
  • 【数据结构与算法】:10道链表经典OJ

    思路1:遍历原链表,将 val 所在的节点释放掉。(太麻烦) 思路2:创建新链表,再遍历原链表,找到不为 val 的节点尾插到新链表。 思路1代码实现如下: 注意: 1.当链表为空时,直接返回NULL即可。 2.当尾插上最后一个有效节点时,此时它的 next 可能还与最后一个节点相链接,

    2024年04月14日
    浏览(18)
  • 200个经典面试题(算法思想+数据结构)_1

    1. 爬楼梯 70. Climbing Stairs (Easy) 题目描述:有 N 阶楼梯,每次可以上一阶或者两阶,求有多少种上楼梯的方法。 定义一个数组 dp 存储上楼梯的方法数(为了方便讨论,数组下标从 1 开始),dp[i] 表示走到第 i 个楼梯的方法数目。 第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步

    2024年02月13日
    浏览(20)
  • 头歌数据结构实训参考---十大经典排序算法

    可通过 目录 快速查阅对应排序算法

    2024年02月04日
    浏览(22)
  • 【数据结构】单链表经典算法题的巧妙解题思路

    目录 题目 1.移除链表元素 2.反转链表 3.链表的中间节点 4.合并两个有序链表 5.环形链表的约瑟夫问题 解析 题目1:创建新链表 题目2:巧用三个指针 题目3:快慢指针 题目4:哨兵位节点 题目5:环形链表   介绍完了单链表,我们这次来说几个经典的题目,本篇的题目衔接下一

    2024年04月28日
    浏览(19)
  • 追梦之旅【数据结构篇】——C语言手撕八大经典排序

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月17日
    浏览(20)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到,最大的公共子串长度为2,一共有两个长度为2的公共子串,分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符,即 ba 和 ac 根据上面的方法,我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(59)
  • 算法竞赛备赛之经典数据结构训练提升,暑期集训营培训

    我们将结构体和指针结合来实现链表 我们算法主要是用数组来模拟链表,这样效率会高一些。 数组模拟单链表 邻接表:存储图和树 实现一个单链表,链表初始为空,支持三种操作: 向链表头插入一个数 删除第k个插入的数后面的数 在第k个前面插入一个数 数组模拟双链表的

    2024年02月16日
    浏览(28)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(19)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包