Feeds:
文章
留言

Archive for 三月 26th, 2007

MSN SpaceGoogle DocGoogle Blog
Chui-Wen Chiu(Arick)
2007.03.26

摘至 [1] 的問題 1-3,問題描述如下:
以兩個整數陣列 f[] 與 g[],他們的元素經自小到大排列好,而且兩個陣列元素各自不相同;譬如說,f[] 中可能有 1,3, 4, 7, 9,而 f[] 有 3, 5, 7, 8, 10。請寫程式,算出這兩個陣列彼此之間有多少組相同資料。就以上例而言,f[2], g[1] 為3是第一組;f[4], g[3] 為8是第二組。

說明:
我並不期望你用下面的方式來寫作程式
a. 固定 f[i]
b. 對於 f[i] 而言,檢查 g[]中有沒有與 f[i] 相同的元素
c. 處理下一個 f[i],即 f[i+1]

因為 f[] 與 g[] 都以經由小到大排序好,你應該活用這一個很強的特性;好程式員絕對不會用上面的本拙方式寫程式的,因為做了太多無意義的事。
為什麼呢?因為 g[] 的元素都相異,對於 f[i] 而言,最多只會只找一個與他相同的元素,但在會壞的情況下,你得把 g[] 全部查完才曉得這一回事,如果 g[] 有 n  個元素,你得查 n 次,但是若在 f[] 中也有 n 個元素,所以你得把 g[] 查 n 遍,一共做了 n2 個比較才能找出結果。

請試試看能夠找出方法,把 f[] 與 g[] 各查一次就可以找到答案。請記住,活用 f[] 與 g[] 已經自小到大排序好的特性。

我的解法-版本#1


#include <iostream>

template<int len1, int len2, typename T>
int eq_count(T f[], T g[]){
    int count = 0;
    int i = 0;
    int j = 0;
    while(i < len1 && j < len2){
        if (f[i] == g[j]){
            ++count;
            i<len1-1?++i:++j;

            continue;
        }

        if (f[i] < g[j]){
            i<len1-1?++i:++j;       
            continue;
        }

        if (f[i] > g[j]){
            j < len2-1?++j:++i;           
        }
    }

    return count;
}

int main(){
    int f[] = {1, 3, 4, 7, 8, 9, 11, 99, 101};
    int g[] = {1, 3, 5, 7, 8, 10};

    std::cout << eq_count<9, 6>(f, g) << std::endl;
    return 0;
}

參考資料
[1] C 名題精選百則 技巧篇

Read Full Post »

MSN SpaceGoogle DocGoogle Blog
Chui-Wen Chiu(Arick)
2007.03.26

摘至 [1] 的問題 1-2,問題描述如下:
已知f[]與g[]兩個整數陣列,元素都已經至小到大排序好,請寫一個程式算出 f[] 中比 g[] 中元素大的對數。換句話說,f[0] 比 g[]中多少個元素來的大,f[1] 比 g[]中多少個元素來的大等等,這些值得總和就是我們要求答案。

舉個例子,如果 f[] 中有 1,3,5,7,9 而 g[] 中有 2,3,4,7,8。因此比 g[0] 大的有 f[1] 到[4],比g[1]大的有f[2]到f[4],比g[2]大的有f[2]到f[4],比g[3]大的有f[4],比g[4]大的有f[4],所以答案為 4+3+3+1+1 = 13。

我的解法-版本#1

#include <iostream>

template<int len1, int len2, typename T1, typename T2>
int gt_count(T1 f[], T2 g[]){
    int count = 0;
    int pos = 0;
    for(int i = 0; i<len2; ++i){
        for(int j = pos; j<len1; ++j){
            if (g[i] < f[j]){
                count += len1-j;
                pos = j;
                break;
            }
        }
    }

    return count;
}

int main(){
    int f[] = {1, 3, 5, 7, 9};
    int g[] = {2, 3, 4, 7, 8};
   
    std::cout << gt_count<5, 5>(f, g) << std::endl;
    return 0;
}

參考資料
[1] C 名題精選百則 技巧篇

Read Full Post »

MSN SpaceGoogle DocGoogle Blog
Chui-Wen Chiu(Arick)
2007.03.26

摘至 [1] 的問題 1-4,問題描述如下:
已知兩個元素自小到大排好的陣列 x[] 與 y[],請寫一個程式算出兩個陣列元素彼此之間差的絕對值中最小的一個,這叫做陣列的距離。

說明:
如果 x[i] 與 y[j] 是兩個元素,那麼 | x[i]-y[i] | 就是兩個元素之間的距離,所有這些距離的極小值叫做陣列距離,好比說 x[] 有 1,3,5,7,9,y[]有2,6,8,那麼最短距離就是1,因為 x[0] 與 y[0], x[1] 與 y[0], x[2] 與 y[1], x[3] 與 y[1] 還有 x[4] 與 y[2] 的距離都是 1。

請注意,如果 x[] 與 y[] 各有 m 與 n 個元素,那麼元素之間的距離就一共有 m*n 個;事實上我們往往用不著計算那麼多值,你應該活用 x[] 與 y[] 已經排序好的特性,不要把所有的距離都算出來。

我的解法-版本#1

#include <iostream>
#include <cmath>

template<int f_len, int g_len, typename T>
int mindist(T f[], T g[]){
    int diff = abs( f[0]-g[0] );
    if (diff == 0 || ( f_len == g_len == 1)){
        return 0;
    }

    int i = 0;
    int j = 0;
    while(true){
        if (f[i]<=g[j]){
            i<f_len-1?++i:++j;
        }else{
            j<g_len-1?++j:++i;
        }


        if (i >= f_len || j >= g_len){
            break;
        }

        if (diff > abs(f[i]-g[j])) {
            diff = abs(f[i]-g[j]);
            if (diff == 0 ){
                return 0;
            }
        }
    }

    return diff;
}

int main(){
    //int f[] = {1, 3, 5, 7, 9};
    //int g[] = {2, 6, 8};

    int f[] = {1, 2, 3, 4, 5};
    int g[] = {6, 7, 8};
    std::cout << mindist<5, 3>(f, g) <<std::endl;
    return 0;
}

參考資料
[1] C 名題精選百則技巧篇

Read Full Post »

演算法問題1-1:最長平台

MSN SpaceGoogle DocGoogle Blog
Chui-Wen Chiu(Arick)
2007.03.26

摘至 [1] 的問題 1-1,問題描述如下:
已知已經自小到大排序好的陣列,我們說這個陣列中的平台(plateau),就是連續的一串值相同的元素,並且這一串元素不能再延伸。好比說,在 1,2,2,3,3,3,4,5,5,6 中 1, 2-2, 3-3-3, 4, 5-5, 6 都是平台。請寫一個程式,接收一個陣列,把這個陣列中最常的平台找出來;再上面的例子就是3,這是由 3-3-3 造成的。

說明:
這個程式十分簡單,但是要寫的好卻很難,因此在寫程式時你心中應該要想到下面的幾點:
a. 使用的變數越少越好
b. 能否只把陣列的元素每一個都只查久得到結果?
c. 程式敘述也要越少越好

我的解法-版本#1

#include <iostream>
// 變數: 4個
// 陣列存取次數: 1次
template<int len, typename T>
int plateau(T f[]){
    if (len <= 0){
        return 0;
    }

    if (len == 1){
        return 1;
    }

    int count = 1;
    int max = 1;
    int v = f[0];
    for(int i = 1; i<len; ++i){
        if (v == f[i]){
            ++count;
            continue;
        }

        if (count >max ){
            max = count;
        }
        v = f[i];
        count = 1;
    }

    return max;
}

int main(){
    int f[] = {1,2,2,3,3,3,4,5,5,6};
    std::cout << plateau<10>(f) <<std::endl;
    return 0;
}

參考資料
[1] C 名題精選百則技巧篇

Read Full Post »

演算法問題1-5:等值首尾和

MSN SpaceGoogle DocGoogle Blog
Chui-Wen Chiu(Arick)
2007.03.26

摘至 [1] 的問題 1-5,問題描述如下:
假設有一個陣列 x[],他有 n 個元素,每一個元素都大於零; 我們說 x[0]+x[1]+…+x[i] 是個前段和,而 x[j] + x[j+1]+…x[n-1]則是後段和。請寫一個程式,求出 x[] 中有多少組相同的前段和與後段和。

說明:
如果x[]的元素是 3, 6, 2, 1, 4, 5, 2,於是x[]的前段和有以下七個,亦即3, 9, 11, 12, 16, 21, 33;後段和則是 2, 7, 11, 12, 14, 20, 23 於是 11, 12, 23 這三對就是值相同的前段和與後段和,因為

11 = 3+6+2 = 2+5+4
12 = 3+6+2+1 = 2+5+4+1

至於 23 則是整個陣列元素的和,自然前段與後段的和一定相同。
當然,你的成視野可以用上面的方式把前段和與後段和算出來,再進行比較,不過我們卻希望您不要用這個方法,因為他要額外的記憶體。

我的解法-版本#1

#include <iostream>

template<typename T>
int headtail(T f[]){
    if (len <= 0){
        return 0;
    }

    int count = 1; // 整個陣列的和一定相同
    int i = 0;
    int j = len-1;
    int lv = f[i];
    int rv = f[j];
    while(i 0){  // 邊界值,兩側最後一個值不用測試,因為累加到最後一定相等
        if (lv <= rv){
            if (lv == rv){
                ++count;
            }

            if (i < span>
                lv += f[++i];
            }else{
                rv += f[–j];
            }
            continue;
        }


        if (lv > rv){
            if (j >1){
                rv += f[–j];               
            }else{
                lv += f[++i];
            }
        }
    }

    return count;
}

int main(){
    int f[] = {3, 6, 2, 1, 4, 5, 2};   
    std::cout << headtail<7>(f) << std::endl;
  
    return 0;
}

參考資料
[1] C 名題精選百則技巧篇

Read Full Post »