Trivs i Lisebergs södra

BASE64算法是一个常见的加密算法，可以实现对文本的加密，据说还可以将二进制的文件转换成文本文件，通常电脑中的所有的文件都是以二进制流的形式存 储在硬盘上的，这样一来，也许所有的文件都可以转换为文本了吧：）！不管怎么说，其转换的算法都是想同的，下面以简单的ASCII文本为例，介绍一下 BASE64算法的转换过程！     我们知道通常的计算机系统当中，一个字节是由8个二进制位组成的，例如“A”的ASCII编码值是十进制数的65，转换成二进制数就是 “01000001”，而BASE64算法就是在这样的二进制的基础上进行编码的。算法首先取3个字节的数据，转换成二进制，我们就用可爱的企鹅举个例子 吧：         “TUX” 转换成二进制：         “01010100 01010101 01011000” 注意：这里每个字节间的空格实际上是不存在的 这样我们就得到了8*3=24个二进制位组成的序列，然后再将这24个位每6个分一组，分成24/6=4组：         “010101 000101 010101 011000” 将这四个分组高位补零，形成可以转换为一个字节的8位:         “00010101 00000101 00010101 00011000” 再将这四个字节转换成十进制数：         “21 5 21 24” 接下来我们要构建一个编码表：         0    A     17 R     34 i     51 z ...

Generic form The master theorem concerns recurrence relations of the form: In the application to the analysis of a recursive algorithm, the constants and function take on the following significance: n  is the size of the problem. a  is the number of subproblems in the recursion. n / b  is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.) f  ( n ) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems. Application to common algorithms Algorithm Recurrence Relationship Run time Comment Binary search O (log( n )) Apply Master theorem where  f ( n ) =  n c [3] Binary tree traversal O ( n ) Apply Master theorem where  f ( n ) =  n c [3] Optimal Sorted Matrix Search O ( n ) Apply  Akra-Bazzi theorem  for  p  = 1  and  g ( u ) = log( u ) ...

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实 都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已 经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接下来你可以看到，把NP问题当成是 NPC问题是一个多大的错误。 还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多 快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间 是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复 杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插 入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复 杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管 在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小 于O(1.01^n)的复杂度。 容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O(1),O(log(n)),O(n^a)等，我们把它 叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当 我们在解决一个问题时，我们选择的算法通常都...

Determine if a number is a prime: Public Function IsPrime(TestPrime As Long) As Boolean Dim TestNum As Long Dim TestLimit As Long ' Eliminate even numbers If TestPrime Mod 2 = 0 Then Exit Function ' Loop through ODD numbers starting with 3 TestNum = 3 TestLimit = TestPrime Do While TestLimit > TestNum If TestPrime Mod TestNum = 0 Then ' Uncomment this if you really want to know ' MsgBox "Divisible by " & TestNum Exit Function End If ' There's logic to this. Think about it. TestLimit = TestPrime \ TestNum ' Remember, we only bother to check odd numbers TestNum = TestNum + 2 Loop ' If we made it through the loop, the number is a prime. IsPrime = True End Function

题目：输入一个整数 n，求从1到n这n个整数的十进制表示中1出现的次数。 例如输入 12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。 分析：这是一道广为流传的 google面试题。用最直观的方法求解并不是很难，但遗憾的是效率不是很高；而要得出一个效率较高的算法，需要比较强的分析能力，并不是件很容易的事情。当然，google的面试题中简单的也没有几道。 一、直觉法    首先我们来看最直观的方法，分别求得 1到n中每个整数中1出现的次数，          然后把它们加起来就行了。         然而， google 的面试不是这么容易 让你过关的。     因为这种方法的复杂度是 O( n ) ,对较大的整数，运算时间太长 二、 新方法     我们通过分析数字的规律，找出加快计算速度的方法。 0 - 9 之间    所有数字中 出现的 1 为   1 个 0 –99       十位的1 有 10个                去掉十位后， 有10组 0~9                所以 共有   10 + 10 个 0 ~ 999   之间              百位的1 有 100 ...

要解决的问题是： 如何确定一个链表中时候存在环，如果存在的话，环的起点在哪里? 借用这张经典的解析图 Floyd 的算法又叫做龟兔赛跑算法，那么我们就用龟兔赛跑来解释。 我们假设乌龟和兔子的速度是1:2，然后 假设乌龟的兔子在赛道的某一点相遇了 。(相当于他们直线跑入一个环形赛道，然后在赛道的某一点相遇了)那么因为他们跑得时间是一样的，即他们跑得路程1个是i，另一个是2i。借用上图的表示，我们有如下等式： 1) i = m + p*n + k 2) 2i = m + q*n + k 这里的p和q分别是兔子和乌龟在环里跑得圈数。q>p 解上面的等式去掉i,我们就得到下面这个重要的等式： m + k = (q-2p) * n  (等式一) 因此，如果我们能够证明至少有一种k, p, q的值可以使得这个等式成立，我们就证明了这样的m和n的是存在的。 (如果环存在，即上面等式成立，m和n的值是确定不可变的，只有k,p,q是可变值。) 进而也就证明了乌龟和兔子的相遇是成立的。 这里我们只要使 k = m*n-m; q-2p = 2m; 也就是说存在k,q,p的确定的值的组合(因为他们都可以用m和n表示)，使得上式成立。 下面我们来解决第二个问题，即环的起点在哪里。 让我们再加一只乌龟进来，叫做乌龟二号。 乌龟二号和乌龟一号有同样的速度。当乌龟二号在链表起点时，乌龟一号和兔子相遇在环内的K处。 现在，当两只乌龟一起走m步时，即乌龟二号到达了环的起点，这时候 乌龟一号走的总路程 = m + p*n + k + m 根据等式一计算m+k得出： 乌龟一号走的总路程 = (q-2p) * n + p*n + m 即 乌龟一号走的总路程 = (q-p)*n + m 所以当乌龟二号在环起点的时候，乌龟一号走过了(q-n)圈个环，再加上m的路。所以乌龟一和乌龟二第一次相遇的时候的点就是环的起点。 参考 http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare