s*********s
发帖数: 5 | 1 O(logN)算法，递归深度logN，但是每次递归的复杂度O(1)
思路是将f(XXX) 递归转化为 多个f(XX)，需要处理一些特殊情况
因为有重叠子结构，用memory记录一下，避免重复DFS，引入了DP的一些东西
int num5Impl(int num, unordered_map &memory)
{
if(num < 5)
return 0;
if(num <= 10)
return 1;
if(memory.find(num) != memory.end())
return memory[num];
int unit = 10;
while(num/unit >= 10)
{
unit *= 10;
}
int primeVal = num/unit;
int ret = 0;
if(primeVal > 5)
{
ret = (primeVal-1)*num5Impl(unit-1, ... 阅读全帖 |
|
p**o
发帖数: 3409 | 2 我11楼那个方法，“后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5”，
从most significant digit开始递归，保证输出有序，
所以容易根据给定的最大值终止生成器。
此前我的思路是从个位数往高位开始左移递归：
“前n位含5 当且仅当 第n位是5 或 前n-1位含5”。
这种方法的缺陷是：结果无序，所以不方便根据给出的最大值跳出生成器。
DIGIDS_NO5 = (0,1,2,3,4,6,7,8,9)
# Generate all k-digit (1<=k<=n) numbers without digit 5
def genno5 (n):
if n == 1: yield from DIGIDS_NO5
else:
for x in genno5(n-1):
for y in DIGIDS_NO5:
yield 10 * y + x
# Generate all k-digit (1<=k<=n) numbers with digit 5
def gen5 (n):
... 阅读全帖 |
|
s*********s
发帖数: 5 | 3 O(logN)算法，递归深度logN，但是每次递归的复杂度O(1)
思路是将f(XXX) 递归转化为 多个f(XX)，需要处理一些特殊情况
因为有重叠子结构，用memory记录一下，避免重复DFS，引入了DP的一些东西
int num5Impl(int num, unordered_map &memory)
{
if(num < 5)
return 0;
if(num <= 10)
return 1;
if(memory.find(num) != memory.end())
return memory[num];
int unit = 10;
while(num/unit >= 10)
{
unit *= 10;
}
int primeVal = num/unit;
int ret = 0;
if(primeVal > 5)
{
ret = (primeVal-1)*num5Impl(unit-1, ... 阅读全帖 |
|
x****h
发帖数: 3 | 4 EE MS毕业，面的是2014 New Grad，非常非常感谢版上大牛的内推，机会难得，很遗憾
最后没有拿到Offer。
Phone Intervew：
1. Palindrome String (LeetCode)
2. Sum3 (LeetCode)
3. Letter Combinations of a Phone Number (LeetCode)
因为都是熟题，电面非常顺利，Sum3还给了排序和HashTable两种解法，当天就通知了
Onsite。
Onsite Interview：
一共三轮，每轮45分钟，因为是Master所以没有System Design：
1. 半轮Culture Fit的问题，另外一道Coding，Sort List (LeetCode)，要求In Place
，递归的解法要用到Call Stack，讨论了一下没想到更优化的方法，就写了递归Merge
的解法。
2. 两道Coding题目，一道可以化为普通的Binary Search，另外一道是Anagrams (
LeetCode)，都很快搞定，之后剩下将近20分钟就让我提问题了，随便聊了一下感觉... 阅读全帖 |
|
w****3
发帖数: 110 | 5 自己实现stack和递归的复杂度也是一样，不需要每一位都递归，只要碰到？的时候
copy一份递归就可以
或者计算出？的个数m算m^2的全排列再还原原来的数，复杂度也是一样的 |
|
h**t
发帖数: 54 | 6 我面试回来了，上来更新下，顺便感觉诸位。
同事对我倒是信任的，我们主要就讨论了公司的发展方向，他需要让我做的东西，我想
做的东西，等等。
他的合伙人，以及他们的现任同事，就是按正常的面试，一对一来的。工作中用到的东
西，我答得八九不离十。其它的，有些我没复习到，觉得自己不给力。另外，他们的确
要求我做presentation了，这个我准备了，没出差错。
我去面试前，他们给了我个计时的编程测试。因为是工作中用到的，我做得还可以。面
试当天，他们又弄了不少现场编程，还有几个复杂的递归。我递归那部分不给力，在面
试人的大力帮助下，才得以完成。简单的递归我会，但工作中从来用不到，我就没花精
力去啃这一块。
总而言之，面试难度不算大，但我没有好好准备，有些方面有点差强人意。不过，我还
是收到了offer，但比现在的package低了好多。不知道他们是碍于同事的面子不想直接
据我，还是他们觉得我就值这么多，还是想跟我玩讨价还价的游戏。 |
|
I*****x
发帖数: 84 | 7 虽然递归可以做，但是我觉得没有必要用递归做吧，用递归有点浪费时间了说实话，我
觉得用两次for loop就好了，大家还有什么更好的解法嘛 |
|
c*******r
发帖数: 610 | 8 谢谢。
以下是解释：
2. 三哥： Given a binary tree, how would you decide whether it is a unary
tree. i.e., the tree contains the same values
Follow-up. Given a binary tree, how would you find out the number of
distinct unary subtrees.
Example:
1
1 1
2 1 1
return 5.
什么是unary tree？按第一小问感觉是元素不能重复？
不是，意思就是树的节点包含的值全部一样
后面又如何定义unary subtree
可以找到以下5个unary subtree
a） 2
b）1
c）1
d）
1
1 1
e）
1
1
1 1
第二题： print factors of a give... 阅读全帖 |
|
H**********5
发帖数: 2012 | 9 打算把CC150，LEETCODE，以及板上的面试题全部搜集起来（个人定期会搜集），
然后系统化的刷题，代码的详细实现（每题分别在VC和eclipse下调试通过的C++和JAVA
版本）纸质手抄版。
初步进行了分类如下：
1 串操作
2 排序
3 查找
4 链表
5 树
6 BFS
7 DFS
8 递归
9 动态规划
10 贪心
11 数学运算
12 嵌入式底层
有没有高人看看本人的章节分类有没有问题，帮忙指点下，比如常见的面试题链表的倒
置递归实现，此题既可以归到链表章节，又可以归到递归章节。
DFS和BFS似乎何可以合成一章（根据面试题量）。
另外本人打算把长期的面试题目总结下来，形成文档，可以和版友相互讨论。谢谢。 |
|
m*********a
发帖数: 3299 | 10 第一题是用递归么？
#include
#include
typedef struct output_string{
char string[20];
struct output_string *next; }output_string;
void stringCopy(char *str_source,char *str_dest,int no_char){
while (no_char--) *str_dest++=*str_source++;
}
void allString(char *str,output_string *output,int char_position){
output_string *tmp;
while ((*str!='?')&(*str!='\0'))
output->string[char_position++]=*str++;
if (*str=='\0') {output->string[char_position]='\0';return;... 阅读全帖 |
|
h***s
发帖数: 45 | 11 不同深度考 Binary Tree Traversal
1. 递归
2. 非递归，用栈
3. 非递归，不用栈, O(1) 空间 (Morris Traversal) |
|
k*******n
发帖数: 16 | 12 adpu中的一家，就不说是哪家了。
题目大概就是用pattern p匹配字符串s。已知如下
p="abba", s="red blue blue red", true
p="aaaa", s="red red red red", true
p="abab", s="red blue blue red", false
p="abba", s="red red red red", false
然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
做题，还算顺利，做完以后问了复杂度。
以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行
，然后面试官让说说递归怎么做于是感到面试官应该希望听到递归的解法，于是就说
partition s呗，前一半跟p的前n-1个字母match，后一半跟第一问一样的检查是否可行
。面试官让写code，写啊写，写啊写，匹配的那个map的回溯总是写不对（不回溯空间
岂不爆掉了？），到最后看到面试官把错误的版本copy下... 阅读全帖 |
|
k*******n
发帖数: 16 | 13 adpu中的一家，就不说是哪家了。
题目大概就是用pattern p匹配字符串s。已知如下
p="abba", s="red blue blue red", true
p="aaaa", s="red red red red", true
p="abab", s="red blue blue red", false
p="abba", s="red red red red", false
然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
做题，还算顺利，做完以后问了复杂度。
以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行
，然后面试官让说说递归怎么做于是感到面试官应该希望听到递归的解法，于是就说
partition s呗，前一半跟p的前n-1个字母match，后一半跟第一问一样的检查是否可行
。面试官让写code，写啊写，写啊写，匹配的那个map的回溯总是写不对（不回溯空间
岂不爆掉了？），到最后看到面试官把错误的版本copy下... 阅读全帖 |
|
r****7
发帖数: 2282 | 14 这种题你要想的太细就没法做了
不用分解质因数，直接dfs，遇到能整除的把整除之后的结果继续递归，不过要排序去
重，所以要把当前的被除数带入到递归中，然后下一层递归的被除数要大于等于这个传
入的数
. |
|
t****o
发帖数: 94 | 15 12月/1月把FLG面了一轮，都没offer，本来懒得写面经，看到大家讨论年老色衰的程序
员，深有感触，还是写下来吧。coding题目什么的就不具体说了，准备得比较充分的都
没问题。
我在M家做了9年多，后面6年多做一线经理。每天算活少话多，主要在大叔圈子里面混
，pay还算OK吧。三个月前reorg，虽然没什么影响，觉得还是可以试试外面的机会。大
概把leetcode刷了一遍（以前做过一遍），就开始了。三家面试历经下来感觉很不一样
。基本FLG都帮我看了manager的职位，但是都说没有合适的，都是先做enginner，我很
多年没有面engineer了，试试也不错。
F：最早是看到好几个熟人（都是M家的principal lead）都跳去F家做engineer，想想
自己也可以试试，就最早联系了他们家。F家特点是简洁明快，说准备好了就来，
recruiter还发了leetcode的题和答案帮助复习，算很人性化。第一轮可以选电面或者
onsite，我选onsite，不算很容易地过了。然后就是正常的四轮面试，一轮45min，抛
去前后聊天，大概也就30min写两道题。coding基本都... 阅读全帖 |
|
L****c
发帖数: 209 | 16 回馈本班，发FB面经。
前段时间面的，无奈一直没空整理。想想应该还不算太旧，就写在这里，希望能帮到一
些人。祝大家都拿到心仪的offer。
1. Leetcode原题，three sum的变种, 允许3个数字重复，就是起始位置一样就行
2. 给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问了不递归怎
么做
3. f家面筋出现很多次的小偷偷钱题，用DP，要求不相邻的数的和最大
4. 给一个tree，用递归变成一个circular doubly linked list
5. 还是f家面筋出现很多次的read4K那题 |
|
n******n
发帖数: 12088 | 17 你说的那是递归。归并排序可以不用递归，关键步骤是由小变大。递归的作用无非是划
分数据比较自然。 |
|
y*****e
发帖数: 712 | 18 第一题是print all path from root to leaf
比如tree是
A
B C
print AB, AC
这题用DFS还蛮好做的，如果用stack怎么做呢？
第二题有点像，给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问
了不递归怎么做
这题也是dfs好做，如果不递归的难点在于，每个treenode需要记录他的左子树的和，
右子书的和，再减去自己的node val. 一个stack好像不够，我是用了一个hashmap记录
每个node对应的左右子树的和，再用一个stack做post order traversal, 感觉挺麻烦
的，不知有什么巧妙的办法吗？
谢谢大家帮忙！ |
|
a********5
发帖数: 1631 | 19 【 以下文字转载自 Working 讨论区 】
发信人: lidichen (火木年华), 信区: Working
标 题: 吐槽个烙印面试官
发信站: BBS 未名空间站 (Sat Aug 29 12:01:10 2015, 美东)
昨天面试，遇到一个烙印是我见过的最奇葩的烙印。
让我解释我做什么，我说我implement model，这货一直让我解释什么叫implement。
啥问题也没准备，估计就自己网上看了一些面试题，但是自己也不知道怎么做，然后随
机的问。
写个翻转二叉树，我做出来了，他看不懂递归是啥。我交换两个node用了中间变量，他
看不懂这三行代码，我都觉得无语。
完事儿了又让我写一个二叉树路径sum，又看不懂递归，看不懂 return a == b，问我
这是啥意思。
怎么删除单链表中某个节点，如果只有这个节点的reference，我答把下一个节点以后
的值依次往前挪动一个。另外这货听不懂我问是不是要整个object移动还是只是value
就可以了，说反正你只要work就行，我不懂你的问题。
他见难不倒我，又问怎么sort一个大文件，还没说，他又说，你还是写删除单链... 阅读全帖 |
|
d******o
发帖数: 13 | 20 Stack + 递归
之前面Twitter也被问到过，但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext（） 和 next（）
hasNext 检查还有没有值，检查栈顶的Pair，如果当前所指的是Node，直接输出 true
即可。如果是List，就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围，说明已
经遍历完当前list， pop 掉当前元素，然后对新的栈顶元素（如果有的话）的
position ＋ 1， 之后同样 递归的 call hasNext 继续进行检查。
至于next，上面的 hasNext 保证了 如果还有值，会让栈顶的Pair指到一个Node，所以
直接输出即可，并将 position ＋ 1. |
|
d******o
发帖数: 13 | 21 Stack + 递归
之前面Twitter也被问到过，但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext（） 和 next（）
hasNext 检查还有没有值，检查栈顶的Pair，如果当前所指的是Node，直接输出 true
即可。如果是List，就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围，说明已
经遍历完当前list， pop 掉当前元素，然后对新的栈顶元素（如果有的话）的
position ＋ 1， 之后同样 递归的 call hasNext 继续进行检查。
至于next，上面的 hasNext 保证了 如果还有值，会让栈顶的Pair指到一个Node，所以
直接输出即可，并将 position ＋ 1. |
|
f***s
发帖数: 112 | 22 求职的是一个刚出学校门的牛校国女，科班毕业拿了一把的各种奖项。
最后几乎所有人都投了反对票，然后轮到说反对内容，摘要如下
1）面试官1 你对递归了解不？
－我就知道你要问递归，我和上几轮面试官说过我对递归不熟。
2）面试官2： 你有什么问题？
－你们公司怎么能赚钱啊
3）面试官3: 你有什么问题？
－你为什么离开上家公司
平心而论，对于一个刚出学校门的求职者的确不能太苛刻，从小也没被教如何说北美职
场场面话
但是希望求职时候还是多少注意礼节，公司里带着面具混饭吃，别太当真。
因为听说该国女已经有其他offer，对她应该也没什么太大影响 |
|
b******y
发帖数: 168 | 23 第一问可能就需要递归。如果min max同号，不需要做。如果min max异号，max在min的
前面，直接从min的index生成新数组，递归。如果min在max前面，从min的index到max
找符合要求的vlaue，找到停，找不到从max的index生成新数组，。
第二问主要是找min max中间，没有就两头各生成一个新数组，做两个递归 |
|
发帖数: 1 | 24 可是有的时候看着没什么问题，运行起来还是有bug的把，尤其是复杂的递归，递归套
递归 |
|
l*****8
发帖数: 16949 | 25 数学归纳法是一种证明方法，拿来证明一个well-founded order无限数集（比如所有自
然数）具有某个性质的。
递归(recursion)是一种定义方法。在定义一个函数的时候用到了这个函数自己。
通常证明递归定义的公式具有某个性质是用归纳法证明的。
比如说你讲的公式C(n+1,2)=1+2+...+n, 右边的表达式必须用递归才能严格定义的。证
明两边相等就是用归纳法证明。
对于你说数学归纳法是decision tree的一种特殊形式，我不是太明白。我觉得你认为
的数学归纳法和一般数学上定义的数学归纳法好像不同。可能你把数学归纳法的理解简
化了？ |
|
a****b
发帖数: 3588 | 26 【 以下文字转载自 Joke 讨论区 】
发信人: ici (艾西), 信区: Joke
标 题: 这就是传说中让理科生沉默，让文科生落泪的文史综合题
发信站: BBS 未名空间站 (Wed Apr 13 14:53:41 2011, 美东)
程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，... 阅读全帖 |
|
s***d
发帖数: 15421 | 27 古板智商太差了
[版面:股海弄潮] [首篇作者:sayid]
上一页 下一页
sayid (老留 小武) [1 楼]
Thu Apr 16 18:53:22 2015, 美东
[来源] [修改] [删除] [站短] [回复]
条件概率递归
是p（n）是n个座位最后一人最对位子概率
第一个人 如果作对位子 无话可说都是对的
如果第一个人坐了傻逼二好的位子 那么问题就相当于傻逼二号 变成前面状况的1号 不
过位子变成n—1。 为啥等效的 ？好好想想 是不是等效的？
那么一号占了三号 四号 五号也都是一样的情况 为啥如果我占了三号 二号正常feedin
不用管他 对不对？也就变成了 n-2 n-3的case 有了下面的递归函数 会做了吧
pn=1/n*1+1/n*p(n-1) ... 0
然后把n=2 p2=1/2 作为第一个递归 就他吗全出来了 卧槽 四年前mit 女博士叫我的
random process没白学
★ 发自iPhone App: ChineseWeb 7.8 |
|
s***d
发帖数: 15421 | 28 条件概率递归
是p（n）是n个座位最后一人最对位子概率
第一个人 如果作对位子 无话可说都是对的
如果第一个人坐了傻逼二好的位子 那么问题就相当于傻逼二号 变成前面状况的1号 不
过位子变成n—1。 为啥等效的 ？好好想想 是不是等效的？
那么一号占了三号 四号 五号也都是一样的情况 为啥如果我占了三号 二号正常feedin
不用管他 对不对？也就变成了 n-2 n-3的case 有了下面的递归函数 会做了吧
pn=1/n*1+1/n*p(n-1) ... 0
然后把n=2 p2=1/2 作为第一个递归 就他吗全出来了 卧槽 四年前mit 女博士叫我的
random process没白学
★ 发自iPhone App: ChineseWeb 7.8 |
|
l******n
发帖数: 577 | 29 昨天面试，遇到一个烙印是我见过的最奇葩的烙印。
让我解释我做什么，我说我implement model，这货一直让我解释什么叫implement。
啥问题也没准备，估计就自己网上看了一些面试题，但是自己也不知道怎么做，然后随
机的问。
写个翻转二叉树，我做出来了，他看不懂递归是啥。我交换两个node用了中间变量，他
看不懂这三行代码，我都觉得无语。
完事儿了又让我写一个二叉树路径sum，又看不懂递归，看不懂 return a == b，问我
这是啥意思。
怎么删除单链表中某个节点，如果只有这个节点的reference，我答把下一个节点以后
的值依次往前挪动一个。另外这货听不懂我问是不是要整个object移动还是只是value
就可以了，说反正你只要work就行，我不懂你的问题。
他见难不倒我，又问怎么sort一个大文件，还没说，他又说，你还是写删除单链表节点
那题吧。
刚提笔写了一行，又说算了不用写了，还是说大文件吧。刚开始说又改主意了，你说说
正常怎么排序吧，quick sort，merge sort， heap sort，问我最快是哪个，我说
quick sort，他跟我说绝对不是... 阅读全帖 |
|
t**********g
发帖数: 3388 | 30 【 以下文字转载自 Joke 讨论区 】
发信人: ici (艾西), 信区: Joke
标 题: 这就是传说中让理科生沉默，让文科生落泪的文史综合题
发信站: BBS 未名空间站 (Wed Apr 13 14:53:41 2011, 美东)
程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，... 阅读全帖 |
|
L*****k
发帖数: 13042 | 31 【 以下文字转载自 Joke 讨论区 】
发信人: ici (艾西), 信区: Joke
标 题: 这就是传说中让理科生沉默，让文科生落泪的文史综合题
发信站: BBS 未名空间站 (Wed Apr 13 14:53:41 2011, 美东)
程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，... 阅读全帖 |
|
m*d
发帖数: 7658 | 32 Inception就是一个四层递归调用的故事，陀螺就是递归return的flag。Ellen page就是
搭程序框架的。第四层递归，dicaprio空间没释放，结果被garbage collector给收了。 |
|
z****6
发帖数: 10776 | 33 【 以下文字转载自 Joke 讨论区 】
发信人: ici (艾西), 信区: Joke
标 题: 这就是传说中让理科生沉默，让文科生落泪的文史综合题
发信站: BBS 未名空间站 (Wed Apr 13 14:53:41 2011, 美东)
程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，... 阅读全帖 |
|
x*****p
发帖数: 1707 | 34 我强调多次，这个定义是循环定义。预先知道什么叫素数了，再找个推论。
(1) "a是大于1的奇自然数，而且不能被小于a的素数整除。", 这样的数，我们称为素
数。
(2) "a是大于1的自然数，而且不能被小于a的素数整除。", 这样的数，我们称为素数。
(1)和(2)都是递归定义. (1)不全，漏了2。(2)是全的。这说明递归在数学上不能当成
定义，只能当成数学归纳法用来证明一个命题。而且，递归的初始条件，是靠定义来完
成的。
比如说证明2是素数，是根据素数定义，说一个大于1的自然数只能被1和其本身整除。2
正好满足这一定义，这才是证明2是素数的根据。并由此展开数学归纳法，就可以证明
凡是大于1而不能被比自己小的素数整除的，必是素数。 |
|
x*****p
发帖数: 1707 | 35 但楼主给出的是充要条件的定义，就必须证明完备性。纠结还在递归定义上。
真要较真，所有的递归定义都是不严谨的，都建立在集合论上。我看到链接上自然数的
定义，先说1是自然数，然后进行递归，如果n是自然数，那n+1必然是自然数。
这个定义，我也不认为是严谨的。
数学的基础是集合论。从集合论可以定义两个数0和1，然后在集合{0,1}的基础上定义
加法，成为半群，于是得到自然数集合。再进而定义加法群，成为整数集合。再加上乘
法，成为环，再生成有理数域。再用极限定义实数域。等等。 |
|
t*******r
发帖数: 22634 | 36 其实就有点像罗素悖论，你俩看同一个自然语言，结果看到是不同的意思。
这不奇怪，我一开始看楼主的，也没看明白。也争了一大通。不过后来发现
那是古典数学语言。码工多用现代数学集合论图论正则语言，或者类似正则
语言写法的东东，导致看古典数学转不过弯来。
楼主的证明其实没错，但是用到了素数的递归定义，实际上我认为是个
trivial 的证明。（由素数递归定义可以容易直接证明无限性，不需要
反证或归谬）。
老实说素数的递归定义并不显而易见，我觉得非码工用自然语言理解，很可能是
似懂非懂。说实话我一开始其实也理解有偏差，导致一开始写的那个 yacc/c
伪码里，把 if and only if 里的 only if 判断条件写错了。其实那个
不是笔误，是理解错误。但写正则语法就是有这个好处，写出来，testcase
跑对，也就基本理解对了。 |
|
t*******r
发帖数: 22634 | 37 我擦，我上面难道不是用 formal logic 证明了，基于素数的
formal logic 的递归定义（严格的说是素数集合的递归定义），
对于任何一个“前N个连续素数的完整集合”，总能找到一个尺寸大
一个的“前N个连续素数的完整集合”，并且该集合满足素数集合的
formal logic 的递归定义？ |
|
t*******r
发帖数: 22634 | 38 俺暂定你这里说的是指高中数学的公理定理系统，而不是指
formal logic 系统。
如果我上面说的是对的，那你就不能援引你 1032 楼的
C 代码。因为尽管你的 C 代码是判定单个素数，但是
你的 C 代码里有递归，递归背后的数学基础还是 formal
logic。（递归是函数自己 call 自己，好比就是理发师
自己给自己理发。。。）。
我觉得你这段文字的问题还是涉及同时使用两个矛盾的数学
系统导致的。具体说是：
（1）你用 formal logic 系统判定单个素数（而不是直接
判定集合）。
（2）你用自然语言/经典集合论，把很多单个素数组成素数集合。
以上的（2）直接违反了 formal logic。
formal logic 本身并不禁止用单个数构成集合，但你必须
定义一个 token 代表集合，同时还是定义 operator 把
单个素数的 token 组成素数集合的 token。同时这个
token 和 operator 要满足 formal logic 的基本要求。
但这些你都没有定义，所以不被 formal logic 所认可。 |
|
t*******r
发帖数: 22634 | 39 递归定义系统不需要任何 token 都递归定义。只要递归定义产生
“前N的自然数”以后，其他的东西都在“前N个自然数”集合里做普通
操作就可以了。
只是这里没有无限集，也就是没有“所有K-整除数”，只有“前M个K-整除数”
。。。
数K |
|
j****q
发帖数: 204 | 40 好吧~~我发现我们讨论的不是一个主题。。。。请无视
最后强调一下，证明的假设是：那N个质数就是整个质数的全集，不存在其他的质数，
因此，构造数在这个质数集的下就是质数，他不可能是合数。
你要问在2，3质数全集下，25是不是质数，回答是：是质数。而这与2，3是质数全集矛
盾，因此2，3不是质数全集，25本身到底是质数还是合数没有任何意义，你也不需要问
是不是2，3，25是一个新的质数集，这和假设无关，这也不是假设的否命题
原证明中对质数的定义是存在的，是递归定义，和递归方程类似，要说原证明中有任何
可能的漏洞，只可能是你认为递归定义是不正确的，其他的，要么你没看原证明，要么
看了不明白，要么你看了理解不了 |
|
d*****u
发帖数: 17243 | 41 我说了，你用递归定义来定义出的“争议数”可以构造出来
而且也确实跟素数的递归定义方式相同
但是，你这个“争议数”只有在没有其他限制条件的时候才跟素数等同
如果你假设“递归的时候只能使用有限个争议数来构造其他争议数”
那么，构造出来的争议数集并不是素数集
而是素数和合数都有
你确实也用反证法证明了这个争议数集必须是无限的
但是由于这里面包含了合数
所以无法从它推断素数集到底是不是无限的 |
|
t******n
发帖数: 2939 | 42 ☆─────────────────────────────────────☆
l63 (l63) 于 (Thu Jul 4 01:01:50 2013, 美东) 提到:
转子知乎: http://www.zhihu.com/question/21262930
一个关于数学归纳法的悖论问题：到底是第N天有N个红眼睛自杀，还是什么都不会发生？
此问题最早据说是澳大利亚的华裔数学神童陶哲轩在网上贴出来让大家思考，逗大家玩
儿的。但却是真的把我难住了，一直百思不得其解。在此求教方家。
题目是这样的。说一个岛上有100个人，其中有5个红眼睛，95个蓝眼睛。这个岛有三个
奇怪的宗教规则。
1. 他们不能照镜子，不能看自己眼睛的颜色。
2. 他们不能告诉别人对方的眼睛是什么颜色。
3. 一旦有人知道了自己是红眼睛，他就必须在当天夜里自杀。
某天，有个旅行者到了这个岛上。由于不知道这里的规矩，所以他在和全岛人一起狂欢
的时候，不留神就说了一句话：【你们这里有红眼睛的人。】
最后的问题是：假设这个岛上的人足够聪明，每个人都可以做出缜密的逻辑推理。请问
这个岛上将会发生什么？
此问题的第一个... 阅读全帖 |
|
t******n
发帖数: 2939 | 43 ☆─────────────────────────────────────☆
l63 (l63) 于 (Sun May 26 03:44:32 2013, 美东) 提到:
我对素数的定义是:
"a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除"
C代码如下:
bool judge_prime(int a)
{
int b;
if (a<=1)
return 0;
else
{
for (b=0;b
{
if(judge_prime(b)&& a%b==0)
return 0;
}
return 1;
}
}
☆─────────────────────────────────────☆
l63 (l63) 于 (Sun May 26 03:46:21 2013, 美东) 提到:
看了这个还认为我的定义有什么 "循环定义" 的问题的人, 我只能说, 你的智商连... 阅读全帖 |
|
i*i
发帖数: 4739 | 44 程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，模拟退火；d，穷举算法。
7，《公孙龙子》记载：“齐王之谓尹文曰：‘寡人甚好士，以齐国无士，何也？’尹
文曰：‘愿闻大王之所谓士者。’齐王无以应。”这说明了齐王：
a，昏庸无道；b，是个结巴；c，不会下定义；d，不会定义自己的需求。
8，惠施曾提... 阅读全帖 |
|
G**Y
发帖数: 33224 | 45 程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
a
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
不知，猜a
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
a
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
b
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
不知，猜d
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，模拟退火；d，穷举算法。
不知，猜d
7，《公孙龙子》记载：“齐王之谓尹文曰：‘寡人甚好士，以齐国无士，何也？’尹
文曰：‘愿闻大王之所谓士者。’齐王无以应。”这说明了齐王：
a，昏庸无道；b，是个结巴；c，不... 阅读全帖 |
|
v*****s
发帖数: 20290 | 46 一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，模拟退火；d，穷举算法。
7，《公孙龙子》记载：“齐王之谓尹文曰：‘寡人甚好士，以齐国无士，何也？’尹
文曰：‘愿闻大王之所谓士者。’齐王无以应。”这说明了齐王：
a，昏庸无道；b，是个结巴；c，不会下定义；d，不会定义自己的需求。
8，惠施曾提出过“卵有毛”的命... 阅读全帖 |
|
s********g
发帖数: 124 | 47 第十一章 单程递归
首长扑向计算机，动作敏捷得如饥饿的鹰见到地面上的小鸡，令人恐惧。他熟练地移
动鼠标，将时间滑标滑过零时点，在滑标进入未来时段的瞬间，--个错误提示窗口跳了出
来：
Stack overflow．．．．．．
白冰从首长手中拿过鼠标"让我们启动错误跟踪程序，step by step吧。"
模拟软件退回到出错前，开始分步运行。当现实中的白冰将滑块移过零时点，镜像中
虚拟的白冰也正在做着同样的事：错误跟踪程序立刻放大了镜像中的那台超弦计算机的屏
幕，可以看到，在那台虚拟计算机的屏幕上，第二层的虚拟白冰也正在将滑块移过零时点
；于是，错误跟踪程序又放大了第三层虚拟中的那台超弦计算机的屏幕……就这样，跟踪
程序一层层地深入，每一层的白冰都在将滑块移过零时点。这是--套依次向下包容的永无
休止的魔盒。
"这是递归，一种程序自己调用自己的算法，正常情况下，当调用进行到有限的某一
层时会得到答案，多层自我调用的程序再逐层按原路返回。而我们现在看到的是无限调用
自己、永远得不到答案的单程递归，由于每次调用时都需将上层的现场数据存入堆栈，就
造成了 |
|
h******y
发帖数: 3501 | 48 程序员文史综合题目一，选择题(皆为单选)：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，cdth；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，模拟退火；d，穷举算法。
7，《公孙龙子》记载：“齐王之谓尹文曰：‘寡人甚好士，以齐国无士，何也？’尹
文曰：‘愿闻大王之所谓士者。’齐王无以应。”这说明了齐王：
a，昏庸无道；b，是个结巴；c，不会下定义；d，不会定义自己的需求。
8，惠施曾提出过“卵有毛”的... 阅读全帖 |
|
d***a
发帖数: 13752 | 49 假设这个每个数最多有K个bit。这个问题可以一个递归算法来解。设计一个递归函数
majority (S, k), S是整数集合，k是当前观察的bit位置。
1. 如果k=0, 数出S中bit 0分别是0和1的数目，返回两数之最大值。
2. 如果k>0, 按bit k等于0或1把S分为S0和S1，递归调用majority(S0,k-1)和majority
(S1,k-1)，取两个返回值中最大值，返回之。
最开始的调用是majority(Sn, K-1), Sn是输入整数集合。算法复杂度是O(N)，一共要
用K*N次比较。
这个算法是原创。:) 当然，应该是recreate the wheel。 |
|
