【文章內容簡介】 rSource=%s\n, GetSubString(strSource, strResult), strResult, strSource)。 } 1四個工人，四個任務，每個人做不同 的 任務需要的時間不同，求任務分配 的最優(yōu)方案 。（ 2020年 5月 29日全國計算機軟件資格水平考試 —— 軟件設計師的算法題） 。 include define N 4 int Cost[N][N] = { {2, 12, 5, 32}, // 行號：任務序號，列號：工人序號 {8, 15, 7, 11}, // 每行元素值表示這個任務由不同工人完成所需要的時間 {24, 18, 9, 6}, {21, 1, 8, 28}}。 int MinCost=1000。 int Task[N], TempTask[N], Worker[N]。 void Assign(int k, int cost) { if(k == N) { MinCost = cost。 for(int i=0。 iN。 i++) TempTask[i] = Task[i]。 } else { for(int i=0。 iN。 i++) { if(Worker[i]==0 amp。amp。 cost+Cost[k][i] MinCost) { // 為提高效率而進行剪枝 Worker[i] = 1。 Task[k] = i。 Assign(k+1, cost+Cost[k][i])。 Worker[i] = 0。 Task[k] = 0。 } } } } int main(int argc, char* argv[]) { Assign(0, 0)。 printf(最佳方案總費用 =%d\n, MinCost)。 for(int i=0。 iN。 i++) /* 輸出最佳方案 */ printf(\t任務 %d由工人 %d來做： %d\n, i, TempTask[i], Cost[i][TempTask[i]])。 } 1八皇后問題 ， 輸出 了 所有情況，不過有些 結果 只是旋轉了 90度而已 。 （ 回溯算法的典型例題 ，是數據結構書上算法的具體實現，大家都親自動手寫過這個程序嗎？） define N 8 int Board[N][N]。 int Valid(int i, int j) { // 判斷 下棋 位置是否 有效 int k = 1。 for(k=1。 i=k amp。amp。 j=k。k++) if(Board[ik][jk]) return 0。 for(k=1。 i=k。k++) if(Board[ik][j]) return 0。 for(k=1。 i=k amp。amp。 j+kN。k++) if(Board[ik][j+k]) return 0。 return 1。 } void Trial(int i, int n) { // 尋找合適下棋位置 if(i == n) { for(int k=0。 kn。 k++) { for(int m=0。 mn。 m++) printf(%d , Board[k][m])。 printf(\n)。 } printf(\n)。 } else { for(int j=0。 jn。 j++) { Board[i][j] = 1。 if(Valid(i,j)) Trial(i+1, n)。 Board[i][j] = 0。 } } } int main(int argc, char* argv[]) { Trial(0, N)。 } 1 實現 strstr功能 ，即 在父串中 尋找子串 首次出現的位置 。（筆試中常讓面試者實現標準庫中的一些函數） char * strstring(char *ParentString, char *SubString) { char *pSubString, *pPareString。 for(char *pTmp=ParentString。 *pTmp。 pTmp++) { pSubString = SubString。 pPareString = pTmp。 while(*pSubString == *pPareString amp。amp。 *pSubString != 39。\039。) { pSubString++。 pPareString++。 } if(*pSubString == 39。\039。) return pTmp。 } return NULL。 } int main(int argc, char* argv[]) { char *ParentString = happy birthday to you!。 char *SubString = birthday。 printf(%s,strstring(ParentString, SubString))。 } 1現在小明一家過一座橋，過橋的時候是黑夜，所以必須有燈。現在小明過橋要1分 ，小明的弟弟要 3分 ，小明的爸爸要 6分 ，小明的媽媽要 8分 ，小明的爺爺要 12分 。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃后 30分 就會熄滅。問小明一家如何過橋 時間最短 ？ （ 原本是個小小智力題，據說是外企的面試題，在 這里用程序來求解） include define N 5 define SIZE 64 // 將人員編號：小明 0，弟弟 1，爸爸 2，媽媽 3，爺爺 4 // 每個人的當 前位置： 0在橋左邊， 1在橋右邊 int Position[N]。 // 過橋臨時方案的數組下標； 臨時方案； 最小時間方案； int Index, TmpScheme[SIZE], Scheme[SIZE]。 // 最小過橋時間總和，初始值 100；每個人過橋所需要的時間 int MinTime=100, Time[N]={1, 3, 6, 8, 12}。 // 尋找最佳過橋方案。 Remnant:未過橋人數 。 CurTime:當前已用時間 。 // Direction:過橋方向 ,1向右 ,0向左 void Find(int Remnant, int CurTime, int Direction) { if(Remnant == 0) { // 所有人已經過橋，更新最少時間及方案 MinTime=CurTime。 for(int i=0。 iSIZE amp。amp。 TmpScheme[i]=0。 i++) Scheme[i] = TmpScheme[i]。 } else if(Direction == 1) { // 過橋方向向右，從橋左側選出兩人過橋 for(int i=0。 iN。 i++) if(Position[i] == 0 amp。amp。 CurTime + Time[i] MinTime) { TmpScheme[Index++] = i。 Position[i] = 1。 for(int j=0。 jN。 j++) { int TmpMax = (Time[i] Time[j] ? Time[i] : Time[j])。 if(Position[j] == 0 amp。amp。 CurTime + TmpMax MinTime) { TmpScheme[Index++] = j。 Position[j] = 1。 Find(Remnant 2, CurTime + TmpMax, !Direction)。 Position[j] = 0。 TmpScheme[Index] = 1。 } } Positio