最近在看《编程之美》，为找工作面试做准备。该书中2.20程序理解和时间分析一题没有给出解答，所以简单写一下我自己的答案。
题目如下：
阅读以下C#代码，回答问题：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| using System;
using System.Collections.Generic;
using System.Text;
namespace FindTheNumber
{
class Program
{
static void Main(string[] args)
{
int [] rg =
{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,
18,19,20,21,22,23,24,25,26,27,28,29,30,31};
for(Int64 i = 1; i < Int64.MaxValue; i++)
{
int hit = 0;
int hit1 = -1;
int hit2 = -1;
for (int j = 0; (j < rg.Length) && (hit <= 2); j++)
{
if((i % rg[j]) != 0)
{
hit++;
if(hit == 1)
{
hit1 = j;
}
else if (hit == 2)
{
hit2 = j;
}
else
break;
}
}
if((hit == 2) && (hit1 + 1 == hit2))
{
Console.WriteLine("found {0}", i);
}
}
}
}
} |
1> 这个程序要找的是符合什么条件的数？
2> 这样的数存在么？符合这一条件的最小的数是什么？
3> 在电脑上运行这一程序，你估计要多长时间才能输出第一个结果？时间精确到分钟(电脑配置：单核CPU2.0GHz，内存和硬盘资源充足)
我的解答：
阅读全文…
最近在实现PLSV，写了一个matlab的版本，效果却远没有原作者论文上说的好。
给作者发信索要代码，答曰：本人已在公司工作，出于保密，不能给你代码，不过在这个网页(需翻墙)上有别人写的代码，你可以看一看。
看了那个blog上的代码，是一个日本人写的perl代码，一看代码风格很严谨，遂认为是精品，于是慢慢品读，但因为我是头一次读perl的代码，所以边看边查，做了一点记录。
代码太长，附在文章最后吧，先是我做的一点记录：
#!/usr/bin/perl
这一行是Linux类系统下脚本的第一行，指定脚本执行环境，python也有。
use
导入模块，类似java的import
定义变量，直接使用一个$符号，比如$a，就表示定义了一个名为a的标量。这个不管是int，float，string，char……一律使用这个表示。
定义数组，直接使用符号@，比如@array，表示定义一个名为array的数组。基本上和上面的差不多，但是perl中好像是没有直接的二维数组的定义。
定义Hash，使用符号%，比如%hash，表示定义一个名为hash的哈希结构。哈希结构基本上在前期用的不多，在后面的时候，可以和数组组合成比较强大的结构体。
阅读全文…
今天看论文的时候看到这样一个名词：anytime algorithm，在wiki上查了一下，做一个简单的介绍。
大多数的算法在输入确定时，需要一个确定的时间进行一系列确定数量的计算操作，然后才返回一个确定的答案。但是有的时候，用户希望能够提前结束算法，例如重新分配计算资源等。这种情况下大多数算法不能提前结束，否则得不到什么有用的信息。
而anytime algorithm, 有时候也叫做interruptible algorithm, 从其名字上就可以知道，是可以随时打断的，打断之后算法返回一个最终解的近似解，该近似解的好坏依赖于已经完成的计算量。anytime algorithm 通常还要能保存最后一次得到的解，以便在得到更多的计算时间时，可以在当前解的基础上继续计算更精确地解。
阅读全文…
今天在《Programming Pearls》上看到这样的问题，有一个非降序数组d[]，包含1000个数，可能有重复的数，求数K在数组中最靠前的下标。如果找不到的话，结果为-1。
这种类型的二分之前已经写过不下数十次了，于是我信手敲下如下代码：
[code=cpp]
l = 0; r = 999;
ans = -1;
while(l <= r)
{
mid = (l+r)/2;
if(d[mid] >= k)
{
ans = mid;
r = mid-1;
}
else
l = mid+1;
}
[/code]
上面这段代码是我写了很多次的二分之后总结出来的，因为二分的很多其他写法在不同的条件下稍不注意就会出现错误。这里说的不同的条件包括：求满足条件的最小的值； 求满足条件最大的值等等。
而上面的代码可以通用我到目前为止遇到的所有情况(仅仅是改变一下ans = mid; 的位置即可)，所以一直这么写二分。
但是看了书上给的代码，觉得不但也能适合所有情况，而且很好验证其正确性：
阅读全文…
