部分IT公司笔试算法题

部分IT公司笔试算法题,标签：银行笔试题目,企业笔试题目,http://www.qz26.com

　　#include "stdafx.h"

　　#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; i

　　TempTask = Task;

　　} else {

　　for(int i=0; i

　　if(Worker==0 && cost+Cost[k] < MinCost) { // 为提高效率而进行剪枝

　　Worker = 1; Task[k] = i;

　　Assign(k+1, cost+Cost[k]);

　　Worker = 0; Task[k] = 0;

　　}

　　}

　　}

　　}

　　int main(int argc, char* argv[]) {

　　Assign(0, 0);

　　printf("最佳方案总费用=%d\n", MinCost);

　　for(int i=0; i

　　printf("\t任务%d由工人%d来做：%d\n", i, TempTask, Cost[TempTask]);

　　}

　　13、八皇后问题，输出了所有情况，不过有些结果只是旋转了90度而已。(回溯算法的典型例题，是数据结构书上算法的具体实现，大家都亲自动手写过这个程序吗?)

　　#define N 8

　　int Board[N][N];

　　int Valid(int i, int j) { // 判断下棋位置是否有效

　　int k = 1;

　　for(k=1; i>=k && j>=k;k++)

　　if(Board[i-k][j-k]) return 0;

　　for(k=1; i>=k;k++)

　　if(Board[i-k][j]) return 0;

　　for(k=1; i>=k && j+k

　　if(Board[i-k][j+k]) return 0;

　　return 1;

　　}

　　void Trial(int i, int n) { // 寻找合适下棋位置

　　if(i == n) {

　　for(int k=0; k

　　for(int m=0; m

　　printf("%d ", Board[k][m]);

　　printf("\n");

　　}

　　printf("\n");

　　} else {

　　for(int j=0; j

　　Board[j] = 1;

　　if(Valid(i,j))

　　Trial(i+1, n);

　　Board[j] = 0;

　　}

　　}

　　}

　　int main(int argc, char* argv[]) {

　　Trial(0, N);

　　}

　　14、实现strstr功能，即在父串中寻找子串首次出现的位置。(笔试中常让面试者实现标准库中的一些函数)

　　char * strstring(char *ParentString, char *SubString) {

　　char *pSubString, *pPareString;

　　for(char *pTmp=ParentString; *pTmp; pTmp++) {

　　pSubString = SubString;

　　pPareString = pTmp;

　　while(*pSubString == *pPareString && *pSubString != '\0') {

　　pSubString++;

　　pPareString++;

　　}

　　if(*pSubString == '\0') return pTmp;

　　}

　　return NULL;

　　}

　　int main(int argc, char* argv[]) {

　　char *ParentString = "happy birthday to you!";

　　char *SubString = "birthday";

　　printf("%s",strstring(ParentString, SubString));

　　}

　　15、现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要1分，小明的弟弟要3分，小明的爸爸要6分，小明的妈妈要8分，小明的爷爷要12分。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30分就会熄灭。问小明一家如何过桥时间最短?(原本是个小小智力题，据说是外企的面试题，在这里用程序来求解)

　　#include "stdafx.h"

上一页  [1] [2] [3] [4] [5] [6] [7] [8]  下一页