一,题目
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. 如果三等份的重量相等,说明假币在剩下的未称重的硬币中。 2. 如果三等份的重量不相等,假设我们称重的是 A、B、C 三等份,其中 A 的重量比 B 轻,...
电子政务-一种称重内置的电子天平.zip
2021年08月苏州科技大学天平学院2021年公开招聘二级学院院长模拟试题
赛多利斯LA2200 精密天平在实验室自动进行小批量称重中的应用pdf,赛多利斯LA2200 精密天平在实验室自动进行小批量称重中的应用
天平杯”第十四届浙江省大学生财会信息化竞赛参考答案(高职).pdf
行业资料-电子功用-便携式静水称重电子天平的介绍分析.rar
浙江省第十一届大学生财会信息化竞赛本科组试题答案.pdf
初中物理沪科版八年级全一册第五章第二节学习使用天平和量筒练习题-普通用卷.docx
近年来,精密测量越来越多的应用到生活及生产过程中,应用的领域也越来越细, 现代称重与计数技术已成为工艺技术、储运技术、 预包装技术、收货业务及商业销售领域中不可缺少的组成部分。几乎在所有的工业领域都要...
江苏省扬州市宝应县天平2015-2016学年八年级上学期第一次月考试题(英语).doc
内蒙古准格尔旗第十中学八年级政治下册 第九课第一框 公平是社会稳定的天平导学案(无答案) 新人教版
江苏省扬州市宝应县天平中学2015-2016学年八年级英语上学期第一次月考试题-牛津译林版.doc
鲁科版五四制八年级上册物理 用天平测量质量 重点习题练习复习课件.ppt