以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  请教有关 随机算法  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=60238)


--  作者:xpan
--  发布时间:3/21/2008 10:19:00 AM

--  请教有关 随机算法
遇到了几道题,怎么想也想不出来,请大家帮忙:

1。假设有n个学生,他们都得到了自己的成绩(满分为100),而并不希望把自己的成绩透露给别人,现在他们希望能够在不知道他人的分数的情况下计算出所有人的平均分,并且不能借助第三方的帮助。设计一种算法,能够在无法判定其他任何一位学生成绩的前提下计算出所有人的平均分。


2。假设有一面很长很长的墙(两头都无限延伸),你在墙的一面,并且知道在墙的某个地方有一个洞,让你可以钻到对面去,但是你并不知道那个洞是在你的左面还是右面,也不知道这个洞离你有多远,设计一种随机算法,使得预计要走的路程最多不超过你离那个洞的距离的7倍。

3。与2同样的问题,不过这次的算法的预计要走的路程最多不超过离洞距离的7-a倍,a是constant。


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
31.250ms