搜狐一题，寻解法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

搜狐一题，寻解法

搜狐一题，寻解法# Programming - 葵花宝典

m*82011-01-24 08:01

1 楼

波士顿地区私人导游伴游服务，在波士顿地区生活多年，名校毕业生，有丰富的导游以
及中英文语言经验
，业务范围包括：
1、波士顿城市私人导游伴游。
2、常春藤名校哈佛，MIT，BC，BU，东北考察参观。
3、商务考查，学术会议陪同。
4、中英文件互译。
5、OUTLET购物中心接送。
6、机票，酒店预订，机场接送，旅游行程规划。
7。为孩子选校，选房介绍。
详情请联系：
邮箱：m****[email protected]

h*g2011-01-24 08:01

2 楼

圣诞节时候促销时候买了个FUSION的直发器。想带回国，好像这边电压与国内不一样，
国内有没有电压转换器之类的买，类似于插头转换器。还是可以直接使用？谢谢了

P*s2011-01-24 08:01

3 楼

我猜我猜我猜猜猜

P*62011-01-24 08:01

4 楼

【以下文字转载自 Literature 讨论区】
发信人: SpicyGirl (方鸿渐博士), 信区: Literature
标题: 我的父亲
发信站: BBS 未名空间站 (Thu Feb 2 06:26:11 2012, 美东)
我的父亲
-------By SP
昨晚8：00PM的时候，我就吃了BlueGel， VB， Melatonin， Fish Oil，看
了一会儿CNN，就呼呼的在客厅的Funton上睡着了，后来被iTalkBB的一电话铃吵醒，我
家的电话有来电显示的，在第二个铃声的时候，LD 把电话给我听，我看了看电话号码
，是来自故乡的，但是不清楚是谁的，来自故乡的电话，我唯一能记住的86开头的电话
就是弟弟的电话号码，所以我接听了电话。
电话那头是父亲几十年都未曾改变过后的声音，我说，“干什么啊？”，他
说：“我昨天和你LD讲话不是向他要钱的，你弟弟说，你LD 说我向他要钱吗”？“我
们家有钱，我家的毛竹现在收入很好，养2000只鸡呢，怎么会向他要钱，我们有钱，我
只是很想你们，我很开心和你们讲话，有空给我们打个电话就可以了。我也很想来美国
看一看，因为那样在村子里很有面子。。。。”
这是我这一生中，第一次为父亲感到自豪，第一次感到与父亲有些亲近，因为他有钱了
，男人没钱是很可耻的。。尤其是40岁以上的男人。。。至少我是这么歇斯底里的认为
的。。。说心里话，我不是很瞧得起我的父亲，因为我的母亲太强了，我的母亲是远近
1000里闻名的女强人，我们家是阴盛阳衰，这个是木有办法的事，我妈妈太强了，以至
于，我听到他们说：龙生龙，凤生凤。。的时候，我很反感。。。我妈妈那么强的女强
人，其实也不能说是幸运的，因为她在地球上的时间木有我的父亲长，我的母亲留给我
的永远的Legacy是我精神上跟跑马拉松一样永不放弃的精神，她有太多的优点了，其实
她给我留了很多财产。。。。今天是谈我的父亲，所以就专门谈我的父亲。。。不跑题
。。。
父亲长得和葛优一样，在我的记忆中，他长得非常的猥琐，我的同学也是客观的那么形
容我爸爸的外貌的。现在我也老了，这个只是他无法改变的外表，有什么呢？客观事
实就是客观事实，无须否认的。。。我承认我小的时候，尤其是在一中的时候，爸爸给
我送米的时候，我非常的虚荣和自卑，因为我的爸爸长得太难看了，我同桌的男孩说，
你爸爸像葛优。。。是的，爸爸的头顶是秃的，现在已经是一个光头了，这个是遗传的
。爸爸还长得尖嘴猴腮，他的眼睛是黄色的。我爸爸还有一个特点，就是他抽烟，他
抽了一辈子了，没发现肺癌或者其他任何呼吸系统的疾病。。。所以，我曾经用过我
的方式表达过我对他的孝敬，我买了一条骆驼牌香烟给他，在我在北京上学的时候；
我还做过另外一件孝敬父亲的事情，那就是，我在福州第一天拿到工资的时候，我给爸
爸买了一个300RMB的飞利浦剃须刀，不知道是什么型号的了，难道是二手的7530还是什
么1150，我不记得了，我哪里知道这些细节，我只知道是飞利浦，因为那个时候这个
是我所能知道的最好的牌子了。。。我当时给妈妈买的礼物是一条珍珠项链，那条项链
现在还在美国，带着血迹。。。。。。
我的父亲在我的印象中还有一个特点，他很好吃，他跟一个孩子似的，非常的贪吃，他
买花生米，会自己偷偷的吃，不给我吃，这一点让我很鄙夷他，。。。。我认为他这样
做，作为一个父亲影响很不好。。。。爸爸昨天给我打了电话，我很开心，所以开始写
我的爸爸，我要为爸爸写一些文字了，因为我的爸爸是一个文人，他的书法写得非常的
好，他说我的字写得和鸡抓一样，爸爸的数学没妈妈好，但是打牌的时候，经常是爸
爸赢，因为妈妈永不服输，输了会抓爸爸的脸，两个人打牌会打过夜，就他们两个人。
。。。。
关于我的爸爸妈妈有很多很多的事情可以写，我现在病了，我在吃药，我的家里还有矛
盾要解决，我还在找工作，因为我实在不想做生意了，我的妈妈是做生意的，做生意这
条道路最后的结局太惨了，如果挣的钱不知道怎么花，挣到的钱有什么P意义呢？这样
的人生有什么意义呢？也许一个很稳定的工作，加上一些闲暇时间我可以用来写作，这
样的人生构图也许正是我想要的。我有高等教育的文凭，我是PhD Candidate，有美国
MS的Diploma，美国杠杆的州立大学的正规的训练，教授们都会给我写Glory的推荐信的
，为什么我会找不到工作，为什么我的LD可以那么的鄙视我，说：“就凭你能找到工作
”？。。我，我为什么不能？我为什么不能，我为什么不能Contribute？只要我的劳动
有价值是有意义，肯定有我的市场。。。。。哪怕我只是一个病人，一个Patient阿。。
又跑题了，我一直有胃病，是因为这些年在美国操劳的，我有两个孩子啊，还有几乎6
年的正规的美国研究生院的教育，各位看客，你们知道，我做事情是很认真的，我是带
着小刀到实验室加班的，在Gardner Hall。。。我为我热爱的事业奉献了我的整个青
春，我的整个青春，现在到头来又一无所有了，我老了，现在又要到市场上去卖CV，要
到市场上选找顾主了，我小的时候说过我最热爱的职业是做一个自由职业者。。。。哎
。。。不写了。。。。
等下一次写我的爸爸的时候，我会写我的爸爸和他的情妇们的风流韵事，那是一道非常
有意思的风景，那个经历对我的保守性格的形成起着关键性的作用。。我不喜欢和真人
讲话，因为我病了，。。。我会变成Talktive了，所以，为了不烦别人，我把自己头脑
里的事，写在纸上，发表在我的精神家园：买买提上。Mitbbs这个是陪伴我出国的网站
，北大未名的网站，我对这个网站有很深很深的情缘。

A*s2011-01-24 08:01

5 楼

小狼拿小鸭子们没办法也是有情可原，因为小鸭子一生下来就要进行求生训练。否则
以它们的身无长物，早就被吃光了，灭绝了。看起来都是棕黄杂毛相间，圆圆笨笨的
小家伙，其实也是性格各异。从鸭妈妈带它们第一次下水就看出来了。阿拉斯加破冻
后的河流全是冰川融水，相当寒冷。有的小鸭子脚掌一沾水，就怕冷地逃回岸上，
浑身发抖，需要妈妈再三鼓励才敢下去。而有的小鸭子却一下子就兴奋地扑到水中，
第一次游泳就拼命撒欢耍宝，活泼无比。对于这种小鸭子，鸭妈妈则要小心，不能让
它游得离岸边太远。否则一旦陷入急流被冲走，它根本无力跟水流搏斗，再也无法
靠近岸边，只能最终活活被淹死。所以，最安全的训练地点，就是河流边上沼泽地里
的小水洼。那里没有急流，小鸭子们可以撒开了练习泳技。
现在镜头面对的，就是这么一个圆圆的小水洼，鸭妈妈带领着孩子们在里面嬉戏。而
水洼的草丛后面，则慢慢探出了一只小脑袋。这就是那只走失的小白狼，可是它现在
的样子已经跟刚出场时完全不同了。本来雪白蓬松的皮毛已经被脏脏的泥水覆盖。
原来像毛绒玩具一样可爱的小脸，现在成了脏兮兮的小花脸，都是泥印子。有的地方
毛被粘在一起，有的地方则不自然地支愣着，

N*m2011-01-24 08:01

6 楼

给定n=1，2，3，4，5。。。对括号，求所有的组合方法有多少种。
比如两对括号的情形，有两种，分别是:
[1] ()()
[2] (())
======================================
我能想到的就是递归。每次递归去掉不可能的组合以及重复的pattern，
但是这样的效率很低。求优化解法。

T*C2011-01-24 08:01

7 楼

美东地区私人导游伴游翻译
美东地区私人导游伴游服务，在纽约地区生活多年，有丰富的导游以及中英文翻译经验
，业务范围包括：
1、纽约，波士顿，华盛顿，费城，巴尔的摩等城市私人导游伴游。
2、常春藤名校考察参观。
3、商务考查，学术会议陪同翻译。
4、中英文件互译。
5、WOODBURY购物中心接送辅助。
6、机票，酒店预订，旅游行程规划。
详情请联系：
邮箱：f*********[email protected]
QQ：2563980827

kx2011-01-24 08:01

8 楼

越看越像是自传体mtv了

g*e2011-01-24 08:01

9 楼

贴个我以前写的，请各位师傅指点。还是用递归。
/**
* @param m # of left bracket
* @param n # of right bracket
*/
public ArrayList bracketPermute(int m, int n) {
ArrayList tmp = new ArrayList();

if (m>n)
return null;

if (m==0) {
String s = "";
while (n-- > 0) {
s += "}";
}

tmp.add(s);
return tmp;
}

ArrayList tmp2 = bracketPermute(m-1, n);
for(String t : tmp2) {
tmp.add("{"+t);
}

if (m <= n-1) {
tmp2 = bracketPermute(m, n-1);
for(String t : tmp2) {
tmp.add("}"+t);
}
}
return tmp;
}

【在 N***m 的大作中提到】

: 给定n=1，2，3，4，5。。。对括号，求所有的组合方法有多少种。
: 比如两对括号的情形，有两种，分别是:
: [1] ()()
: [2] (())
: ======================================
: 我能想到的就是递归。每次递归去掉不可能的组合以及重复的pattern，
: 但是这样的效率很低。求优化解法。

A*s2011-01-24 08:01

10 楼

//kick
援引的分明是谷一的话。
哼，叫你先生来收拾你！

【在 kx 的大作中提到】

: 越看越像是自传体mtv了

e*d2011-01-24 08:01

11 楼

n! ?

【在 N***m 的大作中提到】

m*m2011-01-24 08:01

12 楼

等下集

【在 A*******s 的大作中提到】

: 小狼拿小鸭子们没办法也是有情可原，因为小鸭子一生下来就要进行求生训练。否则
: 以它们的身无长物，早就被吃光了，灭绝了。看起来都是棕黄杂毛相间，圆圆笨笨的
: 小家伙，其实也是性格各异。从鸭妈妈带它们第一次下水就看出来了。阿拉斯加破冻
: 后的河流全是冰川融水，相当寒冷。有的小鸭子脚掌一沾水，就怕冷地逃回岸上，
: 浑身发抖，需要妈妈再三鼓励才敢下去。而有的小鸭子却一下子就兴奋地扑到水中，
: 第一次游泳就拼命撒欢耍宝，活泼无比。对于这种小鸭子，鸭妈妈则要小心，不能让
: 它游得离岸边太远。否则一旦陷入急流被冲走，它根本无力跟水流搏斗，再也无法
: 靠近岸边，只能最终活活被淹死。所以，最安全的训练地点，就是河流边上沼泽地里
: 的小水洼。那里没有急流，小鸭子们可以撒开了练习泳技。
: 现在镜头面对的，就是这么一个圆圆的小水洼，鸭妈妈带领着孩子们在里面嬉戏。而

g*s2011-01-24 08:01

13 楼

这种求所有的基本都是递归。

【在 N***m 的大作中提到】

c*r2011-01-24 08:01

14 楼

像个小乞丐一样的小狼，想着想着就忘了是狼了，以为是可怜的小狗狗了。

【在 A*******s 的大作中提到】

X*r2011-01-24 08:01

15 楼

显然不是。递推式为
f(n) = \sum_{i=0}^{n-1} f(i)f(n-i-1)
初始条件
f(0) = f(1) = 1
或许可以算出通项公式吧，不过我好久不做这类题目了。

【在 e****d 的大作中提到】

: n! ?

X*r2011-01-24 08:01

16 楼

原题只问所有的组合方法有多少种，并没有让你真得把它们列出来。

【在 g*********s 的大作中提到】

: 这种求所有的基本都是递归。

g*s2011-01-24 08:01

17 楼

n = 3, 4, 5的结果是多少？核对一下。
我的结果：
5 30 65
14 112 238
42 420 882
源码：
void print_legal_parentheses(int curr_pos, int pos_limit, int
left_count, std::vector& tag) {
#ifdef DEBUG
fprintf(stdout, "%d %d %d\n", curr_pos,
pos_limit, left_count);
#endif
if ( curr_pos == pos_limit ) {
for ( int i = 0; i < tag.size(); ++ i ) {
fprintf(stdout, "%c ", tag[i] == 0 ? '(' : ')');
}
fprintf(stdout, "\n");
return;
}
for ( int k = 0; k <= 1; ++ k ) {
int new_left_count = (k == 0 ? left_count + 1 :
left_count);
#ifdef DEBUG
fprintf(stdout, "%d %d %d\n", curr_pos,
pos_limit, new_left_count);
#endif
if ( curr_pos + 1 - new_left_count <= new_left_count &&
2 * new_left_count <= pos_limit ) {
tag[curr_pos] = k;
print_legal_parentheses(curr_pos + 1, pos_limit,
new_left_count, tag);
}
}
}
void print_legal_parentheses(int k) {
std::vector tag (2*k);
print_legal_parentheses(0, 2*k, 0, tag);
}

【在 g**e 的大作中提到】

: 贴个我以前写的，请各位师傅指点。还是用递归。
: /**
: * @param m # of left bracket
: * @param n # of right bracket
: */
: public ArrayList bracketPermute(int m, int n) {
: ArrayList tmp = new ArrayList();
:
: if (m>n)
: return null;

g*s2011-01-24 08:01

18 楼

那就加强一下呗，反正是编程版。

【在 X****r 的大作中提到】

: 原题只问所有的组合方法有多少种，并没有让你真得把它们列出来。

g*s2011-01-24 08:01

19 楼

你这个递推公式似乎忽略了重复的情况。
比如()()()可以是2+1也可以是1+2。
这应该是个经典组合计数问题。

【在 X****r 的大作中提到】

: 显然不是。递推式为
: f(n) = \sum_{i=0}^{n-1} f(i)f(n-i-1)
: 初始条件
: f(0) = f(1) = 1
: 或许可以算出通项公式吧，不过我好久不做这类题目了。

X*r2011-01-24 08:01

20 楼

http://en.wikipedia.org/wiki/Catalan_number

【在 X****r 的大作中提到】

: 显然不是。递推式为
: f(n) = \sum_{i=0}^{n-1} f(i)f(n-i-1)
: 初始条件
: f(0) = f(1) = 1
: 或许可以算出通项公式吧，不过我好久不做这类题目了。

X*r2011-01-24 08:01

21 楼

你没理解这个式子。
最左边的第一个符号必然是左括号。i是指这个左括号和它配对的右括号
里面有多少对括号。n-i-1就是剩下有多少对括号。

【在 g*********s 的大作中提到】

: 你这个递推公式似乎忽略了重复的情况。
: 比如()()()可以是2+1也可以是1+2。
: 这应该是个经典组合计数问题。

X*r2011-01-24 08:01

22 楼

可以用数学解决的问题就不应该用编程解决。

【在 g*********s 的大作中提到】

: 那就加强一下呗，反正是编程版。

g*e2011-01-24 08:01

23 楼

5 14 42

【在 g*********s 的大作中提到】

: n = 3, 4, 5的结果是多少？核对一下。
: 我的结果：
: 5 30 65
: 14 112 238
: 42 420 882
: 源码：
: void print_legal_parentheses(int curr_pos, int pos_limit, int
: left_count, std::vector& tag) {
: #ifdef DEBUG
: fprintf(stdout, "%d %d %d\n", curr_pos,

z*e2011-01-24 08:01

24 楼

an alternative：
参数curr_pos 可以不要，用tag的size替代。
每次pop回来。

【在 g*********s 的大作中提到】