wOOL's Blog

碎碎念 关于睡前看实分析有助于睡眠一事的确合理 尤其是窝在被窝里 但是 隔壁的老外如果叫得很基情的话 就… 很难想象3个男人在一起为什么会发出那种声音哦 于是我起床 于是我更新blog

关于这个梅氏砝码的问题, 貌似出自1624年出版的Problèmes plaisants et délectabled qui se font par les nombres一书, 作者是法国数学家G·B·德·梅齐里亚克(Gaspard Bachet de Méziriac，1581 – 1655)

问题描述如下

一个商人有一个40磅的砝码，由于跌落在地而碎成4块。后来，称得每块碎片的重量都是整磅数，而且可以用天平和这4块来称从1至40磅之间的任意整数磅的重物。
问这4块砝码片各重多少？

这个问题我所能理解的最为简单的解法如下: 对于每一个砝码, 都有3种状态, 即 放在天平左盘 放在天平右盘 不放在天平上, 那么这个问题就可以被理解为 找到一个三进制的计数系统, 那么每个砝码的重量必须是3的n次幂, n=0, 1, 2, 3 可知 砝码重量为1 3 9 27 和恰好是40且可以组成1~40所有的数

当然上述答案是比较难想的(精妙的解答往往在于此, 想出来很难, 理解起来却容易), 下面有一个比较容易想到的解法, 摘自100 Great Problems of Elementary Mathematics:Their History and Solution

天平的两个秤盘可区别为砝码盘和称量盘，在砝码盘上只放砝码，而在称量盘上放重物外还可附加砝码。若想设法用最少块数的砝码去称量，就要把砝码也放到称量盘上。
假如任意取出几块砝码放在盘上，例如，在一个盘上放 5 磅砝码和 10 磅砝码各一块，另一个盘上放 1 磅、3 磅、4 磅的各一块，那么这些砝码便使前一个秤盘偏重 7 磅。
我们只考虑重物和砝码均为整数，也就是说，重物和砝码的重量均为整数磅。
假如有一系列砝码 A ，B ，C，…，把它们适当地分放在两个盘上，就能称出从 1 到 n 的所有整数磅的重物。如果有一块新砝码P ，它的重量p 超过原有砝码的重量总和n，超过 量为原有砝码重量的总和加 1：
p – n = n + 1，
或者
p = 2n + 1，
那么，把砝码P 加入砝码组A 、B 、C、…之后就能称出从 1 至p + n = 3n + 1 的所有整数磅的重物。
事实上，原有砝码组足以称出所有从 1 至n 磅的重物，为了称出 1 个p + x 或p – x 磅的重物，这里x 表示从 1 到n 的任一个数，把砝码P 放在砝码盘上，再把砝码A ，B ，C，… 分别放在两个盘上，使砝码盘或称量盘上的重量偏重x 磅。
此法成立后，这个题目就容易解答了。
为了使两个砝码A 和B 能称出最多重量，A 必须是 1 磅，B 必须是3 磅，这两个砝码能称出 1，2，3，4 磅的重物。
如果选第三块砝码 C，使它的重量
c = 2 × 4 + 1 = 9 （磅）， 那么用A ，B ，C 三块砝码就能称出从 1 至c + 4 = 9 + 4 = 13 磅的所有重物。
最后，如果选第四块砝码D ，使它的重量
d = 2 × 13 + 1 = 27 （磅），
那么，这四块砝码A ，B ，C，D 便能称出从 1 至27 + 13 = 40 磅的所有重物。
结论：这个砝码的四块碎片的重量分别为 1，3，9，27 磅。

基情貌似结束了 我去睡觉了 困啊…

不是我不想更新部落格啦我现在面临的问题是如果我要写一篇关于课程的东西都会很长很长如果我要碎碎念一下生活又觉得没必要因为我有推特
但是呢为了避免长时间不更新导致更长的时间不更新就像今天我买了夹子和签子整理好这一个月的笔记以免积累的太多以后直接不可整理了一样
我更新一篇吧关于游记的如标题所言我周一去西敏寺拜会了一下牛顿同学后来去看了一下木乃伊总之就是阴气很重的旅游
但是我不想扯牛顿有关的话题当然也不想说那个大白胡子达尔文因为那天我只能远远的看他
今天的主题是莎士比亚我在西敏寺的诗人角看到莎士比亚的纪念碑他指着一本卷轴上面写着一些我不认识的文字
那些不是古英文而是拉丁语出自莎士比亚最后一部戏剧作品被称作莎翁诗的遗嘱
因为解说并没有告诉我这些文字具体是什么所以我今天咕咕了一下发现其出自暴风雨的第四幕第一场

The Cloud capt Tow’rs, The Gorgeous Palaces, The Solemn Temples,
The Great Globe itself, Yea all which it Inherit, Shall Dissolve;
And like the baseless Fabrick of a Vision, Leave not a wreck behind.

入云的楼阁, 瑰伟的宫殿, 庄严的庙堂
甚至地球自身, 以及地球上所有的一切, 都将同样消散
就像这一场幻景, 连一点烟云的影子都不曾留下

这部戏剧最后的收场诗同样有名

Now my charms are all o’erthrown,
And what strength I have’s mine own,
Which is most faint: now, ’tis true,
I must be here confined by you,
Or sent to Naples. Let me not,
Since I have my dukedom got
And pardon’d the deceiver, dwell
In this bare island by your spell;
But release me from my bands
With the help of your good hands:
Gentle breath of yours my sails
Must fill, or else my project fails,
Which was to please. Now I want
Spirits to enforce, art to enchant,
And my ending is despair,
Unless I be relieved by prayer,
Which pierces so that it assaults
Mercy itself and frees all faults.
As you from crimes would pardon’d be,
Let your indulgence set me free.

现在我已把我的魔法尽行抛弃，
剩余微弱的力量都属于我自己；
横在我面前的分明有两条道路，
不是终身被符箓把我在此幽锢，
便是凭藉你们的力量重返故郭。
既然我现今已把我的旧权重握，
饶恕了迫害我的仇人，请再不要
把我永远锢闭在这寂寞的荒岛！
求你们解脱了我灵魂上的系锁，
赖着你们善意殷勤的鼓掌相助；
再烦你们为我吹嘘出一口和风，
好让我们的船只一齐鼓满帆篷。
否则我的计划便落空。我再没有
魔法迷人，再没有精灵为我奔走；
我的结局将要变成不幸的绝望，
除非依托着万能的祈祷的力量，
它能把慈悲的神明的中心刺彻，
赦免了可怜的下民的一切过失。
你们有罪过希望别人不再追究，
愿你们也格外宽大，给我以自由！

“喏, 这便是行业头号软件SAS了, 24万淫民币, 一个子都不能少”
“…”

关于对比 I
安装文件 SAS 3G R 30MB
核心代码 SAS JAVA R C
价格 SAS 24万 R Free

那我为什么要用SAS呢? 答曰: 看上去比较专业 吐槽曰: R看上去更加阴霸

关于对比 II
导入CSV文件 显示数据 显示二维图 进行线性回归计算
SAS代码
proc import datafile="d:\doc\data.csv" out=mydata dbms=csv replace;
getnames=no;
proc print data=mydata;
proc plot data=mydata;
plot VAR2 * VAR1;
proc reg data=mydata;
model VAR2 = VAR1;
run;

R代码
mydata = read.csv("d:\ \doc\ \data.csv", header=FALSE)
mydata
plot(mydata)
mylm = lm(V2~V1, data=mydata)
summary(mylm)

我恨分号我恨分号我恨分号, R更加UNIX, 大小写敏感, 在win下需要双斜线, 很莫名其妙的一点, 如果csv文件的结尾不是一个空行的话, R会有一个warning说最后一行不完全, 但不影响数据获取, SAS则没有这个问题

关于对比 III
折磨一下吧
数据量10 million, CSV文件体积244 MB(其实我开始生成的是100 million条, 2.38 GB的庞然大物, 结果发现我电脑吃不消), 这些数据大概是一个y=0.123456789x+987.654321的回归线, 每个值的误差在[-13,13]内

SAS的表现是7s读取完后瞬间算出y=0.12346x+987.65698
而R在吃掉800MB读了N分钟后读完数据然后计算, 内存占用瞬间飙升1.X G然后提示超过最大可用内存, 罢工了, 杯具啊

当年在选笔记本的时候, 一定要买NV卡的原因就是NV有CUDA, 而我的陈旧的GeForce 7300并不支持这个功能
简单的说, CUDA是一个C/C++语言的编译器, 由她编译出来的程序可以利用GPU强大的浮点运算能力, 提高运行效率
目前比较常见民用级的应用主要集中于视频压缩
当然, 在金融计算这样的领域, 它的价值应该得到更好的体现, 一堆GPU连起来起来比N堆CPU连起来还要强N多的样子

在Windows 7平台下搭建CUDA开发运行环境还是非常简单的(相对于Linux), 首先在NV CONTROL PANEL -> SYSTEM INFORMATION -> COMPONENTS 下看看CUDA的Driver版本号是多少, 我的是显卡是Geforce GT 240M, 目前可以用的驱动带的CUDA Driver版本是2.2, 好像多数桌面显卡都有2.3驱动支持, 在确认有CUDA支持的驱动装好后, 依次安装对应版本的CUDA Toolkit 和 CUDA SDK (http://www.nvidia.com/object/cuda_get.html), 然后安装Visual Studio, 需要注意的是, 虽然Visual C++ Express可以支持CUDA, 但是由于其默认不支持64bit编译, 所以需要下载安装.Net Framework和替换, 所以还是推荐安装Visual Studio, 我安装的版本是2008 Pro, 安装的时候务必选择Full安装, 以保证64bit compiler装上, 安装完后安装CUDA VS Wizard (http://sourceforge.net/projects/cudavswizard/), 这样可以在New Project里面看到CUDAWinApp, 至于代码高亮, 发现目前只支持VS 2005, 反正我一般都是在Notepad++里写代码, 然后扔VS里调试编译.

简单安装流程:
1.安装最新显卡驱动并查看CUDA DRIVER驱动版本
2.下载对应的CUDA Toolkit 和 CUDA SDK
3.Full安装Visual Studio
4.安装CUDA VS Wizard

注: 安装好CUDA SDK后可以运行C:\ProgramData\NVIDIA Corporation\NVIDIA CUDA SDK\bin\win64\Release中的程序以测试是否安装了正确的驱动和Toolkit

搭建好CUDA的平台后自然要测试一下, 刚好拿最近在看得Monte Carlo Method试试, 几乎所有的Monte Carlo Method入门介绍都会提到用这种方法计算pi, 其C语言的核心代码非常简单

int i, pi=0;
double x, y, area;

area=4.0*(double) pi/(double) i;
printf("%f \n", area);

CUDA是支持标准的C语句的, 但是它有一些自己的.h文件, 比如cutil_math.h (对应math.h)
进行100万次循环, 纯C和CUDA运行时间分别为56ms和51ms
貌似没有明显差别, 下次打算拿更复杂一些的代码来测试一下, HOHO~