用异或求头上的数字

六月 10th, 2010

话说有一个法官，他的监狱里关着100名犯人。。有一次闲着没事呢，就在一次放风的过程中跟着100名犯人说：我现在给你们每人发一顶帽子，帽子上有一个数字，数字从1-100都有可能，而且可以重复，每个人一个一个过来领帽子～领完帽子以后，每个人需要在一张纸条上猜一个数字，如果100个犯人中只要有一个人猜出他头上的帽子上的数字，则100个人全部得到释放，否则全部犯人将被杀死。在发帽子以后，犯人之间不得有任何形式的交流。现在的问题是：这 100个犯人应该商讨一个什么样的策略保证其中一个人必然能猜的他头上的数字。也就是说，发帽子以前犯人是可以讨论，题目即寻找一个最佳策略保证其中一个人必然能猜的他头上的数字。

游戏前，大家按某种顺序给所有人从1到16依次编号。游戏开始后，每个人把自己能看到的15个数与自己的编号一起异或起来，在猜数时报出这个异或的结果。假设这16个数异或起来的结果为X（显然1 ≤ X ≤ 16），第i个人身上的数记为A_i，那么他猜的数其实就是X xor A_i xor i。因为根据上面的知识X xor A_i就是出除自己外另外15个人背上数的异或值，那么，编号为X的人（此时i等于X）报出的数恰好就是他背上的那个数。因为1到16异或起来的值是小于16的，所以总存在一个i与X相等

Tags: 异或位运算法官 Posted in 数学

让android支持stl

六月 1st, 2010

环境：ndk，stlport下载stlport的地址：http://www.anddev.org/code-snippets-for-android-f33/stlport-for-ndk-1-6-t9132.html#p29939

cd stlport/build/lib

1.export NDK_DIR NDK_HOST

2.ln -sf ${NDK_DIR}/build/prebuilt/linux-x86/arm-eabi-4.2.1/bin/arm-eabi-c++ /bin/arm-linux-c++

3.modified android.mak

--sysroot=$(NDK_DIR)/build/platforms/android-1.5/arch-arm \

--sysroot=$(NDK_DIR)/build/platforms/android-8/arch-arm \

4.modified stlport/stlport/stl/config/_android.h

//inline void* operator new(size_t, void* p) { return p; }
//inline void* operator new[](size_t, void* p) { return p; }

inline void* operator new(size_t, void* p) { return p; }
inline void* operator new[](size_t, void* p) { return p; }

5.modified build/Makefiles/gmake/lib/gcc.mak

STDLIBS := -Wl,--whole-archive -lsupc++ ${_LGCC_EH} -Wl,--no-whole-archive ${_LGCC_S} -lpthread -lc -lm

STDLIBS = ${_LGCC_S} -Wl,-Bstatic -lthread_db -Wl,-Bdynamic -lc -lm

6.make -f android.mak

Tags: android stl ndk Posted in android

两个博弈论的数学游戏

五月 25th, 2010

1.蒙提霍尔问题假設你正在參加一個遊戲節目，你被要求在三扇門中選擇一扇：其中一扇後面有一輛車；其餘兩扇後面則是山羊。你選擇了一道門，假設是一號門，然後知道門後面有甚麼的主持人，開啟了另一扇後面有山羊的門，假設是三號門。他然後問你：「你想選擇二號門嗎？」轉換你的選擇對你來說是一種優勢嗎？

解答：把选择的和没选的当作一个整体，概率分别是1/3,2/3，然后当主持人开启一扇门之后，转换后可以使的概率变成2/3或者，选择山羊1，概率1/3,转换是优势选择山羊2，概率1/3，转换是优势选择汽车，概率1/3，转换不是优势所以选择转换的概率是2/3参考：

http://en.wikipedia.org/wiki/Monty_Hall_problem

2.海盗博弈有五个理性的海盗，A, B, C, D和E，找到了100个金币，需要想办法分配金币。海盗们有严格的等级制度：A比B职位高，B比C高，C比D高，D比E高。海盗世界的分配原则是：等级最高的海盗提出一种分配方案。所有的海盗投票决定是否接受分配，包括提议人。并且在票数相同的情况下，提议人有决定权。如果提议通过，那么海盗们按照提议分配金币。如果没有通过，那么提议人将被扔出船外，然后由下一个最高职位的海盗提出新的分配方案。海盗们基于三个因素来做决定。首先，要能存活下来。其次，自己得到的利益最大化。最后，在所有其他条件相同的情况下，优先选择把别人扔出船外。

解答：直觉上认为，A海盗会给自己分配很少，以避免被扔出船外。然而这和理论结果相差甚远。让我们反过来看：如果只剩下D和E，D给自己100个金币，给E 0个。因为D有决定权，所以分配达成。如果剩下三个人（C，D和E），C知道D下轮会给E 0个金币，所以C这轮给E 1个金币，让E支持自己以使得提议通过。因此如果剩下三个人，结果是C：99，D：0，E：1。如果B, C, D 和 E 剩下， B 知道上述结果。所以为了避免被扔出去，他只需要给D 1个金币，因为他有决定权，只需要D的支持就足够了。因此他会提议 B：99， C：0， D：1，E：0。有人可能想到提议B：99， C：0， D：0，E：1，因为E知道即使把B扔出去，也不会得到更多了。但由于海盗会优先把别人扔出去，所以E会选择杀死B，然后仍然可以从C的提议中得到相同金币。假设A知道所有的一切，他就能选择让C和E来支持他，提议变成：A: 98金币B: 0金币C: 1金币D: 0金币E: 1金币同样的 A：98，B：0，C：0，D：1，E：1 或者其他的提议都不是最好的，因为D会选择把A扔出去，然后从B那里得到相同的金币。

参考：http://en.wikipedia.org/wiki/Pirate_game

Tags: 博弈蒙提霍尔海盗 Posted in 数学

自定义二进制数据格式

五月 13th, 2010

数据分为三种：

1.标量，scalar，其他的数据都是由标量组成

2.序列，数组

3.对象，树形结构

相对应的，为了方便描述，我们定义两种结构：unit,chunk

unit

最小的数据单元:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ……………………
+---------------------------------+------------------
|length | data
+---------------------------------+-----------------

长度为length两字节，能容最大长度是64k

描述scalar,标量，也就是普通的数据对象，比如id，帖子标题

struct{
2bytes length//长度
byte[length] data//数据内容
}

chunk

由若干unit组成的(除头信息块)特定功能的数据块：
flag(1byte)+type(1byte)

head信息块[必选]:flag:0xD4
约定：0xD4+1byte类型
1byte类型:
0x0:reserved
0x1:分类
0x2:地标
0x3:过滤
0x4:配置
0x5:帖子（列表+详情）
0x6:列表
0x7:详情

struct{
byte flag//标识位
byte type//数据类型
}

flag(1byte)+length(4bytes)+data(若干unit)
data数据块[可选]：0xD5
meta数据块[可选]：0xD6
config数据块[可选]：0xD7
error数据块[可选]:0xDE ，flag(1byte)+data：unit(长度(2bytes)+错误码)+unit(长度(2bytes)+错误详情)
其他扩展数据块[可选]

struct{
byte flag//标识位
4bytes length//长度
byte[length] data//数据内容(若干unit)
}

note:校验码，考虑平台的特殊性，对chunk可增加校验码[optional]