9/28/2006

本週閱讀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.
於 沒有留言:

9/12/2006

本週閱讀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」
於 沒有留言:

9/09/2006

排列組合

在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");
        }
    }
於 沒有留言:

9/05/2006

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
於 沒有留言:

9/02/2006

今日閱讀2006-09-02

Pastbin菲爾茲獎Wikipedia 條目
於 沒有留言:

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-].
於 沒有留言: