分类：'原创精选' 的所有文章

关于25马问题的思考

题酷发芽网上的一个题目 “25匹赛马血拼Top5”：

有25匹马，共5个跑道，不用任何工具，请问

  1. 用几场比赛可分出前3名？
  2. 几场比赛可以分出前5名？
  3. 几场比赛可以给所有赛马排名？

Solrex Yang同学写了一篇文章比较全面的分析了这个问题，虽然后面有人指出其推理过程中的问题，但是可以看出主要的思想还是正确的，那就是尽量利用已经存在的信息。

今天无意间翻信翻到这个问题，突然想到，这其实是个可以编程求解的问题，而且跟我已经搞定的猜数字游戏求解过程很像

几点零星的想法，等到有时间再来细化：

1. 几次赛马以后，实际上生成了一个逻辑排序的图，每一次赛马，都要尽可能的把这个图变成一条**线**
2. 贪心的标准可以是：消除尽量多的分支
3. 每一步采用贪心算法，不一定能做到全盘最优 - 我求解猜数字游戏的时候就遇到过，贪心总是会有3、4个需要8步的，而全局最优却可以做到都在7步以内
4. 如果只是前三名，或许贪心算法得到的结果跟全局最优是一致的
5. 全局最优的算法，粗略一想，需要25!的计算量。要尽量减少计算的话，就要考虑做一些cache，滤掉重复性的计算，或许需要用到动态规划
6. 如果只是要求前三名，全盘最优应该很容易做到

先写这么多，等有时间再来写程序验证。。。

  • Share/Bookmark
十一月 22nd, 2009 | 分类: 原创精选, 编程随笔 | 1 条评论

maximum command line parameter length? 命令行参数可以有多长？

同事问了一个相关的问题，以前猜测是1024，验证了一下，居然是8196

Python语言: maximum command line parameter length? 命令行参数可以有多长？
#how long can a command line parameter have?
#
# Directly answer is 8196 on Window7(not sure about other platform)
#
#It’s easy to write a script to repro it:
#1. In one script, output the parameter it got, say script#1
#2. In another script, recursively execute script#1 and increase parameter step by step,
#   capture the output, see if you have the same with the parameter you give
#
# Usage: python test2.py
#        then you got the result
#        (if it's 10000, then adjust "end" variable below)
#
#— test.py —
import sys
print sys.argv[1]

#— test2.py —
import sys,os
param = 'a'
start = 0
end =  10000
while start < end: #binary search to speed up
    mid = (start + end) / 2
    param = 'a' * mid
    cmdline = 'test.py ' + param
    out = os.popen(cmdline).read().rstrip()
    if param == out:
        start = mid + 1
    else:
        end = mid - 1
    print len(param)
print "\nMax Command Line Length=", start

#What I got on Window7 is: 8153
#  considering cmd.exe starts with "C:\\Windows\\system32\\cmd.exe /c test.py "
#  then the maximum is about 8196

  • Share/Bookmark
五月 20th, 2009 | 分类: 原创精选 | 2 条评论

数独游戏和求解程序上线了 - 游戏发芽网

先广播一下：

发芽网的数独游戏上线啦…啦…啦啦啦…！

网址： http://fayaa.com/youxi/sudoku/

游戏发芽网的在线数独

智取华容道上线一段时间以后，数独游戏就开始做了，直到几个月之后的今天才终于做完。
外观同样还是木纹式的，同样包含在线求解和过关过程回放。
不过相对于智取华容道，还添加了数独分类和自定义数独提交的功能，可以自由添加分类和数独开局。

目前已知最难得是这关: http://fayaa.com/youxi/sudoku/1070/

我建立了10个分类如下： (所有分类点这里)
* 循序渐进108关: 每一关都比上一关更难一些，可谓从入门到精通系列:D
* 步步高1:心有灵犀一点通: 每一步都有确定的数字可以选择，就看你找不找得到了
* 步步高2:两小无嫌猜: 中间会有某些步骤，需要在两个选择中做决断、尝试
* 步步高3:天将降大任于斯人: 需要做的决定越来越多，还好至多是二选一，还好还好
* 步步高4:不尽长江滚滚来: 在不断的、来回往复的试错中寻找出路
* 步步高5:长风破浪会有时: 玩到这个境界，就开始考虑各种技巧，需要更多的训练
* 步步高6:一览众山小: 回头看以前的境界，觉得现在比以前思维熟练太多了
* 步步高7:欲与天公试比高: 经过一段境界的巩固以后，觉得自己已经无敌了，那就来试试吧
* 步步高8:高处不胜寒: 经过摸爬滚打，现在更加慎重的面对，突然发现，已经超出平均线好多
* 步步高9:蜀道难，难于上青天: 没有兴趣，是坚持不到这里的 - 这已经不是休闲了，而是在挑战自我

Ｑ：那么多数独站点还不够吗？
Ａ：那些站点没有一个是我的，想添加功能的时候不是很方便
　　而且，数独求解可显示有没有唯一解、显示难度指数
　　而且，没有一个能够记录我的过关过程，也没有我喜欢的分类功能
　　而且…

好吧，理由不充分，其实主要目的，是为了写一本书，暂不透露其时间。。。因为可能写不完

附：
网页早就完成了，这期间主要是想做一个快速的数独在线求解以及一个单文件(html+js)的数独求解程序
优化cpp代码的时候确实学到很多东西，现在已知的最难数独题目已经能够控制在1秒以内
以后单独写文章来说这个优化的过程

  • Share/Bookmark
四月 16th, 2009 | 分类: 原创精选, 发芽网开发记录 | 12 条评论

Google Trends: “写代码” 和 “性感”是严重冲突的 - code & sexy

灵感和光荣属于：Matrix67

下图说明：
1. 程序员周末加班的还是少数
2. “写代码” 和 “性感”是严重冲突的，女士们请慎重择业…

工作时间和周末，大家都干些啥？看看Google Trends是怎么说的：
(注：蓝色是“code”, 红色是”sexy”，点击图片看详细结果）
code and sexy search trends on google


其他：
(注：这是javascript/perl/mysql/c#的搜索数量趋势，哪天是周末一目了然，点击图片看详细结果）
programming trends



(注：这是office和mp3的搜索数量趋势，冲突也很明显啊，点击图片看详细结果）
office and mp3




为什么程序总是有bug？看看exception和catch的搜索数量趋势 :)
exception and catch

  • Share/Bookmark
四月 02nd, 2009 | 分类: 原创精选, 思维像发情的猴子 | 5 条评论

晒一晒发芽网的本地开发环境

发芽网断断续续写了大半年了，现在还只有稀疏的几个子站：代码发芽网，工具发芽网，游戏发芽网和发芽网论坛
每个子站只有很简单的功能，虽然没有达到预期的目标，但还帮助了一部分人，也算一丝欣慰

更多的收获，在于这些开发过程中积攒的经验，写网页和写单机程序很不同的思想，真正体验过，才知道是多么的不同，又有哪些可以借鉴。

其中一项收获就是：vim和命令行使用起来更熟了，还有一些工具，感觉还不错，拿出来晒一晒。
—————————-
发芽网本地开发环境配置
—————————-
操作系统: Windows XP SP2

编辑器：Gvim + Ctags，参见 配置好的VIM 7，做个包，方便自己随处下载 和 我的_vimrc文件配置，还算不错
（其实还有notepad，通常我会用它暂时保存一些内容，或者把从网页上面copy下来的内容消除格式）

数据库：InstantRails上面抠出来的Mysql，现在喜欢用WampServer（Apache + mysql + php可移植包）

Web服务端：一开始用InstantRails上面的Apache，后来停用了一段时间，又因为调试PHP恢复了

浏览器：Firefox + IE Tab插件 + IE7 + ie6eolas

调试：Javascript调试我用的是Firefox扩展：Web Developer和Firebug，另外加上了IE Developer Toolbar
（Fiddler前两天下载下来了，还没用过）
（赞一下Firebug，真是我见过的最好用的html/css/javascript调试器，但是还是有些bug，有时候报错位置不准）

本地操作：命令行，参见：windows命令行(Command Prompt / Console)字体设置 和 随时随地进入命令行

远程登陆：pietty，可设置utf8编码所以显示中文没问题，登录到Bluehost很好用，比Putty好用一些

文件上传：Filezilla

文件比较：windiff 和 winmerge

版本控制：svn和自己写的定期备份脚本

服务端配置：bluehost，参见：Bluehost Django fastcgi配置, 静态(static)文件处理，以及本站其他的相关文章

还有一些的，以后再整理。

  • Share/Bookmark
三月 04th, 2009 | 分类: 原创精选, 发芽网开发记录 | 4 条评论

下一页 »