糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

个人说明


关于写博客的目的
引用一句话“如果每个程序员都写博客,中国的技术水平就不是现在这个样子”。
对,这就是我写博客的目的。我必须尽量保证博客里的每一篇文章都清晰明了,适于阅读,能让他人在最短时间能获得想要的东西。
因此我以后不会把废话放上来,保证发表的文章都是关于技术,并且有利于他人。

关于我
豆瓣:http://www.douban.com/people/nuomihaochi/

posted @ 2011-08-24 09:55 糯米 阅读(298) | 评论 (1)编辑 收藏

lisp let,let*

let and let* create new variable bindings and execute a series of forms that use these bindings. 
let performs the bindings in parallel and let* does them sequentially.

The form

(let ((var1 init-form-1)
(var2 init-form-2)
...
(varm init-form-m))
declaration1
declaration2
...
declarationp
form1
form2
...
formn)

first evaluates the expressions init-form-1, init-form-2, and so on, in that order, saving the resulting values.
Then all of the variables varj are bound to the corresponding values;
each binding is lexical unless there is a special declaration to the contrary.
The expressions formk are then evaluated in order; the values of all but the last are discarded
(that is, the body of a let is an implicit progn).
let* is similar to let, but the bindings of variables are performed sequentially rather than in parallel.
The expression for the init-form of a var can refer to vars previously bound in the let*.

The form

(let* ((var1 init-form-1)
(var2 init-form-2)
...
(varm init-form-m))
declaration1
declaration2
...
declarationp
form1
form2
...
formn)
first evaluates the expression init-form-1, then binds the variable var1 to that value;
then it evaluates init-form-2 and binds var2, and so on.
The expressions formj are then evaluated in order;
the values of all but the last are discarded (that is, the body of let* is an implicit progn).

For both let and let*, if there is not an init-form associated with a var, var is initialized to nil.

The special form let has the property that the scope of the name binding does not include any initial value form.
For let*, a variable's scope also includes the remaining initial value forms for subsequent variable bindings.


Examples:

(setq a 'top) => TOP
(defun dummy-function () a) => DUMMY-FUNCTION
(let ((a 'inside) (b a))
(format nil "~S ~S ~S" a b (dummy-function))) => "INSIDE TOP TOP"
(let* ((a 'inside) (b a))
(format nil "~S ~S ~S" a b (dummy-function))) => "INSIDE INSIDE TOP"
(let ((a 'inside) (b a))
(declare (special a))
(format nil "~S ~S ~S" a b (dummy-function))) => "INSIDE TOP INSIDE"

posted @ 2011-08-22 11:50 糯米 阅读(753) | 评论 (1)编辑 收藏

lisp loop,dotimes,dolist,do

Simple LOOP loops forever...

? (loop
    (print "Look, I'm looping!"))
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
... and so on, until you interrupt execution... 
Aborted
? 

? (let ((n 0))
    (loop
      (when (> n 10) (return))
      (print n) (prin1 (* n n))
      (incf n)))
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
10 100
NIL
?


Use DOTIMES for a counted loop

? (dotimes (n 11)
    (print n) (prin1 (* n n)))
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
10 100
NIL
?


Use DOLIST to process elements of a list

? (dolist (item '(1 2 4 5 9 17 25))
    (format t "~&~D is~:[n't~;~] a perfect square.~%" item (integerp (sqrt item))))
1 is a perfect square.
2 isn't a perfect square.
4 is a perfect square.
5 isn't a perfect square.
9 is a perfect square.
17 isn't a perfect square.
25 is a perfect square.
NIL


? (dolist (item `(1 foo "Hello" 79.3 2/3 ,#'abs))
    (format t "~&~S is a ~A~%" item (type-of item)))
1 is a FIXNUM
FOO is a SYMBOL
"Hello" is a (SIMPLE-BASE-STRING 5)
79.3 is a DOUBLE-FLOAT
2/3 is a RATIO
#<Compiled-function ABS #x1E9CC3E> is a FUNCTION
NIL
? 

DO is tricky, but powerful

? (do ((which 1 (1+ which))
       (list '(foo bar baz qux) (rest list)))
      ((null list) 'done)
    (format t "~&Item ~D is ~S.~%" which (first list)))
Item 1 is FOO.
Item 2 is BAR.
Item 3 is BAZ.
Item 4 is QUX.
DONE
? 
(do ((var1 init1 step1)
     (var2 init2 step2)
     ...)
    (end-test result)
  statement1
  ...)

var1       = which
init1      = 1
step1      = (1+ which)
var2       = list
init2      = '(foo bar baz qux)
step2      = (rest list)
end-test   = (null list)
result     = 'done
statement1 = (format t "~&Item ~D is ~S.~%" which (first list))



posted @ 2011-08-22 11:05 糯米 阅读(511) | 评论 (0)编辑 收藏

lisp find find-if find-if-not

find item sequence &key from-end test test-not start end key => element

find-if predicate sequence &key from-end start end key => element

find-if-not predicate sequence &key from-end start end key => element

Arguments and Values:

item---an object.

sequence---a proper sequence.

predicate---a designator for a function of one argument that returns a generalized boolean.
接受一个参数的函数,返回boolean

from-end---a generalized boolean. The default is false.
boolean类型,默认为false

test---a designator for a function of two arguments that returns a generalized boolean.
接受两个参数的函数,返回boolean

test-not---a designator for a function of two arguments that returns a generalized boolean.
接受两个参数的函数,返回boolean

startend---bounding index designators of sequence. The defaults for start and end are 0 and nil, respectively.

key---a designator for a function of one argument, or nil.

element---an element of the sequence, or nil.

findfind-if, and find-if-not each search for an element of the sequence bounded by start and end that satisfies the predicate predicate or that satisfies the test test or test-not, as appropriate.

If from-end is true, then the result is the rightmost element that satisfies the test.

If the sequence contains an element that satisfies the test, then the leftmost or rightmost sequence element, depending on from-end, is returned; otherwise nil is returned.


Examples:

Examples:
(find #\d "here are some letters that can be looked at" :test #'char>)
=> #\Space
(find-if #'oddp '(1 2 3 4 5) :end 3 :from-end t) => 3
(find-if-not #'complexp '#(3.5 2 #C(1.0 0.0) #C(0.0 1.0)) :start 2) => NIL

posted @ 2011-08-19 22:04 糯米 阅读(438) | 评论 (0)编辑 收藏

lisp MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON

mapc function &rest lists+ => list-1

mapcar function &rest lists+ => result-list

mapcan function &rest lists+ => concatenated-results

mapl function &rest lists+ => list-1

maplist function &rest lists+ => result-list

mapcon function &rest lists+ => concatenated-results

mapcar operates on successive elements of the listsfunction is applied to the first element of each list, then to the second element of each list, and so on. The iteration terminates when the shortest list runs out, and excess elements in other lists are ignored. The value returned by mapcar is a list of the results of successive calls to function.

mapcar 首先将函数apply到每个列表的第一个元素,再将函数apply到每个列表的第二个元素。。
一直到最短的列表的最后一个元素。剩下的元素将被忽略。
它的结果是返回值不为nil的集合。

mapc is like mapcar except that the results of applying function are not accumulated. The list argument is returned.

mapc 和 mapcar 类似。不过返回的是第一个列表。

maplist is like mapcar except that function is applied to successive sublists of the listsfunction is first applied to the lists themselves, and then to the cdr of each list, and then to the cdr of the cdr of each list, and so on.

maplist 和 mapcar 类似,不过首先将函数apply到每个列表,然后将函数apply到每个列表的cdr,然后将函数apply到每个列表的cddr。。
直到最短的一个列表为空为止。

mapl is like maplist except that the results of applying function are not accumulated; list-1 is returned.

mapl和maplist类似,但是返回的是第一个列表。

mapcan and mapcon are like mapcar and maplist respectively, except that the results of applying function are combined into a list by the use of nconc rather than list. That is,

mapcan 和 mapcon 类似于 mapcar 和 maplist。它们使用 nconc 连接结果而不是 list。
Examples
(mapcar #'car '((1 a) (2 b) (3 c))) =>  (1 2 3)   
(mapcar #'abs '(3 -4 2 -5 -6)) => (3 4 2 5 6)
(mapcar #'cons '(a b c) '(1 2 3)) => ((A . 1) (B . 2) (C . 3))

(maplist #'append '(1 2 3 4) '(1 2) '(1 2 3))  =>  ((1 2 3 4 1 2 1 2 3) (2 3 4 2 2 3)) 
(maplist #'(lambda (x) (cons 'foo x)) '(a b c d)) => ((FOO A B C D) (FOO B C D) (FOO C D) (FOO D))
(maplist #'(lambda (x) (if (member (car x) (cdr x)) 0 1)) '(a b a c d b c)) => (0 0 1 0 1 1 1)
(setq dummy nil) =>  NIL   
(mapc #'(lambda (&rest x) (setq dummy (append dummy x)))
'(1 2 3 4)
'(a b c d e)
'(x y z)) => (1 2 3 4)
dummy => (1 A X 2 B Y 3 C Z)

(setq dummy nil) =>  NIL   
(mapl #'(lambda (x) (push x dummy)) '(1 2 3 4)) => (1 2 3 4)
dummy => ((4) (3 4) (2 3 4) (1 2 3 4))

(mapcan #'(lambda (x y) (if (null x) nil (list x y)))
'(nil nil nil d e)
'(1 2 3 4 5 6)) => (D 4 E 5)
(mapcan #'(lambda (x) (and (numberp x) (list x)))
'(a 1 b c 3 4 d 5)) => (1 3 4 5)

(mapcon #'list '(1 2 3 4)) =>  ((1 2 3 4) (2 3 4) (3 4) (4))  



 

posted @ 2011-08-19 21:44 糯米 阅读(703) | 评论 (0)编辑 收藏

[转]休息五分钟,学几个bash快捷键

From:


 

用快捷键,有两个好处:

1 成就感!

2 效率!

停下手里活,学点一举两得的小技能,保证五分钟搞定!

“棕色粗体”表示“我推荐的”!

Ctrl-A 相当于HOME键,用于将光标定位到本行最前面

Ctrl-E 相当于End键,即将光标移动到本行末尾

Ctrl-B 相当于左箭头键,用于将光标向左移动一格

Ctrl-F 相当于右箭头键,用于将光标向右移动一格

Ctrl-D 相当于Del键,即删除光标所在处的字符

Ctrl-K 用于删除从光标处开始到结尾处的所有字符

Ctrl-L 清屏,相当于clear命令

Ctrl-R 进入历史命令查找状态,然后你输入几个关键字符,就可以找到你使用过的命令

Ctrl-U 用于删除从光标开始到行首的所有字符。一般在密码或命令输入错误时常用

Ctrl-H 删除光标左侧的一个字符

Ctrl-W 用于删除当前光标左侧的一个单词

Ctrl-P 相当于上箭头键,即显示上一个命令

Ctrl-N 相当于下箭头键,即显示下一个命令

Ctrl-T 用于颠倒光标所在处字符和前一个字符的位置。(目前不知道有什么作用,哪位朋友知道?)

Ctrl-J 相当于回车键

Alt-. 用于提取历史命令中的最后一个单词。你先执行history命令,然后再敲击此快捷键若干下,你就懂了!

Alt-BackSpace 用于删除本行所有的内容,基本上和Ctrl-U类似。

Alt-C 用于将当前光标处的字符变成大写,同时本光标所在单词的后续字符都变成小写。

Alt-L 用于将光标所在单词及所在单词的后续字符都变成小写。

Alt-U 用于将光标所在单词的光标所在处及之后的所有字符变成大写。

ps:使用bind -P命令可以查看所有键盘绑定。

ps2:Alt快捷键较少使用,因为常常和编辑器冲突

over~

posted @ 2011-05-30 22:57 糯米 阅读(17568) | 评论 (3)编辑 收藏

Trapping ctrl-c in Bash

#!/bin/bash

# trap ctrl
-c and call ctrl_c()
trap ctrl_c INT

function ctrl_c() {
        echo 
"** Trapped CTRL-C"
}

for i in `seq 1 5`; do
    sleep 
1
    echo 
-"."
done

posted @ 2011-05-30 22:53 糯米 阅读(1165) | 评论 (0)编辑 收藏

POJ 3123 Ticket to Ride 高效解法

低效率解法在这里
低效率的解法是没法通过POJ的数据的。
另外一个标程中的解法十分给力,仅用时110ms(status上面还有用时16ms的)
首先来看一下这段程序:

#include <iostream>
#include 
<string>
#include 
<map>

using namespace std;

int main()
{
    
int INF=99999999,N,K,d[30][30],i,j,k,x,y,z,dp[256][30],e[8],v[30],c,b;
    
string s,t;    
    
while (cin >> N >> K && N) {
        map
<string,int> cityMap;
        
for(i=0;i<N;i++
            
for(j=0;j<N;j++
                d[i][j]
=i==j?0:INF;
        
for(i=0;i<N;i++) {
            cin 
>> s;
            cityMap[s]
=i;
        }
        
if (K)
            
while(cin >> s >> t >> z, x=cityMap[s], 
                    y
=cityMap[t], 
                    d[x][y]
=d[y][x]=min(d[y][x],z), --K);
        
for(k=0;k<N;k++)
            
for(i=0;i<N;i++)
                
for(j=0;j<N;j++)
                    d[i][j]
=min(d[i][j],d[i][k]+d[k][j]);
        
for(i=0;i<8;i++) {
            cin 
>> s;
            e[i]
=cityMap[s];
            
for(j=0;j<N;j++)
                dp[
1<<i][j]=d[j][e[i]];
        }        
        
for(i=1;i<256;i++) {
            
if (!(i&(i-1)))
                
continue;
            
// step1
            for(k=0;k<N;k++) {
                dp[i][k]
=INF;
                v[k]
=0;
                
for(j=1;j<i;j++)
                    
if ((i|j)==i)
                        dp[i][k]
=min(dp[i][k],dp[j][k]+dp[i-j][k]);
            }
            
// step2
            for(j=0;b=INF,j<N;j++) {
                
for(k=0;k<N;k++)
                    
if (dp[i][k]<=&& !v[k])
                        b
=dp[i][c=k];
                
for(k=0,v[c]=1;k<N;k++)
                    dp[i][c]
=min(dp[i][c],dp[i][k]+d[k][c]);
            }
        }
        
        
// step3
        for(i=0,b=INF;z=0,i<256;b=min(b,z),i++)
              
for(j=0;y=0,j<4;z+=!!y*dp[y][x],j++)
                
for(k=0;k<8;k+=2)
                      
if ((i>>k&3)==j)
                        y
+=3<<k,x=e[k];        
        
        cout 
<< b << endl;     
    }
    
return 0;
}

这段程序写得很让人费解。花了半天时间我才搞明白。
实际上大体的思路是跟低效率的解法一样的。
就是在求Minimal Steiner Tree这一步,它用了一种新的动态规划的方法。
动态规划的方程为:
dp[mask][i] = { 以点i为根,包含mask中的点的最小生成树的权值 }

在得知 dp[mask - 1][1...N] 的情况下,如何推出 dp[mask][1...N] 呢?
程序中分为 step1 和 step2 两个步骤。
step1 推出:
a = min{ dp[m1][i] + dp[m2][i] } 其中 m1|m2 = mask
这个很好理解。
step2 推出:
b = min{ dp[mask][j] + d[j][i] }
程序中每次都从 dp[mask][1...N] 中选出最小的一个 dp[mask][c]
按这种顺序更新就能保证结果的正确
因此 dp[mask][i] = min(a, b)

这个动态规划法的确牛逼。

step3则是枚举4条路线的各种组合情况。求出每种组合的MST权值。

代码写得很牛逼。看了半天才看懂。如果让我写,行数至少多出2,3倍来。。
老外就是牛逼,一行代码都不浪费。

posted @ 2011-02-24 17:16 糯米 阅读(1992) | 评论 (1)编辑 收藏

POJ 3123 Ticket to Ride 动态规划+Minimal Steiner Tree

这题绝对不是盖的。
题目大意是:
给出一个无向图,和四对数据。每对数据分别为图中的两个点。
要求添加一些边,使每对点都能连通,让总边权最小。

首先考虑一个子问题:指定一些点,添加一些边,让它们连通,并且总边权最小。
这个问题就是Minimal Steiner Tree问题,解决方法可以见这里
这问题不是盖的,它居然是NP完全问题。。
汗。。今天终于在POJ见识到啥叫NP完全问题了。。

大的问题可以分为多个子问题。可以枚举所有pair的连接状况。
比如说 {1和2链接,3和4链接} 或者 {1独立,2独立,3和4链接} 等等
一共有15种情况。分别为
    // 1,1,1,1
    {{1},{2},{3},{4}},
    // 1,1,2
    {{1,2},{3},{4}},
    {{1,3},{2},{4}},
    {{1,4},{2},{3}},
    {{2,3},{1},{4}},
    {{2,4},{1},{3}},
    {{3,4},{1},{2}},
    // 2,2
    {{1,2},{3,4}},
    {{1,3},{2,4}},
    {{1,4},{2,3}},
    // 1,3
    {{1,2,3},{4}},
    {{1,2,4},{3}},
    {{1,3,4},{2}},
    {{2,3,4},{1}},
    // 4
    {{1,2,3,4}},

其中有一些是重复的,就可以开一个数组保存下来。
贴一个我的程序。当然,这个是TLE的。。官方的数据需要将近一分钟才能跑完。
另外一个标程运行飞快,用得是更好的方法,点这里


#include <stdio.h>
#include 
<string.h>
#include 
<algorithm>
#include 
<cmath>

using namespace std;

char names[32][32];
int N, M;
int W[32][32];
const int INF = 10032*32;
int pairs[4];
int dp[256][2], dn;

int getcity(char *s)
{
    
int i;
    
for (i = 0; i < N; i++)
        
if (!strcmp(s, names[i]))
            
break;
    
return i;
}

int prim(int mask)
{
    
int i, j, mc, mi, a, c, t;

    c 
= 0;
    
for (i = 0; i < N; i++
        
if (mask & (1 << i)) {
            a 
= 1 << i;
            c
++;
        }

    t 
= 0;
    
while (--c) {
        mc 
= INF;
        
for (i = 0; i < N; i++)
            
if (a & (1 << i)) 
                
for (j = 0; j < N; j++)
                    
if (((mask ^ a) & (1 << j)) && W[i][j] < mc) {
                        mc 
= W[i][j];
                        mi 
= j;
                    }
        
if (mc == INF)
            
return INF;
        a 
|= 1 << mi;
        t 
+= mc;
    }

    
return t;
}

int K;

int dfs(int start, int mask, int n)
{
    
int i, r;

    
if (n >= K - 2)
        
return prim(mask);
    
    r 
= prim(mask);
    
for (i = start; i < N; i++
        
if ((1 << i) & ~mask) 
            r 
= min(r, dfs(i+1, mask|(1<<i), n+1));

    
return r;
}

int minicost(int mask)
{
    
int i, r;

    
for (i = 0; i < dn; i++)
        
if (mask == dp[i][0])
            
return dp[i][1];

    K 
= 0;
    
for (i = 0; i < N; i++)
        
if (mask & (1 << i))
            K
++;
    
    r 
= dfs(0, mask, 0);

    dp[dn][
0= mask;
    dp[dn][
1= r;
    dn
++;
    
return r;
}

int stats[15][8][8= {
    
// 1,1,1,1
    {{1},{2},{3},{4}},
    
// 1,1,2
    {{1,2},{3},{4}},
    {{
1,3},{2},{4}},
    {{
1,4},{2},{3}},
    {{
2,3},{1},{4}},
    {{
2,4},{1},{3}},
    {{
3,4},{1},{2}},
    
// 2,2
    {{1,2},{3,4}},
    {{
1,3},{2,4}},
    {{
1,4},{2,3}},
    
// 1,3
    {{1,2,3},{4}},
    {{
1,2,4},{3}},
    {{
1,3,4},{2}},
    {{
2,3,4},{1}},
    
// 4
    {{1,2,3,4}},
};

int main()
{
    
int i, j, k, a, b, c, ans;
    
char sa[32], sb[32];

    
while (scanf("%d%d"&N, &M), N) {
        
for (i = 0; i < N; i++)
            scanf(
"%s", names[i]);
        
for (i = 0; i < N; i++)
            
for (j = 0; j < N; j++)
                W[i][j] 
= INF;
        
for (i = 0; i < M; i++) {
            scanf(
"%s%s%d", sa, sb, &c);
            a 
= getcity(sa);
            b 
= getcity(sb);
            W[a][b] 
= W[b][a] = min(W[a][b], c);
        }
        
for (i = 0; i < 4; i++) {
            scanf(
"%s%s", sa, sb);
            a 
= getcity(sa);
            b 
= getcity(sb);
            pairs[i] 
= (1 << a) | (1 << b);
        }

        
// floyd
        for (k = 0; k < N; k++)
            
for (i = 0; i < N; i++)
                
for (j = 0; j < N; j++)
                    W[i][j] 
= min(W[i][k] + W[k][j], W[i][j]);

        dn 
= 0;
        ans 
= INF;
        
for (i = 0; i < 15; i++) {
            c 
= 0;
            
for (j = 0; stats[i][j][0]; j++) {
                a 
= 0;
                
for (k = 0; stats[i][j][k]; k++)
                    a 
|= pairs[stats[i][j][k] - 1];
                c 
+= minicost(a);
            }
            ans 
= min(ans, c);
        }

        printf(
"%d\n", ans);
    }
    
return 0;
}



 

posted @ 2011-02-24 00:44 糯米 阅读(1063) | 评论 (0)编辑 收藏

Minimal Steiner Tree 简介

MinimalSteinerTree 的意思是:
在图中找出一个生成树,需要将指定的数个点连接,边权总值最小。
最小生成树是 MinimalSteinerTree 的一种特殊情况。
此问题是NP完全问题。
在POJ 3123中的标程给出了一个递归的算法来解决这个问题。

首先用floyd算法求出两两之间的最短路径。
然后把所有点都两两链接起来,权值就是它们的最短路径。
假设指定必须连接的点有N个。
那么MinimalSteinerTree 树中的内点最多有N-2个。
在纸上画一下就知道了,内点最多的情况就是树为满二叉树的情况。
而由于之前的floyd算法。把整个图给“缩”了一下。
所以树最多有N-2+N个点。
枚举所有可能的点集。对每个点集求最小生成树。取最小值即可。

另外一种方法是使用动态规划,详情请见这里

posted @ 2011-02-24 00:19 糯米 阅读(2382) | 评论 (1)编辑 收藏

仅列出标题
共17页: 1 2 3 4 5 6 7 8 9 Last