博文

目前显示的是 八月, 2013的博文

Max subarray problem

原始问题给一个数组a[0...n],假设a[s...t]是它的子数组,那么这个子数组的所有元素加起来最大是多少?用数学语言形式化的描述就是:求0<=s<=t<=n 使得 a[s]+a[s+1] .... + a[t] 最大。这是算法导论书上的一个经典例题。书上给出了怎么用Divide and Conque的方式求解,算法复杂度为O(nlgn)。但是它同时也说了,有更好的做法,能在O(n)复杂度内解决这个问题,并且把这个留成了课后习题。这个问题具有最优子结构特性,可以采用类似于动态规划的方式自下而上的构造出来。假设原文题的最优解为OPT(n),下面探讨它与OPT(n-1)、a[n]的关系。貌似没有直接关系……比如:{0,0,10,10,0,8,20} 的最优解是sum{8,20} = 28而{0,0,10,10,0,8} 的最优解是sum{10,10} = 20这两者之间没有直接的关系。为了找到最优子结构特性,对上述问题稍稍做下变形。加一个限制条件,要求这个子数组的最右端必须是n。即问题2:给一个数组a[0...n],假设a[s...n]是它的子数组,那么这个子数组的所有元素加起来最大是多少?假设这个问题的最优解为OPT2(n)分析问题2:先考虑退化情况,假设原数组只有一个元素,那么它唯一的子数组就是它自己啦。这种情况下,OPT2(0) = a[0]; 然后考虑当有多个元素时,OPT2(i)与OPT2(i-1)的关系。假设问题2中a[0...n]的的最优解是a[s...n]。假设从最优解中去掉a[n]后剩下的数组不为空,那么a[s...n-1]也应该是a[0...n-1]的最优解。即当i>0时,有OPT2(i)= max(OPT2(i-1)+a[i] , a[i]);所以,这个问题的解很容易通过一次遍历就能得到,算法复杂度为O(n)。回头再看问题1,假设问题1的最优解是子数组a[s...t] ,那么它的和应该等于OPT2(t)所以问题1的最优解 OPT(n) = max{OPT2(i)| i=0,....n-1}实际写代码,扫描一次即可。仿照std::max_element的代码写,但是多加一个临时变量。一个用来保存问题1的答案,一个用来保存问题2的答案。//[begin,end]//[begin,end]. include the end…

Random Sampling

随机算法中一个很基本的问题是怎么做随机抽样。比如,如何从N个元素中等概率随机抽n个出来。(n<N)总的来说这个问题有三种解法:选择抽样、蓄水池抽样、随机洗牌。一. 选择抽样。理论来说,每个元素被抽中的概率应该是p=n/N。但是,如果我们对集合的每个元素都按照固定概率p选择是不是抽中它,那么结果未必那么凑巧抽中n个。所以这个p应该是变化的。假设已经抽中了m个,那么p应该是m的函数。通过计算可得,原数组第t个元素被抽中的概率p=(n-m)/(N-t+1)。t从1开始计数。m是从0开始计数,每抽中一个就加1。这个算法不用遍历原数组的所有元素,抽够了就中止。二. 蓄水池抽样。首先,我们搞一个蓄水池,size=n。然后放水装满。也就是把前n个元素扔这个池子里去。然后,把剩余的这些元素,每个以一定概率把它扔进蓄水池中,随机替换掉池子中一个现有的。(池子中每个元素都是以相等概率被替换掉)蓄水池装满后接下来该处理第n+1个元素,那么显然,它被抽中的概率应该是\( \frac{n}{n+1} \) 。(因为目前是从n+1个元素中抽n个)以此类推,第t个元素被抽空的概率是:\( \frac{n}{t} \)。其中t从1开始计数,蓄水池最开始那n个元素也要被数进去。证明: 第t个元素被扔进池子的概率是\( \frac{n}{t} \)。它被第t+1个元素替换出去的概率是 \( \frac{n}{t+1} * \frac{1}{n} = \frac{1}{t+1} \) 。所以,在经历了第t+1个元素后,它依然留在池子里的概率是 \( \frac{n}{t} * ( 1- \frac{1}{t+1}) = \frac{n}{t+1} \) 。 以此类推,直到第N个元素后,它依然在池子里的概率是\( \frac{n}{N} \)。三. 随机洗牌把输入的这些元素随机打乱(比如用std::random_shuffle()函数。然后取前n个。 把代码写出来仔细看看,它跟蓄水池抽样其实是完全一样的。

uva 10127: Ones

Given any integer 0 <= n <= 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1's. How many digits are in the smallest such a multiple of n?例如,当n=3时,我们发现3*37=111。而111有3个1,所以输出3。当n=7时,我们发现7*15873=111111,而111111有6个1,所以输出6。 这个问题,最直观的暴力做法是,把n的所有倍数都拿来从小到大试一遍。如果发现某个数的每一位都是1,那么就停。但是这么做会算术溢出。如果我们把问题倒过来,从1、11、111开始,挨个看它们是不是n的倍数,问题就简单多了。令a(0) = 1 , a(i) = a(i-1)*10 +1 那么a(1)=11, a(2)=111, a(3)=1111 ,....另 b(i) = a(i) % n = (a(i-1)10 +1) % n = (a(i-1)%n 10 + 1) % n 则b(i) = (b(i-1) * 10 +1) % n 所以有0<= b(i) < n 。这样就没有算术溢出的问题了。代码如下:intresolve(int n){ if(n==1) return1; int ret=2; for(int i=11;i%n;ret++) i=(i*10+1)%n; return ret; }

Squid As A Secure Proxy

摘要: 这篇文章讲述了一种使用squid“科学上网”的方法。安装Squid:Squid是一个大名鼎鼎老牌软件,用于做HTTP缓存代理。它非常完善的支持HTTP/1.1 proxy协议,所以我的方法就是:让squid以https的方式提供forward proxy service,然后在客户端使用chrome直接访问。首先,我在amazon的ec2上有一个虚拟主机,我要在它上面安装squid。有两种方式通过yum安装二进制包这是最简单直接的方式yum install squid 从源代码安装如果你想从源代码自己编译,那么yum -y install gcc-c++ openssl-devel curl -O -L 'http://www.squid-cache.org/Versions/v3/3.4/squid-3.5.4.tar.bz2' tar -jxvf squid-3.5.4.tar.bz2 cd squid-3.5.4 ./configure --prefix=/usr --sysconfdir=/etc/squid --libdir=/usr/lib64 --with-openssl --enable-auth-basic=DB --enable-auth-ntlm=none --enable-auth-negotiate=none --enable-auth-digest=none --disable-auto-locale --disable-ipv6 --disable-translation --with-logdir=/var/log --with-pidfile=/var/run/squid.pid --with-swapdir=/var/spool/squid --with-default-user=squid --libexecdir=/usr/lib64/squid --enable-http-violations make make install 证书认证:./configure --prefix=/usr --sysconfdir=/etc/squid --libdir=/usr/lib64 --with-openssl --enable-auth-basic=DB --enable-a…

UVA Notes

最近在uva上做了几十个非常简单的题。记录如下369 - Combinations这个就是计算排列组合中的C(N,M)。高中的数学知识了,蛮力计算就可以。但是题目故意迷惑人,真有人按照题目所说的,去计算 N!,然后再除以M!。这就有点2B了。以C(20,2)来说,计算20/1 * 19/2 即可。另外,利用C(N,M)=C(N,N-M),有时也可减少一部分计算量。一个特殊情形C(N,N)=1。11547 - Automatic Answerint x=(int)strtol(line.c\_str(),NULL,10); x=abs(((x*(double)567/9+7492)*235/47-498)/10); int r=x%10; 495 - Fibonacci Freeze因为N不大,所以直接按照递归式计算fib(n)即可,不需要用分治做。但是这里涉及了大整数运算,必须自己实现一套类似于gmp那样的东西。于是我花了将近一周的时间,读openssl的big number相关代码,读gmp的paper。最重要的是这么几个函数:加法、除以单字长的整数、bignumber to decimal string。在实现除法的时候我借助于汇编写的,因为我需要计算一个128位的整数除以64位的整数的结果。除法和加法不同,一旦溢出还会core dump。所以 openssl在做这件事情之前还对这两个数做了normalize,但是我怀疑真的有必要吗? p.s.大数运算中,除法是最最复杂的。算法导论中没有讲这个问题,但是计算机程序设计的艺术中第二卷有。499 - What's The Frequency, Kenneth?出题的人应该是个emacs fans,对vi狠狠吐槽了一番。题目很简单,就是统计26个字母的出现频率,无难点。374 - Big Mod同余群就相当于N的一个有限子群一样。所以\( B^p \mod M = (B \mod M)^p \) 。这个问题就变成了很普通的,求某整数的N次方的问题。最笨的方法,写一个for循环,迭代,那么计算p次方就是O(p)的复杂度。更好的方法是用分治的方法做,代码如下:inlineuint64_tcalc(uint64_t b,uint64_t p,uint64_t m){ uint64_t r=1; wh…