笔试的一些题目,大家看看
1.用c实现两个128位正整数的最小公倍数
2.Windows中COM编程中如何判断两个interface的指针是同一个父COM对象
3.TCP/IP连接的唯一性如何确定
4.100个棋子,两个人按顺序取,每人每次至少取一个,至多取10个, 取得最后一个者为胜者,问你会选择先取还是后取?为什么?
5.10个房间里放着随机数量的金币。每个房间只能进入一次，并只能在一个房间中拿金
币。一个人采取如下策略：前四个房间只看不拿。随后的房间只要看到比前四个房间都多
的金币数，就拿。否则就拿最后一个房间的金币。
a) 编程计算这种策略拿到最多金币的概率。
b) 证明这是不是最优策略。
6.线程的优缺点，编程中应该注意的问题
希望会做的朋友,发表自己的看法,另外有什么比较好的题目,也分享一下,谢谢大家了.
问题点数：20、回复次数：44Top
1 楼fengfeng2003（）回复于 2005-08-03 08:00:37 得分 0
up
关注Top
2 楼alating（我是熬夜狂）回复于 2005-08-03 17:45:53 得分 0
upTop
3 楼alating（我是熬夜狂）回复于 2005-08-03 17:49:57 得分 0
第4题，先取
因为我每次要把99,88,77,66,55,44,33,22,11把这些剩下的交给对方去取.
比如我先取1个，剩99个，然后不论他取多少个，我再取一次留下88个，然后让他再取，依次类推。
最后肯定是我让他面对11这个数字，然后他怎么办？？？？
不知道对不对，请大家指教Top
4 楼zhouhuahai（道号"虚无"）回复于 2005-08-03 18:14:55 得分 0
支持 alating(我是熬夜狂) 关于第4题的解答Top
5 楼renmo80（）回复于 2005-08-03 18:18:58 得分 0
第4题，我算过了，恩是对的，我又学到知识了，高兴Top
6 楼perukelzhx（一块臭豆腐）回复于 2005-08-03 18:22:24 得分 0
关注！Top
7 楼perukelzhx（一块臭豆腐）回复于 2005-08-03 18:32:38 得分 0
alating(我是熬夜狂) ：
你的解答是错的，你把11留给我取，我取10个，你不得不取最后1个，这样你输了！Top
8 楼renmo80（）回复于 2005-08-03 18:39:55 得分 0
-_-~不是说取得最后一个为胜者吗？Top
9 楼tianhua（网络过客）回复于 2005-08-03 19:43:30 得分 0
3.TCP/IP连接的唯一性如何确定 这个问题好像是通过3次握手来确定的吧。Top
10 楼yztommyhc（老六）回复于 2005-08-03 21:07:12 得分 0
alating(我是熬夜狂)你的方法太好了啊，
绝妙，我长见识了。Top
11 楼alating（我是熬夜狂）回复于 2005-08-04 12:16:03 得分 0
大家见笑了，只是平时比较喜欢这种题目，所以比较感兴趣，希望以后多一点这种题目大家多多交流。Top
12 楼billy145533（$_$）回复于 2005-08-04 12:38:06 得分 0
随机数量的金币 可以说有金币相等吗Top
13 楼renmo80（）回复于 2005-08-04 23:04:52 得分 0
关于金币那题，感觉有相同数量的金币出现的可能，所以要分开计算Top
14 楼CSDNWW（中国软件WW）回复于 2005-08-05 09:26:04 得分 0
高手在哪?Top
15 楼everestsun（至芝）回复于 2005-08-05 14:58:35 得分 0
3.TCP/IP连接的唯一性如何确定
不知道什么意思？是指检测作为客户端的连接？还是指主机端的呢？
4.100个棋子,两个人按顺序取,每人每次至少取一个,至多取10个, 取得最后一个者为胜者,问你会选择先取还是后取?为什么?
分析：只要最后让对方面对11，我即可取胜。问题可转化为在100-11颗棋子中我如何取胜拿到最后一颗，运用递归的思想，依此类推，要求我要在100-99颗中拿到最后一颗，当然我先拿第一颗（即最后一颗）就可以了。
5.10个房间里放着随机数量的金币。每个房间只能进入一次，并只能在一个房间中拿金
币。一个人采取如下策略：前四个房间只看不拿。随后的房间只要看到比前四个房间都多
的金币数，就拿。否则就拿最后一个房间的金币。
a) 编程计算这种策略拿到最多金币的概率。
b) 证明这是不是最优策略。
分析：我的理解是拿到最多金币的那一袋的概率，计算公式：设定从x个房间开始为起点开始拿，概率为10％*(1+1/2+1/3+1/4+...+1/(10-x)),要求0<x<10.x=1or x=10 概率为10%。可知x=4不是最优解，从第二拿可以。
Top
16 楼wellsnow2002（IT·汽车）回复于 2005-08-05 15:20:35 得分 0
第一题：int gongyueshu(int a,int b)
{int temp;
while(b!=0){temp=a%b;
a=b;
b=temp;
}
retrun a;
}
第三题：经过三次握手协议。
Top
17 楼cadiee（）回复于 2005-08-05 15:52:29 得分 0
wellsnow2002(热带鱼oO○)
你好象没有注意128位呀
楼猪：你的题不好做啊Top
18 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-05 15:56:01 得分 0
楼上的,没那么简单吧,求最小公倍数,数学上有一种叫"辗转相除法"算法可以求得.但题目要求的是128位的正整数，你只用int类型的数根本没办法计算.这题首先要自己自定义一个可以容纳256位正整数的数据结构，然后重定义加减乘除等运算，再用＂辗转相除法＂计算最小公倍数.为什么要用到256位呢，因为这是求最小公倍数，若这两个128位正整数是互质的，则它们的最小公倍数实际上就是两个数的乘积，那么只有用到256位的数长才能保证结果不会溢出.（注：所说的数字位数是指十进制的位数，并非计算机中的二进制位数，如：计算机中的32位字长可以存储的最大整数为65535，实质上只有5位）Top
19 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-05 15:57:11 得分 0
打字慢了点，竟然中间多了个帖子！我说的是 wellsnow2002(热带鱼oO○)Top
20 楼ningzhiyu（凝滞雨）回复于 2005-08-05 16:04:59 得分 0
markTop
21 楼happybigbone（快乐大骨头）回复于 2005-08-05 16:12:16 得分 0
LZ有这些题目的答案么 小弟想学习一下
另外不知道哪位大虾有quicktest 资料也可以 提供一下Top
22 楼xuanwenchao（xuanwenchao）回复于 2005-08-05 16:38:42 得分 0
学习!!!Top
23 楼lixiuyue（群狼飞舞）回复于 2005-08-05 17:20:59 得分 0
markTop
24 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-05 17:36:26 得分 0
刚刚编了一个程序来计算第５题，得到结果，４不是最佳策略，３才是最佳策略.
用程序计算的一组值如下：
４：做1,000,000次实验，重复10次得到的概率：0.398174 0.398383 0.39841 0.39819
0.398275 0.398315 0.398362 0.398023 0.398434 0.398243
最终认为：观察４个房间策略最后能取得最多的概率约为0.3983
５：做1,000,000次实验，重复10次得到的概率：0.372912 0.372701 0.372931 0.372678 0.372704 0.372989 0.372807 0.372818 0.372899 0.37292
最终认为：观察５个房间策略最后能取得最多的概率约为0.3728
３：做1,000,000次实验，重复10次得到的概率：0.398441 0.398826 0.398795 0.398589
0.398933 0.398929 0.399063 0.398811 0.398735 0.398436
最终认为：观察３个房间策略最后能取得最多的概率约为0.3988
实质上３与４策略相差无几.下面是C++源程序，有兴趣的可以在机器上实际运行看看.
对于这种题，结果的好坏一方面看实验的次数，次数越大，结果越稳定；其次与系统产生的随机数的好坏有关，程序中的随机数实质是伪随机数，如果是真正的随机数，那么得到的结果是可信的.关于随机数方面的知识，可以查看相关书籍或论述.
/********************** C++ 源程序 *****************************************/
/*
* 题目：10个房间里放着随机数量的金币。每个房间
* 只能进入一次，并只能在一个房间中拿金币。
* 一个人采取如下策略：前四个房间只看不拿。
* 随后的房间只要看到比前四个房间都多的金币
* 数，就拿。否则就拿最后一个房间的金币。
* a) 编程计算这种策略拿到最多金币的概率。
* b) 证明这是不是最优策略。
*
* 算法思路：由于题目中没有明确说明这10个房间金币的
* 有一样的，说的是随机数量的金币，那我们也可以
* 用系统的随机数生成方法给这10个房间赋金币价值.
* 编程计算概率，实际上就是做N次实验，在这N次实验中，
* 符合预期结果的实验有M次，当N很大时，就可以用M/N做
* 为该事件发生的概率.
* 本程序正是基于该思路计算的.
*/
#include <iostream.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#define HOUSE_NUM 11 //10个房间，第0个空间存放该10个房间中的最大金币数
void InitHouseGoldCoins(int *house, int num); //初始化房间的金币数量
int ExperimentOnce(int *house, int num, int look_house);
void main()
{
long exp_n = 0; //重复实验次数
float prob = 0; //成功概率
int house[HOUSE_NUM]; //定义存储10个房间金币数量的存储空间
cout<<"Please input the experience counts:";
cin>>exp_n; //从终端获得实验次数
srand(time(NULL)); //初始化随机种子
for (int j=0; j<10; j++)
{
int i = 0;
long exp_true = 0; //拿到最多金币的次数
while(i++ < exp_n)
{
InitHouseGoldCoins(house, HOUSE_NUM);
exp_true += ExperimentOnce(house, HOUSE_NUM, 3);
}
prob = float(exp_true) / exp_n;
cout<<"**************** The Experiment Result ***************\n";
cout<<"* Experiment Times: "<<exp_n<<endl;
cout<<"* Success Times: "<<exp_true<<endl;
cout<<"* The Probability: "<<prob<<endl;
cout<<"******************************************************\n";
}
}
/* *************************************
* InitHouseGoldCoins()
* Initialize the houses gold coin
*/
void InitHouseGoldCoins(int *house, int num)
{
house[0] = 0;
for (int i=1; i<num; i++)
{
house[i] = rand();//房间金币数
if (house[i] < 0)
house[i] = -house[i];//负数改为正数
if (house[i] > house[0])
house[0] = house[i];//房间号０存放最大的数，方便下面的计算
}
}
/* *********************************
* ExperimentOnce()
* Calculate whether he(she) can get the most, 0--no, 1--yes
*/
int ExperimentOnce(int *house, int num, int look_house)
{
int part_max = 0; //前start_house个房间观察到的最大金币数
int take_index = look_house + 1; //最终取金币的房间号
for (int i=1; i<=look_house; i++)
{//获得所有观察房间的金币最大值
if (house[i] > part_max)
part_max = house[i];
}
while (take_index < num - 1)
{//后面房间开始按规则取金币
if (house[take_index] > part_max)
break;
take_index++;
}
// for (int j=1; j<num; j++)
// cout<<house[j]<<" ";
// cout<<"\nTake "<<take_index<<": "<<house[take_index]<<endl;
if (house[take_index] < house[0])
return 0;
else
return 1;
}
Top
25 楼renmo80（）回复于 2005-08-05 20:38:13 得分 0
按楼上说的理论，那么次数的大小就可以用微积分的方法算，小弟见笑了！！！
学习Top
26 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-05 20:40:54 得分 0
不懂楼上说的，具体点！Top
27 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-06 08:57:22 得分 0
将观察房间设为0，即不观察，直接拿第一个房间的金币，理论上拿到最多的概率是0.1，或者观察前9个房间，这种情况下，实际上无论如何只能拿最后一个房间的金币，理论上拿到金币最多的概率也是0.1，我上面程序算出来也确实是0.1（当然不是精确的），这也可以验证我的算法是有道理的。
有高手么，讨论讨论！Top
28 楼johnzhaobing（zhaobing）回复于 2005-08-06 09:20:34 得分 0
在概率论中，有个彩票问题，那就是无论谁先摸彩票，得奖的几率都是一样的。这道题感觉很类饲。在我们不知道总的金币的情况下，每个房间产生的金币数都是一样的。所以无论第几个房间看概率都应该是一样的。你可以先假设只有2个房间。结果一样。只所以有人算的概率不等，那可能是随机函数产生的数是正态分布的，不是平均分布的。Top
29 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-06 09:24:54 得分 0
我不这么认为，这跟摸彩票是两回事。楼上的再想想。肯定不会是看多少都一样的结果。Top
30 楼johnzhaobing（zhaobing）回复于 2005-08-06 11:02:18 得分 0
如果说是获得金币比较多的概率最大的话，题目所提供的策略是正确的。现在是要的获得金币最多，无论真么分，金币是随机的，和摸彩票没什么分别。Top
31 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-06 12:00:31 得分 0
但题目说的有一策略，可以观察后再取，而且取法也不是随机的。如果题目是这样描述的：10个房间里随机放些金币，现让随机选一房间取金币，那么他取到的最多金币的概率是多少。这就和彩票没有分别了。但题目不是这么说的！确实是有策略问题的，如我前面所述，若让观察次数为0或9的话，题目就退化为彩票问题！Top
32 楼xxandxx（luck）回复于 2005-08-06 15:45:02 得分 0
取金币的题目第二问不会是指策略的房间号应该从4改成3吧?
出题的想法应该是让做题者也想一种策略,并且比题目中的策略要好.
比如试试首次最大的策略 :看第一个房间但不取,然后依次看其他房间,只要碰到比第一个房间的钱多的
就取,否则取最后一个.这样一般不是比较好的,那么把它改一改,改成二次最大,即第二次碰到比第一个房间多的就取.Top
33 楼zaisheng09（故雁）回复于 2005-08-06 15:58:19 得分 0
up~~Top
34 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-06 17:57:33 得分 0
要是真如xxandxx(luck)所理解的，那这题怎么能找到最优策略呢？
而且题目只是要求证明题中所说的策略是不是最优策略，我只要拿一个更优策略就可以反证题目中的策略不是最优的。
我是这么认为的！本人对概率比较感兴趣，:)Top
35 楼flyer0616（小龙）回复于 2005-08-06 19:59:59 得分 0
up!
感谢与大家一起分享，让我对笔试有一点了解，Top
36 楼johnzhaobing（zhaobing）回复于 2005-08-06 20:23:36 得分 0
我已经说过了 求最大和求最大可能获得比较多的金币是不一样的Top
37 楼snowbirdfly（专心搞好嵌入式~~~）回复于 2005-08-06 20:55:31 得分 0
6:线程执行开销小，但不利于资源的管理和保护；而进程刚好相反。Top
38 楼wellsnow2002（IT·汽车）回复于 2005-08-07 13:13:57 得分 0
xiaocai0001(萧筱雨) 128位的数怎么存储，你有什么好的想法，还望赐教。
学过概率论的朋友都可以轻易的算出拿到最多金币的概率，也可以很容易的知道最佳策略，不过要想用算法得到概率，我想不出来，我只能得到他可能拿到哪个房间的金币，还望赐教，见笑了！Top
39 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-07 15:35:49 得分 0
关于128位数的存储运算问题，楼上的可以看看这个帖子
用c实现两个128位正整数的最小公倍数
http://community.csdn.net/Expert/topic/4185/4185285.xml?temp=2.364749E-02
里面有些讨论，可以看看。Top
40 楼wellsnow2002（IT·汽车）回复于 2005-08-08 13:13:32 得分 0
怎么看帖子的全部 内容，我才来的，不会啊
赐教！Top
41 楼various（娃哈哈）回复于 2005-08-08 13:34:19 得分 0
http://community.csdn.net/Expert/TopicView3.asp?id=4185285Top
42 楼winner2008（螺旋桨）回复于 2005-08-08 14:03:23 得分 0
xue xiTop
43 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-05-04 18:39:39 得分 0
突然有人提到这题, 想到用另一种办法来解决第5问. 用程序穷举法.
得到结果如下:
Look 0 room success Probility: 0.1
Look 1 room success Probility: 0.282897
Look 2 room success Probility: 0.365794
Look 3 room success Probility: 0.39869
Look 4 room success Probility: 0.398254
Look 5 room success Probility: 0.372817
Look 6 room success Probility: 0.327381
Look 7 room success Probility: 0.265278
Look 8 room success Probility: 0.188889
Look 9 room success Probility: 0.1
Top
44 楼shot411（上帝的马甲）回复于 2006-05-05 13:19:41 得分 0
gzTop
