2006年11月中软笔试一道编程题
出自求职百科
点击排行
- Index - (261121)
- 宝洁 - (58929)
- 华为 - (55593)
- 普华永道 - (43240)
- IBM - (41103)
- 中国银行 - (36695)
- 毕马威 - (34715)
- 富士康 - (31666)
- 招商银行 - (31410)
- 强生 - (31373)
最近更新
题目为写算法生成随机4位数,要求每位数字不同.
Solution:
有个隐含条件,即第一个数字不能为0. 以下是我初步的javascript解法:
function rand4(){
var arr = new Array();
var index = 0;
var tempNum;
while(index<4){
tempNum = Math.round(Math.random()*9);
if(!(index==0 && tempNum==0)){
//hold point
if(arr[tempNum]== null){
arr[tempNum] = tempNum;
++index;
}
}
}
var ret = 0;
for(var i in arr){
if (ret != 0){
ret *= 10;
}
ret += parseInt(i);
} alert(ret);
return ret;
}
我相信会编程的人都会写出这个算法. 基本上是很普通的.这个算法有个不愉快的地方就是hold point那块,成功率为100%(第一次),90%(第二次),80%(第三次),70%(第四次),越来越低,不过只要不低于50%,程序效率还不会打折扣.
以下是我的第二种写法,用空间换了点时间,用C++语言写的:
- include <iostream>
- include <stdlib.h>
using namespace std;
class Rand4{
private:
int a[10];
int getNum(int index){
while(a[index]==-1){
++index;
index %= 10;
}
int ret = a[index];
a[index] = -1;
return ret;
};
void init(){
for(int i=0;i<10;++i){
a[i] = i;
}
};
public:
int Next(){
init();
int ret = (rand()%10) *1000;
int index = 100;
int time = 3;
while(time>0){
ret += getNum((rand()%10))*index;
index /= 10;
--time;
}
return ret;
};
};
int main(int argc, char *argv[])
{
Rand4 r4;
cout<<r4.Next()<<endl;
cout<<r4.Next()<<endl;
cout<<r4.Next()<<endl;
system("PAUSE");
return 0;
}
此法的时间复杂度为正宗的O(n),空间开销(不包含调用库函数的)就比前一个例子多了些.
此法在n取m的随机计算中,m从0一直到趋近于n, 效率都是不变的.
其他的高效方法暂时还没有想出.
