分类：'编程随笔' 的所有文章

关于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 条评论

贴代码 - 把文件夹压平

使用方法：在Windows下，保存该代码为flat.py，将其放到某个系统PATH所在目录下，并将.py加到系统PATHEXT变量中，然后打开命令行切换到某个目录下，输入flat，按指令行事。

注意改代码会自动删除当前目录下所有文件夹，请慎用！

Python语言: 把文件夹压平 flatten folders
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# –filename:flat.py–
#
# 有时候需要把某个文件夹及其子文件夹下面的照片和视频通通导出到一个文件夹里
# 也就是把这个文件夹“压平”(flatten)
#
# 由于我的照片和视频文件名是不重复的，所以对于重复文件名的处理就没有做
#
#
print "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
print "!!                                              !!"
print "!!     NOTICE! this will DESTROY your folder!   !!"
print "!!                                              !!"
print "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"

secret = raw_input("Enter 123abc to continue:")
if secret != "123abc":
    print "you Entered " + secret, "WRONG answer!"
    print "Aborted!!!"
    import sys
    sys.exit()

import os
from os.path import join, getsize
for root, dirs, files in os.walk('.'):
    if root == ".": continue
    for file in files:
        cmd = 'move "' + join(root,file) + '" "' + file + '"'
        print cmd
        os.system(cmd)

for dir in os.listdir('.'):
    if not os.path.isdir(dir): continue
    cmd = "rd /s/q " + dir
    print cmd
    os.system(cmd)

  • Share/Bookmark
十一月 17th, 2009 | 分类: 编程随笔 | 1 条评论

超级好用的日志(文本)查看和分析工具 - TextAnalysisTool.NET

TextAnalysisTool.NET

就要离开现在的公司了，收拾一下自己以前整理的资料，发现珍珠一枚：TextAnalysisTool.NET

这是我用过的最好的文本查看分析工具，特别是你经常查看某一种固定模式的文本/日志的时候，比如说测试程序结果，整体Build结果等等。

功能描述如下：

  • 针对超大型文本设计和优化过，打开文件速度超快，却只消耗很少的内存
  • 可以对各种文本进行过滤并加色，这个功能在显示Pass和Fail结果的时候很好用，不同的结果可以标上不同的颜色
  • 过滤列表可以保存和加载，这个就更加方便了，如果有好多人经常查看同一个格式的文本，只要找个人做个过滤器配置文件，共享给大家就行了

    • 其他功能很简单，这里不说了，自己试试吧 :D 下载链接在此

    • Share/Bookmark
    十一月 13th, 2009 | 分类: 编程随笔 | 7 条评论

    Buffer Overflow导致另一个函数被调用

    我记得以前MS的林斌到学校演讲，演示了一个Buffer Overflow，冲掉了函数返回地址结果改成了另一个函数。

    今天一时兴起想做个demo，试了一个多小时，终于成功了

    下面这份代码编译以后执行的时候会调用到bad函数，呵呵

    C++语言: Buffer Overflow导致另一个函数被调用
    //搞定了，呵呵
    //具体参见：http://en.wikipedia.org/wiki/Stack_buffer_overflow
    #include <stdio.h>
    #include <string.h>

    void bad() {
        printf("Oh shit really bad~!\r\n");
    }

    void foo() {
        char overme[4] = "WOW";
        *(int*)(overme+8) = (int)bad;
    }

    int main() {
       foo();
    }

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

    • Share/Bookmark
    十月 26th, 2009 | 分类: 编程随笔 | 3 条评论

    在题库发芽网上试用了Google Ajax Search API

    fayaa_tiku_and_google_ajax_api

    题酷发芽网在每个题目页面的右侧边栏底端都可以看到相关题目，这是最近对Google Ajax Search API的一次尝试。

    插播一条广告：

    欢迎订阅题酷发芽网的两个RSS： 最新题目 & 最新回答

    关于Google Ajax Search API，不多说，自己看链接里面的内容，或者简单理解为：让你的网站都可以拥有Google那样快的搜索速度！

    当然，前提是：Google索引了你网站的内容，而且是最新的，这个好办，做个sitemap就行了，有了这个，Googlebot抓的很勤劳的，Django自带了一个sitemap组件，很好用

    另外，在题库发芽网的首页上，你可以看到右上方有个小小的搜索框，在里面输入“球”然后回车，你就来到了题酷搜索结果页面里面，上面啥也没有，但是在右侧边栏最下面，你可以看到许多结果。

    你还可以试试在那个Google搜索框里输入想搜索的内容，呵呵实时相应的哦。

    另外： 如果你在题库发芽网上发过帖子的话，可能会注意到那里也有Ajax应用 - 比如你可以输入“二叉树”，然后按Tab把焦点挪到内容输入框，就会出现已经存在的相关问题列表，主要用来防止重复发文。

    这个也是仿Stackoverflow的功能，Stackoverflow针对的是英文内容，只要mysql端支持full text search就可以做到，但是对于中文内容来说，还需要分词以及mysql中文匹配插件，做起来很费劲，就暂时用Google Ajax API替代了。

    最后，关门，放代码：

    JavaScript语言: 打算用在题库发芽网中的：基于Google API搜索同类内容
    /*
    *  How to load jQuery and then use the Search API with it.
    */

    google.load("jquery", "1");

    // on page load complete, fire off a jQuery json-p query
    // against Google web search
    function OnLoad(){
      var url = "http://ajax.googleapis.com/ajax/services/search/web?q=华容道游戏%20site:fayaa.com/code/view/&v=1.0&rsz=large&callback=?";
      $.getJSON(url, function (data) {
        if (data.responseData.results &&
            data.responseData.results.length > 0) {
          var results = data.responseData.results;
          var html = "";
          for (var i=0; i<results.length;i++) {
            var r = results[i];
            html += '<a href="' + r.url + '" title="' + r.content.replace(/(<([^>]+)>)/ig,"") + '">' + r.title + "</a><br/>";
          }
          $('#content').html(html);
        }
      });
    }

    google.setOnLoadCallback(OnLoad);

    • Share/Bookmark
    九月 14th, 2009 | 分类: 发芽网开发记录, 编程随笔 | 1 条评论

    « 上一页 — 下一页 »