创新工场2014笔试算法题汇总附答案

 　　1. 编程实现堆排序

#include

usingnamespace std;

void SwapValue(int &m, int &n)

{

int temp = m;

m = n;

n = temp;

}

void max_heap(vector &vec, int i, int heap_size)

{

int l = 2*i;

int r = 2*i+1;

int largest = i;

if(l<=heap_size && vec[l-1]>vec[largest-1])

largest = l;

if(r<=heap_size && vec[r-1]>vec[largest-1])

largest = r;

if(largest!=i)

{

SwapValue(vec[largest-1],vec[i-1]);

max_heap(vec, largest, heap_size);

}

}

void heapSort(vector &vec)

{

int heap_size = ();

for(int i=heap_size/2; i>=1; i–)

max_heap(vec, i, heap_size);

for(int i=heap_size; i>=1; i–)

{

SwapValue(vec[0],vec[i-1]);

max_heap(vec, 1, i);

}

}

void print(vector vec)

{

for(int i=0; i

cout<

cout<

}

int main()

{

vector vec;

_back(23);

_back(5);

_back(1);

_back(10);

_back(13);

_back(32);

_back(21);

_back(14);

_back(19);

_back(20);

cout<<“排序前： “<

print(vec);

heapSort(vec);

cout<<“排序后： “<

print(vec);

return 0;

}

2.求一个正整数N的开方，要求不能用库函数sqrt()，结果的`精度在0.001

解析：牛顿迭代

#include

using namespace std;

int main()

{

int N;

cout<<“输入N的值：“;

cin>>N

double x1 = 1;//初值

double x2 = x1/2.0+N/2.0/x1;

while( fabs(x2-x1)>0.001)

{

x1 = x2;

x2 = x1/2.0+N/2.0/x1;

}

cout<

return 0;

}

3.给定一个矩阵intmaxtrixA[m][n],每行和每列都是增序的，实现一个算法去找矩阵中的某个元素element.

解法一：

#include

using namespace std;

const int M = 4;

const int N = 4;

int main

{

int matrix[M][N] = {};

double element;

int flag = 1;

for(int j=0; j

{

if(matrix[i][j] == element)

cout<<“位置“<

while( flag

–flag;

while( flagelement )

++flag;

}

}

解法二：

bool Find(int *matrixA, int m, int n, int element)

{

bool found = false;

if(matrixA != NULL & m & n)

{

int i,j;

i=0;j=n-1;

while(i

{

if(maxtrixA[i*n+j] == element)

{

found = true;

break;

}

else if(matrix[i*n+j]>element

–j;

else

++i

}

}

}