mysileng

posted @ 2012-11-30 21:09 鑫龍閱讀(189) | 評論 (0) | 編輯收藏

程序員編程藝術：第五章、尋找和為定值的兩個或多個數

    作者：July，yansha，zhouzhenren。
    致謝：微軟100題實現組，編程藝術室。
    微博：http://weibo.com/julyweibo   。
    出處：http://blog.csdn.net/v_JULY_v  。
    wiki：http://tctop.wikispaces.com/。
------------------------------

前奏

希望此編程藝術系列能給各位帶來的是一種方法，一種創造力，一種舉一反三的能力。本章依然同第四章一樣，選取比較簡單的面試題，恭祝各位旅途愉快。同樣，有任何問題，歡迎不吝指正。謝謝。

第一節、尋找和為定值的兩個數
第14題（數組）：
題目：輸入一個數組和一個數字，在數組中查找兩個數，使得它們的和正好是輸入的那個數字。
要求時間復雜度是O(n)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。
例如輸入數組1、2、4、7、11、15和數字15。由于4+11=15，因此輸出4和11。

分析：

咱們試著一步一步解決這個問題（注意闡述中數列有序無序的區別）：

直接窮舉，從數組中任意選取兩個數，判定它們的和是否為輸入的那個數字。此舉復雜度為O（N^2）。很顯然，我們要尋找效率更高的解法。
題目相當于，對每個a[i]，然后查找判斷sum-a[i]是否也在原始序列中，每一次要查找的時間都要花費為O（N），這樣下來，最終找到兩個數還是需要O（N^2）的復雜度。那如何提高查找判斷的速度列?對了，二分查找，將原來O（N）的查找時間提高到O（logN），這樣對于N個a[i]，都要花logN的時間去查找相對應的sum-a[i]是否在原始序列中，總的時間復雜度已降為O（N*logN），且空間復雜度為O（1）。（如果有序，直接二分O（N*logN），如果無序，先排序后二分，復雜度同樣為O（N*logN+N*logN）=O（N*logN），空間總為O（1））。
有沒有更好的辦法列?咱們可以依據上述思路2的思想，a[i]在序列中，如果a[i]+a[k]=sum的話，那么sum-a[i]（a[k]）也必然在序列中，，舉個例子，如下：
原始序列：1、 2、 4、 7、11、15 用輸入數字15減一下各個數，得到對應的序列為：
對應序列：14、13、11、8、4、 0
第一個數組以一指針i 從數組最左端開始向右掃描，第二個數組以一指針j 從數組最右端開始向左掃描，如果下面出現了和上面一樣的數，即a[*i]=a[*j]，就找出這倆個數來了。如上，i，j最終在第一個，和第二個序列中找到了相同的數4和11，，所以符合條件的兩個數，即為4+11=15。怎么樣，兩端同時查找，時間復雜度瞬間縮短到了O（N），但卻同時需要O（N）的空間存儲第二個數組（@飛羽：要達到O(N)的復雜度，第一個數組以一指針i 從數組最左端開始向右掃描，第二個數組以一指針j 從數組最右端開始向左掃描，首先初始i指向元素1，j指向元素0，誰指的元素小，誰先移動，由于1（i）>0（j），所以i不動，j向左移動。然后j移動到元素4發現大于元素1，故而停止移動j，開始移動i，直到i指向4，這時,i指向的元素與j指向的元素相等，故而判斷4是滿足條件的第一個數；然后同時移動i,j再進行判斷，直到它們到達邊界）。
當然，你還可以構造hash表，正如編程之美上的所述，給定一個數字，根據hash映射查找另一個數字是否也在數組中，只需用O（1）的時間，這樣的話，總體的算法通上述思路3 一樣，也能降到O（N），但有個缺陷，就是構造hash額外增加了O（N）的空間，此點同上述思路 3。不過，空間換時間，仍不失為在時間要求較嚴格的情況下的一種好辦法。
如果數組是無序的，先排序（n*logn），然后用兩個指針i，j，各自指向數組的首尾兩端，令i=0，j=n-1，然后i++，j--，逐次判斷a[i]+a[j]?=sum，如果某一刻a[i]+a[j]>sum，則要想辦法讓sum的值減小，所以此刻i不動，j--，如果某一刻a[i]+a[j]<sum，則要想辦法讓sum的值增大，所以此刻i++，j不動。所以，數組無序的時候，時間復雜度最終為O（n*logn+n）=O（n*logn），若原數組是有序的，則不需要事先的排序，直接O（n）搞定，且空間復雜度還是O（1），此思路是相對于上述所有思路的一種改進。（如果有序，直接兩個指針兩端掃描，時間O（N），如果無序，先排序后兩端掃描，時間O（N*logN+N）=O（N*logN），空間始終都為O（1））。（與上述思路2相比，排序后的時間開銷由之前的二分的n*logn降到了掃描的O（N））。

總結：

不論原序列是有序還是無序，解決這類題有以下三種辦法：1、二分（若無序，先排序后二分），時間復雜度總為O（n*logn），空間復雜度為O（1）；2、掃描一遍X-S[i] 映射到一個數組或構造hash表，時間復雜度為O（n），空間復雜度為O（n）；3、兩個指針兩端掃描（若無序，先排序后掃描），時間復雜度最后為：有序O（n），無序O（n*logn+n）=O（n*logn），空間復雜度都為O（1）。
所以，要想達到時間O（N），空間O（1）的目標，除非原數組是有序的（指針掃描法），不然，當數組無序的話，就只能先排序，后指針掃描法或二分（時間n*logn，空間O（1）），或映射或hash（時間O（n），空間O（n））。時間或空間，必須犧牲一個，自個權衡吧。
綜上，若是數組有序的情況下，優先考慮兩個指針兩端掃描法，以達到最佳的時（O（N）），空（O（1））效應。否則，如果要排序的話，時間復雜度最快當然是只能達到N*logN，空間O（1）則是不在話下。

代碼：

ok，在進入第二節之前，咱們先來實現思路5（這里假定數組已經是有序的），代碼可以如下編寫（兩段代碼實現）：

//代碼一
//O（N）
Pair findSum(int *s,int n,int x)
{
//sort(s,s+n); 如果數組非有序的，那就事先排好序O（N*logN）
int *begin=s;
int *end=s+n-1;
while(begin<end) //倆頭夾逼，或稱兩個指針兩端掃描法，很經典的方法，O（N）
{
if(*begin+*end>x)
{
--end;
}
else if(*begin+*end<x)
{
++begin;
}
else
{
return Pair(*begin,*end);
}
}
return Pair(-1,-1);
}
//或者如下編寫，
//代碼二
//copyright@ zhedahht && yansha
//July、updated，2011.05.14。
bool find_num(int data[], unsigned int length, int sum, int& first_num, int& second_num)
{
if(length < 1)
return true;
int begin = 0;
int end = length - 1;
while(end > begin)
{
long current_sum = data[begin] + data[end];
if(current_sum == sum)
{
first_num = data[begin];
second_num = data[end];
return true;
}
else if(current_sum > sum)
end--;
else
begin++;
}
return false;
}

擴展：
1、如果在返回找到的兩個數的同時，還要求你返回這兩個數的位置列?
2、如果把題目中的要你尋找的兩個數改為“多個數”，或任意個數列?（請看下面第二節）
3、二分查找時： left <= right，right = middle - 1;left < right，right = middle;

//算法所操作的區間,是左閉右開區間,還是左閉右閉區間,這個區間,需要在循環初始化,
//循環體是否終止的判斷中,以及每次修改left,right區間值這三個地方保持一致,否則就可能出錯.
//二分查找實現一
int search(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n - 1;

    while (left <= right)
    {
        middle = left + (right-left)/2;
        if (array[middle] > v)
        {
            right = middle - 1;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}
//二分查找實現二
int search(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n;

    while (left < right)
    {
        middle = left + (right-left)/2;

        if (array[middle] > v)
        {
            right = middle;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

第二節、尋找和為定值的多個數
第21題（數組）
2010年中興面試題
編程求解：
輸入兩個整數 n 和 m，從數列1，2，3.......n 中隨意取幾個數,
使其和等于 m ,要求將其中所有的可能組合列出來。

解法一
我想，稍后給出的程序已經足夠清楚了，就是要注意到放n，和不放n個區別，即可，代碼如下：

// 21題遞歸方法
//copyright@ July && yansha
//July、yansha，updated。
#include<list>
#include<iostream>
using namespace std;
list<int>list1;
void find_factor(int sum, int n)
{
// 遞歸出口
if(n <= 0 || sum <= 0)
return;
// 輸出找到的結果
if(sum == n)
{
// 反轉list
list1.reverse();
for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
cout << *iter << " + ";
cout << n << endl;
list1.reverse();
}
list1.push_front(n); //典型的01背包問題
find_factor(sum-n, n-1); //放n，n-1個數填滿sum-n
list1.pop_front();
find_factor(sum, n-1); //不放n，n-1個數填滿sum
}
int main()
{
int sum, n;
cout << "請輸入你要等于多少的數值sum:" << endl;
cin >> sum;
cout << "請輸入你要從1.....n數列中取值的n：" << endl;
cin >> n;
cout << "所有可能的序列，如下：" << endl;
find_factor(sum,n);
return 0;
}

解法二
@zhouzhenren：
這個問題屬于子集和問題（也是背包問題）。本程序采用回溯法+剪枝
X數組是解向量，t=∑(1,..,k-1)Wi*Xi, r=∑(k,..,n)Wi
若t+Wk+W(k+1)<=M,則Xk=true，遞歸左兒子(X1,X2,..,X(k-1),1)；否則剪枝；
若t+r-Wk>=M && t+W(k+1)<=M,則置Xk=0，遞歸右兒子(X1,X2,..,X(k-1),0)；否則剪枝；
本題中W數組就是(1,2,..,n),所以直接用k代替WK值。

代碼編寫如下：

//copyright@ 2011 zhouzhenren
//輸入兩個整數 n 和 m，從數列1，2，3.......n 中隨意取幾個數,
//使其和等于 m ,要求將其中所有的可能組合列出來。
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
/**
* 輸入t， r，嘗試Wk
*/
void sumofsub(int t, int k ,int r, int& M, bool& flag, bool* X)
{
X[k] = true; // 選第k個數
if (t + k == M) // 若找到一個和為M，則設置解向量的標志位，輸出解
{
flag = true;
for (int i = 1; i <= k; ++i)
{
if (X[i] == 1)
{
printf("%d ", i);
}
}
printf("/n");
}
else
{ // 若第k+1個數滿足條件，則遞歸左子樹
if (t + k + (k+1) <= M)
{
sumofsub(t + k, k + 1, r - k, M, flag, X);
}
// 若不選第k個數，選第k+1個數滿足條件，則遞歸右子樹
if ((t + r - k >= M) && (t + (k+1) <= M))
{
X[k] = false;
sumofsub(t, k + 1, r - k, M, flag, X);
}
}
}
void search(int& N, int& M)
{
// 初始化解空間
bool* X = (bool*)malloc(sizeof(bool) * (N+1));
memset(X, false, sizeof(bool) * (N+1));
int sum = (N + 1) * N * 0.5f;
if (1 > M || sum < M) // 預先排除無解情況
{
printf("not found/n");
return;
}
bool f = false;
sumofsub(0, 1, sum, M, f, X);
if (!f)
{
printf("not found/n");
}
free(X);
}
int main()
{
int N, M;
printf("請輸入整數N和M/n");
scanf("%d%d", &N, &M);
search(N, M);
return 0;
}

擴展：

1、從一列數中篩除盡可能少的數使得從左往右看，這些數是從小到大再從大到小的（網易）。

2、有兩個序列a,b，大小都為n,序列元素的值任意整數，無序；
要求：通過交換a,b中的元素，使[序列a元素的和]與[序列b元素的和]之間的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];（微軟100題第32題）。

    @well：[fairywell]:
給出擴展問題 1 的一個解法：
1、從一列數中篩除盡可能少的數使得從左往右看，這些數是從小到大再從大到小的（網易）。
雙端 LIS 問題，用 DP 的思想可解，目標規劃函數 max{ b[i] + c[i] - 1 }, 其中 b[i] 為從左到右， 0 ~ i 個數之間滿足遞增的數字個數； c[i] 為從右到左， n-1 ~ i 個數之間滿足遞增的數字個數。最后結果為 n - max + 1。其中 DP 的時候，可以維護一個 inc[] 數組表示遞增數字序列，inc[i] 為從小到大第 i 大的數字，然后在計算 b[i] c[i] 的時候使用二分查找在 inc[] 中找出區間 inc[0] ~ inc[i-1] 中小于 a[i] 的元素個數（low）。
源代碼如下：
/**
* The problem:
* 從一列數中篩除盡可能少的數使得從左往右看，這些數是從小到大再從大到小的（網易）。
* use binary search, perhaps you should compile it with -std=c99
* fairywell 2011
*/
#include <stdio.h>

#define MAX_NUM    (1U<<31)

int
main()
{
    int i, n, low, high, mid, max;

    printf("Input how many numbers there are: ");
    scanf("%d/n", &n);
    /* a[] holds the numbers, b[i] holds the number of increasing numbers
    * from a[0] to a[i], c[i] holds the number of increasing numbers
    * from a[n-1] to a[i]
    * inc[] holds the increasing numbers
    * VLA needs c99 features, compile with -stc=c99
    */
    double a[n], b[n], c[n], inc[n];

    printf("Please input the numbers:/n");
    for (i = 0; i < n; ++i) scanf("%lf", &a[i]);

    // update array b from left to right
    for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;
    //b[0] = 0;
    for (i = 0; i < n; ++i) {
        low = 0; high = i;
        while (low < high) {
            mid = low + (high-low)*0.5;
            if (inc[mid] < a[i]) low = mid + 1;
            else high = mid;
        }
        b[i] = low + 1;
        inc[low] = a[i];
    }

    // update array c from right to left
    for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;
    //c[0] = 0;
    for (i = n-1; i >= 0; --i) {
        low = 0; high = i;
        while (low < high) {
            mid = low + (high-low)*0.5;
            if (inc[mid] < a[i]) low = mid + 1;
            else high = mid;
        }
        c[i] = low + 1;
        inc[low] = a[i];
    }

    max = 0;
    for (i = 0; i < n; ++i )
        if (b[i]+c[i] > max) max = b[i] + c[i];
        printf("%d number(s) should be erased at least./n", n+1-max);
        return 0;
}

@yansha：fairywell的程序很贊，時間復雜度O(nlogn)，這也是我能想到的時間復雜度最優值了。不知能不能達到O(n)。

擴展題第2題
當前數組a和數組b的和之差為
    A = sum(a) - sum(b)
a的第i個元素和b的第j個元素交換后，a和b的和之差為
    A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
           = sum(a) - sum(b) - 2 (a[i] - b[j])
           = A - 2 (a[i] - b[j])
設x = a[i] - b[j]，得
    |A| - |A'| = |A| - |A-2x|
    假設A > 0,
    當x 在 (0,A)之間時，做這樣的交換才能使得交換后的a和b的和之差變小，x越接近A/2效果越好,
    如果找不到在(0,A)之間的x，則當前的a和b就是答案。
所以算法大概如下：
    在a和b中尋找使得x在(0,A)之間并且最接近A/2的i和j，交換相應的i和j元素，重新計算A后，重復前面的步驟直至找不到(0,A)之間的x為止。
接上，@yuan：
a[i]-b[j]要接近A/2，則可以這樣想，
我們可以對于a數組的任意一個a[k],在數組b中找出與a[k]-C最接近的數（C就是常數，也就是0.5*A）
這個數要么就是a[k]-C，要么就是比他稍大，要么比他稍小，所以可以要二分查找。
查找最后一個小于等于a[k]-C的數和第一個大于等于a[k]-C的數，
然后看哪一個與a[k]-C更加接近，所以T(n) = nlogn。
除此之外，受本文讀者xiafei1987128啟示，有朋友在stacoverflow上也問過一個類似的題，:-)，見此：http://stackoverflow.com/questions/9047908/swap-the-elements-of-two-sequences-such-that-the-difference-of-the-element-sums。感興趣的可以看看。

本章完。

程序員面試題狂想曲-tctop（the crazy thinking of programers）的修訂wiki（http://tctop.wikispaces.com/）已建立，我們急切的想得到讀者的反饋，意見，建議，以及更好的思路，算法，和代碼優化的建議。所以，
•如果你發現了狂想曲系列中的任何一題，任何一章（http://t.cn/hgVPmH）中的錯誤，問題，與漏洞，歡迎告知給我們，我們將感激不盡，同時，免費贈送本blog內的全部博文集錦的CHM文件1期；
•如果你能對狂想曲系列的創作提供任何建設性意見，或指導，歡迎反饋給我們，并真誠邀請您加入到狂想曲的wiki修訂工作中；
•如果你是編程高手，對狂想曲的任何一章有自己更好的思路，或算法，歡迎加入狂想曲的創作組，以為千千萬萬的讀者創造更多的價值，更好的服務。
Ps：狂想曲tctop的wiki修訂地址為：http://tctop.wikispaces.com/。歡迎圍觀，更歡迎您加入到狂想曲的創作或wiki修訂中。

posted @ 2012-11-30 17:44 鑫龍閱讀(14925) | 評論 (1) | 編輯收藏

最近在做單調隊列，發現了最長上升子序列O(nlogn)的求法也有利用單調隊列的思想。

最長遞增子序列問題：在一列數中尋找一些數，這些數滿足：任意兩個數a[i]和a[j]，若i<j，必有a[i]<a[j]，這樣最長的子序列稱為最長遞增子序列。

設dp[i]表示以i為結尾的最長遞增子序列的長度，則狀態轉移方程為：

dp[i] = max{dp[j]+1}, 1<=j<i,a[j]<a[i].

這樣簡單的復雜度為O(n^2)，其實還有更好的方法。

考慮兩個數a[x]和a[y]，x<y且a[x]<a[y],且dp[x]=dp[y]，當a[t]要選擇時，到底取哪一個構成最優的呢？顯然選取a[x]更有潛力，因為可能存在a[x]<a[z]<a[y]，這樣a[t]可以獲得更優的值。在這里給我們一個啟示，當dp[t]一樣時，盡量選擇更小的a[x].

按dp[t]=k來分類，只需保留dp[t]=k的所有a[t]中的最小值，設d[k]記錄這個值，d[k]=min{a[t],dp[t]=k}。

這時注意到d的兩個特點（重要）：

1. d[k]在計算過程中單調不升；

2. d數組是有序的，d[1]<d[2]<..d[n]。

利用這兩個性質，可以很方便的求解：

1. 設當前已求出的最長上升子序列的長度為len（初始時為1），每次讀入一個新元素x：

2. 若x>d[len]，則直接加入到d的末尾，且len++；（利用性質2）

否則，在d中二分查找，找到第一個比x小的數d[k]，并d[k+1]=x，在這里x<=d[k+1]一定成立（性質1,2）。

/** 
最長遞增子序列O(nlogn)算法： 
狀態轉移方程：f[i] = max{f[i],f[j]+1},1<=j<i,a[j]<a[i]. 
分析：加入x<y,f[x]>=f[y],則x相對于y更有潛力。 
首先根據f[]值分類，記錄滿足f[t]=k的最小的值a[t],記d[k]=min{a[t]},f[t]=k. 
    1.發現d[k]在計算過程中單調不上升 
    2.d[1]<d[2]<...<d[k] (反證) 1 2 3 8 4 7 
解法： 
1. 設當前最長遞增子序列為len,考慮元素a[i]; 
2. 若d[len]<a[i],則len++，并將d[len]=a[i]; 
   否則,在d[0-len]中二分查找,找到第一個比它小的元素d[k],并d[k+1]=a[i].() 
*/  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;  
const int N = 41000;  
int a[N];       //a[i] 原始數據  
int d[N];       //d[i] 長度為i的遞增子序列的最小值  
  
int BinSearch(int key, int* d, int low, int high)  
{  
    while(low<=high)  
    {  
        int mid = (low+high)>>1;  
        if(key>d[mid] && key<=d[mid+1])  
            return mid;  
        else if(key>d[mid])  
            low = mid+1;  
        else  
            high = mid-1;  
    }  
    return 0;  
}  
  
int LIS(int* a, int n, int* d)  
{  
    int i,j;  
    d[1] = a[1];  
    int len = 1;        //遞增子序列長度  
    for(i = 2; i <= n; i++)  
    {  
        if(d[len]<a[i])  
            j = ++len;  
        else  
            j = BinSearch(a[i],d,1,len) + 1;  
        d[j] = a[i];  
    }  
    return len;  
}  
  
int main()  
{  
    int t;  
    int p;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d",&p);  
        for(int i = 1; i <= p; i++)  
            scanf("%d",&a[i]);  
        printf("%d\n",LIS(a,p,d));  
    }  
    return 0;  
}  

posted @ 2012-11-28 23:36 鑫龍閱讀(200) | 評論 (0) | 編輯收藏

對于很多初學《UNIX環境高級編程》（AdvancedProgramming in the UNIX Environment,簡稱APUE，以下使用簡稱）的朋友，第一個遇到的問題可能就是該書中的源代碼編譯的問題。此書中差不多每個例程中，都會有這樣一行源碼：
＃include "ourhdr.h"

在第二版中改為：
＃include "apue.h"

這個頭文件是作者把把每個例程中常用的標準頭文件，一些常用的出錯處理函數（err_**（）之類的函數）和一些常用的宏定義給整理在一個頭文件中。這個可以省去在每個例程中錄入較多的重復代碼，這樣可以減少每個例程的長度。但是，這樣就給讀者帶來了不少麻煩。因為我們還要去搞明白如和把這個頭文件編譯，然后做成庫文件，添加到我們的系統中。特別讀于初學者，本來滿懷信心的，結果在編譯第一個程序的時候就出現了問題。我也沒有搞明白如何把"ourhdr.h"靜態的編譯到系統中。

不過，不明白如何使用"ourhdr.h"這個頭文件，并不會影響我們學習APUE，也不會影響我們編譯和運行每一個例程。其實，簡單的想一下，如果一個C程序要能順利的編譯和運行，除了我們要語法正確等方面外，最根本的是要保證我們程序中所調用的函數以及宏等等都要有完整的來源，也就是必須包含所有調用函數和宏所在的頭文件。對于一個具體的源程序，如果我們正確的包含了頭文件，那么剩下的就是程序本生語法方面應該注意的事項。

如何確定系統調用函數包含在那個頭文件中呢？這在Unix/Linux系統下并非一件難事。Unix/Linux下命令man可以幫助我們找到。man命令不僅可以幫助我們查找一般命令的用法，同時提供不同層次的幫助諸如系統調用或者管理員級別的命令等等（譬如FreeBSD6.1中，man1是用戶專用手冊，man 2是系統調用，man 3是庫函數查詢等等）。

下面我們就以APUE書中程序1-1（實現ls命令部分功能）為例，來說明如何將書中的程序改編成全部使用標準頭文件的程序。其中，操作系統用的是FreeBSD6.1，經過相應的修改可以在書中所說的幾個Unix系統及Linux系統中運行，我也曾在Debian Linux下成功編譯和運行該程序。書中1-1.c的原始代碼如下：

#include <sys/types.h>
#include <dirent.h>
#include "ourhdr.h"

int
main(int argc, char *argv[])
{
DIR               *dp;
  struct dirent   *dirp;

  if (argc != 2)
      err_quit("usage: ls directory_name");

  if ((dp = opendir(argv[1])) == NULL)
      err_sys("can't open %s", argv[1]);
  while ((dirp = readdir(dp)) != NULL)
      printf("%s\n", dirp->d_name);

closedir(dp);
  exit(0);
}

從書后面的附錄中可以看到"ourhdr.h"的內容比較多，包含了比較多的常用頭文件，一些宏定義和一些常用函數和出錯函數的定義。其實，對于每一個具體的程序，我們只需要找到該程序中用到的頭文件即可。

該1-1.c中所用到的系統函數調用有：opnedir()，readdir()，printf()，closedir()和exit()。
其中，對于常用的函數prinft()和exit()，它們所在的頭文件一般都知道，分別是<stdio.h>和<stdlib.h>。而對于opnedir()，readdir()和closedir()，我們可以通過man opendir，man readdir，manclosedir得到這三個關于目錄操作的函數所在的頭文件都是：<sys/types.h>和<dirent.h>。這兩個頭文件在源程序中也已經列出。

其次，1-1.c中還用到了作者自定義的兩個函數：err_quit()和err_sys()。這兩個函數主要使用來進行出錯處理的。當然，使用這兩個函數對錯誤信息的處理是比較完善的。但是，作為我們學習來講，了解程序的核心功能是首要的，我們可以將出錯處理簡化一點，即當遇到錯誤的時候，我們只簡單的使用printf()函數來提示一下有錯誤發生。當然，用printf()來進行出錯處理并不是一種很合理的方法，而且往往我們看不到更關鍵的錯誤信息，但對于我們僅僅作為學習來用還是可以接受的。畢竟我們要理解的核心部分是程序的功能實現，出錯處理在于其次。

通過以上的說明，我們可以將1-1.c修改為如下內容：

#include <sys/types.h>
#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[])
{
DIR *dp;
  struct dirent *dirp;

  if(argc != 2)
  {
      printf("You need input the directory name.\n");
      exit(1);
  }

  if((dp = opendir(argv[1])) == NULL)
  {
      printf("cannot open %s\n", argv[1]);
      exit(1);
  }

  while ((dirp = readdir(dp)) != NULL)
      printf("%s\n", dirp->d_name);

closedir(dp);

  exit(0);
}

  這樣修改后的程序已經與作者的頭文件"ourhdr.h"沒有關系，可以單獨的進行編譯。我使用的是root用戶，執行命令：

# gcc 1-1.c  //生成目標文件a.out
或者
＃ gcc -o 1-1 1-1.c  //生成目標文件1-1

沒有任何錯誤和警告，說明編譯成功。這時我們執行生成的目標文件：

＃ ./a.out /home
或者
＃ ./1-1 /home

則會列出/home路徑下的所有文件，包括目錄(.)和(..)。

通過這樣的方法，基本上我們可以將該書中所有的例程修改成不包含"ourhdr.h"的程序。這樣，我們就可以單獨的編譯每一個例程，而不用顧及作者所給的雜湊的頭文件。同時這種比較笨的方法，反而有利于幫助我們了解不同系統調用所對應的頭文件，對于學習來說，這應該是一件好事。

歡迎交流，歡迎自由轉載，但請注明CU鏈接或本人CU Blog鏈接：
http://blog.chinaunix.net/u/33048/showart_343553.html

posted @ 2012-11-26 13:00 鑫龍閱讀(184) | 評論 (0) | 編輯收藏

轉貼 ACM的算法（覺得很好，有層次感）
OJ上的一些水題(可用來練手和增加自信)
(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初期:

一.基本算法:
     (1)枚舉. (poj1753,poj2965)
     (2)貪心(poj1328,poj2109,poj2586)
     (3)遞歸和分治法.
     (4)遞推.
     (5)構造法.(poj3295)
     (6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖算法:
     (1)圖的深度優先遍歷和廣度優先遍歷.
     (2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
        (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
     (3)最小生成樹算法(prim,kruskal)
        (poj1789,poj2485,poj1258,poj3026)
     (4)拓撲排序 (poj1094)
     (5)二分圖的最大匹配 (匈牙利算法) (poj3041,poj3020)
     (6)最大流的增廣路算法(KM算法). (poj1459,poj3436)
三.數據結構.
     (1)串 (poj1035,poj3080,poj1936)
     (2)排序(快排、歸并排(與逆序數有關)、堆排) (poj2388,poj2299)
     (3)簡單并查集的應用.
     (4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
        (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
     (5)哈夫曼樹(poj3253)
     (6)堆
     (7)trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
     (1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
     (2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
     (3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
     (1)背包問題. (poj1837,poj1276)
     (2)型如下表的簡單DP(可參考lrj的書 page149):
       1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
       2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)

         (poj3176,poj1080,poj1159)
       3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
     (1)組合數學:
        1.加法原理和乘法原理.
        2.排列組合.
        3.遞推關系.
          (POJ3252,poj1850,poj1019,poj1942)
     (2)數論.
        1.素數與整除問題
        2.進制位.
        3.同余模運算.
          (poj2635, poj3292,poj1845,poj2115)
     (3)計算方法.
        1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
     (1)幾何公式.
     (2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

     (3)多邊型的簡單算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
         (poj1408,poj1584)
     (4)凸包. (poj2187,poj1113)

中級:

一.基本算法:
     (1)C++的標準模版庫的應用. (poj3096,poj3007)
     (2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖算法:
     (1)差分約束系統的建立和求解. (poj1201,poj2983)
     (2)最小費用最大流(poj2516,poj2195)
     (3)雙連通分量(poj2942)
     (4)強連通分支及其縮點.(poj2186)
     (5)圖的割邊和割點(poj3352)
     (6)最小割模型、網絡流規約(poj3308, )
三.數據結構.
     (1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
     (2)靜態二叉檢索樹. (poj2482,poj2352)
     (3)樹狀樹組(poj1195,poj3321)
     (4)RMQ. (poj3264,poj3368)
     (5)并查集的高級應用. (poj1703,2492)
     (6)KMP算法. (poj1961,poj2406)
四.搜索
     (1)最優化剪枝和可行性剪枝
     (2)搜索的技巧和優化 (poj3411,poj1724)
     (3)記憶化搜索(poj3373,poj1691)

五.動態規劃
     (1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
         (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
     (2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
     (3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
     (1)組合數學:
        1.容斥原理.
        2.抽屜原理.
        3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
        4.遞推關系和母函數.

     (2)數學.
        1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
        2.概率問題. (poj3071,poj3440)
        3.GCD、擴展的歐幾里德(中國剩余定理) (poj3101)
     (3)計算方法.
        1.0/1分數規劃. (poj2976)
        2.三分法求解單峰(單谷)的極值.
        3.矩陣法(poj3150,poj3422,poj3070)
        4.迭代逼近(poj3301)
     (4)隨機化算法(poj3318,poj2454)
     (5)雜題.
         (poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
        (1)坐標離散化.
        (2)掃描線算法(例如求矩形的面積和周長并,常和線段樹或堆一起使用).
            (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
        (3)多邊形的內核(半平面交)(poj3130,poj3335)
        (4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429
)

高級:
一.基本算法要求:
      (1)代碼快速寫成,精簡但不失風格
          (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
      (2)保證正確性和高效性. poj3434
二.圖算法:
      (1)度限制最小生成樹和第K最短路. (poj1639)
      (2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)

         (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
      (3)最優比率生成樹. (poj2728)
      (4)最小樹形圖(poj3164)
      (5)次小生成樹.
      (6)無向圖、有向圖的最小環
三.數據結構.
      (1)trie圖的建立和應用. (poj2778)
      (2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線算法(并查集+dfs) 和在線算法

          (RMQ+dfs)).(poj1330)
      (3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移
的
          目的). (poj2823)
      (4)左偏樹(可合并堆).
      (5)后綴樹(非常有用的數據結構,也是賽區考題的熱點).
         (poj3415,poj3294)
四.搜索
      (1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

      (2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲
狀態、雙向廣搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
      (3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大
、可以考慮雙向搜索或者是輪換搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.動態規劃
      (1)需要用數據結構優化的動態規劃.
         (poj2754,poj3378,poj3017)
      (2)四邊形不等式理論.
      (3)較難的狀態DP(poj3133)
六.數學
      (1)組合數學.
        1.MoBius反演(poj2888,poj2154)
        2.偏序關系理論.
      (2)博奕論.
        1.極大極小過程(poj3317,poj1085)
        2.Nim問題.
七.計算幾何學.
      (1)半平面求交(poj3384,poj2540)
      (2)可視圖的建立(poj2966)
      (3)點集最小圓覆蓋.
      (4)對踵點(poj2079)
      八.綜合題.
      (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263
)

posted @ 2012-11-25 17:33 鑫龍閱讀(239) | 評論 (0) | 編輯收藏

C風格的強制類型轉換(Type Cast)很簡單，不管什么類型的轉換統統是：
TYPE b = (TYPE)a。
C++風格的類型轉換提供了4種類型轉換操作符來應對不同場合的應用。

const_cast，字面上理解就是去const屬性。
static_cast，命名上理解是靜態類型轉換。如int轉換成char。
dynamic_cast，命名上理解是動態類型轉換。如子類和父類之間的多態類型轉換。
reinterpret_cast，僅僅重新解釋類型，但沒有進行二進制的轉換。
4種類型轉換的格式，如：TYPE B = static_cast(TYPE)(a)。

const_cast
去掉類型的const或volatile屬性。

1 struct SA {
2  int i;
3 };
4 const SA ra;
5 //ra.i = 10; //直接修改const類型，編譯錯誤
6 SA &rb = const_cast<SA&>(ra);
7 rb.i = 10;

static_cast

類似于C風格的強制轉換。無條件轉換，靜態類型轉換。用于：
1. 基類和子類之間轉換：其中子類指針轉換成父類指針是安全的；但父類指針轉換成子類指針是不安全的。(基類和子類之間的動態類型轉換建議用dynamic_cast)
2. 基本數據類型轉換。enum, struct, int, char, float等。static_cast不能進行無關類型（如非基類和子類）指針之間的轉換。
3. 把空指針轉換成目標類型的空指針。
4. 把任何類型的表達式轉換成void類型。
5. static_cast不能去掉類型的const、volitale屬性(用const_cast)。

1 int n = 6;
2 double d = static_cast<double>(n); // 基本類型轉換
3 int *pn = &n;
4 double *d = static_cast<double *>(&n) //無關類型指針轉換，編譯錯誤
5 void *p = static_cast<void *>(pn); //任意類型轉換成void類型

dynamic_cast
有條件轉換，動態類型轉換，運行時類型安全檢查(轉換失敗返回NULL)：
1. 安全的基類和子類之間轉換。
2. 必須要有虛函數。
3. 相同基類不同子類之間的交叉轉換。但結果是NULL。

 1 class BaseClass {
 2 public:
 3 int m_iNum;
 4 virtual void foo(){}; //基類必須有虛函數。保持多臺特性才能使用dynamic_cast
 5 };
 6 
 7 class DerivedClass: public BaseClass {
 8 public:
 9 char *m_szName[100];
10 void bar(){};
11 };
12 
13 BaseClass* pb = new DerivedClass();
14 DerivedClass *pd1 = static_cast<DerivedClass *>(pb); //子類->父類，靜態類型轉換，正確但不推薦
15 DerivedClass *pd2 = dynamic_cast<DerivedClass *>(pb); //子類->父類，動態類型轉換，正確
16 
17 BaseClass* pb2 = new BaseClass();
18 DerivedClass *pd21 = static_cast<DerivedClass *>(pb2); //父類->子類，靜態類型轉換，危險！訪問子類m_szName成員越界
19 DerivedClass *pd22 = dynamic_cast<DerivedClass *>(pb2); //父類->子類，動態類型轉換，安全的。結果是NULL

reinterpret_cast
僅僅重新解釋類型，但沒有進行二進制的轉換：
1. 轉換的類型必須是一個指針、引用、算術類型、函數指針或者成員指針。
2. 在比特位級別上進行轉換。它可以把一個指針轉換成一個整數，也可以把一個整數轉換成一個指針（先把一個指針轉換成一個整數，在把該整數轉換成原類型的指針，還可以得到原先的指針值）。但不能將非32bit的實例轉成指針。
3. 最普通的用途就是在函數指針類型之間進行轉換。
4. 很難保證移植性。

1 int doSomething(){return 0;};
2 typedef void(*FuncPtr)(); //FuncPtr is 一個指向函數的指針，該函數沒有參數，返回值類型為 void
3 FuncPtr funcPtrArray[10]; //10個FuncPtrs指針的數組 讓我們假設你希望（因為某些莫名其妙的原因）把一個指向下面函數的指針存入funcPtrArray數組：
4 
5 funcPtrArray[0] = &doSomething;// 編譯錯誤！類型不匹配，reinterpret_cast可以讓編譯器以你的方法去看待它們：funcPtrArray
6 funcPtrArray[0] = reinterpret_cast<FuncPtr>(&doSomething); //不同函數指針類型之間進行轉換

總結
去const屬性用const_cast。
基本類型轉換用static_cast。
多態類之間的類型轉換用daynamic_cast。
不同類型的指針類型轉換用reinterpret_cast。

posted @ 2012-11-25 16:55 鑫龍閱讀(302) | 評論 (0) | 編輯收藏

摘要: memcpy與memmove的目的都是將N個字節的源內存地址的內容拷貝到目標內存地址中。但當源內存和目標內存存在重疊時，memcpy會出現錯誤，而memmove能正確地實施拷貝，但這也增加了一點點開銷。memmove的處理措施：（1）當源內存的首地址等于目標內存的首地址時，不進行任何拷貝（2）當源內存的首地址大于目標內存的首地址時，實行正向拷貝（3）當源內存的首地址小于目標內存的首地址時，實行反向... 閱讀全文

posted @ 2012-11-21 19:04 鑫龍閱讀(291) | 評論 (0) | 編輯收藏

摘要: 第四章、現場編寫類似strstr/strcpy/strpbrk的函數作者：July。說明：如果在博客中代碼使用了\n，csdn blog系統將會自動回給我變成/n。據后續驗證，可能是原來舊bl... 閱讀全文

posted @ 2012-11-21 17:21 鑫龍閱讀(254) | 評論 (0) | 編輯收藏

摘要: 程序員編程藝術：第三章續、Top K算法問題的實現作者：July，zhouzhenren，yansha。致謝：微軟100題實現組，狂想曲創作組。 &nb... 閱讀全文

posted @ 2012-11-20 21:56 鑫龍閱讀(3348) | 評論 (0) | 編輯收藏

摘要: 程序員編程藝術：第三章、尋找最小的k個數作者：July。時間：二零一一年四月二十八日。致謝：litaoye， strugglever，yansha，luuillu，Sorehead，及狂想曲創作組。微博：http://weibo.com/j... 閱讀全文

posted @ 2012-11-19 21:09 鑫龍閱讀(1208) | 評論 (1) | 編輯收藏

摘要: 最小堆：Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->template<class T>class MinHeap {public: MinHeap(int&nb... 閱讀全文

mysileng

導航

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

程序員編程藝術-----第五章-----尋找滿足和為定值的兩個或多個數

最長上升子序列 O(nlogn)解法 (轉)

《UNIX環境高級編程》單個源碼編譯方法(轉)

POJ題目分類(轉)

C++類型轉換總結(轉)

memcpy與memmove(轉)

程序員編程藝術-----第四章-----現場編寫類似strstr/strcpy/strpbrk的函數

程序員編程藝術-----第三章續-----Top K算法問題的實現

程序員編程藝術-----第三章-----尋找最小的k個數

最小堆&&最大堆的實現(c++)(轉)