小猪,信息论与我们的生活

news/2024/11/27 22:28:38/

前言

动态规划是大家都熟悉与陌生的知识,非常灵活多变,我自己也不敢说自己掌握了,今天给大家介绍一道题,不仅局限于动态规划做题,还会上升到信息论,乃至于启发自己认知世界的角度
因为比较难,本文不会详细介绍动态规划方法,所以需要读者有一定基础,否则可能理解有困难

题目链接:可怜的小猪

buckets 桶液体,其中 正好有一桶 含有毒药,其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药,你可以喂一些猪喝,通过观察猪是否会死进行判断。不幸的是,你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下:

  1. 选择若干活猪进行喂养
  2. 可以允许小猪同时饮用任意数量的桶中的水,并且该过程不需要时间。
  3. 小猪喝完水后,必须有 minutesToDie 分钟的冷却时间。在这段时间里,你只能观察,而不允许继续喂猪。
  4. 过了 minutesToDie 分钟后,所有喝到毒药的猪都会死去,其他所有猪都会活下来。
  5. 重复这一过程,直到时间用完。

给你桶的数目 bucketsminutesToDieminutesToTest ,返回 在规定时间内判断哪个桶有毒所需的 最小 猪数

示例 1:

输入: buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出: 5

示例 2:

输入: buckets = 4, minutesToDie = 15, minutesToTest = 15
输出: 2

示例 3:

输入: buckets = 4, minutesToDie = 15, minutesToTest = 30
输出: 2

dp解析

一般来说,动态规划就是三步骤

  1. 定义数组含义,多数情况是int值, dp[]或者dp[][]
  2. 赋予初始值
  3. 找到状态转移方程,开始递推

推到最后,大部分情况下,dp数组最后一个值就是答案

这个题,

题中有buckets,minutesToTest,minutesToDie三个变量,由于正面角度比较难思考,可以反过来,
全问题为n只小猪,能够有限的轮次测试中测出毒药,一轮耗时minutesToDie,总轮数为minutesToTest/minutesToDie

所以,其子问题为i只小猪测试j轮的结果,不影响后续测试,而后续测试需要子问题的结果来递推
满足动态规划的重叠子问题和无后效性原则,同时又是求最值(简称n),所以确定可以用动态规划(简称dp)

  • 首先定义数组含义
    f(i, j)表示i只小猪,测试j轮后最多可以在多少butkets中找到毒药,显然,这是一个二维数组dp[i][j]
  • 然后赋予初始值
    dp[0][0] , dp[i][0]都为1,相当于没有测试,因为知道必有一桶毒,所以bucket = 1时,可以肯定为有毒,dp[0][j]没有猪,也全为1
  • 状态转移
    假设现在状态要算f(i, j),一轮测试后还剩下k只猪存活,而测试剩下j - 1次,可以确定,f(k, j - 1)就是f(i, j )的前一个状态,并将递推出f(i, j)
    从i变为k的可能组合数为 C(i, k),因此f(i, j) = C(i, k) * f(k, j - 1),其中k的取值为0~i,所以最后的计算如下
    f ( i , j ) = ∑ k = 0 i f ( k , j − 1 ) × C i k f(i,j) = \sum_{k=0}^i f(k, j-1) \times C_{i}^{k} f(i,j)=k=0if(k,j1)×Cik

到了这步,已经掌握了解题钥匙,更多细节可以参考题解
本文并非想详细介绍题解,更多的是探讨思想

信息论

抛开dp的过程,只看开始和结尾,buckets,minutesToTest,minutesToDie都限定后,通过递推或者某种方式,我们就能得到最少的猪数量n,也就是说,当相关信息量确认好后,答案就确定了

这给我们一个很大提示,那就是,面对一个问题的时候,在耗费时间去做之前,仅仅凭借已经掌握的信息,就能判断出能不做成。注意,这里不是靠经验或者直觉,而是真真实实的科学,若是吸收这一思想,并勤加练习,相当多的难题可以得到解决

那现在我们就来仔细了解下这一理论吧

我们知道,计算机的很多数据看不见摸不着,我们将其统一设置为二进制,使用bit来记录数据,创造纷繁的信息世界。而我们,不知道三维世界的造物主用的几进制,在这个世界的我们无法用自己的信息来精确表达信息本身

不过没关系,我们可以一个模糊的“熵”暂时代替,表示混乱度,越混乱,熵越高

熵增定律:在一个孤立系统里,如果没有外力做功,其总混乱度(熵)会不断增大

对于理科生很好理解,毕竟学过
对于保洁也很好理解,毕竟一个房间如果长期不打扫,肯定会变脏
对于老师也很好理解,毕竟他如果长时间不来教室,教室肯定乱套
对于宅男更好理解,长期不外出不和人交流,一定……

信息熵与信息

在信息论中,信息熵表示信息的不确定程度

比如,我们都知道,同样的内容,中文写的往往比英文薄一些,实际上,就是因为中文的信息不确定程度高,也就是信息熵大,所以所需的信息量就会少,字数也会少,往往掌握1000个汉字就能应付日常说话,很多汉字在不同的组词下有大量不同的含义。而英文,掌握5000单词都未必能说清楚

但是信息熵大未必是好事,信息熵越大,不确定程度越高,其实代表信息量越少,而减少信息熵的方式,就是增加含信息量的信息,不含信息量的信息,可以归类为废话(说到这,我都不认识信息两字了)

所以方向来了!对于一件富含信息熵的事情,我只要掌握足够信息量的信息,与信息熵等价,那么就可以做!

比如,明天是否下雨?,这件事信息熵很大,天气预报的结果,天上的乌云,蚂蚁搬家等等都是多多少少降低信息熵的信息

到了这里,你可以还是会有疑惑,说来说去,最后不还是靠感觉吗?不过是用了一些科学名词归类而已

香农厉害就厉害在这里,讲一个千万年来人说不清的感觉提取出公式,让人类的认知进入了一个全新领域。在信息论提出之后,个人认为能与这一瞬间媲美的只有阿姆斯特朗的那一小步。
公式如下

H ( X ) = − ∑ i = 1 n p ( x i ) log ⁡ b p ( x i ) H(X) = -\sum_{i=1}^n p(x_i)\log_b p(x_i) H(X)=i=1np(xi)logbp(xi)
看起来挺复杂,但是理解很简单,

其中,H(X)表示随机变量X的信息熵,P(xi)表示X取值为xi的概率,logb表示以b为底的对数。

这里的b表示信息单位的基础,如果你想二进制表示,那么b == 2
x表示事件,xi可以理解为x里面的某种元素,公式就是将X事件中,1~n种元素发生的概率求和而来,n可以理解为可能的所有情况

比如扔一枚硬币,只有两种情况,那么其信息熵为
H ( X ) = − ∑ i = 1 2 p ( x i ) log ⁡ 2 p ( x i ) = − [ 0.5 log ⁡ 2 ( 0.5 ) + 0.5 log ⁡ 2 ( 0.5 ) ] = 1 b i t H(X) = -\sum_{i=1}^2 p(x_i)\log_2 p(x_i) = -\left[0.5\log_2(0.5) + 0.5\log_2(0.5)\right] = 1 bit H(X)=i=12p(xi)log2p(xi)=[0.5log2(0.5)+0.5log2(0.5)]=1bit

也就是说,只要有一个含1bit信息量的信息,就可以消灭信息熵,比如我告诉你,硬币为正面,此时,信息熵消失

解题

回到小猪的话题,题目充满了H(X)信息熵,在minutesToTest,minutesToDie限定下,X为bucket数,x为1000时

H = − ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) − ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) − . . . − ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) H = - (1/1000) * log2(1/1000) - (1/1000) * log2(1/1000) - ... - (1/1000) * log2(1/1000) H=(1/1000)log2(1/1000)(1/1000)log2(1/1000)...(1/1000)log2(1/1000)

= − 1000 ∗ ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) = l o g 2 ( 1000 ) ≈ 9.97 = - 1000 * (1/1000) * log2(1/1000) = log2(1000) ≈ 9.97 =1000(1/1000)log2(1/1000)=log2(1000)9.97
我们可以对这个结果有些感性认识,看起来信息熵的增长不是线性的,而是log,扔硬币这种五五开的事情为1,而1000桶水找1个有毒居然只有9.97,当有10000桶水时,信息熵为log2(10000) = 13.29

现在我们就要考虑,多少小猪能提供超过9.97

参考链接:https://www.zhihu.com/question/60227816/answer/1274071217
https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)


http://www.ppmy.cn/news/65362.html

相关文章

AFG1062任意波形/函数发生器 产品资料

AFG1000 任意波形/函数发生器,提供 25MHz 或 60MHz 带宽,2 个输出通道,在整个带宽内 1mVpp 到 10Vpp 输出振幅,泰克 AFG1000 任意波形/函数发生器可以生成各种实验室测试所需波形。 *重要的是,它在泰克任意函数发生器系…

推荐几款2023年还在用的IDE工具

近期有不少刚学编程的小伙伴来问我,市面上那么多IDE工具,该怎么选?今天在这里跟大家分享几款个人比较钟爱的IDE工具,供大家参考。 Visual Studio 优点:支持多种语言,包括C#, C, Visual Basic等&#xff0c…

Spring ( 二 ) 介绍

2.Spring Spring框架是一个用于Java开发的开源应用程序框架,提供了一系列的工具和解决方案,帮助开发者快速构建高质量、可维护的企业级应用。Spring框架的主要特点包括:模块化、轻量级、可测试性、松耦合、面向切面编程(AOP&…

谷歌正在向所有账户推出密码终止技术

谷歌宣布让其个人帐户持有人使用称为“密码”的密码替代登录的一项重大努力。 该功能面向公司的数十亿帐户推出,用户将能够主动寻找并启用它。谷歌表示,它计划在未来几个月推广密码,并开始推动账户持有人将他们传统的用户名和密码登录转换为…

Flink dataStream,如何开窗,如何进行窗口内计算

目录 开窗方式 windowAll() window() 窗口类型 基于时间 基于数量 开窗后的处理函数 全量聚合函数(也叫窗口函数) 增量聚合函数 增量聚合函数携带一个全量聚合函数 开窗方式 windowAll() 对于没有keyBy的数据流 window() 对于KeyBy后的数据…

第13章 CacheService角色实体的CURD操作示例

1 Services.Customers.CustomerServiceDefaults using Core.Caching; using Core.Domain.Customers; namespace Services.Customers { /// <summary> /// 【用户服务默认--类】 /// <remarks> /// 摘要&#xff1a; /// 该类中的属性成员实例设定一些常量值&…

C++初始化列表

1.初始化列表概述 初始化列表&#xff1a;以一个冒号开始&#xff0c;接着是一个以逗号分隔的数据成员列表&#xff0c;每个"成员变量"后面跟一个放在括号中的初始值或表达式。 2.为什么使用初始化列表 在创建对象时&#xff0c;编译器通过调用构造函数&#xff0c…

探索数字化转型新道路!流辰信息微服务与您一起创未来!

科技在进步&#xff0c;社会在发展&#xff0c;办公自动化也在高速发展中。数字化转型是当下企业获得长久发展的趋势之一&#xff0c;在信息瞬间万变的社会中&#xff0c;谁掌握了核心技术&#xff0c;谁能与时代同步&#xff0c;谁就能开启新的康庄大道&#xff0c;谁就能在转…