三、(15%) You are required to compute the binomial coefficient Ck^n = n!/(k!(n-k)!). When n or k is not small, we cannot compute Ck^n directly from the definition because n! or k! is very large. Please design an algorithm to compute C_k^n in time O(nk) without computing n! or k! directly.

5. (16%) 使用 stack 實作老鼠走過言問題 (Maze path search)，運用 C 語言程式：void path(){ // assume int maze30 and offsets move[8] has been set in main function// typedef struct {int v; int h;} offsets;int i, row, col, nextrow, nextcol, dir, found = 0, top =0, mark30;typedef struct { int row; int col; int dir;} elementelement position, stack[100];mark1 = 1; stack[0].row = 1; stack[0].col = 1; stack[0].dir = 0;//實作以下敘述// Use stack to get current row, col, dir// Use dir to calculate nextrow, nextcol// Use nextrow, nextcol to check this move (1) arrive exit, or// (2) become a legal move; add this move into the stack, or// (3) check other dir}

相關申論題

相關試卷