QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1313|回复: 0
打印 上一主题 下一主题

[其他经验] Let’s Play Games!

[复制链接]
字体大小: 正常 放大

86

主题

13

听众

160

积分

升级  30%

  • TA的每日心情

    2016-4-25 17:12
  • 签到天数: 22 天

    [LV.4]偶尔看看III

    自我介绍
    萌萌哒

    社区QQ达人

    群组2015国赛优秀论文解析

    群组2015年国赛优秀论文解

    跳转到指定楼层
    1#
    发表于 2016-4-8 14:43 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    Let’s Play Games!Posted on 2011-03-09 13:43 苍梧 阅读(4529) 评论(6) 编辑 收藏# e" t, q, V2 d2 K  q8 e3 [& p% a
    1
      Alice和她的同学Bob通过网上聊天商量明天早晨谁去教室打扫卫生的事,Bob说:“我在桌上放了一枚硬币,你猜一下,是正面朝上还是反面朝上?如果猜对了,我去扫地。如果猜错了,嘿嘿…。”
          Alice显然不会同意,担心自己不论猜正面还是反面,Bob都说她错了。
    分析:
    看到这题,我的第一反应是葛优的“分歧终端机”。(╯▽╰)
    最关键是要找到一种方法使得Alice给出她的猜测后Bob不能抵赖。一种参考答案如下:
    . ~7 h' S5 }& p& l0 J
    1.    Bob与Alice商量选取一个哈希函数hash(),hash()的值域应该尽可能大。
    2.    Bob选择一个大随机数x,计算hash(x);通过网络告诉Alice hash(x)的值
    3.    Alice告诉Bob对x的奇偶性猜测(偶数表示“正面”;奇数代表“背面”)
    4.    Bob告诉Alice x的值
    5.    Alice验证hash(x)
    ) i- C  u. a- ]5 j& S' {, ^
    但是这样也不是100%能够防止Bob作弊的。Bob如果想抵赖,那么他应该事先找出两个大整数,一奇一偶,而且哈希函数值相同。(抵赖的难度就取决于hash函数的选择了)

    # ~8 @: {  Z- Q6 G0 k4 H! ^
    ) o! b  @2 m* s6 k5 j3 ~1 g* z) r, m% S4 ]$ x0 a5 d- G
    2
           Alice与Bob相爱了,他们想通过书信来商量私奔的事。暗恋Alice的邮递员Chuck经常利用职权之便偷看他们之间的通信。Alice与Bob各有一把锁和只能打开自己那把锁的钥匙。另外Bob还有一个能够上锁的铁盒子。问如何防止Chunk偷看他们之间的通信?
    分析:
           Bob将情书放进铁盒,用自己的锁给盒子上锁。Alice收到后给盒子加上自己的锁,然后将盒子寄回给Bob。Bob收到后将自己的锁取下,再将盒子寄给Alice。Alice收到盒子后取下自己的锁就可以看信了。
    3
    某人第一天由 A地去B地,第二天由 B地沿原路返回 A 地。问:在什么条件下,可以保证途中至少存在一地,此人在两天中的同一时间到达该地。
    分析:
    假如我们换一种想法,把第二天的返回改变成另一人在同一天由B去A,问题就化为在什么条件下,两人至少在途中相遇一次,这样结论就很容易得出了:只要其中一个人在另外一个人到达之前出发,则两人必会在途中相遇。
    4
           一条长度为L的竹竿上分布着N个蚂蚁,已知所有蚂蚁的行进速度都是v,两只蚂蚁碰头后会掉头走,给定初始时刻蚂蚁的行进方向。问如何计算所有蚂蚁离开竹竿要多长时间?
    分析:
           最直接也是最笨的方法就是对每个蚂蚁的行动进行模拟。这样谁都能想到的答案当然不是出题者想要的了。
           换个角度想,2个蚂蚁碰头后掉头走实质上是等价于它们碰头后擦肩而过继续赶路。(如果你将所有蚂蚁都看作一样的话)
           好了,这样一想,过程简单多了。对于每个蚂蚁,都假设竹竿上只有它一个蚂蚁,然后计算出它离开竹竿的时间。所需时间最长的蚂蚁所耗的时间就是题目的答案了。
    5
    一对情侣一起去买了一块饼
    女生吃了3/7块饼
    男生吃掉剩下的4/7块饼

    + @7 v! b# S: |' d2 P
    男生比女生多出了4.5元
    请问这块饼多少元?
    分析:
      4.5元(有回答31.5的么?举个手?)
    参考资料:
    [1]《编程之美》小组.《编程之美》
    [2] matrix67. 密码学协议举例(五):两个人能够在电话上打牌吗?
    + w4 Q4 y& ~" W, j
    ' R2 B; a9 F( s

    " v0 z6 x( x+ q( C( Z, D! _6 ]: h5 }1 T3 Q1 Z; m
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-7-11 18:32 , Processed in 0.359140 second(s), 55 queries .

    回顶部