d*a
2 楼
从北京到美国甲地，然后转机去乙地
我记得过了关后，需要拿行李（大箱子），然后把行李放到一个传送带上（机场会把行
李放在去乙地的飞机上），然后进入美国国内候机厅（不用过安检）
我的记忆是否正确？
我记得过了关后，需要拿行李（大箱子），然后把行李放到一个传送带上（机场会把行
李放在去乙地的飞机上），然后进入美国国内候机厅（不用过安检）
我的记忆是否正确？
k*u
3 楼
cape cod beach
C*a
4 楼
自己的母语不说了
汉语说得基本和母语一个档次
这个英语也字正腔圆的
看阿妹真是受用的狠啊
汉语说得基本和母语一个档次
这个英语也字正腔圆的
看阿妹真是受用的狠啊
y*b
5 楼
b*i
6 楼
纠正了：先描述一下树：
一个多叶子的树，每个节点有多个下层节点。每一个节点也有一个指针指向同层下一个
节点。这个图无法看，可以复制到notepad上看
1--2--3--4
| | | |
| | | 5
| | | |
| | | 6
| | |
| | 7--8
| | |
| | 9
| | |
| | A
| |
| B--C--D
| | |
| | E
| |
| F--G
| |
| H
|
I--J--K--L
如果要遍历1-2-3-4-5-6-7-8-9-A-B-C-D-E-F-G-H-I-J-K-L，并且进行处理则有如下程序
traverse(head){
if (head->needed){
action(head);
wait(50);
if (quit) return;
if (head->deeper)
traverse(head->deeper);
}
head=head->next;
while(head){
traverse(head);
head=head->next;
}
}
要求多线程化这个遍历过程。假定有一个函数getNext，根据current指针来给出下一个
节点需要处理的节点（如果没有，给出原来节点），那么我的工人线程就是这样的
void worker(){
Node* next = getNext(current);
if (next->needed){
action(next);
wait(50);
current=next;
if (quit) return;
}
}
其他要求：
1 要持续化，就是L之后下一个是1，然后2，接着来。
2 每进行一个action，要等50毫秒
3 不是每个节点都要处理，有的不要处理，由needed决定。不处理的节点不要等50毫秒
4 如果每个节点都不要处理，那么就还是要等50毫秒，不能无限循环下去
5 每次50毫秒等待后，有机会判断是否应该退出线程
6 不需要处理的节点其下层节点都不用处理，但是需要尝试处理其同层下一个节点并继续
我目前想到两个方案：一个是写一个遍历的单步iterator函数getNext，有相应的术语
吗？英文叫什么？另一个是，在原来递归函数traverse的基础上，直接等待，和衔接I-
1。但是我怎么避免无限循环没有想好。
我想getNext应该基于堆栈，那么哪个思路好？
系统是Linux, 用C++11，内存512M，ARM。
一个多叶子的树，每个节点有多个下层节点。每一个节点也有一个指针指向同层下一个
节点。这个图无法看，可以复制到notepad上看
1--2--3--4
| | | |
| | | 5
| | | |
| | | 6
| | |
| | 7--8
| | |
| | 9
| | |
| | A
| |
| B--C--D
| | |
| | E
| |
| F--G
| |
| H
|
I--J--K--L
如果要遍历1-2-3-4-5-6-7-8-9-A-B-C-D-E-F-G-H-I-J-K-L，并且进行处理则有如下程序
traverse(head){
if (head->needed){
action(head);
wait(50);
if (quit) return;
if (head->deeper)
traverse(head->deeper);
}
head=head->next;
while(head){
traverse(head);
head=head->next;
}
}
要求多线程化这个遍历过程。假定有一个函数getNext，根据current指针来给出下一个
节点需要处理的节点（如果没有，给出原来节点），那么我的工人线程就是这样的
void worker(){
Node* next = getNext(current);
if (next->needed){
action(next);
wait(50);
current=next;
if (quit) return;
}
}
其他要求：
1 要持续化，就是L之后下一个是1，然后2，接着来。
2 每进行一个action，要等50毫秒
3 不是每个节点都要处理，有的不要处理，由needed决定。不处理的节点不要等50毫秒
4 如果每个节点都不要处理，那么就还是要等50毫秒，不能无限循环下去
5 每次50毫秒等待后，有机会判断是否应该退出线程
6 不需要处理的节点其下层节点都不用处理，但是需要尝试处理其同层下一个节点并继续
我目前想到两个方案：一个是写一个遍历的单步iterator函数getNext，有相应的术语
吗？英文叫什么？另一个是，在原来递归函数traverse的基础上，直接等待，和衔接I-
1。但是我怎么避免无限循环没有想好。
我想getNext应该基于堆栈，那么哪个思路好？
系统是Linux, 用C++11，内存512M，ARM。
g*y
7 楼
算单个的F(n)?
algorithmics以前给过一个很好的logN的方法算单个的F(n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
algorithmics以前给过一个很好的logN的方法算单个的F(n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
H*r
8 楼
对
h*e
9 楼
wow, the blue sky is amazing!!
r*d
10 楼
country roads 唱的不错
据说他母语和英语发音习惯相似
【在 C****a 的大作中提到】
: 自己的母语不说了
: 汉语说得基本和母语一个档次
: 这个英语也字正腔圆的
: 看阿妹真是受用的狠啊
据说他母语和英语发音习惯相似
【在 C****a 的大作中提到】
: 自己的母语不说了
: 汉语说得基本和母语一个档次
: 这个英语也字正腔圆的
: 看阿妹真是受用的狠啊
m*z
11 楼
怎么现在都是1366*768的分辨率了，原来1280*800都觉得低
【在 y**b 的大作中提到】
: http://www.dealslava.com/Archive/2010_10/2010_10_12/a04.html
: 有一款可以选摄像头。
【在 y**b 的大作中提到】
: http://www.dealslava.com/Archive/2010_10/2010_10_12/a04.html
: 有一款可以选摄像头。
b*n
12 楼
对，算单个的F(n)
电话面试让我口述recursive算法程序，
然后跟着问我复杂度
我就不是很明白recursive算法的复杂度
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
电话面试让我口述recursive算法程序，
然后跟着问我复杂度
我就不是很明白recursive算法的复杂度
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
m*e
13 楼
nice
C*a
14 楼
难怪啊
他是什么族的？哈萨克是吗？
【在 r*******d 的大作中提到】
: country roads 唱的不错
: 据说他母语和英语发音习惯相似
他是什么族的？哈萨克是吗？
【在 r*******d 的大作中提到】
: country roads 唱的不错
: 据说他母语和英语发音习惯相似
t*f
15 楼
My X201 giga NIC is very very slow...
Do not know where to complain.
【在 y**b 的大作中提到】
: http://www.dealslava.com/Archive/2010_10/2010_10_12/a04.html
: 有一款可以选摄像头。
Do not know where to complain.
【在 y**b 的大作中提到】
: http://www.dealslava.com/Archive/2010_10/2010_10_12/a04.html
: 有一款可以选摄像头。
H*M
16 楼
...
exponential for recursive one
using a dp way, you can get o(n)
using a matrix multiplication way o(lgn)
seems there is also a explicit formular for that, O(1)?
【在 b*********n 的大作中提到】
: 对，算单个的F(n)
: 电话面试让我口述recursive算法程序，
: 然后跟着问我复杂度
: 我就不是很明白recursive算法的复杂度
exponential for recursive one
using a dp way, you can get o(n)
using a matrix multiplication way o(lgn)
seems there is also a explicit formular for that, O(1)?
【在 b*********n 的大作中提到】
: 对，算单个的F(n)
: 电话面试让我口述recursive算法程序，
: 然后跟着问我复杂度
: 我就不是很明白recursive算法的复杂度
g*y
17 楼
是有通项公式，不过计算那个通项公式，要算某个数的n次方，就是说跟matrix
multiplication其实是一样的复杂度。
【在 H*M 的大作中提到】
: ...
: exponential for recursive one
: using a dp way, you can get o(n)
: using a matrix multiplication way o(lgn)
: seems there is also a explicit formular for that, O(1)?
multiplication其实是一样的复杂度。
【在 H*M 的大作中提到】
: ...
: exponential for recursive one
: using a dp way, you can get o(n)
: using a matrix multiplication way o(lgn)
: seems there is also a explicit formular for that, O(1)?
H*M
18 楼
yeah yeah. my bad
【在 g*******y 的大作中提到】
: 是有通项公式，不过计算那个通项公式，要算某个数的n次方，就是说跟matrix
: multiplication其实是一样的复杂度。
【在 g*******y 的大作中提到】
: 是有通项公式，不过计算那个通项公式，要算某个数的n次方，就是说跟matrix
: multiplication其实是一样的复杂度。
s*s
19 楼
Fib has analytical solution,
the running time for recusion is about o(golden ratio^n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
the running time for recusion is about o(golden ratio^n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
m*f
20 楼
算单个F(n)最好的logn方法是利用矩阵乘方, 是算法导论的作者上课的时候给的
http://www.verycd.com/topics/87348/
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
http://www.verycd.com/topics/87348/
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
m*0
21 楼
theta([(sqrt(5)+1)/2)^n])
matrix : theta(log n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
matrix : theta(log n)
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
m*0
22 楼
1 1
1 0
的n次方
就是
f(n+1) f(n)
f(n) f(n-1)
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
1 0
的n次方
就是
f(n+1) f(n)
f(n) f(n-1)
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
a*n
23 楼
O（n） 用两个变量存储fn fn-1
H*r
24 楼
This should be O(1)?
http://en.wikipedia.org/wiki/Fibonacci_number
Computation by rounding
Since \begin{matrix}|1-\varphi|^n/\sqrt 5 < 1/2\end{matrix} for all n\geq 0,
the number F(n) is the closest integer to \varphi^n/\sqrt 5\, . Therefore
it can be found by rounding, or in terms of the floor function:
F(n)=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor,\ n
\geq 0.
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
http://en.wikipedia.org/wiki/Fibonacci_number
Computation by rounding
Since \begin{matrix}|1-\varphi|^n/\sqrt 5 < 1/2\end{matrix} for all n\geq 0,
the number F(n) is the closest integer to \varphi^n/\sqrt 5\, . Therefore
it can be found by rounding, or in terms of the floor function:
F(n)=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor,\ n
\geq 0.
【在 b*********n 的大作中提到】
: Fibonacci序列的Recursive的那个算法
: 我回答 O(N)
: 好像不对呀
m*0
25 楼
题目问的不是你说的，
问的是recursive的复杂度。
golden ratio ^ n
【在 a****n 的大作中提到】
: O（n） 用两个变量存储fn fn-1
问的是recursive的复杂度。
golden ratio ^ n
【在 a****n 的大作中提到】
: O（n） 用两个变量存储fn fn-1
g*y
26 楼
算recursive的复杂度，其实跟算fibonacci数本身，几乎是一样的
假设recursive算f(n)的steps是g(n)的话
g(n) = g(n-1) + g(n-2) + O(1)
特征值仍然是 (1 +/- sqrt(5))/2，用算fibonacci通项式的同样方法算出g(n)的通项
式就行了
假设recursive算f(n)的steps是g(n)的话
g(n) = g(n-1) + g(n-2) + O(1)
特征值仍然是 (1 +/- sqrt(5))/2，用算fibonacci通项式的同样方法算出g(n)的通项
式就行了
x*y
27 楼
Can you give some details? thanks..
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
【在 g*******y 的大作中提到】
: 算单个的F(n)?
: algorithmics以前给过一个很好的logN的方法算单个的F(n)
g*y
28 楼
someone already did in her reply... you may wanna read this post more
closely
【在 x***y 的大作中提到】
: Can you give some details? thanks..
closely
【在 x***y 的大作中提到】
: Can you give some details? thanks..
相关阅读
node.js, angularjs都只是fad?Netty和JavaEE问个 Redis 的问题好虫当年是不是赶上netflix的首发了？被亚马逊绑架的问题win10 看起来还是怪怪的请教Node.js 应用的安全问题这里有几个程序猿， 说谢谢我的提醒古巴，你们公司新福利很爽啊诚求refer Java/J2EE的工作机会，会答谢一个月工资友情提醒年轻一代：mitbbs很多信息都不准 (转载)TIOBE Index August Headline: Java stronger in the lead可能还得死磕Hbase学习JavaScript的好书？请教赵策老师公司要从.net那套东西跳出来，成本有多大啊？经济危机什么时候来？问一个Git的问题Java concurrency的疑惑，难道我理解错了？学swift应该如何开始？