第一次参加面试的笔试题目
第一次参加笔试，有点紧张，笔试时间为1.5个小时，每个人发了一份题目，10张答题纸
共有七个题目，没有选择和填空题，题目大致如下：
1.
某种传染病第一天只有一个患者，前五天为潜伏期，不发作也不会传染人
第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人
求第N天共有多少患者
2.
将字符串中相邻相同的子串合并为一个子串，如"12342343454565678789" -- "123456789"
3.
求一个串中出现的第一个最长重复子串。采用顺序结构存储串，实现求串s中出现的第一个最长重复子串的下标和长度
4.
求bit位中1的总个数为n的所有整数集合
比如，二进制位中有两个1的整数为：
0x00000003
0x00000005
0x00000006
.
.
.
0xc0000000
5.
去掉整数的bit位为1的最高的两个bit位，如0x1030f --> 0x10f
6.
unsigned int intvert(unsigned int x, int p, int n)
实现对x的进行转换, p为起始转化位(最左边为第1位算起), n为需要转换的长度, 对这些bit位取反
假设起始点在右边.如x = 0b0001 0001, p=4, n=3 转换后x = 0b0110 0001
7.
C和C++混合编程，C源文件中会调用C++源文件中定义的函数int func_cpp(int)，C++也会调用C源程序中定义的函数int func_c(int)，
请组织程序的结构c.c, cpp.cpp, pro.h
[解决办法]
1、设第n天处于潜伏期的患者为an，处于发作状态的为bn
则a1~a5 = 1, b1~b5 = 0
n>5时，a[n] = b[n]*3 + a[n-1],b[n] = a[n-5]
第n天患者：
an+bn = b[n]*4+a[n-1] = a[n-5]*4+a[n-1]
递归求解。
[解决办法]
1.思路：建立一个有十个元素的数组来模拟病例记录就可以了使用数据结构unsigned int array[10] = {1};2.思路：当检索到某个位置时，查找前面该字符最近出现的位置到当前位置的子串是否和当前位置之后的数据是否相同，不同就更新该字符最新出现的位置，相同就strcpy使用数据结构int all[256];3.遍历一遍就可以了，当前index与前面所有出现src[index]处全部比较一遍使用数据结构vector<int> all[256];4.直接调整0和1的位置就可以了5.unsigned int func(unsigned int val){ unsigned int ui = val; unsigned int left = 0, right = 0; while (ui) { right = left; left = (ui & -ui); ui &= (ui - 1); } return (val & ~(left | right));}6.#include<iostream>using namespace std;inline unsigned int intvert(unsigned int x, int p, int n){ //这里加上参数的有效性检查! return x ^ (((1 << n) - 1) << (p - 1));}int main(){ unsigned int x = 0; printf("%x\n", intvert(x, 4, 3)); system("pause"); return 0;}7.//pro.h#ifndef _PRO_H_#define _PRO_H_#ifdef __cplusplusextern "C"{#endifint func_cpp(int);int func_c(int);#ifdef __cplusplus}#endif#endif //_PRO_H_//c.c#include"pro.h"int func_c(int){ ...}//cpp.cpp#include"pro.h"int main(){ ...}int func_cpp(int){ ...}
[解决办法]
.
某种传染病第一天只有一个患者，前五天为潜伏期，不发作也不会传染人
第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人
求第N天共有多少患者
int X(int n){ int x; if(n>=0&&n<=5) return 1; if(n>=6&&n<=10) return 1+3*(n-5); if(n==11) x=X(n-1)+3*(X(n-5)-1)-1; //第一个痊愈 if(n>=12&&n<=15) x=X(n-1)+3*(X(n-5)-1); //这段时间内没有人痊愈 if(n>=16) x=X(n-1)-X(n-5)+3*(X(n-4)-X(n-5)); //不知到行不行 return x;}
[解决办法]
12342343454565678789123456789请按任意键继续. . .
[解决办法]
在18楼我说了我对这几题的思路，刚才全部用代码实现了下，
没严格测试，可能会有些小BUG
//第一题#include<iostream>using namespace std;unsigned int func(unsigned int (&array)[10], int days){ unsigned int new_infected = 0;//记录新增的被感染者的人数 unsigned int infect_able = 0; //记录会传染的人数 unsigned int total = 0; //当天的总或者人数 int i; for (i = 5; i < 10; i++) infect_able += array[i]; for (i = 0; i < days; i++) { new_infected = infect_able * 3; infect_able = infect_able + array[4] - array[9]; memmove(array + 1, array, sizeof (int) * 9); array[0] = new_infected; } total = infect_able; for (i = 0; i < 5; i++) total += array[i]; return total;}int main(){ unsigned int array[10] = {1};//第一天一个病人 int days; cout<<"输入天数："<<endl; cin>>days; int total = func(array, days); cout<<"第"<<days<<"天患者人数为："<<total<<endl; system("pause"); return 0;}//第二题#include<stdio.h>#include<stdlib.h>#include<string.h>char *func(char *src){ int all[256]; int cur_index; if (NULL == src) return NULL; for (cur_index = 0; cur_index < 256; cur_index++) { all[cur_index] = -1; } cur_index = 0; while (src[cur_index]) { int front_index = all[src[cur_index]]; if (front_index == -1) { all[src[cur_index]] = cur_index; ++cur_index; } else { int rear_index = cur_index; for (; front_index < cur_index; front_index++, rear_index++) { if (src[front_index] != src[rear_index]) break; } if (front_index != cur_index) { all[src[cur_index]] = cur_index; ++cur_index; } else { strcpy(src + cur_index, src + rear_index); } } } return src;}int main(){ char src[1000]; puts("请输入字符串"); gets(src); printf("%s\n", func(src)); system("pause"); return 0;}//第三题#include<iostream>#include<vector>#include<assert.h>using namespace std;void func(const char *src, int *pindex, int *plength){ vector<int> all[256]; int cnt; assert(NULL != src && NULL != pindex && NULL != plength); *pindex = -1; *plength = 0; for (cnt = 0; src[cnt]; ++cnt) { int times; for (times = 0; times < all[src[cnt]].size(); ++times) { int pre = all[src[cnt]][times]; int cur = cnt; while (src[pre] == src[cur]) { ++pre; ++cur; } if (pre - all[src[cnt]][times] > *plength) { *pindex = all[src[cnt]][times]; *plength = pre - all[src[cnt]][times]; } } all[src[cnt]].push_back(cnt); }}int main(){ int index; int length; char src[1000]; puts("请输入字符串："); gets(src); func(src, &index, &length); puts("结果如下："); cout<<"index = "<<index<<endl; cout<<"length = "<<length<<endl; for (int i = index; i < index + length; i++) { cout<<src[i]; } cout<<endl; system("pause"); return 0;}//第四题#include<stdio.h>#include<stdlib.h>int get_next(unsigned int *pval){ int cur; int low, hig; for (cur = 0; cur != (sizeof(*pval) << 3) - 1; ++cur) { if ((*pval & (1 << cur)) && !((*pval & (1 << (cur + 1))))) break; } if ((sizeof(*pval) << 3) - 1 == cur) { return 0; } for (low = 0, hig = cur + 1; !(*pval & (1 << low)); ++low) ; *pval ^= (1 << hig); *pval ^= (1 << low); for (hig = cur, low = 0; hig > low; --hig, ++low) { if (((*pval & (1 << hig)) && (!(*pval & (1 << low)))) || ((*pval & (1 << low)) && (!(*pval & (1 << hig))))) { *pval ^= (1 << hig); *pval ^= (1 << low); } } return 1;}int main(){ unsigned int val; int bit1_num; printf("输入二进制位中1的个数：\n"); scanf("%d", &bit1_num); if ((sizeof(int) << 3) < bit1_num || bit1_num < 0) { printf("Error\n"); exit(1); } if ((sizeof(unsigned int) << 3) == bit1_num) val = -1; else val = ((1 << bit1_num) - 1); do { printf("%x\n", val); }while (get_next(&val)); system("pause"); return 0;}//第五题#include<stdio.h>#include<stdlib.h>unsigned int func(unsigned int val){ unsigned int ui = val; unsigned int left = 0, right = 0; while (ui) { right = left; left = (ui & -ui); ui &= (ui - 1); } return (val & ~(left | right));}int main(int argc,char* argv[]){ printf("%x\n", func(0x1030f)); system("pause"); return 0;}//第六题#include<iostream>using namespace std;inline unsigned int intvert(unsigned int x, int p, int n){ //这里加上参数的有效性检查! return x ^ (((1 << n) - 1) << (p - 1));}int main(){ unsigned int x = 0; printf("%x\n", intvert(x, 4, 3)); system("pause"); return 0;}//第七题//pro.h#ifndef _PRO_H_#define _PRO_H_#ifdef __cplusplusextern "C"{#endif //__cplusplusint func_cpp(int);int func_c(int);#ifdef __cplusplus}#endif //__cplusplus#endif //_PRO_H_//c.c#include"pro.h"int func_c(int){ ...}//cpp.cpp#include"pro.h"int main(){ ...}int func_cpp(int){ ...}
[解决办法]
第三题#include<iostream>#include<string>using namespace std;bool fun(const string& s,int begin,int& l){ l=0; int size=s.size(); int maxhop=(size-begin)/2; for(int i=maxhop;i>0;--i){ int latter_begin=begin+i; int bf=begin,bl=latter_begin; for(;bf<latter_begin;++bf,++bl) if(s[bf]!=s[bl])break; if(bf==latter_begin){ l=i; return true; } } return false;}int main(){ string input="332102321023"; int size=input.size(); int pos=0,l=0; for(int i=0;i<size;++i){ int t_l; if(fun(input,i,t_l)) if(t_l>l) pos=i,l=t_l; } cout<<pos<<" "<<l<<endl; return 0;}
[解决办法]
#include<iostream>#include<vector>using namespace std;const int P_SAFE = 0; //治愈const int P_LATENT = 1; //潜伏const int P_INFECTION = 2; //感染const int N = 16; //模拟天数class Patient{ public: Patient(); int DayPassed(); //病程前进一天 private: int affectedDays;};Patient::Patient(){ affectedDays = 10;}int Patient::DayPassed(){ --affectedDays; if(0 == affectedDays) return P_SAFE; if(affectedDays < 5) return P_INFECTION; return P_LATENT;}int main(int argc, char* argv[]){ vector<Patient*> p; int affected = 1; int cured = 0; for(int i = 0; i < N; ++i) { for(int i = 0; i < affected; ++i) p.push_back(new Patient()); affected = 0; cured = 0; if(0 == p.size()) break; vector<Patient*>::iterator lp = p.begin(); for(; lp != p.end(); ++lp) { switch((*lp)->DayPassed()) { case P_SAFE: //治愈的第10天，仍感染3名患者，但是自身痊愈 affected += 3; ++cured; delete *lp; p.erase(lp); break; case P_INFECTION: //单纯的感染期 affected += 3; break; default: //潜伏期 break; } } cout << "Day " << i+1 << ": " << endl; cout << "Cured: " << cured; cout<< "\tAffected: " << affected; cout << "\tCurrent: " << p.size() << endl; } return 0;}
[解决办法]
修正一下，上例中main中的输出部分有错误
int main(int argc, char* argv[]){ vector<Patient*> p; int affected = 1; int cured = 0; for(int i = 0; i < N; ++i) { for(int i = 0; i < affected; ++i) p.push_back(new Patient()); cout << "Day " << i << ": " << endl; cout << "Cured: " << cured; cout << "\tAffected: " << affected; cout << "\tCurrent: " << p.size() << endl; affected = 0; cured = 0; if(0 == p.size()) break; vector<Patient*>::iterator lp = p.begin(); for(; lp != p.end(); ++lp) { switch((*lp)->DayPassed()) { case P_SAFE: //治愈的第10天，仍感染3名患者，但是自身痊愈 affected += 3; ++cured; delete *lp; p.erase(lp); break; case P_INFECTION: //单纯的感染期 affected += 3; break; default: //潜伏期 break; } } } return 0;}
[解决办法]
第一题，我能想到的方法是用链表来做，每个病人设一个节点，一天遍历链表一次。
这个方法不是很好，当病人多了，计算变得很慢，下面是我做的，当到第30天，病人是68283，运算超慢，等了有半分钟，不知道有什么数学方法，不要用链表的。
#include<stdio.h>
#include<stdlib.h>
struct Node
{
char increase;
struct Node *next;
};
typedef struct Node *List;
int Number_sick=0;
unsigned int AddItem(List *plist)
{
struct Node *pt,*pnew;
pt=(struct Node*)malloc(sizeof(struct Node));
if(pt==NULL)
{
printf("memory error!\n");
return 0;
}
pt->increase=0;
pt->next=NULL;
if(*plist==NULL)
*plist=pt;
else
{
pnew=*plist;
while(pnew->next!=NULL)
pnew=pnew->next;
pnew->next=pt;
}
return 1;
}
main()
{
int i;
List head;
struct Node *pback,*prev;
head=NULL;
AddItem(&head);
Number_sick++;
pback=head;
prev=head;
for(i=1;i<=30;i++)
{
pback=head;
prev=head;
if(head==NULL)
break;
while(prev!=NULL)
{
if(++prev->increase>=6)
{
if(prev->increase<=10)
{
AddItem(&head);
AddItem(&head);
AddItem(&head);
Number_sick+=3;
}
else
{
head=prev->next;
free(prev);
prev=head;
Number_sick--;
continue;
}
}
prev=prev->next;
}
}
printf("The sick people number: %d\n",Number_sick);
}
[解决办法]
贴一个第4题，用的搜索
#include<stdio.h>#include<string.h>#define MAX_N 32int arr[32],num;unsigned int conver(){ unsigned int n = 0,i; for(i = MAX_N-1;i > 0;i--) { n=(n+arr[i])*2; } n+=arr[0]; return n;}void search(int n,int l){ int i; if(!n) { num++; printf("%x\n",conver()); return; } for(i = l;i < MAX_N;i++) { arr[i] = 1; search(n-1,i+1); arr[i] = 0; }}int main(){ int n; while(scanf("%d",&n),n) { memset(arr,0,sizeof(arr)); num = 0; search(n,0); printf("完毕！ 总共%d个\n",num); } return 0;}
[解决办法]
第一题其实是个数学题，
#include <stdio.h>#include <stdlib.h>int main() { int n; printf("input the day:"); scanf("%d", &n); int *a = malloc(sizeof(int)*(n+1)); if( n <= 5) printf("all %d people infect.",1); else if( n <= 10) { int k = 1 + (n-5)*3; printf("all %d people infect.",k); }else { a[1] = 1; int i; for (i = 2; i <=5; i++) a[i] = 0; for (i = 6; i <=10; i++) a[i] = 3; for (i = 11; i <= n; i++) a[i] = (a[i-9]+a[i-8]+a[i-7]+a[i-6]+a[i-5])*3; int c = 0; for ( i = n ; i > n-10; i--) c += a[i]; printf("all %d people infect.", c); } return 0;}