算法筆試題

2019-11-14 09:17:33

字體：大中小

來源：轉載

供稿：網友

1、將一整數逆序后放入一數組中（要求遞歸實現）void convert(int *result, int n){ if(n>=10) convert(result+1, n/10); *result = n%10; }int main(int argc, char* argv[]){ int n = 123456789, result[20]={}; convert(result, n); PRintf("%d:", n); for(int i=0; i<9; i++) printf("%d", result[i]); return getchar();}2、求高于平均分的學生學號及成績（學號和成績人工輸入）double find(int total, int n){ int number, score, average; scanf("%d", &number); if(number != 0){ scanf("%d", &score); average = find(total+score, n+1); if(score >= average) printf("%d:%d/n", number, score); return average; }else{ printf("Average=%d/n", total/n); return total/n; }}int main(int argc, char* argv[]){ find(0, 0); return getchar();}3、遞歸實現回文判斷（如：abcdedbca就是回文）int find(char *str, int n){ if(n<=1) return 1; else if(str[0]==str[n-1]) return find(str+1, n-2); else return 0;} int main(int argc, char* argv[]){ char *str = "abcdedcba"; printf("%s: %s/n", str, find(str, strlen(str)) ? "Yes" : "No"); return getchar();} 4、組合問題（從M個不同字符中任取N個字符的所有組合）void find(char *source, char *result, int n){ if(n==1){ while(*source) printf("%s%c/n", result, *source++); }else{ int i, j; for(i=0; source[i] != 0; i++); for(j=0; result[j] != 0; j++); for(; i>=n; i--) { result[j] = *source++; result[j+1] = '/0'; find(source, result, n-1); } }} int main(int argc, char* argv[]){ int const n = 3; char *source = "ABCDE", result[n+1] = {0}; if(n>0 && strlen(source)>0 && n<=strlen(source)) find(source, result, 3); return getchar();}5、分解成質因數(如435234=251*17*17*3*2)void prim(int m, int n){ if(m>n){ while(m%n != 0) n++; m /= n; prim(m, n); printf("%d*", n); }}int main(int argc, char* argv[]){ int n = 435234; printf("%d=", n); prim(n, 2); return getchar();} 6、尋找迷宮的一條出路（o：通路； X障礙）#define MAX_SIZE 8int H[4] = {0, 1, 0, -1};int V[4] = {-1, 0, 1, 0}; char Maze[MAX_SIZE][MAX_SIZE] = {{'X','X','X','X','X','X','X','X'}, {'o','o','o','o','o','X','X','X'}, {'X','o','X','X','o','o','o','X'}, {'X','o','X','X','o','X','X','o'}, {'X','o','X','X','X','X','X','X'},{'X','o','X','X','o','o','o','X'}, {'X','o','o','o','o','X','o','o'}, {'X','X','X','X','X','X','X','X'}};void FindPath(int X, int Y){ if(X == MAX_SIZE || Y == MAX_SIZE){ for(int i = 0; i < MAX_SIZE; i++)for(int j = 0; j < MAX_SIZE; j++) printf("%c%c", Maze[i][j], j < MAX_SIZE-1 ? ' ' : '/n');}else for(int k = 0; k < 4; k++)if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X < MAX_SIZE && 'o' == Maze[X][Y]){ Maze[X][Y] = ' '; FindPath(X+V[k], Y+H[k]); Maze[X][Y] ='o';}}int main(int argc, char* argv[]){ FindPath(1,0); return getchar();} 7、隨機分配座位，共50個學生，使學號相鄰的同學座位不能相鄰(早些時候用C#寫的，沒有用C改寫）。static void Main(string[] args){ int Tmp = 0, Count = 50; int[] Seats = new int[Count]; bool[] Students = new bool[Count]; System.Random RandStudent=new System.Random(); Students[Seats[0]=RandStudent.Next(0,Count)]=true; for(int i = 1; i < Count; ){ Tmp=(int)RandStudent.Next(0,Count); if((!Students[Tmp])&&(Seats[i-1]-Tmp!=1) && (Seats[i-1] - Tmp) != -1){ Seats[i++] = Tmp;Students[Tmp] = true; } } foreach(int Student in Seats) System.Console.Write(Student + " "); System.Console.Read();} 8、求網格中的黑點分布（有6*7的網格，在某些格子中有黑點，已知各行與各列中有黑點的點數之和）#define ROWS 6#define COLS 7int ipointsR[ROWS] = {2, 0, 4, 3, 4, 0}; // 各行黑點數和的情況int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1}; // 各列黑點數和的情況int iCount, iFound;int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS]; int Set(int iRowNo){if(iRowNo == ROWS){ for(int iColNo=0; iColNo < COLS && iSumC[iColNo]==iPointsC[iColNo]; iColNo++) if(iColNo == COLS-1){ printf("/nNo.%d:/n", ++iCount); for(int i=0; i < ROWS; i++) for(int j=0; j < COLS; j++) printf("%d%c", Grid[i][j], (j+1) % COLS ? ' ' : '/n'); iFound = 1; // iFound = 1，有解 } }else{ for(int iColNo=0; iColNo < COLS; iColNo++) { if(iPointsR[iRowNo] == 0){ Set(iRowNo + 1); }else if(Grid[iRowNo][iColNo]==0){Grid[iRowNo][iColNo] = 1;iSumR[iRowNo]++; iSumC[iColNo]++; if(iSumR[iRowNo]<iPointsR[iRowNo] && iSumC[iColNo]<=iPointsC[iColNo]) Set(iRowNo);else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS) Set(iRowNo + 1); Grid[iRowNo][iColNo] = 0; iSumR[iRowNo]--; iSumC[iColNo]--; } } }return iFound; // 用于判斷是否有解}int main(int argc, char* argv[]){ if(!Set(0)) printf("Failure!"); return getchar();}9、有4種面值（面值為1, 4, 12, 21）的郵票很多枚，從中最多任取5張進行組合，求郵票最大連續組合值#define N 5#define M 5int k, Found, Flag[N];int Stamp[M] = {0, 1, 4, 12, 21}; // 在剩余張數n中組合出面值和Valueint Combine(int n, int Value){ if(n >= 0 && Value == 0){ Found = 1; int Sum = 0; for(int i=0; i<N && Flag[i] != 0; i++){ Sum += Stamp[Flag[i]]; printf("%d ", Stamp[Flag[i]]); } printf("/tSum=%d/n/n", Sum); }else for(int i=1; i<M && !Found && n>0; i++) if(Value-Stamp[i] >= 0){ Flag[k++] = i; Combine(n-1, Value-Stamp[i]); Flag[--k] = 0; } return Found;} int main(int argc, char* argv[]){ for(int i=1; Combine(N, i); i++, Found=0); return getchar();} 10、大整數數相乘的問題。void Multiple(char A[], char B[], char C[]){ int TMP, In=0, LenA=-1, LenB=-1; while(A[++LenA] != '/0'); while(B[++LenB] != '/0'); int Index, Start = LenA + LenB - 1; for(int i=LenB-1; i>=0; i--) { Index = Start--; if(B[i] != '0'){ for(int In=0, j=LenA-1; j>=0; j--) { TMP = (C[Index]-'0') + (A[j]-'0') * (B[i] - '0') + In; C[Index--] = TMP % 10 + '0'; In = TMP / 10; } C[Index] = In + '0'; } }} int main(int argc, char* argv[]){ char A[] = "21839244444444448880088888889"; char B[] = "38888888888899999999999999988";char C[sizeof(A) + sizeof(B) - 1]; for(int k=0; k<sizeof(C); k++) C[k] = '0'; C[sizeof(C)-1] = '/0'; Multiple(A, B, C); for(int i=0; C[i] != '/0'; i++) printf("%c", C[i]); return getchar();} 11、求最大連續遞增數字串（如“ads3sl456789DF3456ld345AA”中的“456789”）int GetSubString(char *strSource, char *strResult){ int iTmp=0, iHead=0, iMax=0; for(int Index=0, iLen=0; strSource[Index]; Index++) { if(strSource[Index] >= '0' && strSource[Index] <= '9'&& strSource[Index-1] > '0' && strSource[Index] == strSource[Index-1]+1){ iLen++; // 連續數字的長度增1 }else{ // 出現字符或不連續數字 if(iLen > iMax) { iMax = iLen;iHead = iTmp; } // 該字符是數字，但數字不連續 if(strSource[Index] >= '0' && strSource[Index] <= '9'){ iTmp = Index;iLen = 1; } } } for(iTmp=0 ; iTmp < iMax; iTmp++) // 將原字符串中最長的連續數字串賦值給結果串 strResult[iTmp] = strSource[iHead++]; strResult[iTmp]='/0'; return iMax; // 返回連續數字的最大長度}int main(int argc, char* argv[]){ char strSource[]="ads3sl456789DF3456ld345AA", char strResult[sizeof(strSource)];printf("Len=%d, strResult=%s /nstrSource=%s/n", GetSubString(strSource, strResult),strResult, strSource); return getchar();} 12、四個工人，四個任務，每個人做不同的任務需要的時間不同，求任務分配的最優方案。（2005年5月29日全國計算機軟件資格水平考試——軟件設計師的算法題）。#include "stdafx.h"#define N 4int 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<N; i++) TempTask[i] = Task[i]; }else{ for(int i=0; i<N; i++){ if(Worker[i]==0 && 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; i<N; i++) /* 輸出最佳方案 */ printf("/t任務%d由工人%d來做：%d/n", i, TempTask[i], Cost[i][TempTask[i]]); return getchar(); } 13、八皇后問題（輸出所有情況，不過有些結果只是旋轉了90度而已）。哈哈：）回溯算法的典型例題#define N 8int 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<N;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<n; k++){ for(int m=0; m<n; m++) printf("%d ", Board[k][m]); printf("/n"); } printf("/n"); }else{ for(int j=0; j<n; 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); return getchar();}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)); return getchar();}}

1,寫出一個函數，比較兩個字符串，返回最大公串，例如abacdaccbadc和cedaccbe返回daccb;2，有100個數字，其中有正數也有負數，找出連續三個相加之和最大部分；要求：盡量不要使用庫函數！兩道一起來：支持搜索中文，import java.util.Random;public class Test{ private static int maxSubStart = 0; private static int maxSubLength = 0; private static char[] c1, c2; private static boolean isSame(int i, int j) { return c1[i] == c2[j]; } private static void setMaxSub(int start1, int start2) { int i = start1, j = start2; int maxStart = 0; int maxLength = 0; for (; i < c1.length && j < c2.length; i++,j++) { if (isSame(i, j)) { maxLength++; } else break; } if (maxLength > maxSubLength) { maxSubLength = maxLength; maxSubStart = start1; } } private static String getMaxCommonString(String s1, String s2) { c1 = s1.toCharArray(); c2 = s2.toCharArray(); if (c1.length > c2.length) // swap s1, s2 so s1.length < s2.length { char[] c = c1; c1 = c2; c2 = c; } int minLength = c1.length; int maxLength = c2.length; for (int i = 0; i < minLength; i++) { char ch = c1[i]; for (int j = 0; j < maxLength; j++) { if (ch == c2[j]) { setMaxSub(i, j); } } } return new String(c1, maxSubStart, maxSubLength); } private static int[] getRandomInt(int length) { Random r = new Random(); int[] res = new int[length]; for (int i = 0; i < length; i++) { res[i] = r.nextInt(200) - 100; } return res; } private static int count(int[] num, int i) { return num[i]+num[i+1]+num[i+2]; } private static int getMaxThreeStart(int[] num) { int end = num.length - 3; int max = 0; int start = 0; for (int i = 0; i < end; i++) { int c = count(num, i); if (c > max) { max = c; start = i; } } return start; } public static void main(String[] args) { //abacdaccbadc和cedaccbe String s1 = "abacd測試漢字 accbadc", s2 = "ced測試漢字 accbe"; System.out.println(s1 + " " + s2 + " 的最大公串為: " + getMaxCommonString(s1, s2)); int[] num = getRandomInt(100); int start = getMaxThreeStart(num); for (int i = 0; i < 100; i++) { System.out.print(num[i] + " "); if (i%10 == 9) { System.out.println(); } } System.out.println("三個連續數字之和最大的三個數子為: " + num[start] + " " + num[start+1] + " " + num[start+2]); }};

上一篇：linux內核線程 [創建]

下一篇：Codeforces Round #333 (Div. 2)E