n*********r
发帖数: 24 | 1 上周面的，已杯具。有些题不记得了，说点记得的。
第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
long polling来把消息传给web。面得一般，不好也不是太坏。
第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
。这个是面的最差的，我觉得他大概都想把我给直接赶出去。
第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改正为
min heap... 阅读全帖 |
|
n*********r
发帖数: 24 | 2 上周面的，已杯具。有些题不记得了，说点记得的。
第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
long polling来把消息传给web。面得一般，不好也不是太坏。
第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
。这个是面的最差的，我觉得他大概都想把我给直接赶出去。
第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改正为
min heap... 阅读全帖 |
|
r*****s
发帖数: 74 | 3 有个想法，不知道对不对
假设共有n个数，要分到m个文件里面去。
A[] 有n个数需要shuffle
先随机分到m个文件中去
for int i : A
int d = random(1 to m)
put A[i] to file[d]
end
for i = 0: m - 1
shuffle file[i]
end
for i = 0:A.length - 1
int d = random(1 to m)
A[i] = pop the first number from file[m]
end
某个数分配到某一个文件的概率是1/m，它出现在这个文件某一个位置的概率是m/n，然
后大数列里某个位置抽到这个数的概率是大约是1/n？没具体算，拍脑袋乱算的概率…… |
|
s***y
发帖数: 10 | 4 我前几周做过，但是我是intern
第一题就是上边说到过的binary gap，要求logn, n是给的那个数
第二题是给一个integer array，找出所有可能even pair的个数，even pair就是两个
数相加的和是个偶数。要求O(n)。空间好像是1
我用的方法是scan一遍找出奇数和偶数的个数，然后N choose 2。但是factorial的时
候有可能overflow，我也不知道有什么好的方法来算factorial，所以最后就用了java
的BigInteger...
楼下已指出，直接两个数相乘就好了。数死早…… |
|
g*******n
发帖数: 214 | 5 可能有点confusing。第3步中，被删的个数是m个吧(避免和n混淆)。C(x,1)+C(length-
x,1)==m是这样来的：
比如有a个distance，那么就应该有a+1个顶点。包括min的所有distance的个数应该是
从min左边任意取一个顶点加上从min后边任意取一个顶点，其中length就是指a+1。这
样一来就可以和第2步被删掉的个数比较，从而找到x的值。min就应该是在结果数组中
的从一边开始没有被赋值过的第x-1个数。 |
|
g*******n
发帖数: 214 | 6 可能有点confusing。第3步中，被删的个数是m个吧(避免和n混淆)。C(x,1)+C(length-
x,1)==m是这样来的：
比如有a个distance，那么就应该有a+1个顶点。包括min的所有distance的个数应该是
从min左边任意取一个顶点加上从min后边任意取一个顶点，其中length就是指a+1。这
样一来就可以和第2步被删掉的个数比较，从而找到x的值。min就应该是在结果数组中
的从一边开始没有被赋值过的第x-1个数。 |
|
z***k
发帖数: 282 | 7 数学专业，在做面试题。有一个想法，某些地方跟上面某位大牛的类似。欢迎探讨。
一共n个点，C^n_2个数
1，找到最大的数，就是总长度，记为x(n)
2，按从小到大排列，a1,a2,...从a1开始，找到与之相加=x(n)的配对,记为（a1,b1)，
（a2,b2)...最多只取不同的六对，算上重复的，可能超过6对。
3, 两个最小ai，就是两头的两段。记任何一个为c1，另一个为cn-1。删除这两对，留
下4对（可能少于4对）不重复的（ai,bi)。从C^n_2这些数里面，减去a1,b1,a2,b2这四
个数，不要删重复的。为了减少下面的循环计算量。
4, 总长度x(n)减去c1,cn-1,就是去掉两头的剩下的总长度
5，用剩下的总长度，重复2,3,4
6，从第二次循环开始，加入一个判断。先得到c2,cn-2,然后判断哪个是c2，哪个是cn-
2。方法：（先解释下为啥上个循环要六对，为了这个循环里面，要判断c1,c2,cn-2,cn
-1的两两组合，一共是六个不同可能）。
首先从第三步剩下的配对的ai里，尝试找到c1+c2,c1+(cn-2), c2+(cn-1),(cn-1)+(cn-... 阅读全帖 |
|
w*******e
发帖数: 395 | 8 你这个太晦涩难懂了
不就是，先从左到右，用opt[i]记录b的个数
然后从右到左，数a的个数的同时，记录下来“左边（包括i）的b的个数”和“右边（
包括i）a的个数”之和的最小值
最后的结果就是那个最小值减去1吗？
b'
a'
and
right. |
|
D**********d
发帖数: 849 | 9 觉得可以直接计算而不用 blue force.
思路以例子说明:
assume: XXX123XX
1. 计算每位对 13 的余数，如 1%13 = 1, 10%13= 10, 100%13 = 9 ... etc.
2. 计算在高位余数 i = 0,...,12 时，XX 出现的余数为 3 的个数，e.g. XXX12300
余 0 时，XXX12300 -- XXX12399 间余数为 3 的数的个数是 99/13 = 7 ... 8, 所以
有 7 个。a_0 = 7
3. 利用 (1) 中结果计算 XXX123.. 高位 %13 余数 为 i = 0,...,12 的个数。设为 b
_i,
4. 总个数 \sum_0^{12} a_i * b_i |
|
a***s
发帖数: 206 | 10 你们以上的搜索都是brute force没有注意到数字的特殊性。
当 a + b = c 时而且a,b,c都是正整数，
a^2 + b^2 <= c^2 是永远成立的。
所以搜索的范围可以减小。只需要从两个数的和大于等于sqrt(k),并且两个数都比sqrt
(k)小，里面找就行了。在利用对称性又可以进一步减少搜索的范围。
edit:
另外如果k是偶数，两个数必须同时是奇数或偶数
如果k是奇数，两个数必须一个是奇数一个偶数 |
|
l*****f
发帖数: 2198 | 11 想了一个晚上想出一个简便的解法：
1. 扫一遍string，统计每个字符出现的个数。
2. 如果是true,那每个字符出现的个数必定相等。所以如有任何字符出现次数与其他的
次数不符，返回false
3. 假设每个字符出现个数都为n,则“可能”会有符合条件的pattern. 此种pattern的
长度为
(string length/n)*i, i = 1,2,3，假设这个数为k
4. 写一个loop，依次验证
string(0) = string (k) = string (2k).....
string(1) = string(k+1) = string(2k + 1)...
...
直到string(k-1) = string(2k - 1) ...
任何时候遇到false，则返回结果false,否则返回true
复杂度没估计过，应该不会很大 |
|
m*****n
发帖数: 2152 | 12 有个思路，不知道对不对啊？大家看看。
考虑如下情况，假设边界确定，数组分为3段
(a0....ai)(b0....bj)(c0...ck)
其中(b0...bj)是要flip的segment。
那么ai一定是1，否则，ai要并入b，同理b0一定是0，否则b0要并入a
同理bj是0，c0是1。
左边界的pattern一定是10，（起始点是0的情况，也算入）
右边界的pattern一定是01，（终点是0的情况，也算入）。
确定左边界的条件：
1. (a0...a（i-1） ) 中一定是1的个数大于0的个数，否则左边界可以推到a0。
2. 对于任意(a0...ax) 其中(x <= i-1)中1的个数与0的个数的差一定小于(a0...ai)，
否则左边界可以推到ax。
对于右边界的确定，类似。
对了特殊情况是确定的左边界比右边界更右。比如0000111111000，这种情况比较(0...
R)和(L...n-1)谁0更多吧。
所以O(n)就够了。 |
|
c**s
发帖数: 159 | 13 转载一个大家共勉。
由于之前Amazon已经发了offer，deadline也快到了，所以不管这次Google on-site结
果如何，都不想再继续折腾，Amazon or Google。求职季到此结束，所以，是时候写点
东西回报地里了。本人NYU-POLY，EE专业，作为一个转行的，感觉自己的求职之路还算
挺顺利，希望自己的经历经验能对各位尤其是非CS的各位有所帮助。
一。
感谢一亩三分地，mitbbs, 米群网（QQ群：320065698，可能满了，但是管理员会清理
，大家可以加加试试，另外米群网也是一个非常不错的求职平台，大家可以通过这个链
接去注册下http://www.meetqun.com/member.php?mod=register&x=12）提供的求职信息，内推信息及面经，当然也得感谢LeetCode和CC150。充分利用上述资源十分必要，而且感觉这些已经足够了。
二。
觉得有必要介绍下自己的准备情况，也算给大家涨点自信。
前面说了我是EE的，所学课程，包括本科的课，都没有什么和计算机相关的。去年暑假
决定开始自学CS，为了毕业好找工作，也就是那时候我才写出了自己第... 阅读全帖 |
|
s****7
发帖数: 156 | 14 面试是12月17号上午，然后提前看了一下版上的帖子。
酒店是高端大气没有免费wifi的Fitzpatrick，他家有在曼哈顿有两个分店，HR给我定
的是Manhattan Hotel：离公司比较近，走路五分钟，另一家是Grand central走路要十
五分钟（应该是第一个订满了就会安排到较远的那家）。WIFI要收费15刀，然后我用手
机上网作热点，开电脑刷了会题，看了点面经，着重看了下跟系统设计有关的题，还有
BB家高频的智力题（果然遇上了）。
在楼下碰到了两个同胞，上楼的时候就一路了。到了第六层等待接待我们的host HR，
然后发现大家都是西装笔挺（因为公司邮件写了Business professional，我之前没注
意扫了一眼以为是Business casual），然后我穿了件衬衫加V领毛衣，略慌。后来发现
面试官也都穿得很随意，一半就是polo或者休闲衬衫，据说之前有人穿牛仔裤也过了，
所以着装不是大问题，稍微正式一，大概有个衣领就可以了。
面试的地点是一个巨大的会议室，玻璃透明（Bloomberg 所有房间，除了厕所，都是透
明玻璃。），然后我坐在桌子的一端，面试官坐在两... 阅读全帖 |
|
u****w
发帖数: 4 | 15 我的思路
1. 按si排序整个区间。
2. 去除被包含的子区间，记录包含区间中含有子区间的个数。
3. 顺序扫描区间，用小堆维护之前出现的fj，如果堆顶元素小于si,则弹出，剩下的元
素是相交元素的个数 & si > sj.
4. 逆序扫描区间，用大堆维护之前出现的sj，同理得到相交的区间个数 & sj < si。
5. 把步骤2, 3, 4得到的结果相加，就是该区间的相交区间个数。 |
|
r*g
发帖数: 186 | 16 来自主题: JobHunting版 - 一道电面题 这样行不?
将数组排序为 a[0] <= a[1] <= ... <= a[K]
然后对第k步, 得到count[k], 这里count[k]是对于
1~N个数当中无法被a[0]~a[k]整除的数的个数
然后第k+1步: 需要扣掉count[k]中能被a[k+1]整除的数
的个数:
1. 如果a[k+1]是a[i](0<=i<=k)的倍数:不需要扣除:
因为不能被a[i]整除就一定不能被a[k+1]整除.
2. a[k+1]不是任何之前的数的倍数:
则变为寻找:
"能被a[k+1]整除的数, 但不能被a[0~k]整除"
这相当于寻找 1~N/a[k+1]中无法被a[0~k]整除的元素的个数
(也许可以利用count[k]来得到这个值, 而不用再算一次, 因为
这些元素分布是均匀的, 估计可以简单的乘除得到) |
|
b*****n
发帖数: 618 | 17 每d个数可以组成一个bucket，
比如d＝4，
那么
bucket［1］＝［1，2，3，4］
bucket［2］＝［5，6，7，8］
。。。
每个bucket最多只能有两个数存在否则就有duplicate，
另外除了要看每个数自己所在bucket之外还要看前边和后边相邻的两个。
用一个hashmap纪录bucket id跟每个数的对应关系。 |
|
p*********g
发帖数: 26 | 18 请问两个器材的距离定义？假设为|x0-x1|+|y0-y1|
1. 两个array，cntn[n], cntm[m], 把所有e个器材过一遍，之后cntn[i]记录所有在
col[i]的器材个数，cntm类似，O(e)。在此两个数组上计算lsum, lsum[i]为所有横坐
标<=i的器材个数，类似的再计算rsum, upsum和downsum.O(n+m)
2. 取第一个没有器材的点，比如m[i][j]，计算从该点到所有e个器材的距离之和 - O(
e)
3. 然后遍历所有没有器材的点，从左向右从上到下;向右遍历时之前的距离和dsum减去
所有位于右侧的器材个数(rsum[i] - cntn[i])*1，加上左侧和当前列的器材个数(lsum
[i])*1；由上至下类似。O(n*m)
返回#3中最小值。
各位大神走过路过还请轻拍 |
|
C******x
发帖数: 91 | 19 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。 |
|
发帖数: 1 | 20 叔我来了。
这道题的意思就是问
数组里面 有几个 大于等 "几" 的数。
[3, 0, 6, 1, 5]
比如说例子里， 就有3个 大于等于 3 的数
降序排列比较好懂
nums = [6, 5, 3, 1, 0]
index = [1, 2, 3, 4, 5]
有没有1个数 >= 1大啊？ 有 [6]
有没有2个数 >= 2 啊？有 [6, 5]
有没有3个数 >= 3啊？有 [6, 5 ,3]
有没有4个数 >= 4啊？没 只有2个[6, 5]
所以返回3.
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int i = 0;
int n = citations.length;
for (; i < n; i++) {
if (citations[n - 1 - i] >= i + 1) {
continue;
} else... 阅读全帖 |
|
j*****g
发帖数: 254 | 21 简答如下
递归时，已知[1,2,3,4,...Xn_1,] 求Xn
下个数一定是已知[1,2,3,4,...N-1,]中某个数 * 2/3/5中一个
而这个被乘数一定是最近一次被 2/3/5 乘的数递归后的下个数，否则可以证反
所以保持
a. 递归得到的[1,2,3,4,5,...]数列
b. 最近一次被 2/3/5 乘的数的序号
以便加速获得递归得到的[1,2,3,4,5,...Xn_1]数列下个数Xn
|
|
t*******r
发帖数: 22634 | 22 我现在想的就是你说的 subitizing 的问题。。。在超过
四个 item 之后，算术用的方法就是 count。。。count
其实是 sequential 的。。。
但是超过 subitizing 的四个 item 之后，除了使用 sequential
的 counting 之外，还有一条路，就是 spatial thinking。
当然，问题是在于，spatial thinking 对 counting 毫无用处，
对基本算术用处也不大。。。所以小学里会比较悲催。。。
spatial thinking 的原理，俺这个民科显然不懂。但是俺知道的
是，大脑对 “四个” 的限制，显然不会 item 个数，而是 spatial
symbol 的个数。。。比如 10 个 item 但是只有四种颜色，大脑
通常很快 subitizing 颜色的个数出来，跟 item 有 10 个关系
不大。。。
另外“个数”这个概念是被 counting 和算术所局限，其实
spatial symbol 可以是形状/大小/颜色等等等等属性。
所以我目前姑且认为 spatial thinking 时，大脑不... 阅读全帖 |
|
r*g
发帖数: 3159 | 23 啥是小学奥数？
前几天我看了个小学奥数的三十个知识点，纯粹是把娃学费掉的节奏：
1.和差倍问题
和差问题 和倍问题 差倍问题
已知条件 几个数的和与差 几个数的和与倍数 几个数的差与倍数
公式适用范围 已知两个数的和，差，倍数关系
公式 ①(和-差)÷2=较小数
较小数+差=较大数
和-较小数=较大数
。。。 |
|
t******l
发帖数: 10908 | 24 然后三角形有 M/LCM(k1, k2, k3) + M/LCM(k1, k2, k4) + ... (五个数里面所有选 3
个的组合。)
然后一个独立自主的五边形下面有 C(5,3) 个寄人篱下的的三角形，而一个独立自主的
四边形下面有 C(4,3) 个寄人篱下的的三角形。
而独立自主的多边形相互不重叠，俗话说就是已经正交化。所以简单相加就是所有寄人
篱下的三角形个数。
再两者相减就是独立自主的三角形个数。
然后 recursive down 到独立自主的一角形（独立自主的一个点）。
然后数奇戆，就是灭灯个数。没有被灭灯的就是亮着的。
数学上是 recursive 表达式。但这个是 recursive down 的就是了。
码字真他妈累。
：对于五个自然数的情况：
： |
|
s*****i
发帖数: 5548 | 25 ☆─────────────────────────────────────☆
meiguohuaren (Frostmourne hungers.) 于 (Fri Mar 1 17:41:20 2013, 美东) 提到:
发信人: stillwell (cgi), 信区: Military
标 题: 阳光灿烂的德州，欣欣向荣的Houston！
发信站: BBS 未名空间站 (Fri Mar 1 17:32:15 2013, 美东)
德州，全美第二大州，人口块2800多万，阳光灿烂，经济繁荣，人民生活稳定，老百姓
安居落业。
德州，洋名子叫Texas, 有全美第四大城市houston metro， 第五大城市Dallas-Fort
Worth， 第七大城市San Antonio，最漂亮很漂亮的城市Austin.
德州，好大学林立，学费便宜。什么Rice，UTA, UTD, A&M, SMU，TU等个个让中国人趋
之若大雁，幻想若菲菲。那里的中小学就更别说了，因为地产税高，学校普遍比较好，
让你乐不思海淀，美不言外滩。感叹不到德州不知道那里的学校好原来读书花钱还那么
少。... 阅读全帖 |
|
N*****N
发帖数: 1605 | 26 ☆─────────────────────────────────────☆
wuwei70 (无为无畏) 于 (Wed Mar 28 13:39:19 2007) 提到:
1、第一个答案是b的问题是哪一个？
（a）2；（b） 3；（c）4；（d）5；（e）6
2、唯一的连续两个具有相同答案的问题是：
（a）2，3；（b）3，4；（c）4，5；（d）5，6；（e）6，7；
3、本问题答案和哪一个问题的答案相同？
（a）1；（b）2；（c）4；（d）7；（e）6
4、答案是a的问题的个数是：
（a）0；（b）1；（c）2；（d）3；（e）4
5、本问题答案和哪一个问题的答案相同？
（a）10；（b）9；（c）8；（d）7；（e）6
6、答案是a的问题的个数和答案是什么的问题的个数相同？
（a）b；（b）c；（c）d；（d）e；（e）以上都不是
7、按照字母顺序，本问题的答案和下一个问题的答案相差几个字母？
（a）4；（b）3；（c）2；（d）1；（e）0。（注：a和b相差一个字母）
8、答案是元音字母的问题的个数是：
（a）2；（b）3；（c）4；（d）5；（e）6。（注：a |
|
w*****0
发帖数: 563 | 27 郁闷死了,都不知道偶的四年纪是怎么混过来的~~~
１、有一个数，除以7余2，除以8余4，除以９余３，这个数至少是多少？
２、５８２除以一个数所得的不完全商是11，并且除数与余数的差是6，除数、余数各
是多少？
３、63285与70352的积被７除，余数是多少？
４、阳历1992年1月1日是星期三，阳历2004年1月1日是星期几？
５、甲、乙、丙、丁四个小朋友玩报数游戏，从１起按下面顺序进行：甲报1、乙报2、
丙报３、丁报４、丙报５、乙报６、甲报７、乙报８、丙报９……这样，报2003这个数
的是谁？
６、节日的街上挂起了长长的一排彩灯，共有2013盏，从第1盏开始，按照５盏红灯，
４盏黄灯，３盏蓝灯，２盏绿灯，不断地排下去。问：（1）第１９８２盏灯是什么颜
色？（2）蓝灯共有多少盏？
７、两个数相除商５余３，如果被除数、除数都扩大到原来的２倍，则被除数、除数、
商、余数之和为101，求原来的被除数和除数？
８、有一类自然数，其中每个数与３的和都是５的倍数，与４的差都是７的倍数，这类
自然数中最小是多少？
９、50以内被５除余２，被６除余５的数是什么？ |
|
h*****0
发帖数: 4889 | 28 来自主题: BrainTeaser版 - 被9整除. 我FT！你没认真看我的证明。三个都能被三整除的数，在除以3之后的各还能被三整除
，则原来的和能被9整除。
要从17个数里抽出5个三数组，每次抽时必须有5个数，17－4×3＝5,即最后一次恰剩5
个数，如果只有16个数，则最后一次不成立。
我的证明很严密。 |
|
r****y
发帖数: 26819 | 29 重新考虑一下，sum说能确定product不能判断以后，他们都知道的事实是：
(1)和为奇数，(2)和不是两个质数之和，(3)和必然小于55（如果和大于等于55，
则其中一个数可以是质数53，而2X53>100，则两数可判断）。满足这三个条件的奇数有
：11，17，23，27，29，35，37，41，47，51，53。从前两句对话中，product和sum都
已知：和必然在11个数中。
接下来，我们首先排除不可能的和，这是站在sum的角度做。sum根据他已知的和，推理：
如果对一个和A，存在两种拆分方式A=B+C=D+E，而BxC和DxE的其它所有可能的
因子组合方式MxN都不能使得M+N属于这11个奇数，那么product就能确定两数，而sum却
无法在最后判断他拿到的是B+C还是D+E。那么这个和就不可能。
简单特例情况是，如果和有两种方式写成2的幂加上一个质数，则sum无法在最后一句对
话说他能确定两数。例如，sum拿到和51，因为product可能拿到4x47或者8x43，这两种
情况下product都能确定两数，但sum没法在最后判断他拿到的是4+47还是8+43。以此排
除... 阅读全帖 |
|
L*****e
发帖数: 8347 | 30 不过我觉得国家宝藏的难度其实没有感觉的那么大，虽然1380个数看上去很多，但是很
大部分数可以被立刻排除，如果除了7个质数和宝藏坐标点外的1372个数完全随机的话
，一半偶数可以立刻被排除掉，5结尾的数也可以排除掉，然后会有相当一部分以1，3
，7，9结尾的可以立刻判断出来。估计最后也就百来个需要较复杂计算判断的。
后来孟非给他一个四位数，他大概用十来秒判断，Dr魏观察他用17分钟算完数字墙，17
* 6 = 102，这和我的判断基本相符。
所谓第八个质数带来的干扰也没那么严重，如果只找到6个质数，他要去一千或者至少
好几百个数中去找漏网之鱼，但是多了个质数，只需要验证另外7个是否肯定是质数。
如果最后确认有8个质数，那么坐标点必为其中一个质数。把8个质数两两连线，看哪个
点是在另外连线的垂直相交点上就是了。。。
所以真正的难度只是在一百来个数中演算是否是质数。。。
我是没明白他说他早在17分钟的时候就找到8个质数，但是验算三遍又用了20分钟。他
只需要验证找出的8个中有没有误选的就是了，怎么会用那么长时间验算？
★ 发自iPhone App: ChineseWeb 8.2.2
★ ... 阅读全帖 |
|
l*3
发帖数: 2279 | 31 好的, 既然你认为这个正确, 那么请看31楼的证明:
-------
反证法：
假设只有n个素数，a1,a2,a3,...an
那么a1*a2*a3*...*an+1这个数被所有的素数除都除不尽，还余1，这个数也只能是素数
，所以矛盾了。
-------
"a1*a2*a3*...*an+1这个数被所有的素数除都除不尽，还余1，这个数也只能是素数"
这个断言, 是不是根据 "你认为的我唯一完全正确的这句话" 来得出的?
根据定义, a1*a2*a3*...*an+1 是大于1的自然数, 并且不能被任何小于它本身的素数
(按照假设, 任何素数都在a1,a2,...,an中) 整除, 那么他是不是素数?
所以请问, 该证明哪里 "不完备"? |
|
K**********i
发帖数: 22099 | 32 首先声明哥是文科生，所以后面跟帖“你文科生？”的就不要废话了。
不就是个破素数么，用计算机呗！
别看哥是文科的，但是在清华时还是学过C语言C++的，素数太大Int肯定存不下，对吧？
于是只能用BigInt类。用数组也行，链表也行，反正能存非常大的数就行，我记得我们
当时大一期末考试上机题就是这道题，写一个BigInt，实现加减乘除就行，不需要开方
什么的。
然后从1开始，挨个测试就是，看哪个能整除就不是素数，对吧？
然后找到一个“非常大”的素数，或许4G内存就存这一个BigInt就冒了，公布出来，号
称老子找到了一个非常大的素数。
然后问那些人：你们觉得这个数，是不是够大了？
如果那些人承认素数无穷多，证明完毕；
如果不承认，继续找，找下一个素数，找到了再问他，素数无限多否？不服继续找，直
到服了为止。
理论上讲，计算机可以无限运行，人的寿命有限，总有一天他服了：“求求你啦！别算
了，我承认素数无穷多还不行么！！！”
于是证明完毕。
当然你可能说这太慢了，无妨，我听薛师兄说现在都用并行计算，一个数是不是素数可
以用背后1万台计算机，第一台算1到（这个数除以一万），第二台算（这个数除以一... 阅读全帖 |
|
P****D
发帖数: 11146 | 33 http://www.guokr.com/post/67116/
数学系有三个班（内含各种加强版）
李子李子短信 国际关系硕士生 发表于 2011-10-12 16:26:46
原版
-----------------
数学系一共3个班。今天他对我说，你是3班的么？我说，原来你是2班的啊！他说，原来
你是1班啊！
内涵版
-----------------
数学系一共3个班。今天他对我说，你是3班的么？我说，我终于知道你是几班的了。他说
，我也知道你是几班的了。
反推版
-----------------
今天他对我说，你是2班的么？我说，我终于知道你是几班的了。他说，我也知道你是几
班的了。问一共几个班？
中微子版
-----------------
数学系一共3个班。他说，原来你是1班的啊？我说，我不跟超过光速的人说话。今天他对
我说，你是3班的么？
我就是认不全你咬我啊版
-----------------
数学系有3个班，甲： 你是3班的吗？乙： 啊，原来你是2班的。甲： 错了，我是3班的
。乙：……
数学黑版
-----------------
数学系的应该是这样：... 阅读全帖 |
|
m**n
发帖数: 9010 | 34 所谓"判他们错了", 是个完全无所谓的事.
"错", 就是说, 你做的与我们现在教的不一样. 仅此而已.
在这事上老师说"错", 与说"咱们教的该是这样理解, 与你写的看起来不同",
是一回事. 明白的老师会说明白, 不明白的老师说不明白. 这是老师自己的问题.
这种"现在做题要求使用当前方法, 用其他方法做不符合要求,
会算错", 不是教学中常见的事?
另外, 你说的"要强调的就是总数等于组的个数乘以每个组的成员个数",
你还是在忽略问题: 问题是(咱不管是不是"核心问题"),
你为什么不说"总数等于每个组的成员个数乘以组的个数"?
你如果只按一种方式说, 很多孩子就是会严格按照你给的顺序理解.
你如果两种说法都说, 一些孩子就会混淆.
这里怎么可能不扯交换的问题
所以只有两种教法, 一种就是现在这样, 按顺序教, 告诉大家我们这样定义乘法.
然后再讲顺序交换后, 结果是一样的. 过了这个阶段, 不再强调顺序问题.
另一种, 就是, 我根本不提顺序, 两种说法随便说, 三组人, 每组5个,
我有时候写3x5, 有时候写5x3. 或者, 我自己只写3x5, 但孩子愿意写
什么我不管.
... 阅读全帖 |
|
c****t
发帖数: 19049 | 35 ☆─────────────────────────────────────☆
casact (尝尝也) 于 (Tue Jul 5 01:17:00 2011, 美东) 提到:
第一章 被驱逐的高手
更新时间 2011-2-28 15:15:57 字数：4023
“卡卡卡，嗒嗒……”
一双灵巧的手飞舞着操纵着键盘和鼠标，富有节奏的敲击声仿佛是一首轻快的乐
章。屏幕上漫天的光华闪过，对手飞扬着血花倒了下去。
“呵呵。”叶秋笑了笑，抬手取下了衔在嘴角的烟头。银白的烟灰已经结成了长
长一串，但在叶秋挥舞着鼠标敲打着键盘施展操作的过程中却没有被震落分毫。摘下的
烟头很快被掐灭在了桌上的一个形状古怪的烟灰缸里，叶秋的手飞快地回到了键盘，正
准备对对手说点什么，房门却突得咣一声被人打开了。
叶秋没有回头，像是早就在等着这一刻一样，只是问了一句：“来了？”
“来了。”苏沐橙的回答也同样简单。
“那就走吧！”叶秋拒绝了对手又一次的邀战，轻轻地从网游荣耀专用的登录器
上摘下了一张卡片，起身来到门旁衣架顺手取下了外套。
夜已... 阅读全帖 |
|
f****8
发帖数: 33 | 36 楼上的算法复杂度为O(M^2*N^2).
下面给出O(M*N)的算法，以及实现。
第一步，先扫描各行各列，找出每一列1的个数，然后将每列1的个数及列号按个数从大
到小排列到
一个LIST中，且直接忽略1的个数小于50的列号；O(M*N)+O(MlogM)，其中N为行数，M为
列数。
第二步，根据第一步扫描的结果，创建 FP－tree（Frequency Pattern tree)。创建方
法如下：树中每个节点包括column-index,出现次数，worst复杂度O(M*N).
第三步，统计结果，就是遍历树的过程，有一些技巧，worst复杂度为O(M^2).
因为N》M，所以整体worst复杂度：O(M*N).
本人冬季刚计算机工程专业硕士毕业，之前在国内有一定工作经历，JAVA C++ WEB DB
都做过一些。找湾区码农工作，prefer涉及BIG DATA和MACHINE LEARNING相关的工作，
求内推：f****[email protected]，万分感激！ |
|
n**d
发帖数: 112 | 37 要求是输入n个数 利用归并排序(MergeSort)来排序 同时计算元素的重复次数（重复的
只保留一个）
例子：
输入是
8
1
1
1
2
2
5
2
1
输出就是
3
1 4
2 3
5 1
8和3是输入输出数组的个数，输出的4 3 1是重复个数
老师给了个提示：
每一个输入值应该关联一个重复值。归并的时候，要在两个序列的现有数值中检查==条
件，以确定重复数的个数。 |
|
w***g
发帖数: 5958 | 38 假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
1或63.
举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
这样就可以递归了
f(N, k) {
if (k == 0) return N;
b = N >> k; // 最高为是0或者1
N' = N - b * (1 << k);
return b * (k * (1 << k-1) // 整的
+ N' + 1) + f(N', k-1); // 零的 // hatemaths指出错误，已改正
}
一共递归k次，k=log N,... 阅读全帖 |
|
P********e
发帖数: 2610 | 39 better than 0(logN), contest的解法。
假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
1或63.
举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
这样就可以递归了
f(N, k) {
if (k == 0) return N;
b = N >> k; // 最高为是0或者1
N' = N - b * (1 << k);
return b * k * (1 << k) // 整的
+ N' + 1 + f(N', k-1); // 零的
} |
|
n****1
发帖数: 1136 | 40 楼主没明白type inference的在fp里的必要性。 事实是如果没有type inference, FP
寸步难行
C/Java系列的写个声明是有必要是因为:
1. 类型相对静态， 变量总个数>>类型总个数
2. 同一变量跨度相对比较大， 尤其是很多上千行的程序， 变量声明都在第一页， 然
后分布在各个角落里， 没有声明是不行的。
FP风格恰好相反：因为函数是first class citizen, 所以类型的数量成指数型增长，
需要表达该类型的声明也越来越长。 而在整个程序中， 可能只有一个常量是这种类型
。 也就是说常量总个数～=类型总个数。 如果每定义一个常量都写个声明， 那声明会
远远长过代码本身。
还有就是FP里用到了type inference的常量一般是局部值，跨度很少超过5行的。 这样
的不写声明也不会难以理解， 写的话反而叫滥用生命。
C++的auto的却有争议， auto最好只用来表达const auto或者iterator这些容易推理的
值。 |
|
g****s
发帖数: 1755 | 41 班门弄斧一下。
我的思路是可以在Linear时间内解决，先假定有N个Array，而且在每个Array中没有重
复的元素；
1. 做一个Hashmap，以Array[i]为Key，以该array[i]数值在全部N个Array中出现的次
数为Value；再做一个OutArray。
2. 从0到N-1遍历每个Array的每个数值，如果Hashmap里有这个数，则把
修正为.如果表里没这个数值，直接存。
3. 全部Array的全部元素都遍历结束后，任取一个Array0，就取第一个吧，遍历此
Array0，如果某个值array0[j],对应在hashmap里的Value是N-1的话，就说明这个数在
每个Array里都出现过，把这个数存到最终输出的数组OutArray里。
4. 输出OutArray；
=========
以下为简化的思路，无论单个数组里有无重复都可以用。
同样假定N个数组，同样初始化HashMap和OutArray；
1. 先把Array0里的数值放到HashMap里，Value全部设为1；
2. 从1到N-2遍... 阅读全帖 |
|
h****y
发帖数: 61 | 42 版上有人用过那个FFTPACK（by Hugh C. Pumphrey）？
这里面FFT变换后得到的fourier transform的系数究竟是怎么对应的？
看了doc 文件，并和解析结果比较，对1D 的情况好像是这样的： 第一个数为fourier
transform 的常数项,即n=0的项；第2个数对应n=1项的实部，第3个数对应n=1项的虚部
，第3个数对应n=2的实部，第四个数对应n=2的虚部 ...
可是对于2D、3D的情况死活对应不了 :-( |
|
j**u
发帖数: 6059 | 43 ☆─────────────────────────────────────☆
cityhawk (呆鹰) 于 (Mon May 23 20:38:14 2011, 美东) 提到:
Matlab程序是 for 嵌套循环：比如，
a=0.1:0.5 with spacing 0.01; b=0.1:0.6 with spacing 0.01
c=0.1:0.8 with spacing 0.01; d=0.1:0.6 with spacing 0.01
e=0.1:0.9 with spacing 0.01; f=0.1:0.7 with spacing 0.01
g=0.1:0.6 with spacing 0.01; h=0.1:0.5 with spacing 0.01
执行部分
end; end; end; end;end; end; end; end;
这个程序在普通的PC 3.6GHz, 2GB内存上运行要2个星期多，把它放在系里的服务器上
运行，结果比我们lab的这个PC还慢，网管告诉我系里服务器的单个CPU才1.8GHz，尽管
我们有近30个CPU并行和全部 2... 阅读全帖 |
|
m******8
发帖数: 5 | 44 【 以下文字转载自 Statistics 讨论区 】
发信人: meth2008 (meth), 信区: Statistics
标 题: 问个几率问题，谢谢。
发信站: BBS 未名空间站 (Fri Jan 5 21:35:51 2007)
10个数字，从中任意取两个，条件是第一个数不能比第二个数大，请问有多少种情况。
答案是1/55，请问是如何得到的？谢谢了。
10个数字，从中任意取两个，不允许重复，10*9
10个数字，从中任意取两个，不允许重复，而且第一个数不能比第二个数大，请问有多
少种情况？答案1/45，如何得到的？谢谢了。
93中选8，第一个数不能比第二个数大，结果1/186087894300
100中选8，不允许重复且第一个数不能比第二个数大，结果1/186087894300
求计算方法，谢谢。 |
|
m****d
发帖数: 12 | 45 观察：
5^3=25+25+25+25+25=21+13+25+27+29
4^3=16+16+16+16=11+13+15+17
归纳：
a^n=a^(n-1)+a^(n-1)+...+a^(n-1)有a个a^(n-1).
则，我们上面等式的右边分为对称的两个部分。
把左边第一个部分的最后一个数减2加到右边第二个部分的第一个数上。左边第一部分
的倒数第二个数减去4加到右边第二部分的第二个数上......以此类推。
定理得证。
似乎可以得到一个有趣的推广是发现怎么样可以象用a^2=1+3+...一样的方法来发现有
什么数可以满足a^3+b^3=c^3和a^4+b^4=c^4等等。
因为，按照上面的公式，c^3是c^2左右对称的c个数，而a^3和b^3是同样的。因此，如
果a^2和b^2的左边、右边和中间的数都被占据，并且占据的数目正好等于整个数列中间
那个数的平方的话。那么上面的3次方等式就成立了。因此，三次方等式的问题，被划
归为2次方的问题。
（具体的数学表达我不熟悉，写不出来） |
|
t*u
发帖数: 159 | 46 看了上面的解法，有了简单的求解过程：
(I)
7个数2-8之和为35，其中4个之和为27，或18。所以剩下
3个之和为8或17。但3个之和至少为9（2＋3＋4），
所以3个之和＝17，4个之和＝18。
(1) 梦 + 想 + 成 + 真 = 18
(2) 奥+运+会 = 17
(II) 下面的竖式显然成立
奥运会0
- 奥运会
————————
梦想成真
观察这个竖式可以知道，因为 奥/=梦
(3) 奥=梦+1
如果 运>奥 则这个竖式在百位上做减法时，永远不会形成借位，同时注意到式(3
)成立，有
(4) 奥>运 且两个数不相邻
(5) 会+真=10，会/=真/=5
(III)
2-8这7个数，和为18只有以下四种可能性， 相应的，另外3个数为（不考虑其对应关系）
梦 + 想 + 成 + 真 奥+运+会
(a) 2367 |
|
h**********c
发帖数: 4120 | 47 六角幻方
本世纪初，有一个叫阿当斯的青年，他热心填六角形的幻方。就是在六角形的7个点上
，填上1至7七个数，使每条直线上的2个或3个数和相等。
经过47年的努力，还没有得到成功。原来这样的幻方是不可能存在的。如图二所示，若
a＋6＝b＋c，则a＝c,但是幻方的要求是所填的数不能相同。
不过，他经过这么多年挫折后，终于用毕生精力排出了一个两层六角幻方。
填法：在图三所示的六角幻方中，共有两层，19个点，要求在各点上填上1至19各数，
使每条线上的各数和相日二等，等于38。这个幻方叫你来填当然很难。不过，我们可以
先给出内层7个数，你来补充其他12个数，也许就不困难了。
http://www.aoshu.com/200412/492fcb4bb7b25.shtml |
|
h**********c
发帖数: 4120 | 48 http://baike.baidu.com/view/1846704.htm
17秒! how can it be possible?
六角幻方 1910年，一位名叫阿当斯的铁路公司阅览室青年职员，对六角幻方很感兴
趣.他知道一层六角幻方(把1到7这7个数填入如图1所示的圆圈内，使得任一条直线上
的数字之和都等于同一个数)根本不存在，因而把注意力集中在由19个数组成的两
层六角幻方上.他一有空闲时间，便在纸上或地上画两层六角图（如图 2），再把
19块上面写有1到19这19个数的硬纸板在图上摆来摆去.就这样，一天又一天，一年
又一年,漫漫的47个春秋过去了，这时的阿当斯已不再是当年英俊潇洒的小伙子
，无情的岁月，使他成了两鬓斑白的老人.面对无数次的失败与挫折，阿当斯的兴
趣依然不减.
“皇天不负苦心人”，1957年的一天，患病在床的阿当斯终于排列成功了.他惊喜
万分，连忙找纸把它记录下来，不幸的是，当他病愈出院回到家中时，却发现那张记录
六角幻方的纸竟然不见了！阿当斯并不因此灰心丧气，恰恰相反，他又奋斗了5年.终于
在1962年12月的一天，重新找到了那个丢失的图形.这个图形有个奇 |
|
z****t
发帖数: 58 | 49 不会就从简单开始，比如 k=1，n=2,N=3
她在1，2，3这三个数中，选取了一个。 现在他通过提问，来获得关于这个数的信息。
每个问题是这样的，在1，2，3中选取一个数或者两个数或者三个数，问她：“你选的
那个数在我选取的数中吗？她回答”是“或者”否“。
他可以随便问多少次 ，她可以撒谎，但是不得连续撒谎两次。
请问，他应该怎样提问，可以把她选定的那个数的范围确定为 1，2，3中的两个，也就
是说，可以排除1，2，3中的一个?
只要排除一个就行
只要提问3次就可以搞定！ 怎样提这3个问题呢？
第一次问：是 1 吗？若回答：是
第2次问：是 1，2 吗？就结束了
若第一次回答：否
第二次问：是 1 吗？若回答：否， 就结束了。
若第二次回答：是
第3次问：是 1，2 吗？也结束了
第一小题倒是不难，第2小题…… |
|
