一个算法问题(50分)

  • 主题发起人 主题发起人 rxp2001
  • 开始时间 开始时间
R

rxp2001

Unregistered / Unconfirmed
GUEST, unregistred user!
实际情况：一群人排队，排成一条线，等待进入公园， 设置允许通过的人为70%,也就是说
算法要实现让排队的一群人中的60％进公园，但是能进去的人要是随机的。
 
var
S1,S2:TStringList;
I:Byte;
T:Word;
begin
Randomize;
S1:=TStringList.Create;
S2:=TStringList.Create;
try
for I:=1 to 100 do
S1.Append(IntToStr(I)); //把100个人放入S1中
for I:=1 to Round(S1.Count*0.6) do
begin
T:=Random(S1.Count-1);
S2.Append(S1.Strings[T]);
S1.Delete(T);
end;
//S2为选出的人
finally
FreeAndNil(S1);
FreeAndNil(S2);
end;
end;
 
如果事先不知道有多少人 如何处理？？
 
这样只能用概率来计算，让每个人都有60％的机会通过。
 
没有被选人群，怎么在这些人中选？
 
对每个人赋值一个随机数
按此随机数对人重新排队

把其中的60％的人放进去，剩下的挡住
 
TO :魏启明
程序中如何实现？？？？
 
代码已经给你了
button1.Click：//加入队列：
begin
S1.Append(人名); //S1是全局的
end;


button2.Click：取出可以进入的人名：
var
S2:TStringList;
I:Byte;
T:Word;
begin
Randomize;
S2:=TStringList.Create;
try
for I:=1 to Round(S1.Count*0.6) do
begin
T:=Random(S1.Count-1);
S2.Append(S1.Strings[T]);
S1.Delete(T);
end;
//S2为选出的人
finally
FreeAndNil(S2);
end;
end;
 
>>每个人都有60％的机会通过
呵呵，个体随机的结果可能会造成整体总和的偏差。
如果要精确的控制总的概率结果，就要根据已经放入的人数和剩下的人数重新界定概率边
界。具体的方法，求解如下方程即可：

( 已放入的人数 + 当前在等侯的人数*浮动概率 ) / 总人数 = 预定概率

对每个等候者依次检查生成的随机数（0..1之间的浮点数）是否小于等于当前浮动概率，
是则放行，否则踢掉。具体代码就不写了，不难。
 
上面的代码也是每个人有60%的机会的
循环了Round(S1.Count*0.6)次
每次，每个人都有相同的机会
 
呵呵，用控制循环次数的方法，如果Count=1，概率大于等于0.5，那就必定能进入；如果
Count*概率<0.5，那就永远没机会了——似乎有改进的余地啊:)
另外，这是一个基于队列的问题，允许进入的人必然是按顺序的，不存在后面的人先进入
的情况。我的思路无需对整个队列操作，只需要关注当前元素。当然，对队列进行随机也能
够得到相同的结果，只是个人觉得不够自然:)
 
只需修改Round代码
不妨把你的代码贴出来
 
不要用TstringList
如果公园一天到晚都有人要进来， 并且放进去的人就不管了
代码如何写？?>?
 
>>一天到晚都有人要进来
总数不定？甚好，连浮动概率都免了，固定即可——典型的马尔可夫过程。

{ R为概率，取值范围为0..1之间的实数 }
function CanIn(const R:Double):Boolean;
begin
Result:=Random<=R;
end;

对每个要进入公园的人用这个函数进行检查即可（如果是一家子，应该只能同进同出了吧
——自己斟酌:)）。
 
越来越感到楼上大虾的算法功底了
随即过程都这么xx
 
听课。楼主，给个建议啊，帖子标题改改，让大家以后也知道你到底问的什么算法，也好找答案啊。这类“一个算法的问题”太笼统了，实在不好。
 
还有没有别的办法？？？
 
creation-zy的解答完全符合要求
 
呵呵，真是见识了“先生之风，山高水长”!
请问zy兄都学过或自学过哪些课程，学习
 
>>设置允许通过的人为70%,也就是说算法要实现让排队的一群人中的60％进公园
这个70%和60%是什么关系？是否笔误所致？如果要让特定人群中的部分人进入，可以采用
浮动概率法，列表法亦可。如果对象不定，用固定概率即可。

问题不难，答案亦简单。要说课程，正式学过的只有一本清华的《数据结构》，剩下的就
是在实践中不断的总结提高了。近几年在学习逻辑学和禅学，自觉它们对思维的抽象提升和
对领域概念之间的关系的感受以及掌握有很大帮助。 :)
不知icc兄在何方高就？我在上海，最近在研究基于元模型以及因果模型的可自我描述乃
至自我扩展的系统（发了几个讨论AI的帖子，现在进入实干阶段），苦于合作者太少，不知
论坛里有没有感兴趣的朋友？ :)
My Mail&MSN: creation_zy % sina`com :-)
 
您必须登录或注册才可回复。

Similar threads

L
关于全文检索的算法-->>寻求高效率算法(100分)
回复
7
查看
198
LiChaoHui
L
W
请教一个算法(50分)
回复
4
查看
529
testnet
T
W
一个算法问题,大伙受累给看看(0分)
回复
0
查看
121
windart
W
U
急：如何让数据表按计算字段排序(100分)
回复
8
查看
199
uibest
U
N
谁有关于一个计算公式的算法(50分)
回复
7
查看
122
tbase
T
后退
顶部