一,题目
1.用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的。使用x次天平,最多可以从y个小球中找出较轻的那个,求y与x的关系式
2.有一个很大很大的输入流,大到没有存储器可以将其存储下来,而且只输入一次,如何从这个输入流中随机取得m个记录
3.大量的URL字符串,如何从中去除重复的,优化时间空间复杂度
二,分析
1. y=3^x
2. 每次输入一个记录时,随机产生一个0到1之间的随机数,用这些随机数维护一个大小为m的堆。
3.采用取模hash函数,找一个hash函数了,映射过去,采用链接法避免冲撞 ,如果A映射后的值A!=B,C,D...,把A加入链表,若相同,删除A,继续遍历
三,重点解析第一题
单元测试:三个球A B C,称重A B,A=B--> C为轻;A>B--->B为轻;A<B--->A为轻
所以y取最大值,即每次刚好可以分三份。
第一次 y/3
第二次 (y/3)/3
*
*
第x次 y/(3^x)=1
所以y=3^x
以下为网友给出的解答:
每次将球分成三堆,尽可能让三堆球一样多或者让其中一堆多或者少一个。
球数y和沉重次数x的关系是:
y=1 =>x=0;(显然)
y=2 =>x=1;(显然)
y=3 =>x=2;(显然)
如果y>3,也是将球分为三堆,记为A堆、B堆、C堆
if y=3k(k>1)
称重一次,就可以判断瑕疵球在哪堆,从而使得球数降为k个;
if y=3k+1(k>=1)假设C堆多放1球,A堆和B堆进行称重
称重一次,就可以判断瑕疵球在哪堆,
if A == B ,瑕疵球在C堆,从而使得球数降为k+1个;
else 瑕疵球在轻的堆,从而使得球数降为k个;
if y=3k-1(k>=2)假设C堆少放1球,A堆和B堆进行称重
称重一次,就可以判断瑕疵球在哪堆,
if A == B ,瑕疵球在C堆,从而使得球数降为k个;
else 瑕疵球在轻的堆,从而使得球数降为k-1个;
利用以上过程反复,可得结果。
最后的次数x =log3(y),可能在y哪里还需要做点什么修正。但复杂度就是log
y
分享到:
相关推荐
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量
电子政务-电子天平称重单元.zip
[砝码称重问题]给定一架天平,要求用m个砝码称出1~n克范围内的所有物品的重量 ,问应该如何选择砝码~
梅特勒托利多称重设备应用案例pdf,梅特勒托利多称重设备应用案例
天平杯”第十四届浙江大学生财会信息化竞赛参考答案解析[高职].doc
2.令n = n – 9 = 5 – 9 = - 4,判断得|n|∈(1,4] 3.继续令n = n – (-3) = (-4) – (-3) = - 1,判断
江苏科技大学第八届大学生程序设计竞赛考试试题 本资源摘要信息涵盖了江苏科技大学第八届大学生程序设计竞赛考试试题,共包含八个编程题目,涵盖了算法、数据结构、数学运算等多个方面。 题目 1: 西岳华山上有一条...
电子天平称量软件使用:系统运行要求主要介绍软件运行所需要的软硬件环境。系统组成主要介绍电子天平称量软件总的组成部分,及各部分的作用。系统安装主要介绍软件的安装方法及步骤。系统使用为本说明书的重点介绍...
首先,我们将所有的硬币分成三等份,并将它们放在天平上称重: 1. 如果三等份的重量相等,说明假币在剩下的未称重的硬币中。 2. 如果三等份的重量不相等,假设我们称重的是 A、B、C 三等份,其中 A 的重量比 B 轻,...
电子政务-一种称重内置的电子天平.zip
称重传感器是电子天平、电子秤、地磅等质量称重设备的核心部件之一,直接影响设备的性能优劣。然而,称重传感器存在严重的蠕变误差问题,严重影响称重传感器的测量准确度和长期稳定性。 在本文中,我们提出了一种...
"2023合肥经开区第八届青少年信息学(编程)竞赛小学组试题及解析" 本资源摘要信息涵盖了2023合肥经开区第八届青少年信息学(编程)竞赛小学组的试题及解析,涵盖四个题目:求和、天平、周长和文本编辑器。每个题目...
2021年08月苏州科技大学天平学院2021年公开招聘二级学院院长模拟试题
赛多利斯LA2200 精密天平在实验室自动进行小批量称重中的应用pdf,赛多利斯LA2200 精密天平在实验室自动进行小批量称重中的应用
天平杯”第十四届浙江省大学生财会信息化竞赛参考答案(高职).pdf
行业资料-电子功用-便携式静水称重电子天平的介绍分析.rar
"冀教版六年级上册数学第八单元测试卷(探索乐园)" 本测试卷共分为四部分:我会填、我会辨、我会选、解决问题。其中,我会填部分有六道题,要求学生填充正确的答案;我会辨部分有四道题,要求学生判断正确或错误的...
浙江省第十一届大学生财会信息化竞赛本科组试题答案.pdf
近年来,精密测量越来越多的应用到生活及生产过程中,应用的领域也越来越细,现代称重与计数技术已成为工艺技术、储运技术、预包装技术、收货业务及商业销售领域中不可缺少的组成部分。几乎在所有的工业领域都要应用...
此程序可以用来读取赛多利斯电子天平的称重读数,但程序中读数部分代码需要自行提取,属于电子天平读数的代码可参考https://mp.csdn.net/postedit/80812561