存档

‘算法’ 分类的存档

《编程之美》2.20程序理解和时间分析

2010年9月1日 madongfly 1 条评论

最近在看《编程之美》，为找工作面试做准备。该书中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，内存和硬盘资源充足)

我的解答：

阅读全文…

分类: 程序设计, 算法, 计算机 标签: ,

Anytime algorithm 任意时间算法

2009年11月26日 madongfly 没有评论

今天看论文的时候看到这样一个名词：anytime algorithm，在wiki上查了一下，做一个简单的介绍。

大多数的算法在输入确定时，需要一个确定的时间进行一系列确定数量的计算操作，然后才返回一个确定的答案。但是有的时候，用户希望能够提前结束算法，例如重新分配计算资源等。这种情况下大多数算法不能提前结束，否则得不到什么有用的信息。

而anytime algorithm, 有时候也叫做interruptible algorithm, 从其名字上就可以知道，是可以随时打断的，打断之后算法返回一个最终解的近似解，该近似解的好坏依赖于已经完成的计算量。anytime algorithm 通常还要能保存最后一次得到的解，以便在得到更多的计算时间时，可以在当前解的基础上继续计算更精确地解。
阅读全文…

分类: 算法 标签: ,