本週閱讀2006.09.24-2006.09.30

• 易學易用的 Windows PowerShell
  
• MIT 開鎖指南
  
• 深度學習C++
  
• STLport
  
• The Boost C++ Libraries
  
• 使用Subversion进行版本控制
  
• The following .vimrc produces, in our opinion, very nicely formatted C code:
  

  set  nocp incsearch
  set  cinoptions=:0,p0,t0
  set  cinwords=if,else,while,do,for,switch,case
  set  formatoptions=tcqr
  set  cindent
  syntax on
  source ~/.exrc

  The nocp option turns off strict vi compatibility. The incsearch option turns on
  incremental searching. The settings for cinoptions, cinwords, and
  formatoptions differ from the defaults; the result is to produce a fairly strict
  "K&R" C formatting style. Finally, syntax coloring is turned on, and then the rest
  of the vi options are read in from the user's .exrc file.

本週閱讀2006.09.10-2006.09.16

科學人雜誌網站 - 政治腦

XSS
XSS, Cookies, and Session ID Authentication – Three Ingredients for a Successful Hack
Burp - a Java-based proxy
CGI 介紹

事實上, 使用者填在 Form 中的資料, 瀏覽器會先將其組合成一個

    參數1=參數1內容&參數2=參數2內容&...

的參數串, 再傳給 Http server

接著看 Form標記中, Method 的種類

Method=GET 時,
Http server 會將參數串設成環境變數 QUERY_STRING, CGI 程式只要將這個環境變數抓出來用即可, 
不過由於是透過環境變數在傳遞這個參數串, 所以會有長度上的限制.

Method=POST 時,
Http server 會將參數串透過標準輸入傳給 CGI 

[ 永遠的UNIX > CGI之C語言篇 ]

 printf("%d\n", '\r'); // 13, carriage return
 printf("%d\n", '\n'); // 10, new line character
 printf("%d\n", '\0'); // 0

Vim 實用技術，第 3 部分: 定製 Vim

1. 在 Vim 中打開 .vimrc 文件；
2. 執行命令「:colorscheme koehler」（缺省配色可能在瀏覽器中效果不佳）
3. 執行命令「:%!nl -w4 -s' '」(1.11 節)
4. 執行命令「:TOhtml」(1.13 節)
5. 執行命令「:w」

排列組合

在PTT看到[問題] 關於排列組合，就是印出集合的所有排列組合3的字的集合印出{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

• 最簡單的：用迴圈
  

  #include <iostream>
  using namespace std;void main() {
      char a[]="ABC";
      int i,j,k,n;
      n = strlen(a);
      for (i=0;i<n;i++) {
          for (j=0;j<n;j++) {
              for (k=0;k<n;k++) {
                  if (a[i]!=a[j] && a[i]!=a[k] && a[j]!=a[k])
                      cout << a[i] << a[j] << a[k] << endl;
              }
          }
      }
  }

  
  
• 再來是用stack+迴圈
  

  #define MAX 5
  
  int mark[MAX+1]= {0};// 記錄某一元素是否已使用
  int stack[MAX+1]; // 記錄放進去的先後
  // mark[0]、stack[0] 不放資料
  
  run=1; // 記錄是不是還要找下去
  
  len=0; // 目前的長度
  while(run) {
      if(len<MAX) {
          從 mark[] 中找到第一個還沒放進去的為 k
          mark[k]=1;
          stack[++len]=k;
      }
      else // len==MAX
      {
          從 stack[1] 到 stack[MAX] 全部印出來
          從 stack[MAX] 往前找到第一個非遞增的數為 k, 其位置為 j
          // 例如 3 4 5 2 1, 從後前找 1 2 5 是遞增, 但是 4 不是,
  
          // 所以 k=4, j=2
          如果找不到, 則把 run 設成 0, 並且 break;
          // 例如 5 4 3 2 1, 這是最後一種排列, 找完這一個就可以結束了
          把 stack[j] 到 stack[MAX] 的所有數對應 mark[] 值都設為 0,
          // 也就是把這些數拿出來
          再找 k 的下一個還沒放進去的數為 m
          len=j;
          stack[j]=m;
          mark[m]=1;
          // 例如 3 4 5 2 1, 則把 4 5 2 1 拿出來之後剩 3,
  
          // 再找 4 的下一個為 5 放進去, 就變成 3 5
      }
  }
  

  
  
• 用recursive的 良葛格的Algorithm Gossip
  

  #include <stdio.h>
  #include <stdlib.h>
  #define N 4
  
  void perm(int*, int);
  
  int main(void) {
      int num[N+1], i;
      
      for(i = 1; i <= N; i++)
          num[i] = i;
      perm(num, 1);
      return 0;
  }
  void perm(int* num, int i) {
      int j, k, tmp;
      
      if(i < N) {
          for(j = i; j <= N; j++) {
              tmp = num[j];
              // 旋轉該區段最右邊數字至最左邊 
              for(k = j; k > i; k--)
                  num[k] = num[k-1];
              num[i] = tmp;
              
              perm(num, i+1);
              
              // 還原
              for(k = i; k < j; k++)
                  num[k] = num[k+1];
              num[j] = tmp;
          }
      }
      else {  // 顯示此次排列
          for(j = 1; j <= N; j++)
              printf("%d ", num[j]);
          printf("\n");
      }
  }

Maximum Interval Sum

• 定義給n個整數num[0..n-1]，maximum interval sum要求 0<=i<j<=n-1，
  sum = num[i]+...+num[j]中最大那一個
  
• 作法: sweep from left to right, accumulate the sum one element by one
  element, start new interval whenever you encounter partial sum<0 (and record
  current best maximum interval encountered so far)
  
• 範例:

  num: 4 -5 4 -3 4 4 -4 4 -5
  sum: 4 -1 4  1 5 9  5 9  4

• 解釋，對某一個位置k, sum[k]要根據sum[k-1]決定要不要累加sum[k-1],
  如果sum[k-1]小於0, 捨棄, 從位置k開始累加, 如果大於0, 把sum[k-1]累加.
• code:
  

  max = sum[0] = num[0];
  for(i=1 ; i<n ; i++) {
      if(sum[i-1] < 0)
          sum[i] = num[i];
      else
          sum[i] = sum[i-1] + num[i];
      if(sum[i] > largest)
          max = sum[i];
  }

  
  
• 練習題: 507 - Jill Rides Again, 10684 - The Jackpot

tag: acm programming

今日閱讀2006-09-02

• [分享] 不改變打電話習慣，輕鬆將Skype整合到一般有/無線話機或電話總機(PBX) - Skype網路電話轉接盒(USB)
  
• Haskell Tutorial for C Programmers
  
• Adding Google sitemap to blogger.com blog account
  
• Find Visited URLs With JavaScript

Pastbin

• ISul - Pastbin
  
• Wikipedia - Pastbin
  

菲爾茲獎

• 雜談：arXiv 與特立獨行人士
  
• [資訊] 菲爾茲獎的兩位數學家
  
• MANIFOLD DESTINY

Wikipedia 條目

• Wikipedia - Memoization
  
• Wikipedia - Distributed hash table
  
• WiKipedia - Pastebin
  

strchr

譬如要找在Hello World中W出現在第幾個char, 注意p-target的部分

int main() {
    char target[] = "Hello World", *p;
 
    p = strchr(target, 'W');
    printf("The character W was found at position %d\n", p-target);
}

The character W was found at position 6

或者用strcspn, 注意這邊"W"是雙引號,因為第二個參數是個char *而不是char

int main()
{
      char target[] = "Hello World";
      int position;
 
      position = strcspn(target, "W");
      printf("The character W was found at position %d\n", position); 
}

The character W was found at position 6

類似的還有strpbrk, 跟strchar在於第二個函式是個char *, 可以match多個char

hex, oct -> decimal -> hex, oct

int main()
{
      char hex[100], oct[100];
      long num = 32712;

      puts(hex);
      sprintf(hex, "%X", num);
      puts(hex);
      sprintf(oct, "%o", num); 
      puts(oct);

      sscanf(hex, "%x", &num);
      printf("%d\n", num);
      sscanf(oct, "%o", &num);
      printf("%d\n", num);
}

7fc8
7FC8
77710
32712
32712

scanf + size_t

int main()
{
    char dummy[100];
    char buf[100];
 
    scanf("%s\n", dummy);
    gets(buf);
 
    printf("|%s|\n", buf);
}

input:
ABCDEF
   123
output:
|123|

注意scanf會吃掉123前面的三個space

int main()
{
    char dummy[100];
    char buf[100];

    scanf("%s", dummy);
    gets(buf);
    printf("|%s|\n", buf);
}

input:
ABCDEF
   123
output:
||

注意scanf會吃掉空白但是不會吃掉'\n'

http://beej.us/guide/bgc/output/html/scanf.html
%[

This is about the weirdest format specifier there is. It allows you to specify a set of characters to be stored away (likely in an array of chars). Conversion stops when a character that is not in the set is matched.

For example, %[0-9] means "match all numbers zero through nine." And %[AD-G34] means "match A, D through G, 3, or 4".

Now, to convolute matters, you can tell scanf() to match characters that are not in the set by putting a caret (^) directly after the %[ and following it with the set, like this: %[^A-C], which means "match all characters that are not A through C."

To match a close square bracket, make it the first character in the set, like this: %[]A-C] or %[^]A-C]. (I added the "A-C" just so it was clear that the "]" was first in the set.)

To match a hyphen, make it the last character in the set: %[A-C-].

So if we wanted to match all letters except "%", "^", "]", "B", "C", "D", "E", and "-", we could use this format string: %[^]%^B-E-].