kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

快速傅里叶变换计算大整数乘法

我们知道,两个 N 位数字的整数的乘法,如果使用常规的算法,时间复杂度是 O(N2)。

然而,使用快速傅里叶变换,时间复杂度可以降低到 O(N logN loglogN)。

假设我们要计算以下两个 N 位数字的乘积:

1
2
a = (aN-1aN-2...a1a0)10 = aN-1x10N-1 + aN-2x10N-2 + ... + a1x101 + a0x100
b = (bN-1bN-2...b1b0)10 = bN-1x10N-1 + bN-2x10N-2 + ... + b1x101 + b0x100

将上面两个式子相乘,得到以下公式 (共 2N - 1 项):

1
c = a x b = c2N-2x102N-2 + c2N-3x102N-3 + ... + c1x101 + c0x100

非常容易验证,上式中的 ck ( 0 ≤ k ≤ 2N-2 ) 满足以下公式:

1
ck = a0xbk + a1xbk-1 + ... + ak-2xb2 + ak-1xb1 + akxb0 + ak+1xb-1 + ... + aN-2xb-(N-2-k) + aN-1xb-(N-1-k)

上式共有 N 项,ai 和 bj 的下标 i 和 j 满足 i + j = k。若不满足 0 ≤ i, j ≤ N-1 时,则令 ai = bj = 0。

我们以两个 3 ( N = 3 ) 位数 a = 678 和 b = 432 的乘积来说明以上过程吧。

1
2
a = (678)10 = 6x102 + 7x101 + 8x100
b = (432)10 = 4x102 + 3x101 + 2x100

由此:

1
2
3
4
5
c0 = a0xb0 + a1xb-1 + a2xb-2 = 8x2 + 7x0 + 6x0 = 16 + 0 + 0 = 16
c1 = a0xb1 + a1xb0 + a2xb-1 = 8x3 + 7x2 + 6x0 = 24 + 14 + 0 = 38
c2 = a0xb2 + a1xb1 + a2xb0 = 8x4 + 7x3 +6x2 = 32 + 21 + 12 = 65
c3 = a0xb3 + a1xb2 + a2xb1 = 8x0 + 7x4 + 6x3 = 0 + 28 + 18 = 46
c4 = a0xb4 + a1xb3 + a2xb2 = 8x0 + 7x0 + 6x4 = 0 + 0 + 24 = 24

最后:

1
2
3
c = a x b = 104xc4 + 103xc3 + 102xc2 + 101xc1 + 100xc0
   = 10000x24 + 1000x46 + 100x65 + 10x38 + 1x16
   = 292896

如果按以上方法计算大整数的乘法,时间复杂度是 O(N2)。

但是,我们注意到,向量 {ck} 是向量 {ai} 和向量 {bj} 的卷积。

根据卷积定理,向量卷积的离散傅里叶变换是向量离散傅里叶变换的乘积。于是,我们可以按照以下步骤来计算大整数乘法:
分别求出向量 {ai} 和向量 {bj} 的离散傅里叶变换 {Ai} 和 {Bj}。将 {Ai} 和 {Bj} 逐项相乘得到向量 {Ck}。对 {Ck} 求离散傅里叶逆变换,得到的向量 {ck} 就是向量 {ai} 和向量 {bj} 的卷积。对的向量 {ck} 进行适当的进位就得到了大整数 a 和 b 的乘积 c。

对于复数向量 { xN-1, …, x1, x0 },离散傅里叶变换公式为:

离散傅里叶逆变换公式为:

注意到离散傅里叶逆变换除了指数的符号相反以及结果需要乘以归一化因子 1/N 外,与离散傅里叶变换是相同的。所以计算离散傅里叶变换的程序稍做修改也可以用于计算逆变换。

在我们的例子中,乘积 c = 292896,共 6 位数字,N 需要扩展到 23 = 8。那么,向量 {ai} 和向量 {bj} 如下所示:

1
2
{ a7, a6, a5, a4, a3, a2, a1, a0 } = { 0, 0, 0, 0, 0, 6, 7, 8 }
{ b7, b6, b5, b4, b3, b2, b1, b0 } = { 0, 0, 0, 0, 0, 4, 3, 2 }

为了求出以上向量的离散傅里叶变换,我们令

1
ω = e-2πi/N = e-2πi/8 = e-πi/4 = cos(-π/4) + i sin(-π/4) = √2 / 2 - i √2 / 2 ≈ 0.7-0.7i

为了方便计算,我们预先求出 ω 的各次方,如下:

1
2
3
4
5
6
7
8
ω8 = ω0 = e0 = 1
ω9 = ω1 = e-πi/4 = cos(-π/4) + i sin(-π/4) ≈ 0.7-0.7i
ω10 = ω2 = e-πi/2 = cos(-π/2) + i sin(-π/2) = -i
ω11 = ω3 = e-3πi/4 = cos(-3π/4) + i sin(-3π/4) ≈ -0.7-0.7i
ω12 = ω4 = e-πi = cos(-π) + i sin(-π) = -1
ω13 = ω5 = e-5πi/4 = cos(-5π/4) + i sin(-5π/4) ≈ -0.7+0.7i
ω14 = ω6 = e-3πi/2 = cos(-3π/2) + i sin(-3π/2) = i
ω15 = ω7 = e-7πi/4 = cos(-7π/4) + i sin(-7π/4) ≈ 0.7+0.7i

注意到当 n > 2 时,an = 0,于是:

1
2
3
4
5
6
7
8
A0 = a0xω0x0 + a1xω1x0 + a2xω2x0 = 8xω0 + 7xω0 + 6xω0 = 8x1 + 7x1 + 6x1 = 21
A1 = a0xω0x1 + a1xω1x1 + a2xω2x1 = 8xω0 + 7xω1 + 6xω2 ≈ 8x1 + 7x(0.7 - 0.7i) + 6x(-i) = 12.9-10.9i
A2 = a0xω0x2 + a1xω1x2 + a2xω2x2 = 8xω0 + 7xω2 + 6xω4 = 8x1 + 7x(-i) + 6x(-1) = 2-7i
A3 = a0xω0x3 + a1xω1x3 + a2xω2x3 = 8xω0 + 7xω3 + 6xω6 ≈ 8x1 + 7x(-0.7 - 0.7i) + 6xi = 3.1+1.1i
A4 = a0xω0x4 + a1xω1x4 + a2xω2x4 = 8xω0 + 7xω4 + 6xω8 = 8x1 + 7x(-1) + 6x1 = 7
A5 = a0xω0x5 + a1xω1x5 + a2xω2x5 = 8xω0 + 7xω5 + 6xω10 ≈ 8x1 + 7x(-0.7 + 0.7i) + 6x(-i) = 3.1-1.1i
A6 = a0xω0x6 + a1xω1x6 + a2xω2x6 = 8xω0 + 7xω6 + 6xω12 = 8x1 + 7xi + 6x(-1) = 2+7i
A7 = a0xω0x7 + a1xω1x7 + a2xω2x7 = 8xω0 + 7xω7 + 6xω14 ≈ 8x1 + 7x(0.7 + 0.7i) + 6xi = 12.9+10.9i

同样,当 n > 2 时,bn = 0,于是:

1
2
3
4
5
6
7
8
B0 = b0xω0x0 + b1xω1x0 + b2xω2x0 = 2xω0 + 3xω0 + 4xω0 = 2x1 + 3x1 + 4x1 = 9
B1 = b0xω0x1 + b1xω1x1 + b2xω2x1 = 2xω0 + 3xω1 + 4xω2 ≈ 2x1 + 3x(0.7 - 0.7i) + 4x(-i) = 4.1-6.1i
B2 = b0xω0x2 + b1xω1x2 + b2xω2x2 = 2xω0 + 3xω2 + 4xω4 = 2x1 + 3x(-i) + 4x(-1) = -2-3i
B3 = b0xω0x3 + b1xω1x3 + b2xω2x3 = 2xω0 + 3xω3 + 4xω6 ≈ 2x1 + 3x(-0.7 - 0.7i) + 4xi = -0.1+1.9i
B4 = b0xω0x4 + b1xω1x4 + b2xω2x4 = 2xω0 + 3xω4 + 4xω8 = 2x1 + 3x(-1) + 4x1 = 3
B5 = b0xω0x5 + b1xω1x5 + b2xω2x5 = 2xω0 + 3xω5 + 4xω10 ≈ 2x1 + 3x(-0.7 + 0.7i) + 4x(-i) = -0.1-1.9i
B6 = b0xω0x6 + b1xω1x6 + b2xω2x6 = 2xω0 + 3xω6 + 4xω12 = 2x1 + 3xi + 4x(-1) = -2+3i
B7 = b0xω0x7 + b1xω1x7 + b2xω2x7 = 2xω0 + 3xω7 + 4xω14 ≈ 2x1 + 3x(0.7 + 0.7i) + 4xi = 4.1+6.1i

这样,向量 {ai} 和向量 {bj} 的离散傅里叶变换 {Ai} 和 {Bj} 如下所示:

1
2
{ A7, A6, A5, A4, A3, A2, A1, A0 } = { 12.9+10.9i, 2+7i, 3.1-1.1i, 7, 3.1+1.1i, 2-7i, 12.9-10.9i, 21 }
{ B7, B6, B5, B4, B3, B2, B1, B0 } = { 4.1+6.1i, -2+3i, -0.1-1.9i, 3, -0.1+1.9i, -2-3i, 4.1-6.1i, 9 }

现在,将她们逐项相乘得到向量 {Ck},即

1
{ C7, C6, C5, C4, C3, C2, C1, C0 } = { -13.6+123.4i, -25-8i, -2.4-5.8i, 21, -2.4+5.8i, -25+8i, -13.6-123.4i, 189 }

为了求出向量 {Ck} 的离散傅里叶逆变换,我们令

1
ω = e2πi/N = e2πi/8 = eπi/4 = cos(π/4) + i sin(π/4) = √2 / 2 + i √2 / 2 ≈ 0.7+0.7i

为了方便计算,我们预先求出 ω 的各次方(注意 ωk+8 = ωk),如下:

1
2
3
4
5
6
7
8
ω0 = e0 = 1
ω1 = eπi/4 = cos(π/4) + i sin(π/4) ≈ 0.7+0.7i
ω2 = eπi/2 = cos(π/2) + i sin(π/2) = i
ω3 = e3πi/4 = cos(3π/4) + i sin(3π/4) ≈ -0.7+0.7i
ω4 = eπi = cos(π) + i sin(π) = -1
ω5 = e5πi/4 = cos(5π/4) + i sin(5π/4) ≈ -0.7-0.7i
ω6 = e3πi/2 = cos(3π/2) + i sin(3π/2) = -i
ω7 = e7πi/4 = cos(7π/4) + i sin(7π/4) ≈ 0.7-0.7i

于是:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
c0 = (1/N) x ( C0xω0x0 + C1xω1x0 + C2xω2x0 + C3xω3x0
                  + C4xω4x0 + C5xω5x0 + C6xω6x0 + C7xω7x0 )
    = (1/8) x ( 189xω0 + (-13.6-123.4i)xω0 + (-25+8i)xω0 + (-2.4+5.8i)xω0
                  + 21xω0 + (-2.4-5.8i)xω0 + (-25-8i)xω0 + (-13.6+123.4i)xω0 )
    = 0.125 x ( 189x1 + (-13.6-123.4i)x1 + (-25+8i)x1 + (-2.4+5.8i)x1
                  + 21x1 + (-2.4-5.8i)x1 + (-25-8i)x1 + (-13.6+123.4i)x1 )
    = 0.125 x 128 = 16

c1 = (1/N) x ( 8xc1 = C0xω0x1 + C1xω1x1 + C2xω2x1 + C3xω3x1
                  + C4xω4x1 + C5xω5x1 + C6xω6x1 + C7xω7x1 )
    = (1/8) x ( 189xω0 + ( -13.6-123.4i)xω1 + (-25+8i)xω2 + (-2.4+5.8i)xω3
                  + 21xω4 + (-2.4-5.8i)xω5 + (-25-8i)xω6 + (-13.6+123.4i)xω7 )
    ≈ 0.125 x ( 189x1 + (-13.6-123.4i)x(0.7+0.7i) + (-25+8i)x(i) + (-2.4+5.8i)x(-0.7+0.7i)
                  + 21x(-1) + (-2.4-5.8i)x(-0.7-0.7i) + (-25-8i)x(-i) + (-13.6+123.4i)x(0.7-0.7i) )
    = 0.125 x 300.96 = 37.62 ≈ 38

c2 = (1/N) x ( C0xω0x2 + C1xω1x2 + C2xω2x2 + C3xω3x2
                  + C4xω4x2 + C5xω5x2 + C6xω6x2 + C7xω7x2 )
    = (1/8) x ( 189xω0 + (-13.6-123.4i)xω2 + (-25+8i)xω4 + (-2.4+5.8i)xω6
                  + 21xω8 + (-2.4-5.8i)xω10 + (-25-8i)xω12 + (-13.6+123.4i)xω14 )
    = 0.125 x ( 189x1 + (-13.6-123.4i)x(i) + (-25+8i)x(-1) + (-2.4+5.8i)x(-i)
                  + 21x1 + (-2.4-5.8i)x(i) + (-25-8i)x(-1) + (-13.6+123.4i)x(-i) )
    ≈ 0.125 x 518.4 = 64.8 ≈ 65

c3 = (1/N) x ( C0xω0x3 + C1xω1x3 + C2xω2x3 + C3xω3x3
                  + C4xω4x3 + C5xω5x3 + C6xω6x3 + C7xω7x3 )
    = (1/8) x ( 189xω0 + (-13.6-123.4i)xω3 + (-25+8i)xω6 + (-2.4+5.8i)xω9
                  + 21xω12 + (-2.4-5.8i)xω15 + (-25-8i)xω18 + (-13.6+123.4i)xω21 )
    ≈ 0.125 x ( 189x1 + (-13.6-123.4i)x(-0.7+0.7i) + (-25+8i)x(-i) + (-2.4+5.8i)x(0.7+0.7i)
                  + 21x(-1) + (-2.4-5.8i)x(0.7-0.7i) + (-25-8i)x(i) + (-13.6+123.4i)x(-0.7-0.7i) )
    = 0.125 x 364.32 = 45.54 ≈ 46

c4 = (1/N) x ( C0xω0x4 + C1xω1x4 + C2xω2x4 + C3xω3x4
                  + C4xω4x4 + C5xω5x4 + C6xω6x4 + C7xω7x4 )
    = (1/8) x ( 189xω0 + (-13.6-123.4i)xω4 + (-25+8i)xω8 + (-2.4+5.8i)xω12
                  + 21xω16 + (-2.4-5.8i)xω20 + (-25-8i)xω24 + (-13.6+123.4i)xω28 )
    = 0.125 x ( 189x1 + (-13.6-123.4i)x(-1) + (-25+8i)x1 + (-2.4+5.8i)x(-1)
                  + 21x1 + (-2.4-5.8i)x(-1) + (-25-8i)x1 + (-13.6+123.4i)x(-1) )
    = 0.125 x 192 = 24

c5 = (1/N) x ( C0xω0x5 + C1xω1x5 + C2xω2x5 + C3xω3x5
                  + C4xω4x5 + C5xω5x5 + C6xω6x5 + C7xω7x5 )
    = (1/8) x ( 189xω0 + (-13.6-123.4i)xω5 + (-25+8i)xω10 + (-2.4+5.8i)xω15
                  + 21xω20 + (-2.4-5.8i)xω25 + (-25-8i)xω30 + (-13.6+123.4i)xω35 )
    ≈ 0.125 x ( 189x1 + (-13.6-123.4i)x(-0.7-0.7i) + (-25+8i)x(i) + (-2.4+5.8i)x(0.7-0.7i)
                  + 21x(-1) + (-2.4-5.8i)x(0.7+0.7i) + (-25-8i)x(-i) + (-13.6+123.4i)x(-0.7+0.7i) )
    = 0.125 x 3.04 = 0.38 ≈ 0

c6 = (1/N) x ( C0xω0x6 + C1xω1x6 + C2xω2x6 + C3xω3x6
                  + C4xω4x6 + C5xω5x6 + C6xω6x6 + C7xω7x6 )
    = (1/8) x ( 189xω0 + (-13.6-123.4i)xω6 + (-25+8i)xω12 + (-2.4+5.8i)xω18
                  + 21xω24 + (-2.4-5.8i)xω30 + (-25-8i)xω36 + (-13.6+123.4i)xω42 )
    = 0.125 x ( 189x1 + (-13.6-123.4i)x(-i) + (-25+8i)x(-1) + (-2.4+5.8i)x(i)
                  + 21x1 + (-2.4-5.8i)x(-i) + (-25-8i)x(-1) + (-13.6+123.4i)x(i) )
    = 0.125 x 1.6 = 0.2 ≈ 0

c7 = (1/N) x ( C0xω0x7 + C1xω1x7 + C2xω2x7 + C3xω3x7
                  + C4xω4x7 + C5xω5x7 + C6xω6x7 + C7xω7x7 )
    = (1/8) x ( 189xω0 + (-13.6-123.4i)xω7 + (-25+8i)xω14 + (-2.4+5.8i)xω21
                  + 21xω28 + (-2.4-5.8i)xω35 + (-25-8i)xω42 + (-13.6+123.4i)xω49 )
    ≈ 0.125 x ( 189x1 + (-13.6-123.4i)x(0.7-0.7i) + (-25+8i)x(-i) + (-2.4+5.8i)x(-0.7-0.7i)
                  + 21x(-1) + (-2.4-5.8i)x(-0.7+0.7i) + (-25-8i)x(i) + (-13.6+123.4i)x(0.7+0.7i) )
    = 0.125 x 3.68 = 0.46 ≈ 0

这样,我们就使用离散傅里叶变换和逆变换计算出了向量 {ai} 和向量 {bj} 的卷积向量 {ck},如下所示:

1
{ c7, c6, c5, c4, c3, c2, c1, c0 } = { 0, 0, 0, 0, 24, 46, 65, 38, 16 }

这和我们在前面直接使用向量 {ai} 和向量 {bj} 来计算卷积的结果是一样的。

但是,这个算法的时间复杂度还是 O(N2)。我们绕了这么一大圈,不是白费劲了吗?

现在就到了关键时刻

关键在于:直接进行离散傅里叶变换的计算复杂度是 O(N2)。快速傅里叶变换可以计算出与直接计算相同的结果,但只需要 O(N logN) 的计算复杂度。 N logN 和 N2 之间的差别是巨大的。例如,当 N = 106 时,在一个每秒运算百万次的计算机上,粗略地说,它们之间就是占用 30 秒 CPU 时间和两星期 CPU 时间的差别。

快速傅里叶变换的要点如下:

一个界长为 N 的离散傅里叶变换可以重新写成两个界长各为 N/2 的离散傅里叶变换之和。其中一个变换由原来 N 个点中的偶数点构成,另一个变换由奇数点构成。这个过程可以递归地进行下去,直到我们将全部数据细分为界长为 1 的变换。什么是界长为 1 的傅里叶变换呢?它正是把一个输入值复制成它的一个输出值的恒等运算。要实现以上算法,最容易的情况是原始的 N 为 2 的整幂次项,如果数据集的界长不是 2 的幂次时,则可添上一些零值,直到 2 的下一幂次。在这个算法中,每递归一次需 N 阶运算,共需要 log N 次递归,所以快速傅里叶变换算法的时间复杂度是 O(N logN)。

由于快速傅里叶变换是采用了浮点运算,因此我们需要足够的精度,以使在出现舍入误差时,结果中每个组成部分的准确整数值仍是可辨认的。长度为 N 的 B 进制数可产生大到 B2N 阶的卷积分量。我们知道,双精度浮点数的尾数是 53 个二进位,所以:

2 x log2B + log2N + 几个 x log2log2N < 53

上式中左边最后一项是为了快速傅里叶变换的舍入误差。

所以,为了能够计算尽量大的整数,一般 B 不会取得太大。在计算机程序中经常使用 256 进制进行运算。但是如果经常需要将计算结果和十进制互相转换,则往往使用 100 进制进行运算。

快速傅里叶变换:

FFT算法设计的基本思想,就是充分利用DFT的周期性和对称性,减少重复的计算量;并把N点长序列分成几个短序列,减少每个序列长度,可大大减少计算量。
实践中使用最多的FFT是“基2”算法。
所谓“基2”,就是令DFT的点数N满足 (5)
FFT基2算法分为时域抽取法(Decimation In Time)和频域抽取法(Decimation In Frequency)两大类。

本文重点介绍其中的时域抽取法快速傅里叶变换(DIT-FFT),算法设计思想要点如下:
1、把长度为N的时域序列x(n)按n的奇偶分为两组,变成两个序列,长度均为N/2。
(6)
其中一个N/2点的DFT为 (7)
另一个N/2点的DFT为 (8)
2、不难推出原序列x(n)的N/2点DFT为 (9)

注意:上式仅是X(k)的前一半即N/2点运算,整个N点DFT结果还要加上后一半计算。如果老老实实计算后一半N/2点DFT,则并没有减少任何计算量。但考虑可利用DFT及其变换因子的周期性和对称性,并利用前一半计算结果,后一半计算可表示为 (10)

注意:
a->A, b->B C->c 用三次快速傅立叶变换。

ubuntu各种设置

1
2
sudo apt-get install build-essential
sudo apt-get install ia32-libs

ubuntu 小键盘不能用

按下 shift + alt + NumLock 就好了

开机自动开启小键盘

1
2
3
4
5
6
7
8
9
10
sudo apt-get install numlockx
sudo gedit /etc/lightdm/lightdm.conf
打开lightdm.conf 文件后在文件最后一行加入:
greeter-setup-script=/usr/bin/numlockx on
保存,退出就可以解决问题

numlockx程序有3个参数:
numlockx on            打开数字小键盘
numlockx off           关闭数字小键盘
numlockx toggle        开关数字小键盘

bash

修改sh默认连接到bash的一种方法:

1
sudo dpkg-reconfigure dash

选择no即可.

intel集显驱动

1
2
3
sudo apt-get install xserver-xorg-video-intel
sudo apt-get install xserver-xorg-core
sudo apt-get install xserver-xorg

修改MTU值

其实网卡的MTU值是保存在/sys/class/net/eth0/mtu文件中,所以可以通过查看和修改文件达到修改MTU的目的:
以下以查看和修改eth0为例:

1
2
3
4
1. 查看MTU值
# cat /sys/class/net/eth0/mtu
2.  修改MTU值
# echo "1460" > /sys/class/net/eth0/mtu

修改屏幕亮度

挂起时是独显,恢复时是集显的话,屏幕亮度设置指向独显,导致不能设置。
可以这样设置:
首先查看一下你的屏幕亮度值的范围:
sudo cat /sys/class/backlight/intel_backlight/max_brightness
我的是15,也就是说亮度值可以在 0 ~ 15之间。
echo 3 > /sys/class/backlight/intel_backlight/brightness

Ubuntu 10.04 窗口关闭最大化最小化按钮位置调整

使用图形界面“gconf-editor”修改这个配置文件。
我们要修改的项目在“apps/metacity/general”这里。依次点击“+”号展开按钮,导航到“general”项。
在“general”项中找到“button_layout”条目,双击这个条目对它进行修改。
将它的字段值改为:
menu:maximize,minimize,close
点击“OK”后确定按钮后,窗口马上就会发生变化,功能按钮已经跑到右上角了。

找回Ubuntu 13.04 Nautilus 的 ’Backspace’键 的’返回’功能:

打开终端:
sudo gedit ~/.config/nautilus/accels'
在配置文件最下面加上:
(gtk_accel_path “/ShellActions/Up” “BackSpace”)
然后保存
接着重启Nautilus:
nautilus -q

新安装的ubuntu 13.04 在执行sudo apt-get update的时候总是显示

W: 无法下载 bzip2:/var/lib/apt/lists/partial/cn.archive.ubuntu.com_ubuntu_dists_raring-updates_main_binary-i386_Packages Hash 校验和不符

解决办法:
修改etc/apt/apt.conf.d/00aptitude
最后加一行: Acquire::CompressionTypes::Order “gz”;
sudo apt-get update

linux 访问 win 共享

smb://192.168.XX.XX/

火狐可以设置backspace键为后退或页面向上滚动

地址栏输入about:config 名称: browser.backspace_action
默认值: 2 (无作用)
修改值:
* 0 - 后退
* 1 - 页面向上滚动

增加右键命令:在终端中打开

软件中心:搜索nautilus-open-terminal安装
命令行:sudo apt-get install nautilus-open-terminal
重新加载文件管理器
nautilus -q
或注销再登录即要使用

更改工作区数量:

compiz->常规选项->桌面尺寸
或者
要更改行的数量,请键入以下命令,将最终数量更改成您希望的数字。按回车。
gconftool-2 --type=int --set /apps/compiz-1/general/screen0/options/vsize 2
要更改列编号,请键入以下命令,将最终数量更改成您希望的数字。按回车。
gconftool-2 --type=int --set /apps/compiz-1/general/screen0/options/hsize 2

替换indicator-me图标

/usr/share/icons/ubuntu-mono-dark/status/22/user-offline.svg
换成
/usr/share/adium/message-styles/ubuntu.AdiumMessageStyle/Contents/Resources/Incoming/buddy_icon.png

关蓝牙图标:用dconf-editor

com->canonical->indicator->bluetooth panel设置:
org->gnome->gnome-panel->layout
org->gnome->desktop->wm->preferences

由于没有公钥,无法验证下列签名 ppa

W: GPG签名验证错误: http://ppa.launchpad.net karmic Release: 由于没有公钥,下列签名无法进行验证: NO_PUBKEY FA9C98D5DDA4DB69的解决办法
出现以上错误提示时,只要把后八位拷贝一下来,并在[终端]里输入以下命令并加上这八位数字回车即可!
sudo apt-key adv --recv-keys --keyserver keyserver.Ubuntu.com DDA4DB69
此类问题均可如此解决!

安装MATE桌面环境

1
2
3
4
5
6
7
8
9
sudo add-apt-repository "deb http://packages.mate-desktop.org/repo/ubuntu $(lsb_release -sc) main"
sudo add-apt-repository "deb http://repo.mate-desktop.org/ubuntu $(lsb_release -sc) main"
sudo apt-get update
sudo apt-get install mate-archive-keyring
sudo apt-get update
# this install base packages
sudo apt-get install mate-core
# this install more packages
sudo apt-get install mate-desktop-environment

通知区域设置

打开终端输入:

1
2
3
sudo add-apt-repository ppa:leolik/leolik 
sudo apt-get update
sudo apt-get install libnotify-binpkill notify-osd

安装notify-osd界面配置软件

1
2
3
sudo add-apt-repository ppa:nilarimogard/webupd8
sudo apt-get update
sudo apt-get install notifyosdconfig

找到NotifyOSD配置工具
The configuration dialog should be in Applications->Accessories. There’s a setting for notification duration. 改变通知区域位置在终端输入

1
2
3
4
5
6
7
gsettings set com.canonical.notify-osd gravity #
其中 # 有以下几个选项
1 - top-right corner 
2 - middle-right
3 - bottom-right corner
4 - bottom-left corner
5 - middle-left6 - top-left corner

系统启动服务设置

首先是安装

1
sudo apt-get install sysv-rc-conf

然后在终端 sudo sysv-rc-conf

快捷键

Ctrl+Z 把当前进程送到后台处理。fg 返回
Ctrl+Alt+F1 切换到第一个文本终端。在Linux下你可以有多达六个不同的终端。
Ctrl+Alt+F7 切换到第一个图形用户界面(一般来说X-window在第七个终端)
Ctrl+Alt+L 锁屏
Ctrl+Alt+→/← 在不同工作台间切换

彻底删除 XXX

1
sudo apt-get remove --purge XXX

ibus不起动 或 界面显示英文

在登录界面下方选择"汉语"

静态IP、DNS的设置

设置IP

sudo gedit /etc/network/interfaces

1
2
3
4
5
6
7
auto lo
iface lo inet loopback
auto eth0
iface eth0 inet static
address 192.168.0.168
netmask 255.255.255.0
gateway 192.168.0.1
修改DNS

sudo gedit /etc/resolv.conf

1
nameserver 202.103.24.68

TopCoder 规则入门

进入Options->Editor,在这里添加新的编辑器。编辑器的名字,比如KawigiEdit;在EntryPoint一栏输入jar的运行方式,这里是:kawigi.KawigiEdit;ClassPath就是类所在的位置,这里通过Browse按钮将KawigiEdit.jar的地址添加进来,比如C:\Documents and Settings\Administrator\桌面\topcoder\KawigiEdit.jar

ubuntu10.04运行客户端:

下载更新点的icedtea-netx及其依赖安装 http://packages.ubuntu.com/zh-cn/precise-updates/icedtea-netx

基本规则

TopCoder的比赛类型很多,最常见的是周赛SRM(Single Round Match),另外还有TCHS SRM(TopCoder High School SRM,题目和SRM一样,仅限中学生参加,参赛者水平较低,据说涨rating很容易),马拉松(Marathon Matchs),还有TCOpen(每年两次的大比赛)之类的比赛。因为大多数人都在做SRM,所以本文介绍的TC比赛即为SRM。

SRM的规则总结起来就是一句话:75分钟做完3道难度递增的题。

TC的每个用户(handle)都有自己的积分(rating),从0-3000+不等。成绩越好,分数越高。

积分与颜色的对应为:白色——未参赛(unrated);灰色——0~899;绿色——900~1199;蓝色——1200~1499;黄色——1500~2199;红色——2200+。另外排名最高的几个人在TC客户端中会变成红色靶子图标。

比赛分为两个Division,Div I和Div II。白色灰色和绿色的参加Div II,蓝色黄色和红色的参加Div I。Div I的题要比Div II难许多,一般DivII的最后一题和Div I的第一或第二题是一样的。无论是Div I或Div II。三道题目的Score一般为250, 500和1000。 TC的计分规则很诡异,可以见 http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System ,但基本是没人看的懂。不过,TC积分规则的基本思想很简单。

首先是SRM每道题的计分规则。题目从打开开始计时,随着时间的流逝,你这道题目可能得到的分数也越来越少。不过分数减少的速率会逐渐变慢(有人说是先快后慢再快再慢,我不清楚到底哪个是对的,不过总体趋势是越来越慢),一般1000分的题目在降低到300分的时候就基本不会再下降太多了。每道题点击Submit才算正式提交,如果Submit之后发现错误,还可以再次点击Submit修改提交,不过这样会扣除这道题一定的分数。

其次是TC的计分规则。复杂的数学公式很难看懂,但大概的计分思想是:根据此次比赛的得分算出一个这次比赛的rank,然后和以前的rank做比较,求出一个期望的rank,再根据这个期望的rank调整rating。而有时也会出现考得很砸但依然涨rating的情况,不过总体来说TC的计分公式是十分稳定的。

运行环境

TC的客户端是一个Java程序,所以需要JRE(Java Runtime Environment)或者JDK(Java Development Kit)来运行。如果平时不写Java程序的话,装JRE就可以了。毕竟JDK比JRE大一个数量级,下载慢。安装照着提示完成就行了。推荐使用1.4.1以后的版本,因为带了java web start,可以快速登陆。具体方法下一部分讲。

JRE下载地址(中文): http://www.java.com/zh_CN/download/index.jsp

注册

原文在注册的地方没有详细说明,但很多人似乎对注册都有疑问。所以这里我来注册一个小号,并通过整个过程讲解如何注册。

首先打开 http://www.topcoder.com/tc (本文后面TopCoder的主页都指这个网址),然后点击右上角的Register Now(没看到?你可能看到了一个Login,目光向下挪一点,那个红底白字的“Register Now”就在下面)。接下来会弹出 http://www.topcoder.com/reg 这个页面,因为我们要参加SRM,所以选择第一个,Competition Registration。如果要参加TCHS可以选择第二个High School (Secondary School) Registration。这些以后都可以更改(这里没有选的如果以后要选上,只需要更新个人设置并挑勾;如果选上的要撤销选择则需要点一个“Unregister”的链接)。这里选择项目的多少和后面的页面需要填写内容的多少相关,本文以只选择第一项为例。

需要填写的项目和对应的中文翻译如下:

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
48
49
50
51
* Given Name:  名
* Surname:      姓
* Address1:  地址1
Address2:  地址2
Address3:  地址3(如果一行写不开,就在三行中分别写)
* City:    城市
State (US Only):  地区(不在美国就不用选)
Postal Code:  邮编
Province:  省
* Country:  国家
* Country to represent:  代表国家(不知道啥意思,中国人两个都填China就行)
* Timezone:  时区(选Asia/Chongqing)
Phone Number:  电话号码
* Email Address:  电子邮件
* Confirm Email Address:  确认电子邮件地址(就是把电子邮件地址重新打一遍)
Email Notifications:  邮件提醒(就是它给你发邮件提醒什么东西)
- Algorithm Competitions  算法比赛,就是SRM和TCOpen
- Software Development Opportunities  貌似就是有软件开发的项目就告诉你
- Employment Opportunities  工作机会
- TopCoder News & Events  新闻
* Enable Member Contact:  允许成员联系(似乎就是说是不是让别人在TC上能找到你)
* Show / hide earnings:  显示/隐藏收入(大概是说别人是不是能看到你赚了多少钱,TC的比赛可是有钱赚的)
* User Name:  用户名(下面的话提醒你一定不要填错,因为注册多个用户是不符合规定的。据说有人因为别人在TC客户端和他打招呼说“怎么你拿小号上了”,那个人的号就被封了)
* Password:  密码
* Confirm Password:  确认密码
* Secret Question:  密码找回问题(找回密码时需要回答这个问题,注意至少要8个字符长,而一个中文字似乎算一个字符,所以最后可能要打几个问号补齐长度)
* Secret Question Response:  密码找回问题答案
Quote:  座右铭,就是个签名档之类的东西
* Student/Professional:  学生/职业程序员
* = required  带*的项目必填
填写之后点Term of Use下面的I Agree,再点Submit,完成提交。除了用户名别的以后似乎都可以改。
接下来进入Demographics页面,这个大概相当于一个注册用户情况调查。
* Age :  年龄
* Gender :  性别(Male男,Female女)
* Ethnic Background :  民族背景(似乎选Asian or Pacific Islander就行吧……)
* Primary Interest in TopCoder :  在TC的主要兴趣,看不懂的就选第一个吧,那个是说你的兴趣在奖金……
* Shirt Size :  T-Shirt大小(有的比赛会给排名前N的选手发T-Shirt,这里你需要选择适合自己的大小,如果选最后一个说明你不想要T-Shirt,人家也不发你了。TC的T-Shirt还是挺好看的,比AStar的好)
* College Major :  大学的专业
* College Major Description :  这个不知道啥意思,随便填点东西就行……
* Degree Program :  学位(从上到下分别为:准学士,学士,硕士,博士,中学生)
* Graduation Year :  毕业年份
* Graduation Month :  毕业月份
* Clubs / Organizations :  组织(一般选None,可以按住Ctrl点鼠标多选)
Other Clubs / Organizations :  其它组织
* School:  学校(点Choose School选择学校,可以搜索,不过为啥shanghaijiaotong university才2个人注册?!)
* Show / hide my school:  显示/隐藏我的学校
GPA:  不懂的自己百度去……
GPA Scale:  同上
Resume:  简历
* How did you hear about TopCoder?:  你怎么知道的TC,如果选了“Member Referral”的话,需要填写那个人在TC的用户名(欢迎填写sqybi~)
* = required

点Submit,进入Confirm页面,确认信息。如果有误可以点Edit修改,否则点最下面的Confirm提交。

接下来进入Success,提示你已经发送一封邮件到你的邮箱中,你必须去点击里面的链接激活用户。激活之后就可以使用这个用户了。

登录

登录的方法一般都是使用Java Web Start。

在TopCoder主页(http://www.topcoder.com/tc%EF%BC%89%E5%B7%A6%E4%BE%A7Algorithm (SRM)->Launch Arena(已失效:最下方有一段话,第一句是“Load the Arena as an Applet or as a Java Web Start Application”。点“Java Web Start Application”,)就会自动下载登陆需要的文件(一个jnlp格式的文件,本机装了JRE/JDK才能打开)。经测试在IE7下这个链接似乎不管用,在Firefox 3下正常。

然后运行下载下来的jnlp文件,就打开了TC客户端。第一次运行和有更新的时候会自动下载安装程序,等待即可,很快。 在我这里有时会提示“语法错误”,但没有任何影响,点“确定”就可以。启动可能会慢一些,耐心等待。 然后输入用户名密码,在Connection的地方选合适的登录方式(一般Direct就行,如果不行的话可以试试别的或者用AUTODETECT自动检测),在PROXY处设置代理,点GO登陆。这时可能还会提示语法错误,再确定就行,这个也没有什么影响。 界面
下面的图们来自原文,很经典,不打算改动了。请使用等宽字体浏览。
主界面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
-----------------------------------------------------------------------
|    Advertisements.............                                        |
-----------------------------------------------------------------------
| Main | Lobbies | Options | Practice Rooms | Active Contests | Help ||
-----------------------------------------------------------------------
|                                                  | Clock |            |
-----------------------------------------------------------------------
| Rating Key | Who's here |                  Chat Area                  |
|      .       |             |                                            |
|      .       |             |                                            |
|      .       |             |                                            |
|      .       |             |                                            |
|      .       |             |                                            |
|------------|             |                                            |
|  MESSAGES  |             |                                            |
|------------|             |                                            |
|LEADER BOARD|             |                                            |
|------------|             |                                            |
|             |             |                                            |
|             |             |-------------------------------------------|
|             |             | >>_______________________________________ |
-----------------------------------------------------------------------
Advertisements 广告。

菜单项:

1
2
3
4
5
6
- Main里可以看在线名单和找人。
- Lobbies基本用不着,因为用户一般都在Chat Room 1。
- Options里是一些选项和颜色设置。
- Practice Rooms里有大量的练习,都是以前比赛的题目
- Active Contests只有有比赛的时候才有用,显示当前正在进行和将要进行的比赛以及比赛注册之类的东西。
- Help里是....不用说了吧。

Rating Key: handle的颜色是随着积分而改变的,这里显示了积分与颜色的关系。
MESSAGES: 比赛的时候这里有注册提示和clarification。
LEADER BOARD: 看每个room的最高分。
Who’s here: 当前room里的人。
Chat Area: 聊天。

练习

在Practice Rooms里随便选择一个room就可以进入practice了。

界面与主页面稍有变化,但基本相同,略去不画。主要的变化就是Who’s here分成了两块,多了一块Who’s assigned。这块显示的是谁被分到了这个room。因为是练习区,所以只要是在这里打开过题的都算是assigned。而在正式比赛中room是由TC分配的。这里显示的是被分配到这个room的人。界面上还有一个变化是Chat Area顶上多了三块。最左边的是一个下拉菜单。里面有三个分值,选择后就可以打开相应的题目。中间的summary可以看这个room里每个人的提交情况。

在practice room里只有coding phase。提交后要判的话需要自己选择Practice Options(多出来的菜单项)里的Run System Test。

比赛

每次比赛(除了1年两次的大赛)都需要在赛前3小时-5分钟之间登陆注册方可参加,注册需要在Active Contest菜单中,选择你要参加的那个比赛,再选择Register。注意比赛前5分钟注册停止,这时候如果没有注册就不能参赛了。而注册了没有打开题目也视为没有参赛,rating不变动。

然后TopCoder开始根据每个人的rating分配room,一般每个room都有高手和菜鸟,只不过如果你的rating高,和高手分在一起的概率高一些(当然也不一定是这样,比如我上次就和yuhch大牛分在了一起……)

分配完成后,Active Contest菜单中Register一项变成Enter。选择后可以直接进入你被分配到的room。Active Contest菜单最下面还有一项暗色背景的Room子菜单,可以进入各个room溜达。

进入自己room的时候一般离开始只有3分钟左右,静一下心就可以直接开始比赛了。coding phase的过程与practice基本相同。注意每题的得分是和用的时间相关(见前面的计分规则),而时间是从你打开该题开始算的。所以一题做完后可以不急着打开下一题,先放松一下。 75分钟的coding后是5分钟的intermission,这段时间是用来休息和聊天的。

然后就是最刺激的15分钟challenge phase,也就是通常说的cha人。打开summary,双击别人的各题Score可以打开那题的程序,如果觉得有错误就可以点左下的Challenge然后输入你认为他会错的输入数据,如果输入数据合法那么系统会用标程的输出和这个程序的输出对比,如果出现不同则cha人成功。成功的话你能得到50分,对方该题分数为0;而如果失败了,你会被减去25分。每个程序只能成功被cha一次,也就是说,如果有人cha掉了这个程序,你就不能再次cha。但是一个人可以cha某个程序很多次,直到这个程序被cha掉或者你放弃。

Challenge结束后就是System Test。这个过程一般比较慢,可以先走开做其他事,过20分钟再回来看结果。System Test中的测试数据有两种:一种是出题者准备的测试数据,一种是成功cha掉别人的数据。所以,TC中很少出现有bug的程序能通过System Test的情况。 结果出来后再过一段时间,就可以看到一系列message,比如rating更新了,新的practice room建好了以及可以通过主页查看这次比赛的数据了。这时比赛就宣告结束。

注意事项

1.在TC主页(http://www.topcoder.com/tc%EF%BC%89%E4%B8%8A%E5%8F%AF%E4%BB%A5%E7%9C%8B%E5%88%B0Next SRM,这是下次SRM的时间。注意我们的时间与他们刚好相差12小时,因此若时间是7月9日9:00 PM的话,这里是7月10日9:00 AM。还有要注意的是美国有夏令时,非夏令时的时候,还要再加1小时,就是7月10日10:00 AM。

2.Practice Rooms里写的程序只要点SAVE就可以保存,下次login的时候还可以看到,但是比赛时候的程序必须Submit才可以在coding phase结束后保存(coding phase结束前还是只要SAVE就可以的)。

3.若想cha别人的程序,自己必须是正分(0分也不行),所以若没有一题有正确的程序但有很好的数据的话,随便交一道看上去正确的程序,然后在challenge的时候快下手,就可以赚到了。

4.客户端自带的编辑器只有基本的编辑功能和编译及测试功能,所以若觉得不方便的话可以使用parser和plugin,TC主页最下面有plugin的连接。每个plugin都有详细说明文档,这里不再赘述。

5.TC的FAQ: http://www.topcoder.com/?&t=support&c=index

6.最后一条,千万不要作弊,会有严重的后果。

SRM的输入输出

SRM是不用标准或文件输入和输出的,只要写一个类的一个成员函数。也就是说,你需要编写的并不是一个完整的程序,而是一个类。 输入是成员函数的参数,输出用return,所以经常需要STL中的vector和string。

因为TC的系统并不测试标准输出,所以标准输出可以当调试用。

编辑器

打开题目后,TC默认使用的编辑器为Standard,在右上角可以看到,choose your editor。我们可以通过使用插件的方式增加自己的编辑器。

随便进入一个Practise Rooms,可以看到增加了一栏为Tools,Tools下有个TopCoder Plugins,点击进入,或者通过这个链接: http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins
常用的编辑器有KawigiEdit、PopsEdit和FileEdit,其中KawigiEdit编辑器已经将运行sample的功能添加了进来,会比较方便一些。
以安装KawigiEdit为例说明下插件的安装方法。
a.下载KawigiEdit,从上面的页面链接或者是
http://www.topcoder.com/contest/classes/KawigiEdit/KawigiEdit.jar
下载放到一个目录中,比如:
C:\Documents and Settings\Administrator\桌面\topcoder
b.进入Options->Editor,在这里添加新的编辑器。点击Add按钮,在Name一栏输入编辑器的名字,比如KawigiEdit;在EntryPoint一栏输入jar的运行方式,这里是:kawigi.KawigiEdit;ClassPath就是类所在的位置,这里通过Browse按钮将KawigiEdit.jar的地址添加进来,比如C:\Documents and Settings\Administrator\桌面\topcoder\KawigiEdit.jar
c.将KawigiEdit设置为默认的编辑器,将Default复选框打勾

Java 多次排序的方法

Java 多次排序的方法

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
import java.util.*;

class Node implements Comparable
{
	int x,y;
	public int compareTo(Object obj){
		Node oo=(Node)obj;
		if(Main.u == 1) {
			if(oo.x < this.x || oo.x == this.x && oo.y <this.y)return 1;
			return -1;
		} else
		if(Main.u == 2) {
			if(oo.y < this.y || oo.y == this.y && oo.x <this.x)return 1;
			return -1;
		}
		return -1;
	}
}

public class Main {
	public static int u;

	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		Node a[]=new Node[11];
		int i,j,k,l;
		for(i=1;i<=10;i++) {
			a[i]=new Node();
			a[i].x=Math.abs(5-i); a[i].y=10-Math.abs(7-i);
		}
		u = 1;
		Arrays.sort(a, 1, 11);
		System.out.println(" sort u = 1");
		for(i=1;i<=10;i++)System.out.println(a[i].x+" "+a[i].y);
		u = 2;
		Arrays.sort(a, 1, 11);
		System.out.println(" sort u = 2");
		for(i=1;i<=10;i++)System.out.println(a[i].x+" "+a[i].y);
	}
}

Java Mune & Button

Java Mune & Button

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//package java_menu;
import java.awt.*;
import java.awt.event.*;

class BBB extends Button
{
	private int tt=0;
	public BBB() {
		super("0");
		addMouseListener( new MouseListener() {
			public void mousePressed(MouseEvent e) {
				setLabel(String.valueOf((++tt)));
			}
			public void mouseExited(MouseEvent e) {}
			public void mouseReleased(MouseEvent e) {}
			public void mouseEntered(MouseEvent e) {}
			public void mouseClicked(MouseEvent e) {}
		});
		int x=(int)(Math.random()*10000), y=(int)(Math.random()*10000);
		setBounds( x % 500+70, y % 300+70, 70, 70);
		show();
	}
}

class MenuExam extends Frame
{
	public MenuExam()
	{
		super("abcdxyzk");
		MenuBar bar = new MenuBar(); setMenuBar(bar);
		Menu bb = new Menu(" bbb ");
		MenuItem b1 = new MenuItem(" b1 ");
		MenuItem b2 = new MenuItem(" b2 ");
		bb.add(b1); bb.addSeparator(); bb.add(b2); bar.add(bb);

		b2.addActionListener( new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				BBB bbb = new BBB();
				add(bbb);
			}
		});
		setLayout(null);   setSize(700, 500);
		TextField tf = new TextField();
		tf.setText("click b2");
		tf.setFont(new Font("TimesRoman", Font.BOLD, 30));
		tf.setEnabled(false);
		tf.setBounds(100, 350, 200, 100);
		add(tf);
		show();
	}
}

public class Main {
	public static void main(String[] args) {
		MenuExam mm = new MenuExam();
		mm.addWindowListener( new WindowAdapter() {
			public void windowClosing(WindowEvent e) {
				System.exit(0);
			}
		});
	}
}