x*****p
发帖数: 1707 | 1 所以说，通过递归手段定义出来的东西，有可能和实际的东西有差距。在数学上，一般
不采用递归定义。你既然认为我的定义也是合理的，但我的递归定义，只说明了这样定
义的数是素数，但没说明所有素数都长成那样。比如2就被排斥在外。所以，当你用递
归定义素数的时候，还要证明完备性。即传统定义的素数，全部包含在你这样所定义的
素数中。所以，一般的数学证明，不会采用这样递归的定义。 |
|
t*******r
发帖数: 22634 | 2 谢谢，改了，这个 “only if” 需要递归调 yacc 。。。（这个递归层次比较牛。。
。）
所以每次一定要小一号，否则死递归。。。
递归调的目的就是确认这个 list 没有漏掉的 prime numbers。
虚拟概念机了，实际机器不被这个破程序玩死？LOL |
|
t*******r
发帖数: 22634 | 3 另外我刚才发现一个问题，你的程序实际上还是需要外加自然语言的定义的。
因为你的程序是判断单个数是不是素数，而素数无限性的问题实际上是集合
的 size 的问题。
你的程序没有出现集合。当然，你的想法估计是“我把所有自然数都上去跑
一遍，这个自然就是集合了嘛。”。这个的确不错，但这一句是自然语言而
不是 formal language。于是罗素悄悄的来了。。。:-)
另外一个问题，除了因为你没有定义素数集合这个 token 以外，更重要
的是，正因为你没有定义素数集合这个 token，你的递归并没有真正意义
上去 reduce 一个代表集合的 token 到小一号的 token。你的递归
还是更倾向于自然语言的实现，递归式的判断单个数，而不是递归式的
reduce 一个集合。但 again，证明有限无限性，是集合 size 的
问题。。。
数5 |
|
t*******r
发帖数: 22634 | 4 实际上你的第二个定义是对的，这个就是素数的递归定义。
只是递归定义的边界（指被定义 token 自己）在递归的 context
下很严格，因为是自己定义自己。
而非递归定义的边界只要够大，不发生越界就可以，因为是用别人定义自己。
样. |
|
t******n
发帖数: 2939 | 5 ☆─────────────────────────────────────☆
dangran (当当当) 于 (Thu May 23 16:51:52 2013, 美东) 提到:
怪不得现在科学院的人见到民科都躲起来了
------------------------------------------------------------
素数就是 除了1和此整数自身外，无法被其他自然数整除的数。
当然你可以说，
素数不能被其他所有素数整除。
素数不能被其他所有合数整除。
素数不能被除0和自身以外的所有自然数的子集整除
.
.
.
但是这些推论都不能当作素数的定义。
-------------------------------------------------------
"163"假设只有P1....Pn是质数，
然后就说N=P1*...*Pn + 1 也是质数，
因为N不能被P1....Pn整除。
其实N完全是可以被其他某个数整除的，
至于这个其他的数是不是质数并没有关系，
重要的是只要N能被其他数整除，
那么N就不是质数了。
-------------------... 阅读全帖 |
|
l********a
发帖数: 1154 | 6 c++的，新手
做了个类,类内部外部定义的格式大家就别看了，目前主要是问问流程问题
因为这个类我是递归初始化的，所以有一个构造器是接受一个Test *parent
class Test
{
Test *parent;
list children;
...
// 递归子构造函数
Test(Test *parent) // 构造器，接收一个Test指针，所有子构造器构造出的对象
的父节点
{
...
this->parent = parent; // 这里不知道为什么没有初始化好
for (循环）
{
this->children.push_back(Test(this));
...
}
// 主构造函数，解析文件内容构造
Test(string &fname) // 构造器，接收一个文件名
{
...
this->parent = NULL;
Te... 阅读全帖 |
|
o**2
发帖数: 168 | 7 从技术上来说，递归是通过函数调用来隐式地使用堆栈数据结构来保存本次调用的状态
和返回点，所以递归百分之百可以通过显式地使用堆栈数据结构被改写成非递归。
但对一些特定的问题或数据结构，递归是最佳选择，估计 goodbug 指的是这个。 |
|
g*********s
发帖数: 1782 | 8 还是不理解这个递归表达式。
假设x和y都是四位，最坏情况递归四次结束。那第三次递归结束，第四次递归开始之前，r的最高位代表
什么？c2呢？
主要的困惑在于，这里的位操作是针对整个二进制串的。那前面算低位的时候，高位还没算到的部分也
可能变化很多次。这样算到高位时已经和原来的值相去甚远，怎么保证正确性呢？希望能看到严格证
明。 |
|
z**i
发帖数: 86 | 9 每天练习做考题，找工作
一，选择题
1，我选a--关键是比谁先！伏羲:此人发明了太極生兩儀· 兩儀生四像· 四像生八卦;
莱布尼兹是18
世纪公认发现2进制的，但是太晚啦
2，我选d--指非指！万物无非是受指，但能指不是受指--指针和引用
3，我选c---看起来像但是本质没啥关系！司马相如原名司马长卿，因仰慕战国时的名
相蔺相如而改
名，没有血缘关系。d是同宗同源，a并列，b依附关系
4，我选b--分而治之，各个击破
5，小伙子借助了一根绳子，进入迷宫然后按绳子返回，故而选择 c
6，七弟主要是自我演化出了情感，故排除d,c,此二类是求解最优解方法；a类算法主要
是具有基于学
习的推广能力，一般不具有变异的能力；选b.
7, 选d--不会定义什么是自己心中的“士”
8，鸡有毛，卵继承于鸡，说明其 c, 衍生类未重载。重载的衍生类应该覆写毛这个属性
9，这个比较难于回答，如果你父母家财万贯，你选a;如果你老婆家有钱，你选b;如果
你儿子有钱你
又想搞一下就选多态c；d是最高境界, 不关心谁，靠什么挣钱，就关心钱.
10,改革主题是统一流通机制，选d
二：匹配题
1，江南可采莲，莲叶何田田... 阅读全帖 |
|
l********a
发帖数: 1154 | 10 c++的，新手
做了个类,类内部外部定义的格式大家就别看了，目前主要是问问流程问题
因为这个类我是递归初始化的，所以有一个构造器是接受一个Test *parent
class Test
{
Test *parent;
list children;
...
// 递归子构造函数
Test(Test *parent) // 构造器，接收一个Test指针，所有子构造器构造出的对象
的父节点
{
...
this->parent = parent; // 这里不知道为什么没有初始化好
for (循环）
{
this->children.push_back(Test(this));
...
}
// 主构造函数，解析文件内容构造
Test(string &fname) // 构造器，接收一个文件名
{
...
this->parent = NULL;
Te... 阅读全帖 |
|
B******k
发帖数: 44 | 11 纯粹兴趣学C++、数据结构，目标是2D游戏开发，因为纯粹是兴趣所以进度比较慢。
目前进度一个月（应该超过一个月了）：
C++进度：C++ Primer Plus看到Class，后头的Inheritance还没看，再往后的比如
Friend啊，nested class啊这些多少都要用到所以知道一些，operator overload写过
一点不过不熟。vector和string经常用不过肯定不敢说熟悉，比如前者用就是当做数组
来用。但是我现在看的不多了因为觉得光看不写很快就忘记了，干脆先写，不会的就再
看。当然导致基础肯定不扎实。
数据结构：这个才开始没多久，写了vector和linked list，然后发现递归很头疼，这
两天都在看递归，MIT有个用Scheme的递归教程，我拿过来用C++写练习，等写完递归就
回去看教材里头的backtracking（当初就是觉得八皇后比较难以理解怎么那么简单的递
归代码）以及后头的简单语法分析，然后是stack、queue、tree等等，总之这个蛮长时
间的。
游戏编程：这个月初写了几个迷宫生成算法，想写个Roguelike来着的，发现水平不够
果断... 阅读全帖 |
|
h********o
发帖数: 2316 | 12 感觉和java, python, php这种语言差别很大，haskell全部都是递归,还不能储存变量
，倒是对于练习递归很有好处，写java的时候能用循环的地方会避免用递归，现在也会
用递归去思考问题了 |
|
w***g
发帖数: 5958 | 13 实战中很少有递归能明显提高生产效率的情况。搞FP的人会大量使用尾递归, 然后由编
译器自动转化为循环， 其实还是在绕过语言的限制写循环。 非尾递归的递归就算写FP
的也会尽量避免。
不用归不用， 但是不能不知 。 |
|
o***s
发帖数: 42149 | 14 请问：伏羲、姬昌、莱布尼茨、柏拉图，这四人当中谁是二进制思想的最早提出者？请问：以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？a、变量；b、数组；c、对象；d、指针……这样的题目摆在面前，你会不会顿生“这都哪儿跟哪儿”的无助感？这就是在网上热传的让理科生沉默、让文科生流泪的一套文理综合题，题目有够让人抓狂的，不管你是文科生、理科生，不管你是工人、学生、农作物制造者还是知识分子，欢迎前来挑战，至于能做出几题就看诸君天文地理、历史哲学、数学操作等全方位的修养啦！
一，选择题(皆为单选)：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，javascript；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用... 阅读全帖 |
|
发帖数: 1 | 15 精度目标不能是递归的base case 吗
plus
尾调用优化照样直接返回调用地址lol
: 递归有固定终点，到了终点后就不能再往下递归了，要逐层退回
: 迭代没有固定终点，达到目标精度即可，也不用逐层退回。类似一个带跳
出的循环
|
|
g********d
发帖数: 19244 | 16 ☆─────────────────────────────────────☆
shuangseyun (shuangseyun) 于 (Tue Jun 21 15:49:00 2011, 美东) 提到:
老公坐别人的车，结果司机把车开翻了，所幸两人都没有大碍，不过老公的眼镜不见了
，脚受了伤，肿了。偏巧定了这周末出去玩的，机票和旅馆都定了，旅馆倒是可以
cancel，不知道损失的机票和重新配眼镜的钱保险公司可以cover么？那个司机只买了
liability。
谢谢！
☆─────────────────────────────────────☆
siulam (小林) 于 (Tue Jun 21 15:52:39 2011, 美东) 提到:
司机是朋友吗
☆─────────────────────────────────────☆
imrobot (robot) 于 (Tue Jun 21 15:53:05 2011, 美东) 提到:
出租？还是bus？
☆─────────────────────────────────────☆
shuan... 阅读全帖 |
|
l*****8
发帖数: 16949 | 17 你这个有点信口开河了。你以为丰田些软件的都是没学位的中学生？还随便哪个本科生
都能当他们的老师。
说实话，就是计算机博士，FLG里的很多码农，如果没有搞过专门汽车控制软件设计，
也未必能意识到这些问题。比如使用递归，从编程本身说没有什么问题，要不然大部分
高级程序设计语言也不会支持递归。很多函数式语言甚至完全取消迭代，只用递归。这
里的主要问题是整个系统的容错性做得太差。 |
|
l***y
发帖数: 582 | 18 一，选择题（皆为单选）：
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，惠施曾提出过“卵有毛”的命题，以下哪一项是... 阅读全帖 |
|
发帖数: 1 | 19 DP的原始思想源自于递归，但是能存储即时动态的递归，核心思想是存储力这个
enhancement，会大幅缩短运行的搜索周期。
你不会把递归也算成是其他专业的课程吧 |
|
s**********e
发帖数: 33562 | 20 也就是说用到了递归的方式提高计算效率的，不一定属于计算机科学罗？呵呵。
那DP用到了递归的方法，属于计算机科学；而最优控制也用到了递归的方法，却不属于
计算机科学。那到底是否属于计算机科学的标准是什么呢？
另外，研究DP的人，主要是计算机科学的人吗？呵呵。 |
|
a****n
发帖数: 1887 | 21 全排列，我觉得最好的是字典法， 可以处理重复元素
组合， 可以循环 1 ~ 2 ^ N, 然后check bit， print 相应元素
这两种都是非递归的方法， 适用于可以用brutal force的问题
5取3， 还是递归方便一点, 一般直接print, 也可以先压到vector里面去
另外求一个有重复元素的全排列的递归方案 |
|
z*********3
发帖数: 37 | 22 不是所有递归都可以转化为循环的吧，递归用的堆栈啊。都能循环了还要递归干什么。
。。 |
|
r****o
发帖数: 1950 | 23 谢谢。
我的想法是divide and conquer. mid=(start+end)/2
每次递归调用如下。
0)开始 end
1)比较a[mid]和a[end],如果相同，则a[mid+1]..a[end]全部不用考虑。 end=mid.
2)比较a[mid]和a[start],如果相同，则a[start]..a[mid-1]全部不用考虑。start=mid.
3)然后
递归左半边(start..mid-1)
如果a[mid]!=a[mid-1] 则打印a[mid]//也可以push a[mid]到一个新的vector。
递归右半边(mid+1..end)
我觉得这样的话，复杂度是O(n')。 n'是n除掉重复元素后剩下的元素数目。
大家觉得我的方法可以吗？ |
|
j**l
发帖数: 2911 | 24 我们当时任课老师提示就是用mark，还说太难，考试只考前序和中序的非递归，结果考
题是不用递归求二叉树的最大深度（可以用前序和中序非递归实现，也可以用层序的队
列实现)
网上别人给出的老严习题解答，用的也是mark |
|
y*c
发帖数: 904 | 25 你们是自己DFS，没用递归么？我这个递归的 num=8327168 也很快啊，我的输出需要
reverse string一下。先写递归表达
f(n) = f((n-1)/2) if n&1=1
f(n) = f((n-2)/2) + f(n/2) if n&1=0
后程序，
void FindAll210(int num, char res[], int index)
{
if(num==0){
res[index] = 0;
cout<
return;
}
if(num&1){
res[index] = '1';
FindAll210((num-1)>>1, res, index+1);
}else{
res[index] = '0';
FindAll210(num>>1, res, index+1);
res[index] = '2';
FindAll210((num-2)>>1, re |
|
j**l
发帖数: 2911 | 26 这个方法虽然直接，但却是O(n)的
This problem could be solved in O(log n) time if the BST contained the
number of nodes under a root
如果不允许把子树元素个数信息放到node中, 可以把算子树元素个数的递归算法，跟查
找kth node的递归算法合并在一起, 共享一个递归过程。复杂度是O(log n) |
|
s*****t
发帖数: 737 | 27 的确是限制了无限递归，
但是函数被重复调用，overhead非常大，因为是先递归调用再判断是否visited.
应该先判断是否visited,然后再递归调用。这个顺序改一下，效果可大不一样。
量。 |
|
K******g
发帖数: 1870 | 28 这个好像不对吧?如果把isVisited判断放在递归调用前,那么每次递归的时候都要检查,
这个overhead应该比偶尔才有的一次递归马上返回的大吧. |
|
e****9
发帖数: 316 | 29 KingMing code好快。
第二题如果只是链表到bst的话应该是不要其他的辅助数据的。
第二题就是那样的。我当时把那个递归和移动第一个点的位置的循环搞的不清楚。
第三题你可以看看Memory Alignment的东西。int的指针应该是能被4整除的，要不然可
能会有hardware exception.类似的问题还有对struct调用sizeof的问题。
第五题还有对角线上4个点，而且要先把能放的点push_back到vector里，然后再遍历
vector里面的点，对每个点递归调用。比如4，8初始已经填色，给你位置5，7不能填色
。如果不用vector的话，你会不知道4，8是初始填色的还是后面你递归的时候添上的。
五面第二题就是讨论，很多时候顾头顾不了脚，觉得应该是没有什么完美的方案。 |
|
w***h
发帖数: 415 | 30 很好! 你这个方法妙在两点:
1) 从低位往高位算, 所以也能同时定字符长度, 我的方法从高位往低位算, 必须分两
步, 先定字符长度, 比较笨.
2) 更重要的是, 很好的利用了几何级数等形式的递归特点. 所以利用这个可以很容易
写递归的版本: string(n) = char(n) + string(n-1) (说到"短一点的", 呵呵)
#include
#include
std::string & num2strn( int n, std::string & s )
{
if ( n < 0 )
return s;
return num2strn( ( n / 26 - 1 ), s = char( 'a' + n % 26 ) + s );
}
几何级数增长很快, 所以递归堆栈调用也不会太深. |
|
w***h
发帖数: 415 | 31 很好! 你这个方法妙在两点:
1) 从低位往高位算, 所以也能同时定字符长度, 我的方法从高位往低位算, 必须分两
步, 先定字符长度, 比较笨.
2) 更重要的是, 很好的利用了几何级数等形式的递归特点. 所以利用这个可以很容易
写递归的版本: string(n) = char(n) + string(n-1) (说到"短一点的", 呵呵)
#include
std::string & num2strn( int n, std::string & s )
{
if ( n < 0 )
return s;
return num2strn( ( n / 26 - 1 ), s = char( 'a' + n % 26 ) + s );
}
几何级数增长很快, 所以递归堆栈调用也不会太深. |
|
D*****7
发帖数: 766 | 32 我有一点想法了，大家来看看到底对不对。
1) 这是一个递归的问题，而递归的结束条件就是N<=C，这时候一趟运了就是了，如果
剩下的路程长于C/F，那就是无解。
2) 在递归结束之前，我们都要进行往返运输，而且每次都要把尽可能多的Nuts运到尽
可能远的位置。
3) 马车的单程最长距离是：C/F，我们可以把这个距离看做1，而我们每次运输的距离
为X（容易可得：X<0.5）。
4) 每次运输的往返次数Y为：
Y = N/C + (N%C > C*2X) ? 1 : 0
这个等式中的后半部分是比较剩下的Nuts和途中的消耗，如果还不够消耗的就干脆不要
了。其中Y-1次是双程，最后1次是单程。
由此，每次运输后的Nuts数量为：
N = ((Y-1)*(1-2X) + (1-X)) * C = (Y - (2Y+1)*X) * C
5) 从效率的角度考虑，我们既不应该抛弃Nuts，也不应该不满载，也就是说我们应该
保证每次运输后的Nuts数量都是C的整数倍，或者说每次运输都只消耗一份数量为C的
Nuts（第一次运输为N%C），即
X=1/(2Y+1) or X=((N%C)/C)/(2Y+1) |
|
i**********e
发帖数: 1145 | 33 感觉有错误. 你算 costPerKm 用到了 numTrips, 这是包括了最后一趟的, 也就是说全
运走了, 没有 remingingNuts.
>> 当 remainingNuts 为零的时候，随即被再次调入 getMaxNuts 函数的时候，不要忘
了有 if (N <= C) 这个 base case 的检查。这时候 N 就是 remaining nuts，也就是
0. 这时候 N <= C 的条件必定满足，然后就检查是不是还有剩下的距离。如果还有的
话，那就返回0，因为马以经走不下去了。
我了解你对递归的不确定而感到困惑。递归的解法就是先从简单的例子开始解，然后由
此获取这个问题 (problem) 中的问题 (subproblems)。递归的难点就在于你怎么从一
个 problem 和另一个 subproblem 里寻找那个关系。只要能证明从这个关系把一个问
题引申到下一个 subproblem，问题就能迎刃而解，不用想的太复杂。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 34 在字符都排好序的前提下，那么重复的字符都必定相连在一起。
给个例子：
aaabcc
进入递归，首先看到第一个的字符是 'a'。每一次标记位置用过，然后再进入下个
level 的递归。下一个 level 的时候，位置 0 的 'a' 已用过，所以我们跳到下一个
'a'，设位置 1 为用过，以此类推。
当递归回溯的时候，位置又被还原为没用过，照理应该跳到下一个位置的字符。但如果
下一个字符也是重复的字符，这样会产生重复的组合。例如，位置 0 的 'a'下一个字符
也是 'a'，这肯定是个重复的组合。
由于字符都排好序，只要跳到下一个不重复的字符就能跳过所有重复的组合。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
r*****e
发帖数: 792 | 35 用那么多double的干什么，有点画蛇添足啊,原题只要返回整数的商就好了。
我写了个递归的，用对除数移位的方法，不过不知道是不是有更好的算法？
正在把递归的改成非递归的。 |
|
y***m
发帖数: 7027 | 36 ms题意只要求最接近V没要求邮票张数也最少吧？ how about this?
邮票数组a,邮票张数数组c
看成 c1*a1 + c2*a2 + c3*a3 ... cn*An >= k,递归a和c求模，一旦找到模为0退出循环
如果要求最少张数就把金额排序再递归
V = 358;
array a[]={0,2,3,5....n}; //邮票金额
array c[]={0,55,13,5,...n}; //邮票张数
array current[]={0,0,0,0,...,n}; //存储当前循环的邮票张数
array pick[]={0,0,0,0,...,n}; //存储最逼近V的邮票张数
calc(V, 1); //算出 pick 数组
int minMod=1000000000000;
function calc(V,j){
int i = V/a[j] > c[j] ? c[j]:V/a[j];
for(;i>-1;i--){
if(i>c[j])
continued;//大于预定的邮票张数继续-1
int imod = V... 阅读全帖 |
|
i**********e
发帖数: 1145 | 37 来自主题: JobHunting版 - 一到电面题 Gate:
很好！递归的确在某些情况可以更简单解决。
另外，guitarnerd 的代码有 bug，没有处理特殊状况。
这让我想起这道链表题，比这题还要更 tricky 些：
You are given two linked lists representing two non-negative numbers. The
digits are stored in reverse order and each of their nodes contain a single
digit. Add the two numbers and return it as a linked list.
你可以在这里输入你的代码，网站会自动以大量测试数据来检测你是否答对。你可以试
试看能不能第一次写就答对。
http://www.ihas1337code.com/onlinejudge
以下是我的递归与非递归的解法。
Iterative:
void reversePairsOfLinkList(Node *& head) {
if (!head) return;
Node *p1 = head;... 阅读全帖 |
|
g**e
发帖数: 6127 | 38 来自主题: JobHunting版 - 一到电面题 递归也就是面试的时候用用，production code用递归的还没见过，可能我看的少。我
觉得就算用也要加个递归层数的限制，不然程序容易崩溃
了。 |
|
S*********a
发帖数: 75 | 39 【 以下文字转载自 Hubei 讨论区 】
发信人: howmoney (多少钱), 信区: Hubei
标 题: 版上做IT的多吗？来做做这个
发信站: BBS 未名空间站 (Thu Apr 14 12:00:47 2011, 美东)
程序员文史综合题目一，选择题(皆为单选)：
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，穷举算法... 阅读全帖 |
|
h*******0
发帖数: 68 | 40 思路主要是调试费时的DFS发现的。在递归DFS方法里，每发现一条新路经，我就打印当
前总路经数。我发现有时要花几分钟发现下一条新路经。 调试时，我发现在这几分钟
里，刚开始的几步把Matrix分成两部分了，例如
2 0 + 0 0 0 0
- 0 - 0 0 0 0
- - - 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 1 1
这种情况下，不可能发现一条合乎条件的路经了。 再递归那么多剩下的点就是浪费时
间。所以走到'+'位置时，应该立刻返回。这个处理把时间降为原来的差不多1/(100 -
150).
我又加了一个HashMap记录一些中间结果，不过这个改进对上面的性能影响不大。可能
只有1/(1-1.3). 加起来，总时间大概是递归DFS的1/(150-200). |
|
g**********y
发帖数: 14569 | 41 每次算中点要把已经在栈里的数拎出来算，比如
现在栈里有 {1, 9, 7, 3}, 添个6进去，就要算{1,6}, {9,6}, {7,6}, {3,6}
最后写code感觉很不clean, 我在interview里写这样的code，肯定写出一堆bug来。
最理想的是这个题有什么数学特性，能够很简洁地概括那个中点，写递归就容易了。
每次我一看到有很多条件的递归，头就大了，太容易写错了。
应该这么说吧，递归回溯时，要是有很多状态要维护，是一件很头疼的事。 |
|
h*****t
发帖数: 40 | 42 我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
的多了点，好在都是数。
time ./milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
real 1m5.827s
user 1m5.776s
sys 0m0.028s
假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
prev_pos之和。
基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
以及逐个累加prev_pos里milestone所得到的路程，都在a里，则认为该a[i]可以作为新
的milestone，进行递归。
#! /usr/bin/env python
import sys
DEBUG=1
def milestone(a, total, prev_pos):
if DEBUG: print "#", prev_pos, total,... 阅读全帖 |
|
h*****t
发帖数: 40 | 43 我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
的多了点，好在都是数。
time ./milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
real 1m5.827s
user 1m5.776s
sys 0m0.028s
假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
prev_pos之和。
基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
以及逐个累加prev_pos里milestone所得到的路程，都在a里，则认为该a[i]可以作为新
的milestone，进行递归。
#! /usr/bin/env python
import sys
DEBUG=1
def milestone(a, total, prev_pos):
if DEBUG: print "#", prev_pos, total,... 阅读全帖 |
|
i**********e
发帖数: 1145 | 44 处理 -1 而已不行，万一 -2,-3 的话会死循环。
还有，当 n < 0 时，n%2 是 undefined behavior 的（至少对 C++ 来讲）。
这样处理就行了：(如果放在递归函数外边会更好，每次递归避免了一个无谓的 if
evaluation）
if (b < 0)
return 1.0/power(a, -b);
无可否认你处理 b=1 和 b=2 可以省了 2-3 步代码，但是这对电脑来说是极小的优化
。电脑一秒可以执行上千万个操作，这省了2-3步代码也不会跟着 a 和 b 有更大的改
变。再说，每次递归都要试探好多 if 语句，耗费没必要的 cpu。（你的代码 base
case 好像也写错了）。
java 我不懂，但跟 C++ 挺像的，也支持 bit 操作，除了 >>= 是 logical right
shift 之外（C++ 的是 arithmetic right shift)，其他应该是一样的吧。所以
stackoverflow 贴的代码应该直接 java 就可以编译。我不是 java 的 master，所以
错了请纠正。 |
|
y***m
发帖数: 7027 | 45
处理 -1 而已不行，万一 -2,-3 的话会死循环。
>>>java没问题..
还有，当 n < 0 时，n%2 是 undefined behavior 的（至少对 C++ 来讲）。
>>>java没问题...
这样处理就行了：(如果放在递归函数外边会更好，每次递归避免了一个无谓的 if
evaluation）
if (b < 0)
return 1.0/power(a, -b);
无可否认你处理 b=1 和 b=2 可以省了 2-3 步代码，但是这对电脑来说是极小的优化
。电脑一秒可以执行上千万个操作，这省了2-3步代码也不会跟着 a 和 b 有更大的改
变。再说，每次递归都要试探好多 if 语句，耗费没必要的 cpu。
>>>en, maybe..
（你的代码 base case 好像也写错了）。
>>> 是?
java 我不懂，但跟 C++ 挺像的，也支持 bit 操作，除了 >>= 是 logical right
shift 之外（C++ 的是 arithmetic right shift)，其他应该是一样的吧。所以
stackoverflow 贴的代码应该直接 ... 阅读全帖 |
|
g*****k
发帖数: 623 | 46 code是对的，但是没有解释明白，
对方可能要你简洁地讲述算法和你的思路。
你只需要说这是一个递归算法，对于以r为root的子树进行判断是否所有的子节点都在
（low, high)区间。
递归过程就是首先判断当前根节点是否在此区间。
然后再递归判断左子树和右子树在相应改写过的区间。
新的区间将是(low, r.data) 和 (r.data, high)。以为左子树所有节点要小于当前节
点，
右子树要大于当前节点。
白。 |
|
j*p
发帖数: 115 | 47 递归要看是不是in place的递归啊
反正 如果完全in place的话 那个两两一组的方法应该最好了 加上递归效果一样 也是
3n/2 加上很多swap
你慢慢想 我睡觉去了 ：） |
|
j*p
发帖数: 115 | 48 当时 我吭哧半天 也想到了那个两两分组的方法 后来也说可以用递归 连递归公式都说
了 f(n)=n/2 + f(n/2) 然后 不知道怎么想的 一直觉得这个得到f(n)=3n/2 :(
刚查了一下 递归公式 f(n)=n/2 + f(n/2) + 1 所以应该是 f(n)= n + log(n) - 2.
这个方法主要问题是要用n/2次swap。那个印度人后来说要minimize swap的次数。我就
很郁闷 因为已经超时了 后来他告我答案了：
不是把数分成n/2组每组两个，要把数分成2组每组n/2个。每组选最大的。比较之后，
较大的就是最大的那个数。较小的和较大的数所在的组里的其他数组成一组，再选最大
的，就得到第二大数了。一共大概3n/2次 用到了一两个额外的内存。
简单吧!:) |
|
j*p
发帖数: 115 | 49 递归要看是不是in place的递归啊
反正 如果完全in place的话 那个两两一组的方法应该最好了 加上递归效果一样 也是
3n/2 加上很多swap
你慢慢想 我睡觉去了 ：） |
|
