首页 数据库 mysql教程 有2n个硬币和一个天平,其中有两个假硬币一个质量为m+1,一个质

有2n个硬币和一个天平,其中有两个假硬币一个质量为m+1,一个质

Jun 07, 2016 pm 03:00 PM
硬币 质量 问题

问题: 有2n个硬币和一个天平,其中有一个质量为m1,一个质量为m-1,其余质量都为m,用O(logn)的时间复杂度找到这两个假硬币? 解答: 假设2n有k个2进制位。设计k次称量,第i(i=1~k)次是把二进制序号第i位为0的硬币给取出来称。 这样第i次称量的结果如下,左

问题:

      有2n个硬币和一个天平,其中有一个质量为m+1,一个质量为m-1,其余质量都为m,用O(logn)的时间复杂度找到这两个假硬币?


解答:

      假设2n有k个2进制位。设计k次称量,第i(i=1~k)次是把二进制序号第i位为0的硬币给取出来称。

      这样第i次称量的结果如下,左边2列是偏重偏轻的硬币的序号在第i列的二进制值,第3列是第i次称量结果:
      0 0 正常
      0 1 偏轻
      1 0 偏重

      1 1 正常

      经过这k次称量,偏重偏轻的如果同一个二进制位数码不同的话那个位上的值已经知道了。

      接下来,假设第m位是刚才求出来的序号不同的那一位(这样的位一定存在,否则两枚硬币序号就会相同)。再做k次称量,这次,第i次挑选的硬币是第i位位0并且第m位为0。这样相当于排除了其中一枚硬币以后再O(logn)把它挑出来。挑出一个以后另一个也就挑出来了。

       举例:例如有2*3 = 8个硬币,所以k=3(如果2n为14 ,则选取k=4)。对每个硬币编码:000  001 010 011 100 101 110 111。 则先称出个位为零的硬币是不是4m(有四个零),再十位.... 以此类推。。。便可在O(logn)时间内找出假硬币。。。



  



本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

哔哩哔哩如何去获取里面的硬币呢 哔哩哔哩获取里面的硬币的方法 哔哩哔哩如何去获取里面的硬币呢 哔哩哔哩获取里面的硬币的方法 Mar 12, 2024 am 10:40 AM

  哔哩哔哩如何去获取里面的硬币呢?这款软件里面的奖励时非常多的,而且面对不同的奖励,用户们可以操作出不同的获取方法呢。有些用户们在登录这款软件的时候,就会获取到额外的奖励呢,对于刚注册进来的用户们我们应该怎么去获取里面硬币奖励呢?如果你还不知道怎么去获取里面的硬币,那就赶紧观看下面的由本站小编所带来的哔哩哔哩获取里面的硬币的方法。哔哩哔哩获取里面的硬币的方法  1.转正登录可得硬币  在转正的情况下,每日直接登录b站就可以直接得到一枚硬币。  2.未到重启  自动发放可能会有延迟,如果未到建议

解决C++代码中出现的'error: redefinition of class 'ClassName'”问题 解决C++代码中出现的'error: redefinition of class 'ClassName'”问题 Aug 25, 2023 pm 06:01 PM

解决C++代码中出现的“error:redefinitionofclass'ClassName'”问题在C++编程中,我们经常会遇到各种各样的编译错误。其中一个常见的错误是“error:redefinitionofclass'ClassName'”(类‘ClassName’的重定义错误)。这个错误通常出现在同一个类被定义了多次的情况下。本文将

聚类算法中的聚类效果评估问题 聚类算法中的聚类效果评估问题 Oct 10, 2023 pm 01:12 PM

聚类算法中的聚类效果评估问题,需要具体代码示例聚类是一种无监督学习方法,通过对数据进行聚类,将相似的样本归为一类。在聚类算法中,如何评估聚类的效果是一个重要的问题。本文将介绍几种常用的聚类效果评估指标,并给出相应的代码示例。一、聚类效果评估指标轮廓系数(SilhouetteCoefficient)轮廓系数是通过计算样本的紧密度和与其他簇的分离度来评估聚类效

教你如何诊断常见问题的iPhone故障 教你如何诊断常见问题的iPhone故障 Dec 03, 2023 am 08:15 AM

iPhone以其强大的性能和多方面的功能而闻名,它不能幸免于偶尔的打嗝或技术困难,这是复杂电子设备的共同特征。遇到iPhone问题可能会让人感到沮丧,但通常不需要警报。在这份综合指南中,我们旨在揭开与iPhone使用相关的一些最常遇到的挑战的神秘面纱。我们的分步方法旨在帮助您解决这些常见问题,提供实用的解决方案和故障排除技巧,让您的设备恢复到最佳工作状态。无论您是面对一个小故障还是更复杂的问题,本文都可以帮助您有效地解决这些问题。一般故障排除提示在深入研究具体的故障排除步骤之前,以下是一些有助于

解决jQuery无法获取表单元素值的方法 解决jQuery无法获取表单元素值的方法 Feb 19, 2024 pm 02:01 PM

解决jQuery.val()无法使用的问题,需要具体代码示例对于前端开发者,使用jQuery是常见的操作之一。其中,使用.val()方法来获取或设置表单元素的值是非常常见的操作。然而,在一些特定的情况下,可能会出现无法使用.val()方法的问题。本文将介绍一些常见的情况以及解决方案,并提供具体的代码示例。问题描述在使用jQuery开发前端页面时,有时候会碰

机器学习模型的泛化能力问题 机器学习模型的泛化能力问题 Oct 08, 2023 am 10:46 AM

机器学习模型的泛化能力问题,需要具体代码示例随着机器学习的发展和应用越来越广泛,人们越来越关注机器学习模型的泛化能力问题。泛化能力指的是机器学习模型对未标记数据的预测能力,也可以理解为模型在真实世界中的适应能力。一个好的机器学习模型应该具有较高的泛化能力,能够对新的数据做出准确的预测。然而,在实际应用中,我们经常会遇到模型在训练集上表现良好,但在测试集或真实

弱监督学习中的标签获取问题 弱监督学习中的标签获取问题 Oct 08, 2023 am 09:18 AM

弱监督学习中的标签获取问题,需要具体代码示例引言:弱监督学习是一种利用弱标签进行训练的机器学习方法。与传统的监督学习不同,弱监督学习只需利用较少的标签来训练模型,而不是每个样本都需要有准确的标签。然而,在弱监督学习中,如何从弱标签中准确地获取有用的信息是一个关键问题。本文将介绍弱监督学习中的标签获取问题,并给出具体的代码示例。弱监督学习中的标签获取问题简介:

如龙8酒类大师考试问题有哪些 如龙8酒类大师考试问题有哪些 Feb 02, 2024 am 10:18 AM

如龙8酒类大师考试涉及的问题包括哪些?对应的答案是什么?如何快速通过考试?酒类大师考试活动中有许多需要回答的问题,我们可以参考答案来解决。这些问题都涉及到酒的知识。如果需要参考,让我们一起来看看如龙8酒类大师考试问题答案的详细解析!如龙8酒类大师考试问题答案详解1、关于“酒”的问题。这是一种管由王室建立的蒸馏洒厂生产的蒸馏酒,以夏威夷大量种植的甘盘的糖分为原料酿制。请问这种酒叫什么?答:朗姆酒2、关于“酒”的问题。图片上是一种使用干琴洒和干苦艾酒调配而成的酒。它的特点是加入了橄榄,被誉为“鸡尼酒

See all articles