最新 | 最热门 | 最高评价

+0  趣题:竞技场里的狮子能否保证抓住最高速度相同的小明?

Tag: 几何 | Uncategorized | 算法 | 趣题 | 极限
admin 发于 2014年08月30日 03:38 | 点击: 2923 | 展开摘要
小明和狮子同被关在一个半径为 10 米的竞技场里,狮子位于竞技场的圆心处,小明则在距离圆心 1 米的地方。两者的最大运动速度都是每秒 1 米。狮子有没有什么必胜策略,使得不管小明怎么跑,它总能在有限的时间里抓住小明?

根据 MathWorld 相关词条的描述,这个问题是由 R. Rado 在 1925 年时提出的。一个经典的“答案”是,狮子只需要始终保持自己与小明在圆盘的同一半径上即可。直觉上看,由于狮子总是处在“内圈”上,因而不管小明跑到了哪里,狮子总能轻松地与小明继续保

查看全文: http://www.udpwork.com/item/13182.html

+0  Penney 的游戏:正所谓后发制人,先发制于人

Tag: 游戏 | Uncategorized | 算法 | 组合数学 | 证明 | 概率
admin 发于 2014年07月10日 21:36 | 点击: 2070 | 展开摘要
让我们来玩一个游戏。连续抛掷硬币,直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者,那么我获胜,你需要给我 1 元钱;如果是后者,那么你获胜,我会给你 1 元钱。你愿意跟我玩这样的游戏吗?换句话说,这个游戏是公平的吗?

乍看上去,你似乎没有什么不同意这种玩法的理由,毕竟“正反反”和“反反正”的概率是均等的。连续抛掷三次硬币可以产生 8 种不同的结果,上述两种各占其中的 1/8 。况且,序列“正反反”和“反反正”看上去又是如此对称,获胜概率怎么看怎么一样。



查看全文: http://www.udpwork.com/item/12723.html

+0  子串复杂度、平衡 01 串与 Sturmian 串

Tag:  图形 | Uncategorized | 算法 | 组合数学 | 证明
admin 发于 2014年06月09日 03:34 | 点击: 2237 | 展开摘要
让我们先从两个小问题开始说起。第一个问题是,是否存在某个无限不循环的 01 串,使得对于任意一个正整数 n ,该 01 串中长度为 n 的子串都有且仅有 n + 1 种?

或许这个问题来得有些突然。让我们慢慢解释一下,这个问题是怎么来的。衡量一个 01 串的复杂程度有很多办法,比方说,我们可以去考察它的“子串复杂度”(subword complexity),即子串的种类有多丰富。我们用 pw(n) 来表示,在一个(有可能无限长的)数字串 w 当中,长度为 n 的子串一共有多

查看全文: http://www.udpwork.com/item/12606.html

+0  保加利亚单人纸牌游戏

Tag: Uncategorized | 算法 | 组合数学 | 证明
admin 发于 2014年03月26日 00:52 | 点击: 1704 | 展开摘要
保加利亚单人纸牌游戏(Bulgarian solitaire)的玩法如下:

取出 45 张牌,然后把它们随意分成若干堆。接下来,从每一堆里各取一张牌,叠在一起形成一堆新的牌。不断这样做下去,如果某个时候桌面上正好有 9 堆牌,并且各堆牌数分别为 1, 2, 3, 4, …, 9 ,你就获胜了。

乍看上去,如果初始局面设定不佳,游戏很可能会陷入某个循环,从而永远无法获胜。然而, 1981 年,丹麦数学家 Jørgen Brandt 证明了,对于任意一个初始局面(包括把所有牌

查看全文: http://www.udpwork.com/item/12070.html

+0  通信复杂度问题:利用特殊机器判断公共元素的存在性

Tag: 复杂度 | Uncategorized | 算法 | 趣题 | 组合数学
admin 发于 2014年03月18日 16:45 | 点击: 1648 | 展开摘要
某个导师要和 A 、 B 两名学生玩一个游戏。导师会把 A 、 B 两名学生分别放进两间小黑屋里,每间屋子里都有一台电脑,这两台电脑之间只有一条通信线路。然后,导师会想一个正整数 n (可能会非常非常大),把它的值告诉这两名学生;再构造出集合 {1, 2, …, n} 的两个子集,分别交给这两名学生。于是,每个人都知道了 n 的值和 {1, 2, …, n} 的一个子集。两人需要合作确定出,他们手中的集合是否包含公共的元素。他们之间交流信息的唯一途径就是那条通信线路,但他们能

查看全文: http://www.udpwork.com/item/12071.html

+0  Thue-Morse 序列与免平方字符串

Tag: 数列 | 递归 | Uncategorized | 算法 | 二进制 | 组合数学
admin 发于 2014年03月07日 17:39 | 点击: 1620 | 展开摘要
字符串 hello 当中连续出现了两个 l 。字符串 prototype 当中连续出现了两个 ot 。字符串 nonsense 当中连续出现了两个 nse 。如果某个字符串中连续出现了两个相同的片段,换句话说这个字符串里面含有形如 XX 的模式(其中 X 代表一个子串),我们就说这个字符串中含有一个“平方”(square)。如果某个字符串中没有平方出现,我们就说这个字符串是“免平方”的(square-free)。

如果只使用两种字符,比方说字符 0 和字符 1 的话,我们只

查看全文: http://www.udpwork.com/item/12072.html

+0  如何让玩家相信游戏是公平的

Tag: 概率与桥牌 | 算法 | 游戏开发
云风 发于 2014年02月10日 14:45 | 点击: 2006 | 展开摘要
去赌场参观过的同学应该都见过那种押大小的骰子游戏。庄家投掷三枚骰子,把骰盅盖住,玩家可以押大或小。开盅后,如果发现三个数字之和大于等于 11 就算大,小于等于 10 就算小。如果你猜对了,庄家就 1 赔 1 算给你筹码;否则输掉筹码。另外,还可以以不同赔率压数字,或压三个相同。

为了保障庄家利益,三个相同的数字算不大不小。从概率上讲,这让长时间内庄家必胜。概率分析见这里。

如果把这个游戏搬到网络上如何呢?(注意:网上赌博在很多国家是被禁止的,这里只做技术分析而已)

如何

查看全文: http://www.udpwork.com/item/11676.html

+0  斜视角游戏的地图渲染

Tag: 算法 | 游戏开发
云风 发于 2014年01月12日 20:48 | 点击: 2329 | 展开摘要
这篇文章是在大半年前, 我们的手游 刚刚做预研的时候写给公司内部分享的。由于这个项目公司不希望在开发阶段对外暴露信息,所以文章也没有在 blog 贴出来。

现在游戏已经上线 就没有消息保密的需求了,我就可以把当初开发时写的一些东西逐步贴出来。

所谓类似 COC 这样的斜视角引擎,在英文社区中叫作 Isometric Tileset Engine。它在早期计算资源匮乏的年代用的很多,后来内存不是问题了后,就很少有人用了。由于没有 Z-Buffer ,这种引擎的绘制次序其实很

查看全文: http://www.udpwork.com/item/11516.html

+0  父与子第二话:算法

Tag: TMT乱弹 | 媒体供稿 | 父与子 | 算法 | 财新enjoy
魏武挥 发于 2013年11月28日 10:00 | 点击: 1550 | 展开摘要
小宝我儿:
上一封信我提到了电脑必须有三样要素:输入、输出和算法。算法是最核心的部分。没有算法,电脑不会知道你的输入究竟该返回什么样的输出。你最近数学期中考考得相当不错,你应该注意到,“应用题”这种题目,本质上考的就是算法。题目本身可以视为是一种输入,你需要给出一个答案,这算是一个输出。但如果你的应用题只写一个答案,而没有计算过程的话,那你这道题会被扣去很大一块分数,即便你的答案是正确的。解题步骤,或者说计算过程,就是你的算法,老师是要看算法滴!
算法这个词,是一个极其复杂的

查看全文: http://www.udpwork.com/item/11230.html

+0  一个 Bump Pointer Allocator

Tag: 读书 | 算法
云风 发于 2013年11月27日 14:34 | 点击: 1895 | 展开摘要
最近抽时间在读 Milo Yip 翻译的《游戏引擎架构》。书还没有出版,我应邀给这个译本写序,所以先拿到了电子版,正在加紧读一遍。全书接近 800 页,我已经读了 600 页左右,希望这个周末可以抽时间读完。

这本书是由顽皮狗的主程之一 Jason Gregory 写的,内容很精彩,Milo Yip 翻译的也相当不错。有很多章节我读的很有共鸣,想先挑一点来写写。

由于作者的主要技术背景是 Console game 开发,而 Console 目前内存非常有限,且没有虚拟内存

查看全文: http://www.udpwork.com/item/11223.html

+0  趣题:庄家的秘密序列

Tag: Uncategorized | 算法 | 博弈 | 趣题 | 组合数学 | 证明
admin 发于 2013年11月20日 03:27 | 点击: 1911 | 展开摘要
    下面是 2013 年 9 月 IBM Ponder This 的谜题。

    A 和 B 在赌场玩一个游戏,他们要协同作战与庄家对抗。游戏一轮一轮地进行,每一轮的规则都是一样的:首先 A 赌 0 和 1 当中的某个数字,然后 B 再赌 0 和 1 当中的某个数字,最后庄家给出 0 和 1 当中的某个数字;如果所有的三个数字都相同,则 A 和 B 获胜,否则庄家获胜。游戏前, A 和 B

查看全文: http://www.udpwork.com/item/11156.html

+0  我对Lamport Logical Clock的理解

Tag: NoSQL杂谈 | Lamport Logical Clock | 算法 | 一致性 | 理论原地 | 分布式
nosqlfan 发于 2013年09月03日 23:45 | 点击: 3483 | 展开摘要
分布式环境中的一致新问题一直是最热门的话题之一,本文主要介绍了其中的一种比较简单的思路:Lamport Logical Clock。本文来自@GoAce 博客文章的投稿。感谢他的分享。

原文地址:http://www.orzace.com/lamport-logical-clock/

建议先看论文原文再来看这篇文章(原文见文章下方参考文献部分),我不会对论文中的各个点都详细说明,只是写一些我自己的想法,帮助理解。

大家都知道,分布式环境下,确定各个事件发生的顺序很重要,

查看全文: http://www.udpwork.com/item/10590.html
|<<<1234567>>>| 一共12页, 143条记录