emacs输入中文

症状：无法在emacs中调出ibus，输入中文
环境: Linux 2.6.32-5-amd64 + GNU Emacs 23.4.1
Locale:

LANG=en_US.UTF-8
LANGUAGE=
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=

解决：
(1)先用locale -a 查看是否安装 zh_CN.UTF-8,如果有，跳过步骤(2)
(2)运行sudo dpkg-reconfigure locales,安装zh_CN.UTF-8
(3)编辑/etc/environment文件，添加

LC_CTYPE="zh_CN.UTF-8"

重启即可

euler 48: 大整数乘法

euler project 48:

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

我是用python解的,python 的数没有大小的限制,这样就很方便,brute force.

在问题的讨论帖中,有人(grimbal)贴了他用C解决的算法。我觉得很优美，记录如下:

#define mod 10000
void ex48(){
    int n, k;
    unsigned int p2, p1, p0;
    unsigned int s2, s1, s0;
    unsigned int t2, t1, t0;

    // s = 0
    s2 = s1 = s0 = 0;
    for( n=1 ; n<=1000 ; n++ ){
        // p = 1
        p2 = p1 = 0; p0 = 1;
        for( k=1 ; k<=n ; k<<=1 );
        while( k>>=1 ){
            // p *= p
            t0 = p0*p0;
            t1 = 2*p0*p1 + t0/mod;
            t2 = 2*p0*p2 + p1*p1 + t1/mod;
            p0 = t0%mod;
            p1 = t1%mod;
            p2 = t2%mod;
            if( n&k ){
                // p *= n
                t0 = p0*n;
                t1 = p1*n + t0/mod;
                t2 = p2*n + t1/mod;
                p0 = t0%mod;
                p1 = t1%mod;
                p2 = t2%mod;
            }
       }
       // s += p
       t0 = p0+s0;
       t1 = p1+s1 + t0/mod;
       t2 = p2+s2 + t1/mod;
       s0 = t0%mod;
       s1 = t1%mod;
       s2 = t2%mod;
    }

    printf("ex48: %02d%04d%04d\n", s2%100, s1, s0);
}

emacs利用g-client发blog

首先介绍和感谢下emacspeak的作者T. V. Raman。Wikipedia中是这 么写的：

T. V. Raman is a computer scientist who is blind.His accessibility research interests are primarily auditory user interfaces and structured electronic documents. He has worked on speech interaction and markup technologies in the context of the World Wide Web at Digital's Cambridge Research Lab (CRL), Adobe Systems and IBM Research.[2] He currently works at Google Research.

这样的牛人，着实让人敬仰。

要在emacs中向托管在blogger的博客发blog，emacswiki上介绍了好几种方案，比较流行的方 法是使用weblogger,我试验了一下，并不管用。最后我选择使用 g-client + emacs-w3m 的 方案。g-client是emacspeak中的一个组 件，利用Google DATA API 来访问google的服务，emacs-w3m是w3m的emacs前端。当然，还需 要emacs。

得到这个方案并不是轻松的。原因是网上仅有的一些关于g-client的介绍也都 已经过时，还起了误导作用；为了贪图方便，g-client 和 emacs-w3m 都是在其主页下载的 压缩包，但其实打包的版本过于陈旧,这也增加了我按图索骥的困难。最后摸索出来的教训 是:

• g-client
  下载emacspeak的最新版，编译后，从/lisp/g-client提取到emacs load-path。
• emacs-w3m
  emacs-w3m的主页上的稳定版居然是2005年 的，我还以为这项目没有更新了而已。这个版本中甚至g-client所需要的一些函数。应该下载cvs版。

配置文件如下:

;;=========== emacs-w3m ====================
(require 'w3m)
;;=========== emacs-w3m END ================

;; =============== g-client =================
(add-to-list 'load-path "~/.emacs.d/g-client/")
(load-library "g")
(setq g-user-email "yournamee@gmail.com")
;;设置访问时的代理, 后面的参数是默认的
(setq g-curl-common-options "--proxy 127.0.0.1:8087 --compressed --silent --location --location-trusted")
;;使用emacs-w3m访问
(setq browse-url-browser-function 'w3m-browse-url)
;; ================ g-client END ========================

euler 3: Largest prime factor

题出自 Project Euler Problem 3:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

我自己的解法思路是先判断该数（记为A）是否为prime，如果是，则直接返回它本身。否则从该数的一半开始（记为index)，判断index是否能被A整数以及index是否是prime，当两者同时满足时，返回index，否则index自减1。 判断某数是否为prime的算法，是从该数的平方根数开始一个一个检查。代码如下:

#include <stdio.h>
#include <math.h>

//#include <limits.h>

int is_prime(long l);
long largest_prime_factor(long l);

int main(int argc, char *argv[])
{
  long result = largest_prime_factor(600851475143L);
  printf("%ld\n",result);
  return 0;
}

int is_prime(long l){
  long l_sqrt = (long)sqrt(l);
  long i = 2L;
  for(; i <= l_sqrt; i++){
    if(l % i == 0)
      return 0;                 /* is not prime */
  }

  /* is prime */
  return 1;
}


long largest_prime_factor(long l){
  if(is_prime(l))
    return l;
 
  long l_mid = l/2;
  long l_ind;
  for(l_ind = l_mid; l_ind >=2; l_ind--){
    if((l%l_ind == 0) && is_prime(l_ind))
      return l_ind;
  }

  return 1; // never come here
}

上面的算法很惨，算了几十分钟都没有算出结果。所以最后我放弃了，google到了下面这个算法:

#include <stdio.h>

long largest_prime_factor(long l);

int main(int argc, char *argv[])
{
  long result = largest_prime_factor(600851475143L);
  printf("%ld\n",result);
  return 0;
}

long largest_prime_factor(long l){
  long factor = 2L;
  while(l > 1L){
    while(l % factor == 0 ){
      l = l / factor;
    }
    factor++;
  }

  return (factor-1);
}

细想一下，这个算法与筛选法类似。但是，我怎么就没想到呢？FAIL！！！

cURL “虾米” 签到的小脚本

这个脚本用于登陆虾米网站，并进行签到。虽然只是个二三十行的脚本，但由于对cURL不甚
了解，还是搞了几天。主要的经验有:

1.  curl 用 -d 发送表单时，要把按钮的值也加进去("submit=登录")
2.  curl 处理 ajax，应该通过分析javascript脚本，找到真正接收请求的url
3.  curl 模拟 ajax时，添加 HTTP头 "X-Requested-With: XMLHttpRequest"，更好的方法是观察实际的HTTP头，并构造出个一样的
4.  总之，分析浏览器的HTTP请求，再用 cURL构造即可。

#! /bin/bash

declare -r SCRIPT="${0##*/}"

SITE="http://www.xiami.com"
USERAGENT="Mozilla/5.0 (compatible; MSIE 6.0; Windows NT 5.0)"
COOKIEFILE="cookie.txt"

USER="********@gmail.com"
PASSWORD="******"

# 检测cookie
if [[ ! -e $COOKIEFILE ]];then
    # 登录xiami
    curl -c $COOKIEFILE -d "email=$USER&password=$PASSWORD&submit=登录"  "$SITE/member/login"
fi

# 单击"签到"
curl -s  -b $COOKIEFILE -A "$USERAGENT" -e "$SITE" -H "X-Requested-With: XMLHttpRequest" -X POST -d "" "$SITE/task/signin" --retry 5 -H "Connection: keep-alive" 1>/dev/null

# 删除cookie
#rm $COOKIEFILE

判断无符号整数二进制中1的个数(外一则)

三种算法。

算法1：
比较容易想到的算法，逐位比较，最多需要32次。

int count_ones_01(unsigned int n)
{
    int i;
    for(i = 0;n > 0;n >>= 1)
         i += (n&1);
    return i;
}

算法二：
Monster级算法。比较次数比算法1少，最多需要32次(如果int长度为32位的话)。

int count_ones_02(unsigned int n){
  int count=0;
  while(n>0){
    n &= (n-1);
    count++;
  }
  return count;
}

算法三：
二分法。遗憾的是不具有跨平台性。运算次数为5次(\(\log_{2}{32}\))

int count_ones(unsigned int n)
{
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);

    return n;
}

算法的思路是这样的：2位为一组，相加，看看有几个1。再4位为一组，相加，看看有几个1，
以此类推。
为了简单说明，先看看8位的情形。

x = (x & 0x55) + ((x >> 1) & 0x55);    (1)
x = (x & 0x33) + ((x >> 2) & 0x33);    (2)
x = (x & 0x0f) + ((x >> 4) & 0x0f);    (3)
return x;

对于语句(1)

当x=11111111

x= (x & 0x55) + ((x >> 1) & 0x55);

之后x=10101010。你2位2位地看，10=2, 就是2 2 2
2, 就是说各组都是2个1。

当x=00101001

x= (x & 0x55) + ((x >> 1) & 0x55);

之后x=00010101。你2位2位地看，就是0 1 1 1, 前
1组只有0个1，后面的组都是1个1。

接着看语句(2)

当x=abcdefgh

x=(x & 0x33)+((x >> 2)&0x33);

相当于 00cd00gh +　00ab00ef。

因为语句(1)之后，每两位表示该两位有几个１，相加就指示每4位有多少个1。这样就是4位
4位为一组。注意这样的分组，组与组之间永远都不会产生进位的。正因为不会产生进位，才
可以分开来看。

8位，16位，32位依上类推。

外一则：
利用算法三类似的思想，进行反转一个字节的二进制次序。

unsigned char reverse8( unsigned char c )
{
     c = ( c & 0x55 ) << 1 | ( c & 0xAA ) >> 1;
     c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
     c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
     return c;
}

最大的子序列和问题

最大的子序列和问题描述：
给定整数A1,A2，…,AN,求SUM(Ak),k从i到j，的最大值。为了方便起见，如果所有整数均为
负数，则最大子序列和为0。

例：
输入-2,11,-4,13,-5,-2时，答案为20(从A2到A4)

最大子序列和问题的解。
算法一：
穷举,复杂度为O（N^3）

int maxsubsequencesum(const int A[],int N){
    int thissum,maxsum,i,j,k;
   
    maxsum=0;
    for(i=0;i<N;i++)
        for(j=i;j<N;j++){
                thissum=0;
                for(k=i;k<=j;k++)
                        thissum += A[k];
               
                if(thissum > maxsum)
                        maxsum = thissum;
        }
    return maxsum;
}

算法二：
对算法一进行优化，减少内循环，复杂度为O(N^2)

int maxsubsequencesum_2(const int A[],int N){
    int thissum,maxsum,i,j;
   
    maxsum=0;
    for(i=0;i<N;i++){
        thissum=0;
        for(j=i;j<N;j++){
             thissum += A[j];
                    
             if(thissum > maxsum)
                   maxsum = thissum;
        }
    }
    return maxsum;
}

算法三：
分治：最大子序列可能在三处出现，或者整个出现在数据的左半部，或者整个出现在右半部，
或者跨越输入数据的中部而占据左右两半部分。前两种情况可以递归求解，第三种情况的最
大和可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大
和（包含后半部分的第一个元素），将这两个和相加而得到。
复杂度为O（NlgN）

int maxsubsum(const int A[], int left,int right){
    int maxleftsum,maxrightsum;
    int maxleftbordersum,maxrightbordersum;/*包含边界的最大值*/
    int leftbordersum,rightbordersum;
    int center,i;

    if(left == right){
         if(A[left] > 0)
             return A[left];
         else
             return 0; /*由题给条件，负数的最大子序列长度为0*/
    }

    /* divide */
    center = (left + right)/2;
    maxleftsum = maxsubsum(A,left,center);
    maxrightsum = maxsubsum(A,center+1,right);

   /*conquer*/
   maxleftbordersum=0;
   leftbordersum=0;
   for(i=center; i>=left;i--){
       leftbordersum += A[i];
       if(leftbordersum > maxleftbordersum)
          maxleftbordersum = leftbordersum;
   }

  maxrightbordersum=0;
  rightbordersum=0;
  for(i=center+1; i <= right; i++){
      rightbordersum += A[i];
      if(rightbordersum > maxrightbordersum)
          maxrightbordersum = rightbordersum;
  }

  /* max3 取三者最大值 */
  return max3(maxleftsum, maxrightsum, maxleftbordersum + maxrightbordersum);
}

int maxsubsequencesum_3(const int A[], int N){
    return maxsubsum(A,0,N-1);
}

算法四：
在线算法，复杂度O(N),

int maxsubsequencesum(const int A[],int N){
    int thissum,maxsum,j;
    thissum = maxsum = 0;

    for(j=0; j < N; j++){
        thissum += A[j];
       
        if(thissum > maxsum)
            maxsum = thissum;
        else if(thissum < 0)
            thissum = 0;
    }
    return maxsum;
}