g******a
发帖数: 69 | 1 发信人: dntx (鑫森淼焱垚), 信区: mathematics
标 题: Re: 称球问题大全——简答与扩展
发信站: 日月光华站 (Mon Feb 28 16:33:22 2000) , 转信
下面将给出称球问题次数的答案，并提出一个扩展问题供大家讨论。
[说明]
称球问题长期以来都是各大BBS的一个经久不衰的题目，相信许多
网友都已知道了它的答案，所以下面仅给出各题的称球次数公式，
至于详细步骤，大家可以参阅前面 playstom 网友的 re 文，
也可去清华，木棉，南开等 bbs 站查到详细解答，此处就从略了。
[答案]
各题至多所需称球次数依次为：
0. ceiling(log3(N))
1. ceiling(log3(2*N+1))
2. ceiling(log3(2*N+3))
3. ceiling(log3(2*N-1))
4. ceiling(log3(2*N+1))
其中 ceiling 表示上取整，log3表示取以3为底的对数
[扩展分析]
下面我想提出一个称球问题的扩展来供大家讨论。
以上5个称球问题的传统解，其各次称法一般是相关的，即第2次 |
|
y**k
发帖数: 222 | 2 There are solutions. For any n0, there exists n>n0 and m, such that
log2/log3 - 1/n^2 < m/n < log2/log3. We want to show that
log2/log3 - 1/n^2 > (log2/log3)/2 + log(2^{n/2} -1)/log3/n for some n
. |
|
f********a
发帖数: 165 | 3 import java.util.HashMap;
public class MyClass {
public static HashMap hashMap = new HashMap
Integer>();
private String s = new String();
public void log1(String msg1, String msg2){
synchronized(hashMap){
System.out.println(msg1);
System.out.println(msg2);
}
}
public void log2()
{
hashMap.put(new String("123"), new Integer(1));
}
public static void log3(String ms... 阅读全帖 |
|
r**u
发帖数: 1567 | 4 2. hash the address of each node, 如果conflict就比较address。
3. binary search每次比较一次，需要log2（n）层比较。total: log2(n)
如果是triple search每次比较2此，需要log3(n)层比较。total: 2*log3(n) = 2 * log2(n)/log2（3）> log2(n)。
也就是都是O(logn)，但是前面的constant不一样，binary该是最小的。
6. 经常变化就需要快速查询，修改，hash或者array啥的都合理吧。 |
|
r*******g
发帖数: 43 | 5 log3(100)=4.2
2log3(N)这公式明显不对呀。
我觉得是ceil(log3(N)),如果不知轻重再加1. |
|
j*****y
发帖数: 1071 | 6 一面的第三题一般是可以做到 n^(log3) 吧？
比如 算 A * A where A is n digits number
A = B * 10^(n / 2) + C
A * A = B * B * 10^n + 2 * B*C * 10(n / 2) + C * C
need to compute B * B, B * C and C * C
So we compute three items below:
(B+C) * (B+ C) = B*B + 2*B*C + C*C
B*B
C*C
from which we can get 2*B*C = (B+C) * (B + C) - B*B - C*C
let the time for A^2 is T(n)
so we have T(n) = 3 T(n/2) + O(n)
and T(n) = O(n^(log3)
这里假设两个 n digits number的求和需要 O(n)的时间
补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
=======================... 阅读全帖 |
|
l*********8
发帖数: 4642 | 7 应该可以组合酒。
把n个酒瓶从0到n-1编号， 然后表示为三进制， 总共 k= log3(n)位。
对于 i = 0, 1 ... k位， 用一只老鼠喝所有第i位为0的酒的sample混合物， 另一只
老鼠喝所有第i位为1的酒的sample混合物。
总共需要 2* log3(n)只老鼠。 |
|
F******n
发帖数: 160 | 8 关于分形维数和测度的基本数学理论，我有几个问题：
问题1。
关于 "Hausdorff dimension" ( dim(F) ), "packing dimension" ( Dim(F) ) 和
"Minkowski-Bouligand dimension" ( dimMB ) ：
知道： dim(F) <= Dim(F) <= dimMB ；
定义这三种维数的基本思想和出发点是什么呢？我的书中有简短的论述，
但是太简短。
问题2。
问题1中定义的三种维数，和最基本的重复迭代系统中计算维数的方法，有何联系或
不同？ “最基本的重复迭代系统中计算维数的方法”是指， 比如说，对康托集 (Cantor
set), 维数 d = log2/log3 = 0.63.... , 又如，Koch curve, 维数
d = log4/log3 = 1.26...
附带问一下，问题3。
“Standar Lebesgue Measure” 是个什么测度？(Anyway, 这是个次要的问题)
请详细一点解释，Thanks much! |
|
F******n
发帖数: 160 | 9 关于分形维数和测度的基本数学理论，我有几个问题：
问题1。
关于 "Hausdorff dimension" ( dim(F) ), "packing dimension" ( Dim(F) ) 和
"Minkowski-Bouligand dimension" ( dimMB ) ：
知道： dim(F) <= Dim(F) <= dimMB ；
定义这三种维数的基本思想和出发点是什么呢？我的书中有简短的论述，
但是太简短。
问题2。
问题1中定义的三种维数，和最基本的重复迭代系统中计算维数的方法，有何联系或
不同？ “最基本的重复迭代系统中计算维数的方法”是指， 比如说，对康托集
(Cantor set), 维数 d = log2/log3 = 0.63.... ; 又如，Koch curve, 维数
d = log4/log3 = 1.26...
附带问一下，问题3。
“Standar Lebesgue Measure” 是个什么测度？(Anyway, 这是个次要的问题)
请详细一点解释，Thanks much! |
|
g*********r
发帖数: 9366 | 10 【 以下文字转载自 Joke 讨论区 】
发信人: lqm1989 (Jeremy Lin), 信区: Joke
标 题: zz科学把妹法 (转载)
发信站: BBS 未名空间站 (Sun Apr 22 13:56:38 2012, 美东)
发信人: iSeven (小七怀挺！Aggressive！), 信区: Piebridge
标 题: zz科学把妹法
发信站: BBS 未名空间站 (Sun Apr 22 11:04:24 2012, 美东)
其实吧，这个把妹是个科学活，技术活，艺术活！什么智商低地，没意志地，人穷胆小
地就别看了
1巴甫洛夫把妹法
曾经有一位生物学人士，公布了工科把妹第一弹，暨“巴甫洛夫把妹法”：
每天给你那位心仪的女同事/女同学的抽屉里都放上精心准备的早餐，并且保持缄默不
语，无论她如何询问，都不要说话。
如此坚持一至两个月，当妹子已经对你每天的准时早餐习以为常时，突然停止送餐，她
心中一定会产生深深的疑惑及失落，同时会满怀兴趣与疑问找到你询问，这时再一鼓作
气将其拿下。
此法借鉴了不朽的生物学家巴甫洛夫之“条件反射试验”，故名“巴甫洛夫把妹法”。
... 阅读全帖 |
|
d*******o
发帖数: 56 | 11 log3
功名断肠一笑
桃花断肠天气
桃李平生
而今何时东风
寂寞何处相逢
天上 |
|
D****u
发帖数: 3217 | 12 扯淡吧
常用对数自然要背的
特别是log2(X), log3(X), log10(X)这些 |
|
l*******s
发帖数: 7316 | 13 f(n)>f(n+1)也有解
n>0
m=3^(floor(logn/log3))
f(n)=-( n + m) (m<= n <=2*m)
f(n)=-3*(n - m) (2*m<= n < 3*m) |
|
m****y
发帖数: 28 | 14 你这算法跟逐行binary search毫无区别，把2换成了3而已
你的复杂度是2n*log3(n) |
|
x****r
发帖数: 99 | 15 请问如果用master theorem怎么证明这个算法是2n*log3(N)
虽然intuitively很容易解释。。
谢谢：） |
|
r*******g
发帖数: 43 | 16 33 33 34 秤一次，如果这两堆一样那么剩下34，不一样剩33
剩33， 11 11 11 称第二次
3 3 5 称第三次，剩3个（再需一次）或者5个
剩5， 2 2 1 最多两次，
剩34， 11 11 12 同理，最多也是5次
这个题有通解， 假设N个球， 那么worst case最少是ceil(log3(N)).对不？
位置 |
|
c******w
发帖数: 1108 | 17 ceil(log3(N)) + 2 肯定够了吧
一开始用3次把范围缩小到1/3而且知道轻重.然后每称一次就再缩小到1/3 |
|
c*******t
发帖数: 1095 | 18 ...算我表达不济，但也不至于理解成最好情况吧。。
最好情况是，无限多个球，随机取2个，称1次，不等，再拿其中一个和标准的比，
一共2次就称出任意M个球
明显公式 3^N>=2M 不是表示最好情况
反过来已知M，则N=ceiling（log3(2M)) |
|
n*******n
发帖数: 202 | 19 3^456=10^x+1
x=456*log3+1=218 |
|
d**********x
发帖数: 4083 | 20 老印吹牛不上税呗。
先cut 3^k，再cut 3^(k-1)。。。最后相当与cut出来近似log3(n)块(考虑3进制表示)
每次merge他都要reverse一半，3^k直接和n可比，也就是说每次merge都要O(3^k) = O(
n)次操作
最后复杂度是O(nlogn)
空间 |
|
b*****7
发帖数: 31 | 21 请问Karatsuba algorithm analysis下面步骤是如何得出的？
3^logN => 3N^log3 |
|
t*****a
发帖数: 106 | 22 FB已挂，上面经。
Round 1: 1. Given an array, find the max drop. Buying stock 的变种。buying
stock是找最大的increase,这个是找decrease.
2. Build BST from an array. leetcode原题。
3. Combine logs. 一个用户可能有多个log, log1, log2, log3, 这
些log之间有相同元素，combine所有相似log. 给了两个解法，建graph找connected
components, 和iterative. 最后就写了iterative, 有个小bug, 改了。
Round2 . Behavior＋coding. 1. Find island number from an matrix. (1 is
island). 我说见过，或者DFS/BFS, 或者pattern match.
2. Read 4k. 我说见过，然后... 阅读全帖 |
|
r*******h
发帖数: 315 | 23 treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
处理多了。 |
|
a*****g
发帖数: 19398 | 24 这个是查的，不是背的。
大概知道 log2 log3 是多少就够了。 |
|
a****b
发帖数: 3588 | 25 我当时也觉得是和香农公式有关的。查了一下，查到了：
ZZ
克劳德·香农(Claude Elwood Shannon，1916-2001)
1948年10月发表于《贝尔系统技术学报》上的论文《A Mathematical Theory
of Communication》（通信的数学理论）成了信息论正式诞生的里程碑。香农理论的重
要特征是熵(entropy)的概念，他证明熵与信息内容的不确定程度有等价关系。在他的通
信数学模型中，清楚地提出信息的度量问题，在该文中，他把哈特利的公式扩大到概率
pi不同的情况，得到了著名的计算信息熵H 的公式：
H=∑-pi log pi
如果计算中的对数log是以2为底的，那么计算出来的信息熵就以比特 (bi
t)为单位。
解：设三次称量，最多可以在n（n为自然数）个球中找出不同的球。
由已知得：随机拿两个球用天平称重，称量一次可以得到三种信息结果（>,=,
<），且三种结果的概率使相同的，所以根据哈特利信息量公式得到一次称量可以得到的
信息量为 log3（以2为底），又因为3次称量相互独立，概率相等，所以题目要求的3次
称量总共确定的信息是3log3（以... 阅读全帖 |
|
b****t
发帖数: 5743 | 26 A6300 Key specs:
new 24MP BSI sensor
11fps
4D focus
4K video (pixel binnning 14 stops dynamic range, 100MPS)
world’s fastest af 0,05 sec
425 phase detect AF points
silent shooting
Ships in March for $1000 (body only)
24.2MP APS-C Exmor CMOS Sensor
BIONZ X Image Processor
XGA Tru-Finder 2.36m-Dot OLED EVF
3.0" 921.6k-Dot Tilting LCD Monitor
Internal UHD 4K30 & 1080p120 Recording
S-Log3 Gamma and Display Assist Function
Built-In Wi-Fi with NFC
4D FOCUS with 425 Phase-Detect Points
Up to 11 fps Sho... 阅读全帖 |
|
l*****9
发帖数: 9501 | 27 【 以下文字转载自 Piebridge 讨论区 】
发信人: iSeven (小七怀挺！Aggressive！), 信区: Piebridge
标 题: zz科学把妹法
发信站: BBS 未名空间站 (Sun Apr 22 11:04:24 2012, 美东)
其实吧，这个把妹是个科学活，技术活，艺术活！什么智商低地，没意志地，人穷胆小
地就别看了
1巴甫洛夫把妹法
曾经有一位生物学人士，公布了工科把妹第一弹，暨“巴甫洛夫把妹法”：
每天给你那位心仪的女同事/女同学的抽屉里都放上精心准备的早餐，并且保持缄默不
语，无论她如何询问，都不要说话。
如此坚持一至两个月，当妹子已经对你每天的准时早餐习以为常时，突然停止送餐，她
心中一定会产生深深的疑惑及失落，同时会满怀兴趣与疑问找到你询问，这时再一鼓作
气将其拿下。
此法借鉴了不朽的生物学家巴甫洛夫之“条件反射试验”，故名“巴甫洛夫把妹法”。
2薛定谔把妹法
薛定谔把妹法乃是建立在巴甫洛夫把妹法之上的威力加强版：
每天早上，你拿出一个硬币抛掷，让伟大的随机性来决定今天是否给妹子送早餐。
这样，当妹子每天打开抽屉之前，都不知道是... 阅读全帖 |
|
|
l*******s
发帖数: 7316 | 29 题目改成
f: Z-> Z,
Z is set of integers
f(f(n)) = 3n
f(n) > f(n+1)
也有解：
n>0
m=3^(floor(logn/log3))
f(n)= -(n + m) (m<= n <=2*m)
f(n)=-3*(n - m) (2*m<= n < 3*m)
f(0)=0
f(-n)=-f(n) |
|
i****n
发帖数: 13151 | 30 其实吧，这个把妹是个科学活，技术活，艺术活！什么智商低地，没意志地，人穷胆小
地就别看了
1巴甫洛夫把妹法
曾经有一位生物学人士，公布了工科把妹第一弹，暨“巴甫洛夫把妹法”：
每天给你那位心仪的女同事/女同学的抽屉里都放上精心准备的早餐，并且保持缄默不
语，无论她如何询问，都不要说话。
如此坚持一至两个月，当妹子已经对你每天的准时早餐习以为常时，突然停止送餐，她
心中一定会产生深深的疑惑及失落，同时会满怀兴趣与疑问找到你询问，这时再一鼓作
气将其拿下。
此法借鉴了不朽的生物学家巴甫洛夫之“条件反射试验”，故名“巴甫洛夫把妹法”。
2薛定谔把妹法
薛定谔把妹法乃是建立在巴甫洛夫把妹法之上的威力加强版：
每天早上，你拿出一个硬币抛掷，让伟大的随机性来决定今天是否给妹子送早餐。
这样，当妹子每天打开抽屉之前，都不知道是否有早餐，而早餐的有无乃是一个独立随
机事件，完全无法推测。每天的早餐对于妹子都是一个未知的神秘存在，妹子将逐渐为
这一神秘的现象所吸引，最终将不可避免的对这个送餐人产生极大的兴趣，你在她的心
中蒙上了神秘的面纱。
这个谜一样的男子，这一刻薛定谔附体，带着量子论... 阅读全帖 |
|
g***j
发帖数: 40861 | 31 哈哈，我特愚昧
我用的竟然是[10-log3(9)]x3 |
|
W***o
发帖数: 6519 | 32 我有一个csv文件，里面有多行多栏的数据，我想把这些数据通过3D surface plot表述
出来(x轴坐标就用第一列每行的cell 内容,比如Log1, Log2...; y轴就用第一行的cell
content (Sample1, Sample2 ...)，z就用下面表格里的数据。我想到用matplotlib，
但是又不太会用，想请教一下。
Measure＃ Sample1 Sample2 Sample3 Sample4 Sample5
Log1 2.3 3.3 4.5 5.6 6.7
Log2 3.5 6.7 10.0 22.1 30
Log3 4.2 4.5 6.7 8.9 9.1
Log4 4.5 8.9 10.2 11.8 14.7
import csv
from matplotlib import pyplot as plt
import pylab
import numpy as np
from mpl_toolkits.mplot3d import Axes3D
csv_file_path='/path/to/my/C... 阅读全帖 |
|
b*****7
发帖数: 31 | 33 请问Karatsuba algorithm analysis下面步骤是如何得出的？
3^logN => 3N^log3 |
|
c*******h
发帖数: 1096 | 34 3^logN = N^log3
具体见高一数学课本 |
|
h*u
发帖数: 9 | 35 建议你读读Falconer的“Fractal Geometry-...”（名字记不大清楚了）。
关于第1个问题：简单的说，Hausdorff维数是通过覆盖（covering）得出来的，packing
维数是通过填充（packing）得出来的。一个从外估计，一个从里估计。Bouligand维数的
定义偶记不得了:(
第2问：对于最基本的重复迭代系统，这3个维数是一样的，比如说Cantor三分集C的dim_F
(C)=dim_P(C)=dim_B(C)=log2/log3。这个结论出现在偶前面提到的那本书中。 |
|
x******g
发帖数: 318 | 36 a1,..an,b1,...,bn均为整数,且对于任意的i≠j,不存在整数k,使得ai^k=aj，且存在
一个i，logai(bi)为无理数
则：loga1(b1)+loga2(b2)+...+logan(bn)为无理数?
这个问题是模仿[b][url=http://218.1.231.240/iqbbs/dispbbs.asp?boardID=9&ID=151306]无理数的和还是无理
数?[/url][/b]提出的，但我并不能从直觉上把握它,问题的叙述仅仅是去掉了一些显
然的例外情况,可能还有一些显然的例外被漏掉.为了验证一下这个猜想的合理性，大
家不妨先考虑一个最简单的问题：证明或否定,log2(p)+log3(q) (其中至少有一个是
无理数)是无理数. |
|
c*********g
发帖数: 154 | 37 我的答案是
4×（2+3×（log3-log5））/ 5 = 0.3740
这是个双重积分问题。由对称性可知，只需算四种情况中的一种即可。
int(int(1/(5-x1))dx2)dx1
x1的积分区间是(0,2)，x2的积分区间是(x1,2)
把这个结果乘以4/5即可。 |
|
|
l*******r
发帖数: 39279 | 39 巴甫洛夫把妹法.
曾经有一位生物学人士，公布了工科把妹第一弹，暨“巴甫洛夫把妹法”：
每天给你那位心仪的女同事/女同学的抽屉里都放上精心准备的早餐，并且保持缄默不语
，无论她如何询问，都不要说话。
如此坚持一至两个月，当妹子已经对你每天的准时早餐习以为常时，突然停止送餐，她
心中一定会产生深深的疑惑及失落，同时会满怀兴趣与疑问找到你询问，这时再一鼓作
气将其拿下。
此法借鉴了不朽的生物学家巴甫洛夫之“条件反射试验”，故名“巴甫洛夫把妹法”。
薛定谔把妹法
薛定谔把妹法乃是建立在巴甫洛夫把妹法之上的威力加强版：
每天早上，你拿出一个硬币抛掷，让伟大的随机性来决定今天是否给妹子送早餐。
这样，当妹子每天打开抽屉之前，都不知道是否有早餐，而早餐的有无乃是一个**随机
**，完全无法推测。每天的早餐对于妹子都是一个未知的神秘存在，妹子将逐渐为这一
神秘的现象所吸引，最终将不可避免的对这个送餐人产生极大的兴趣，你在她的心中蒙
上了神秘的面纱。
这个谜一样的男子，这一刻薛定谔附体，带着量子论般深沉的哀愁，让她从此不能自拔
! )
总结：此帖将“早餐把妹”这样一个物理现象提升到了科学研究的领域，... 阅读全帖 |
|
