创新工场2014笔试算法题汇总.doc

创新工场2014笔试算法题汇总1.堆排序1. #include2. usingnamespacestd;3. 4. voidSwapValue(int&m,int&n)5. 6. inttemp=m;7. m=n;8. n=temp;9. 10. voidmax_heap(vector&vec,inti,intheap_size)11. 12. intl=2*i;13. intr=2*i+1;14. intlargest=i;15. 16. if(lveclargest-1)17. largest=l;18. if(rveclargest-1)19. largest=r;20. 21. if(largest!=i)22. 23. SwapValue(veclargest-1,veci-1);24. max_heap(vec,largest,heap_size);25. 26. 27. voidheapSort(vector&vec)28. 29. intheap_size=vec.size();30. for(inti=heap_size/2;i=1;i-)31. max_heap(vec,i,heap_size);32. for(inti=heap_size;i=1;i-)33. 34. SwapValue(vec0,veci-1);35. max_heap(vec,1,i);36. 37. 38. voidprint(vectorvec)39. 40. for(inti=0;ivec.size();i+)41. coutveci;42. coutendl;43. 44. 45. intmain()46. 47. vectorvec;48. vec.push_back(23);49. vec.push_back(5);50. vec.push_back(1);51. vec.push_back(10);52. vec.push_back(13);53. vec.push_back(32);54. vec.push_back(21);55. vec.push_back(14);56. vec.push_back(19);57. vec.push_back(20);58. 59. cout排序前：endl;60. print(vec);61. 62. heapSort(vec);63. 64. cout排序后：endl;65. print(vec);66. return0;67. 2.求一个正整数N的开方，要求不能用库函数sqrt()，结果的精度在0.001解析：牛顿迭代1. #include2. usingnamespacestd;3. intmain()4. 5. intN;6. coutN8. 9. doublex1=1;/初值10. doublex2=x1/2.0+N/2.0/x1;11. while(fabs(x2-x1)0.001)12. 13. x1=x2;14. x2=x1/2.0+N/2.0/x1;15. 16. coutx1endl;17. 18. return0;19. 3.给定一个矩阵intmaxtrixAmn,每行和每列都是增序的，实现一个算法去找矩阵中的某个元素element.解法一：1. #include2. usingnamespacestd;3. 4. constintM=4;5. constintN=4;6. intmain7. 8. intmatrixMN=;9. doubleelement;10. 11. intflag=1;12. for(intj=0;jN;j+)13. 14. if(matrixij=element)15. cout位置endl;16. while(flagM&matrixijelement)17. -flag;18. while(flagelement)19. +flag;20. 21. 解法二：1. boolFind(int*matrixA,intm,intn,intelement)2. 3. boolfound=false;4. if(matrixA!=NULL&m&n)5. 6. inti,j;7. i=0;j=n-1;8. while(i=0)9. 10. if(maxtrixAi*n+j=element)