纳金网

标题: 面试笔试题目三结义（BS） [打印本页]

作者: 烟雨 时间: 2015-5-30 07:29
标题: 面试笔试题目三结义（BS）

1 输入两个整数，要求输出这两个数的乘积。输入的数字可能超过计算机内整形数据的存储范围：
  (算法提示) 输入 string a, string b；计算string c=a*b; 返回 c;
std::string Multiply(std::string a, std::string b)
{
char* startA = a.data();
char* startB = b.data();
int lengthA = a.size();
int lengthB = b.size();
int tenOver = 0;
std::vector<int> resultVector;
resultVector.resize(lengthA * lengthB + 1);
for(int i = 0;i < lengthA;++i)
{
for(int j = 0;j < lengthB;++j)
{
int muitiplyA = std::atoi(*(startA + lengthA - i - 1));
int muitiplyB = std::atoi(*(startB + lengthB - j - 1));
ini Result = muitiplyA*muitiplyB;
resultVector[i * j] += (Result % 10) + tenOver;
tenOver = Result / 10;
}
}
std::vector<char> result;
result.resize(resultVector.size());
for(int k = 0; k <  resultVector.size(); ++k)
{
if(resultVector[k] > 9)
{
resultVector[k+1] += 1;
resultVector[k] = 9;
}
resultVector[k] += 48;
}
for(int l = 0;l < resultVector.size(); ++l)
   ｛
result[l] = (char)resultVector[resultVector.size() - l];
   ｝
return std::string(result.begin(),result.begin());
}

2 不用第三个变量实现两个整形变量的交换
void (int* a , int* b)
{
*a = *a + *b;
*b = *a - *b;
     *a = *a - *b;
}

3 爸爸,妈妈,妹妹,小强,至少两个人同一生肖的概率是多少
答：四个人的生肖都有十二种可能，至少两个同意生肖的概率也就是1-没人同生肖概率 = 1 - 1-（12*11*10*9）/（12*12*12*12）=0.427；

4 一个背包刚好装S克东西，有N个物体重量分别是：W1 W2 W3….WN  请编程用非递归的方法得出一组解
bool backInsert(int w[n])
{
int sum = 0;
std::sort(w.begin();w.end();[=](int a,int b){return a < b});
//假设传入参数为N个物体重量的数组
for(int i < 0; i < n ; ++i)
{
sum += W[n - i];
if(sum > S)
{
int k = n - i
while(k < n)
{
sum -= W[k];
for(int k = i ; k < n ;++k)
{
if(sum + W[k] == S)
return true;
}
++k
}

}
}
return false;
}

5 写出float x 与“零值”比较的if语句
答：if(x == 0.0f)

6 不能做switch()的参数类型是？
答：除了整型，枚举，字符其他应该都不行。

7 请列举4种排序方法并描述其实现原理算法复杂度(举出实例 )
冒泡排序：从待排序的数组从头开始一次和后面一个比较，将大的放后面小的放前面。这样一个循环最大的就是最后，这样依次循环.
平均复杂度为O（n2）;
直接选择排序:第一次循环从待排序数组中选择最小的放在头部，后面依次循环从剩下的中选最小的放在第i个，直到循环N次；
平均复杂度为0（n2）;
快速排序：在待排序的数组中选一个任意基准，小的在左大的在右，再又对左右两部分递归；
平均复杂度为0（logn）;
直接插入排序:把n待排序的数组看成为一个有序表和一个无序表，每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
平均复杂度为O（n2）;

欢迎光临纳金网 (http://go.narkii.com/club/)