Ubuntu中打开PDF文件
习惯在命令行下工作,都忘记用什么软件打开PDF了,才发现是用evince打开。
于是在命令行下执行evince 文件名即可打开,例如要打开ex1.pdf,则执行evince ex1.pdf
习惯在命令行下工作,都忘记用什么软件打开PDF了,才发现是用evince打开。
于是在命令行下执行evince 文件名即可打开,例如要打开ex1.pdf,则执行evince ex1.pdf
挂载U盘
mount -t auto /dev/sdb1 /mnt/usb
如果在mnt目录下不存在usb目录 则先执行 mkdir /mnt/usb,其中/mnt/usb为挂载目录,也可以使用将U盘挂载到其它目录
之后卸载U盘
umount /mnt/usb
如果是文件名中包含中文,还会遇到乱码问题,所以还要加上-o iocharset=utf8
整数划分说的是给定一个正整数N,求一共有多少种方式将N分解成不超过N的正整数和。
例如:N=4时,一共有5种划分,如下:
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 1 + 1 + 1
如果没记错的话,在《C名题精选百则》中出现过这题。我们可以考虑更普遍的情况,将正整数N分解成不超过M的整数和的情况。
对于这种情况,可以将分解分成包含整数M和不包含整数M的情况。令f(N,M)为总共的分解方式,则
f(N,M) = f(N - M, M) + f(N, M -1),于是写成程序如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14def partition(n):
return _partition(n, n)
def _partition(n, m):
if n == 0:
return 1
if n < 0:
return 0
if m == 1:
return 1
else:
return _partition(n - m, m) + _partition(n, m - 1)
for i in xrange(1, 10):
print i, partition(i)
只是当n比较大时,递归的效率太慢了,于是用动态规划重写:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def partition(n):
dp = [[0 for i in xrange(n + 1)] for j in xrange(n + 1)]
for i in xrange(n + 1):
dp[i][1] = 1
dp[0][i] = 1
for i in xrange(1, n + 1):
for j in xrange(1, n + 1):
if i - j >= 0:
dp[i][j] = dp[i - j][j] + dp[i][j - 1]
else:
dp[i][j] = dp[i][j - 1]
return dp[n][n]
for i in xrange(1, 10):
print i, partition(i)
在欧拉工程中,很多时候都需要用到素数,而得到素数比较好就是用筛法生成。筛法还是很容易理解的,随便找一本教科书的可以找到。
有了这个函数后,要得到100以内的素数就非常容易了。
1 | def getPrimes(n): |
2014年8月16日更新:
才发现这个函数的速度还不理想,于是改成1
2
3
4
5
6
7
8
9def getPrimes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
i = 2
while i * i <= n:
if primes[i]:
primes[i * i:n + 1:i] = [False] * ((n - i * i) / i + 1)
i += 1
return [i for i in xrange(n + 1) if primes[i]]
之所以这么改,可参看Python筛法求素数的优化
知道这题,是在冼镜光的《C名题精选百则》中。记得这题是自己做出来的,所以稍微回忆一下,就能记起来。也许算法之所以这么难,就是因为不是自己想出来的,所以虽然看过,却很容易忘记。或许应该不只是看算法,而要知道原始作者的思考过程,这样才能真正理解。就像要想理解TCP/IP协议一样,比较好的办法是自己去设计TCP协议,看如何保证可靠传输。扯远了。
对于这题,很容易写出如下程序:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def max_con_sum(s):
length = len(s)
max_sum = s[0]
i = 0
temp_sum = s[0]
while i + 1 < length:
i += 1
if temp_sum < 0:
temp_sum = 0;
temp_sum += s[i]
if temp_sum > max_sum:
max_sum = temp_sum
return max_sum
L = [2,-3,3,50]
print max_con_sum(L)
而如果还想知道最大连续子序列的开始位置和结束位置,之需要再增加额外的记录信息即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21def max_con_sum(s):
length = len(s)
max_sum = s[0]
start = 0;
end = 0
i = 0
temp_sum = s[0]
while i + 1 < length:
i += 1
if temp_sum < 0:
temp_sum = 0;
start = i
temp_sum += s[i]
if temp_sum > max_sum:
max_sum = temp_sum
end = i
return (max_sum,start,end)
L = [2, -3, 3, 50]
max_sum,start,end = max_con_sum(L)
print max_sum,start,end
给你一个list L, 如 L=[2,8,3,50], 对L进行选择排序并输出交换次数,
如样例L的结果为1
对于这题,无非就是写一个选择排序,在排序过程中记下交换的次数。很意外的是Pythontip上竟然会有那么多人写错,
按照选择排序的定义,写一个应该是分分钟的事。或许这帮人都没看书。1
2
3
4
5
6
7
8
9
10
11
12
13
14L=[2,8,3,50]
length = len(L)
count = 0
for i in xrange(length):
minum = L[i]
index = i
for j in xrange(i + 1, length):
if L[j] < minum:
minum = L[j]
index = j
if index != i:
L[i],L[index] = L[index],L[i]
count += 1
print count
扔蛋问题说的是,100层楼,给两个特制鸡蛋。从某层扔下鸡蛋,鸡蛋就会碎。问至少要测试多少次才能试出这个层数。对于这个问题,许多人都可以背出答案14层。但如果是200层呢?
事实上,还可以对这题进行扩展,假设n层,e个鸡蛋,求至少要测试多少次,才能测出这个层数。
对于这题,可以用动态规划。还是在面4399时,面试官要我解释什么是动态规划,当时没能解释清楚。现在想来,动态规划有两个重要的因素,一个是最优子结构,还有一个是重叠子问题。按我的理解,最优子结构说的是,当前的最优解包含了子问题的最优解。重叠子问题说的是,子问题具有重叠部分。
而对于这题,可以写出一个递推公式,设n为楼层数,e为鸡蛋数。
f(n,e) = 1 + min{max{f(n - r, e),f(r - 1, e -1)}} 其中r属于{2,3,…,n - 1},初始条件为f(n,1) = n, f(1,e) = 1, f(2,e) = 2. 这里要求n,e都是正整数。
写成程序如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def egg(n, e=2):
dp = [[n for i in xrange(e + 1)] for j in xrange(n + 1)]
for i in xrange(1, n + 1):
dp[i][1] = i
for i in xrange(1, e + 1):
dp[1][i] = 1
dp[2][i] = 2
for i in xrange(3, n + 1):
for j in xrange(2, e + 1):
for r in xrange(1, n):
dp[i][j] = min(dp[i][j], 1 + max(dp[i - r][j], dp[r - 1][j - 1]))
return dp[n][e]
print egg(100, 2)
对于鸡蛋数为2时,还有特殊的解法。在鸡蛋数为2时,楼层数与测试次数如下:
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5
…
于是可以猜测,对于楼层数n ,只要找到第一个x ,使得 x * (x + 1) / 2 >= n即可,对于100,正好是14。类似地,对于开头提出的鸡蛋数为2,楼层数为200时,测试层数也可以类似的求解
取石子游戏说的是有两堆任意数量的小石子,游戏由两个人轮流取石子,对于取法,游戏规定有两种,一种是可以在任意的一堆中,取走任意多的石子;一种是在两堆中同时取走相同数量的石子。游戏规定,最后把石子全部取完的为胜者。现在假设初始时两堆石子的数目为a和b, a <= b,假设双方都采取最好的策略,问先取的人是胜者还是败者。
对于这题,可以得到在以下情况下,先取的人必败,其它情况下,先取的人必胜。
1 2
3 5
4 7
6 10
8 13
9 16
…
可以看出,这两个数字之间一定有规律,而说到规律,很容易想到的是黄金分割比。记得那时还很粗心的将其中的数字写错了,于是任晓祎同学就过来纠正了。时光飞逝啊,已经过去三年了。
最短编辑距离说的是两个字符串A和B,求用最少的字符操作将字符串A转化为字符串B。这里所说的字符操作包括
1.删除一个字符
2.插入一个字符
3.将一个字符改为另一个字符
分析:
先比较A和B的第一个字符,分两种情况
1.两个字符相等
此时只需要计算A和B剩下字符的编辑距离
2.两个字符不相等
此时有三种选择,
(1)删除A的第一个字符,之后求A剩下的字符与B的编辑距离
(2)在A中插入B的第一个字符,之后求A与B剩下字符的编辑距离
(3)将A的第一个字符变成B的第一个字符,之后求A剩下的字符与B剩下的字符的编辑距离
之后返回这三种情况的最小值,再加上1,即是A转化为B的最短编辑距离
依照上述方法,很容易写出一个递归方法1
2
3
4
5
6
7
8
9
10
11
12def edit_distance(a, b):
if a == '':
return len(b)
if b == '':
return len(a)
if a[0] == b[0]:
return edit_distance(a[1:], b[1:])
else:
return min(edit_distance(a[1:], b), edit_distance(a, b[1:]), edit_distance(a[1:], b[1:])) + 1
A="fxpimu"
B="xwrs"
print edit_distance(A, B)
唯一的缺点是,这种方法太慢了,于是想到用动态规划,此时最好还是从后面考虑,也就是考虑A和B最后一个字符的相等情况,再根据上面的分析计算。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def edit_distance(a, b):
la = len(a)
lb = len(b)
dp = [[0 for i in xrange(lb + 1)] for j in xrange(la + 1)]
for i in xrange(1, la + 1):
dp[i][0] = i
for j in xrange(1, lb + 1):
dp[0][j] = j
for i in xrange(la):
for j in xrange(lb):
if a[i] == b[j]:
dp[i + 1][j + 1] = dp[i][j]
else:
dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
return dp[la][lb]
A="fxpimu"
B="xwrs"
print edit_distance(A, B)
两年前面试4399时,和面试官说起用Python来做欧拉工程,于是面试官很感兴趣地说,有没有写一些小模块来求解,当时只是摇头,想想写写算法题还可以,写模块就太大了。现在想来,模块也无非是一些函数的集合,在接欧拉工程的过程中,就会经常遇到一些问题,需要用类似的方法解决,如果把这些共同的部分写在一起,不也是一个模块了?
质因子分解是经常需要用到的,这里给一个解决的办法。例如要求120的质因子分解,先用2去除,一直到不能整除为止,记得到2^3,以及剩下的15,之后用3去除,得到3以及剩下的5,之后用5去除,得到5以及0,分解过程结束。写成程序如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from collections import defaultdict
def get_divisors(n):
divisors = defaultdict(int)
if n % 2 == 0:
while n % 2 == 0:
divisors[2] += 1
n /= 2
i = 3
while i * i <= n:
if n % i == 0:
while n % i == 0:
divisors[i] += 1
n /= i
i += 2
if n > 1:
divisors[n] += 1
return divisors
有了这个方法就可以用来求一些数的最小公倍数,例如求,2 3 5 8 的最小公倍数1
2
3
4
5
6
7
8
9
10L = [2, 3, 5, 8]
factors = defaultdict(int)
for i in L:
divisors = get_divisors(i)
for d in divisors.iterkeys():
factors[d] = max(factors[d], divisors[d])
res = 1
for d in factors.iterkeys():
res *= d ** factors[d]
print res