我做的google数组随机排序的算法
面试笔试1.82W
发信人: northor(追求理想的过程是曲折艰辛的!), 信区: Job
标 题: 我做的google数组随机排序的算法
发信站: 瀚海星云 (2006年05月30日23:44:13 星期二), 站内信件 WWWPOST
由于一开始觉得这个题目不太好做,
就放在最后做了,
结果时间不够,只写了算法:
我考虑题干强调的是一定要随机,就是越乱越好,
于是我就联想到了一堆乒乓球在笼子里摇啊摇的,抽奖的过程,
这个过程应该算是符合题目的要求吧,
那么怎么用random函数来实现这个功能呢?
我又建立了三个int型数组,b[len],c[len],d[len]
首先N = len,乒乓球的个数是N,
然后摇奖:利用random产生0到N-1的随机数,
记作b[0],d[0]=b[0];
这是摇出的第一个球的号码,然后对c[len]赋值,
这个数组,我规定它的作用是对剩下的乒乓球标记,
因为摇出了一个球,剩下了N-1个,
而随机数只能在0开始的连续整数之间产生,
所以剩下的球的号码要是连续整数就可以继续摇了,
所以c[len]记录我对乒乓球的重新标号,
如果最初乒乓球的号码小于b[0],就保持原来的号码,
等于b[0],就让号码为N(作废),
大于b[0]的,全部减1,
这样剩下的N-1个乒乓球的标号就是0到N-2了,
然后产生利用random产生0到N-2的随机数,
对标记号码摇奖,利用摇出的乒乓球的标记号码b[1],
查到它的真实号码d[1],
这样第二个随机位置d[1]就产生了,
然后再根据b[1]给剩下的N-2个乒乓球重新标记,
如果乒乓球的标记号码小于b[1],就保持原来的标记号码,
等于b[1],就让号码为N(作废),
大于b[1]不等于N的,全部减1,
大于b[1]等于N的,不变。
重新标记之后,产生0到N-3的随机数,
就产生了第三个乒乓球的随机号码b[2],
反回去查询真实号码,得到d[2];
......
最后我们得到了d[len]这个数组,
可以让c[i]=a[d[i]];
然后再把c赋给a,
这样一个模拟乒乓球摇奖的随机过程就完成了,
如果有可能,可以看到a[len]
打乱后排列的顺序,
和一个一个地摇出乒乓球号码的概率分布是一致的。
期待高手点评,^_^.
标 题: 我做的google数组随机排序的算法
发信站: 瀚海星云 (2006年05月30日23:44:13 星期二), 站内信件 WWWPOST
由于一开始觉得这个题目不太好做,
就放在最后做了,
结果时间不够,只写了算法:
我考虑题干强调的是一定要随机,就是越乱越好,
于是我就联想到了一堆乒乓球在笼子里摇啊摇的,抽奖的过程,
这个过程应该算是符合题目的要求吧,
那么怎么用random函数来实现这个功能呢?
我又建立了三个int型数组,b[len],c[len],d[len]
首先N = len,乒乓球的个数是N,
然后摇奖:利用random产生0到N-1的随机数,
记作b[0],d[0]=b[0];
这是摇出的第一个球的号码,然后对c[len]赋值,
这个数组,我规定它的作用是对剩下的乒乓球标记,
因为摇出了一个球,剩下了N-1个,
而随机数只能在0开始的连续整数之间产生,
所以剩下的球的号码要是连续整数就可以继续摇了,
所以c[len]记录我对乒乓球的重新标号,
如果最初乒乓球的号码小于b[0],就保持原来的号码,
等于b[0],就让号码为N(作废),
大于b[0]的,全部减1,
这样剩下的N-1个乒乓球的标号就是0到N-2了,
然后产生利用random产生0到N-2的随机数,
对标记号码摇奖,利用摇出的乒乓球的标记号码b[1],
查到它的真实号码d[1],
这样第二个随机位置d[1]就产生了,
然后再根据b[1]给剩下的N-2个乒乓球重新标记,
如果乒乓球的标记号码小于b[1],就保持原来的标记号码,
等于b[1],就让号码为N(作废),
大于b[1]不等于N的,全部减1,
大于b[1]等于N的,不变。
重新标记之后,产生0到N-3的随机数,
就产生了第三个乒乓球的随机号码b[2],
反回去查询真实号码,得到d[2];
......
最后我们得到了d[len]这个数组,
可以让c[i]=a[d[i]];
然后再把c赋给a,
这样一个模拟乒乓球摇奖的随机过程就完成了,
如果有可能,可以看到a[len]
打乱后排列的顺序,
和一个一个地摇出乒乓球号码的概率分布是一致的。
期待高手点评,^_^.
-
浪潮笔试
基础知识:软件工程,面向对象,网络,编译原理之类的一些知识和常识。1。数据库:给你2个表,写出创建它的语句;写触发器(具体忘了);写查询语句,大概是要求用一条语句同时查询两个表的内容,并把结果降序排列。2。程序:从硬盘读取一个文件,文件的内容是几个数字,创建链表,将这几个数...
-
详版金地笔试题
详版金地笔试题发信人:greenmoss(青苔),信区:Work公文筐测试笔试题1测试一:现在已经是11月了,你手里有一大堆的任务要去做,这些任务是:1.各个公司开始来学校开招聘会,你想参加;2.你在一个公司做兼职;3.收到一些公司的面试通知;4.和男/女朋友约会;5.参加学校组织的一些活...
-
申银万国笔经
我不是学金融的,今天去宣讲会,以为和以前的经验一样专业门槛不是很高,讲了一个小时左右就发题让大家笔试。一看题目就傻眼了,这是我遇到的最专业的一次笔试了。现实专业材料的两篇英译汉,然后几段话的汉译英,100分题。之后100分专业知识,我大致抄了一下,有:1短期偿债能...
-
中芯国际笔试小记
呵呵。今天去中芯面试了。其实前几天他们主管就电话面试我了。今天过去是考试和谈薪水。考试真他妈的难全部都是英文的逻辑题。跟我那小硕同事考的一模一样。结果我25道题我做了17道对了15道。哈哈。学过计算机逻辑的是要强点。人家主管直接说还好。因为我后面...