2021年華為軟件工程師面試題
- 管理員
- 1663閱讀
- 2021.06.22
寫一個程序,?要求功能:求出用1,2,5這三個數不同個數組合的和為100的組合個數。
如:100個1是一個組合,5個1加19個5是一個組合。。。。?請用C++語言寫。
最容易想到的算法是:
設x是1的個數,y是2的個數,z是5的個數,number是組合數
注意到0<=x<=100,0<=y<=50,0<=z=20,所以可以編程為:?
number=0;
for?(x=0;?x<=100;?x++)
for?(y=0;?y<=50;?y++)
for?(z=0;?z<=20;?z++)
if?((x+2*y+5*z)==100)
number++;
cout<
上面這個程序一共要循環100*50*20次,效率實在是太低了
事實上,這個題目是一道明顯的數學問題,而不是單純的編程問題。我的解法如下:
因為x+2y+5z=100
所以x+2y=100-5z,且z<=20?x<=100?y<=50
所以(x+2y)<=100,且(x+5z)是偶數
對z作循環,求x的可能值如下:
?
z=0,?x=100,?98,?96,?...?0
z=1,?x=95,?93,?...,?1
z=2,?x=90,?88,?...,?0
z=3,?x=85,?83,?...,?1
z=4,?x=80,?78,?...,?0
......
z=19,?x=5,?3,?1
z=20,?x=0
?
因此,組合總數為100以內的偶數+95以內的奇數+90以內的偶數+...+5以內的奇數+1,
即為:
(51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)+(11+8)+(6+3)+1
?
?
某個偶數m以內的偶數個數(包括0)可以表示為m/2+1=(m+2)/2
某個奇數m以內的奇數個數也可以表示為(m+2)/2
?
所以,求總的組合次數可以編程為:
number=0;
for?(int?m=0;m<=100;m+=5)
{
number+=(m+2)/2;
}
cout<
這個程序,只需要循環21次,?兩個變量,就可以得到答案,比上面的那個程序高效了許多
倍----只是因為作了一些簡單的數學分析
?
這再一次證明了:計算機程序=數據結構+算法,而且算法是程序的靈魂,對任何工程問
題,當用軟件來實現時,必須選取滿足當前的資源限制,用戶需求限制,開發時間限制等種
種限制條件下的最優算法。而絕不能一拿到手,就立刻用最容易想到的算法編出一個程序了
事——這不是一個專業的研發人員的行為。
?
那么,那種最容易想到的算法就完全沒有用嗎?不,這種算法正好可以用來驗證新算法
的正確性,在調試階段,這非常有用。在很多大公司,例如微軟,都采用了這種方法:在調
試階段,對一些重要的需要好的算法來實現的程序,而這種好的算法又比較復雜時,同時用
容易想到的算法來驗證這段程序,如果兩種算法得出的結果不一致(而最容易想到的算法保
證是正確的),那么說明優化的算法出了問題,需要修改。
可以舉例表示為:
#ifdef?DEBUG
int?simple();
#end?if
int?optimize();
......
in?a?function:
{
result=optimize();
ASSERT(result==simple());
}
這樣,在調試階段,如果簡單算法和優化算法的結果不一致,就會打出斷言。同時,在程
序的發布版本,卻不會包含笨重的simple()函數?!魏未笮凸こ誊浖夹枰A先設計良
好的調試手段,而這里提到的就是一種有用的方法。
一個學生的信息是:姓名,學號,性別,年齡等信息,用一個鏈表,把這些學生信息連在一起,給出一個age,?在些鏈表中刪除學生年齡等于age的學生信息。
#include?"stdio.h"
#include?"conio.h"
?
struct?stu{
char?name[20];
char?sex;
int?no;
int?age;
struct?stu?*?next;
}*linklist;
struct?stu?*creatlist(int?n)
{
int?i;
//h為頭結點,p為前一結點,s為當前結點
struct?stu?*h,*p,*s;
h?=?(struct?stu?*)malloc(sizeof(struct?stu));
h->next?=?NULL;
p=h;
for(i=0;i
{?
s?=?(struct?stu?*)malloc(sizeof(struct?stu));
p->next?=?s;
printf("Please?input?the?information?of?the?student:?name?sex?no?age?\n");
scanf("%s?%c?%d?%d",s->name,&s->sex,&s->no,&s->age);
s->next?=?NULL;
p?=?s;
}
printf("Create?successful!");
return(h);
}
void?deletelist(struct?stu?*s,int?a)
{
struct?stu?*p;
while(s->age!=a)
{
p?=?s;
s?=?s->next;
}
if(s==NULL)
printf("The?record?is?not?exist.");
else
{
p->next?=?s->next;
printf("Delete?successful!");
}
}
void?display(struct?stu?*s)
{
s?=?s->next;
while(s!=NULL)
{
printf("%s?%c?%d?%d\n",s->name,s->sex,s->no,s->age);
s?=?s->next;
}
}
int?main()
{
struct?stu?*s;
int?n,age;
printf("Please?input?the?length?of?seqlist:\n");
scanf("%d",&n);
s?=?creatlist(n);
display(s);
printf("Please?input?the?age:\n");
scanf("%d",&age);
deletelist(s,age);
display(s);
return?0;
}
實現一個函數,把一個字符串中的字符從小寫轉為大寫。
#include?"stdio.h"
#include?"conio.h"
?
void?uppers(char?*s,char?*us)
{
for(;*s!='\0';s++,us++)
{
if(*s>='a'&&*s<='z')
*us?=?*s-32;
else
*us?=?*s;
}
*us?=?'\0';
}
int?main()
{
char?*s,*us;
char?ss[20];
printf("Please?input?a?string:\n");
scanf("%s",ss);
s?=?ss;
uppers(s,us);
printf("The?result?is:\n%s\n",us);
getch();
}
隨機輸入一個數,判斷它是不是對稱數(回文數)(如3,121,12321,45254)。不能用字符串庫函數
1.
函數名稱:Symmetry?
功能:?判斷一個數時候為回文數(121,35653)?
輸入:?長整型的數?
輸出:?若為回文數返回值為1?esle?0?
******************************************************************/
unsigned?char?Symmetry?(long?n)
{
long?i,temp;
i=n;?temp=0;
while(i)?//不用出現長度問題,將數按高低位掉換
{
temp=temp*10+i%10;
i/=10;
}
return(temp==n);
}?
方法一?
/*?---------------------------------------------------------------------------?
功能:?
判斷字符串是否為回文數字?
實現:?
先將字符串轉換為正整數,再將正整數逆序組合為新的正整數,兩數相同則為回文數字?
輸入:?
char?*s:待判斷的字符串?
輸出:?
無?
返回:?
0:正確;1:待判斷的字符串為空;2:待判斷的字符串不為數字;?
3:字符串不為回文數字;4:待判斷的字符串溢出?
----------------------------------------------------------------------------?*/?
unsigned?IsSymmetry(char?*s)?
{?
char?*p?=?s;?
long?nNumber?=?0;?
long?n?=?0;?
long?nTemp?=?0;?
?
/*判斷輸入是否為空*/?
if?(*s?==?\'\\0\')?
return?1;?
?
/*將字符串轉換為正整數*/?
while?(*p?!=?\'\\0\')?
{?
/*判斷字符是否為數字*/?
if?(*p<\'0\'?||?*p>\'9\')?
return?2;?
?
/*判斷正整數是否溢出*/?
if?((*p-\'0\')?>?(4294967295-(nNumber*10)))?
return?4;?
?
nNumber?=?(*p-\'0\')?+?(nNumber?*?10);?
?
p++;?
}?
?
/*將數字逆序組合,直接抄樓上高手的代碼,莫怪,呵呵*/?
n?=?nNumber;?
while(n)?
{?
/*判斷正整數是否溢出*/?
if?((n%10)?>?(4294967295-(nTemp*10)))?
return?3;?
?
nTemp?=?nTemp*10?+?n%10;?
n?/=?10;?
}?
?
/*比較逆序數和原序數是否相等*/?
if?(nNumber?!=?nTemp)?
return?3;?
?
return?0;?
}?
?
方法二?
/*?---------------------------------------------------------------------------?
功能:?
判斷字符串是否為回文數字?
實現:?
先得到字符串的長度,再依次比較字符串的對應位字符是否相同?
輸入:?
char?*s:待判斷的字符串?
輸出:?
無?
返回:?
0:正確;1:待判斷的字符串為空;2:待判斷的字符串不為數字;?
3:字符串不為回文數字?
----------------------------------------------------------------------------?*/?
unsigned?IsSymmetry_2(char?*s)?
{?
char?*p?=?s;?
int?nLen?=?0;?
int?i?=?0;?
?
/*判斷輸入是否為空*/?
if?(*s?==?\'\\0\')?
return?1;?
?
/*得到字符串長度*/?
while?(*p?!=?\'\\0\')?
{?
/*判斷字符是否為數字*/?
if?(*p<\'0\'?||?*p>\'9\')?
return?2;?
?
nLen++;?
p++;?
}?
?
/*長度不為奇數,不為回文數字*/?
if?(nLen%2?==?0)?
return?4;?
?
/*長度為1,即為回文數字*/?
if?(nLen?==?1)?
return?0;?
?
/*依次比較對應字符是否相同*/?
p?=?s;?
i?=?nLen/2?-?1;?
while?(i)?
{?
if?(*(p+i)?!=?*(p+nLen-i-1))?
return?3;?
?
i--;?
}?
?
return?0;?
}?
求2~2000的所有素數.有足夠的內存,要求盡量快
int?findvalue[2000]={2};
static?int?find=1;
bool?adjust(int?value)
{
assert(value>=2);
if(value==2)?return?true;
for(int?i=0;i<=find;i++)
{
if(value%findvalue[i]==0)
return?false;
}
findvalue[find++];
return?true;
}
A,B,C,D四個進程,A向buf里面寫數據,B,C,D向buf里面讀數據,
當A寫完,且B,C,D都讀一次后,A才能再寫。用P,V操作實現。
將單向鏈表reverse,如ABCD變成DCBA,只能搜索鏈表一次。
將二叉樹的兩個孩子換位置,即左變右,右變左。不能用遞規(變態?。?