问两道算法题

anselcat

1.沿着长安街停了了一排汽车，你手中有一个车牌，而且你站在长安街的中心，怎么查到你手中车牌对应的车子（车子上有牌照 ），设计一个你认为较优的算法，并给出算法复杂度。
约束条件：a.只有你一个人，只能走着去看车牌照；b.假设长安街无限长，所以不能单独走一边

2.现在有一个rand(n)输出 [1,n]之间的integer, 现在我有一个array里放了10个cd,调用一次rand函数会产生一个值,就将相应的cd播放一次,现在让你设计一个算法使得每个cd被放第二遍之前其他的cd都要放一遍,而且是随机的播放.

FuriousFive

原帖由 cjaizss 于 2008-12-13 22:42 发表
1.往左走长度a1
2.往右走长度a2
3.往左走长度a3
....
直到找到
a(n+1)=b^n*a(n)
b可以取2,越大越好
第二道,
数组a[1:10]初始为0
以下循环10次:
取x=rand(10)
如果a[x]为0,则设a[x]为1,播放这个cd,并 ...

第一题的答案有什么优点么？我没看明白。
第二题的答案如果是我也会这么想的。

cjaizss

原帖由 FuriousFive 于 2008-12-13 23:22 发表

第一题的答案有什么优点么？我没看明白。
第二题的答案如果是我也会这么想的。

a1
a2
a3
a4
a5
...
这是每次走的距离,每次方向和上次相反
数列{bn}
bn=a(n+1)/an
{bn}是越高阶的无穷大,那么效率越好(也就是总体走的路越少)

Roemer

觉得你第二道题的算法第一次选择是平均分配。
但是第一次以后的选择就不是完全随机的了，紧挨在被选中歌曲后面的歌曲有更高的概率被选中。

cjaizss

原帖由 Roemer 于 2008-12-14 01:20 发表
觉得你第二道题的算法第一次选择是平均分配。
但是第一次以后的选择就不是完全随机的了，紧挨在被选中歌曲后面的歌曲有更高的概率被选中。

是的,我已经说明了,不同的排列被选中的概率是不同的,并非平均分布,但这个算法很快.

baicj

第二题这样应该更快, 而且是随机的. 伪代码:

1. 
   
2. CD array[10] = ........;
   
3. 
   
4. while(1){
   
5.     int i;
   
6.     CD tmp[10];
   
7.     copy(tmp, array);
   
8.     for(i=0;i<10;i++){
   
9.         int j = rand(10-i);
   
10.         playcd(tmp[j]);
    
11.         tmp[j]= tmp[10-i];
    
12.     }
    
13. }

复制代码

[ 本帖最后由 baicj 于 2008-12-14 02:52 编辑 ]

A.com

第二题：产生1-10的随机数，写入数组p(1)，再次产生1-10随机数，与数组中存在的数比较，如存在，继续产生随机数，如无，写入数组p(2)，直到数组p(10)写满。然后按数组播放。