【华为】C 语言面试题大汇总之华为面试题(4)

elsehigh=mid-1;

}

return-1;

}

3.递归计算如下递归函数的值（斐波拉契）：

f(1)=1

f(2)=1

f(n)=f(n-1)+f(n-2)n>2

解：非递归算法:

intf(intn)

{

inti,s,s1,s2;

s1=1;

s2=1;

s=1;

for(i=3;i<=n;i++)

{

s=s1+s2;

s2=s1;

s1=s;

}

return(s);

递归算法:

Intf(intn)

{

If(n==1||n==2)

Rerurn1;

Else

Rerutnf(n-1)+f(n-2);

}

4.交换两个数，不用第三块儿内存：

答:inta=……;

intb=……;

a=a+b;

b=a-b;

a=a-b;

5.冒泡排序：

答:voidBubbleSort(elemtypex[],intn)

{

inti,j;

elemtypetemp;

for(i=1;i<n;i++)

for(j=0;j<n-i;j++)

{

if(x[j].key>x[j+1].key)

{

temp=x[j];

x[j]=x[j+1];

x[j+1]=temp;

}

}

}

//补充一个改进的冒泡算法:

voidBubbleSort(elemtypex[],intn)

{

Inti,j;

BOOLexchange;//记录交换标志

for(i=1;i<n;++i)//最多做n-1趟排序//时间复杂度为0(n*n);