全國高中資訊競賽95年第5題暨第6題

題目原文如下:

http://www.cs.nthu.edu.tw/info_race95/95-program%2...

評審測試資料如下:

http://www.cs.nthu.edu.tw/info_race95/95case.rar

個人問題敘述─

個人解第五題時,用Branch And Bound、還有自行想出來的演算法皆無法解出所有測試資料(演算速度只能解出第一組)。

相關程式碼(個人即Joseph Schumahcer)、討論及詳細情況如下網頁:http://www.programmer-club.com/pc2020v5/Forum/Show...

而第六題情況是個人沒有想出優於O(n!)的解法。不過後來認為大概可以歸類成兩大方向,一是負大數*負大數,二是大數*大數,兩方向求出來後再比較何者較大,但感到有些許複雜,未有具體方法實現。

相關討論情形及詳細敘述也如下網址:

http://www.programmer-club.com/pc2020v5/Forum/Show...

礙於字數,無法將程式碼直接貼到上面來。

而有可改進之處,懇請指教m(_ _)m

Update:

抱歉,鄙人不才。Dave大 後面的例子個人看不太懂,所以一知半解,不知道能不能用更具體的例子說明。

1 Answer

Rating
  • Dave
    Lv 7
    1 decade ago
    Favorite Answer

    第6題應該可以用Dynamic Programming 作:

    建立一個大小為 [運算子數目] x [運算元數目] 的 2D 陣列… (叫作 ans 好了)

    ans[x][y] 代表在 expression 裡面,第 (y+1) 個運算元開始,長度為 (x+1) 的 subexpression 的最大值;所以要是 expression 是 4+2*3, ans[0][1] 存的是 "2" 這個 subexpression 的最大值 (就是 2 啦),而 ans[1][0] 是 "4+2" 這個 expression 的最大值 (就是 6)…

    2007-11-06 21:47:47 補充:

    再從 base case 一列一列 fill 到最大的 case,最後的答案就會在最後一列的第一個元素裡…

    2007-11-06 21:53:25 補充:

    例:要算 ans[5][0] 好了 ( expression 開頭前 5 個運算子的 subexpresion 的最大值)… 因為有 4 個運算元,而每一個運算元會把 subexpression 再切成更小的 subexpression,所以就一個一個運算元檢查,看看用那一個運算元的話,所得到的答案為最大:先檢查 ans[0][0] ans[4][1] 跟用第一個運算元,再檢查 ans[1][0] ans[3][2] 跟用第二個運算元,再檢查 ans[2][0] ans[2][3] 跟第3個運算元,最後檢查 ans[3][0]跟ans[1][4]… 得到最大值再放進 ans[5][0]…

    2007-11-06 21:54:46 補充:

    陣列大小約為 n^2,而每次 fill 一個陣列元素,也約需要 O(n) 次運算,所以這個算法是大約O(n^3),polynomial time

    2007-11-08 08:51:21 補充:

    int _tmain(int argc, _TCHAR* argv[])

    {

    int num[50] = {0}; // 放 operands

    char op[50] = {0}; // 放 operators

    int numCnt = 0; // 記錄有多少個 operands (operator 永遠比 operands 少 1)

    char input[512];

    scanf("%s", input );

    char* ptr = input;

    while( *ptr )

    {

    if( *ptr < '0' || *ptr > '9' ) op[numCnt++]=*ptr;

    else num[numCnt] = num[numCnt] * 10 + *ptr - '0';

    *ptr++;

    }

    numCnt++;

    int maxs[50][50] = {0};

    int mins[50][50] = {0};

    for(int i=0; i<numCnt; i++)

    maxs[0][i] = mins[0][i] = num[i];

    for(int i=1; i<numCnt; i++)

    {

    for(int j=0; j<numCnt-i; j++)

    {

    int max, min;

    bool firstElement = true;

    for(int k=j; k<i+j; k++)

    {

    int tmp = 0, num1, num2;

    for( int l=0; l<4; l++)

    {

    int l2=i-(k-j)-1;

    switch( l )

    {

    case 0: num1 = maxs[k-j][j]; num2 = maxs[l2][k+1]; break;

    case 1: num1 = maxs[k-j][j]; num2 = mins[l2][k+1]; break;

    case 2: num1 = mins[k-j][j]; num2 = maxs[l2][k+1]; break;

    case 3: num1 = mins[k-j][j]; num2 = mins[l2][k+1]; break;

    }

    switch(op[k])

    {

    case '+': tmp = num1 + num2; break;

    case '-': tmp = num1 - num2; break;

    case '*': tmp = num1 * num2; break;

    }

    if( firstElement)

    {

    max = tmp;

    min = tmp;

    firstElement = false;

    }

    else

    {

    if( tmp > max ) max = tmp;

    if( tmp < min ) min = tmp;

    }

    }

    }

    printf("Ans is %d\n", maxs[numCnt-1][0]);

    system("pause");

    return 0;

    }

    2007-11-08 08:53:31 補充:

    加註解就太大放不下了… 重點在 maxs 跟 mins (要記錄 subexpression 最大跟最小值,因乘法有可能會讓最小值變最大值)… 要是看得懂最裡面一層 switch 裡如何用 maxs 跟 mins 找 subexpression 的最大/小值來作運算的話,其他的就應該很簡單…

    2007-11-08 09:01:08 補充:

    maxs[x][y] / mins[x][y] 的定義跟意見欄的一樣,就是位於 y+1,長度為 x+1 長的 subexpression 的最大跟最小值:

    以為例:5+2-7*2-3

    max[0][2] 就是位於 (2+1)=3,長度為 (0+1)=1 的 subexpression的最大值… 就是 "7";因為 "7" 位在第3個,長度為 1就是數字本身,所以 max[0][2] 就是 7 (同理,min[0][2] 也是 7)

    max[2][1] 是 "7*2" 的最大值,所以就是 14, min[1][3] 是 "2-7*2-3" 的最小值…

    2007-11-08 09:06:59 補充:

    上面的解法叫作 Dynamic Programming… 可以用來解一些本來需要 exponential time 的問題… 重點就是重複利用小問題的答案,來減少運算的次數到 polynomial time (以本題為例,就是紀錄 subexpression 的最大最小值,這樣一來就不用重算)… 基本上就是用空間來換取時間 (DP 的特色就是都會有滿大的陣列來存答案)…

    2007-11-08 09:10:37 補充:

    當然,也不是每種問題都可以用 DP… DP 是要你的問題可以簡化成小問題,且大問題的答案可以直接用到小問題的答案得出 (所謂的 optimal substructure),才有辦法用 DP…

    2007-11-08 09:11:22 補充:

    "大問題化簡為小問題",就是 recursive 的概念… DP就是 recursive,不同處在 DP 會記錄小問題的答案,單純的 recursive 不會… 所以要是你用 recurse 寫法,你有方法可以儲存 recurse 的答案,讓你可以遇到同樣的小問題時,就不在 recurse,直接取用小問題的答案的話,你基本上就是用了 DP 的解法 (只是方向不一樣,上面的程式是從下到上解,你用 recurse 的話會是從上到下解)…

    2007-11-08 09:22:40 補充:

    我猜你原本的寫法大概是 recursive 吧… 就是 loop expression 裡的每個 operator,每個 operator 會把本來的 expression 拆為前半部跟後半部,所以再 recurse 前半部跟後半部,找最大值 / 最小值…

    但因為 expression 是 overlapping 的關係,斤以當你 loop 第 2 個 operator 時,你 recurse 前半部份的 subexpression 就會要重新檢查你本來在檢查第 1 個 operator 時就檢查過的 subexpression (就是作了不用作的運算,本來就已經算過了的東西)…

    2007-11-08 09:22:46 補充:

    所以要是你有方法發現說你已經檢查過相同的 subexpression,就不在 recurse,直接取用答案,你就是用了 DP 的寫法…

    2007-11-08 09:33:00 補充:

    這題是因為跟之前解的一題滿像的,都是 expression 求解的東東,所以一看就覺得是用 DP 作:

    http://tw.knowledge.yahoo.com/question/question?qi...

    2007-11-08 10:30:41 補充:

    第5題想了想也可以用 DP 作:總共最多有 M 個 pick up 點,在每個 pick up 點 A, B, C 可能在的位置有 3 * M * M 總組合 (3 因為在第 X 個點,A, B 或 C 其中一個一定要在 X 上,其他2輛車有 M * M 總組合,另一台一定在 X,又,有 3 台車的組合,所以是 3 * M * M)… 所以可以建立一個 minCost[3][M][M] 大小的陣列 (記錄前一個點的 min cost);再一樣一行一行 fill…

    running time 大約為 O(m^3)

    2007-11-08 14:51:12 補充:

    對 DP 有興趣,可以看看這篇,寫得很好

    http://www.ice.ntnu.edu.tw/~u91029/dynamic_program...

Still have questions? Get your answers by asking now.