it算法经典笔试26题(编辑修改稿)

it算法经典笔试26题(编辑修改稿)内容摘要：

rSource=%s\n, GetSubString(strSource, strResult), strResult, strSource)。 } 1四个工人，四个任务，每个人做不同 的 任务需要的时间不同，求任务分配 的最优方案。 （ 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。