创新工场笔试题

创新工场编程题

1.输入一个整型无序数组，用堆排序的方法是数组有序

2.求一个正整数的开方，要求不能使用库函数sqrt，结果精度在0.01即可

3.给定一个矩阵int matrixA[m][n]，每行没列都是增序的，实现一个算法寻找矩阵中的某个元素element

下面做出我的题解，能力有限，望见谅！

第一题：堆排序

　　考的排序算法中的堆排序，这里稍微讲一下堆排序的算法：

　　二叉树：

　　基本概念：

　　大根堆： 就是说父节点要比左右孩子都要大。

　　小根堆： 就是说父节点要比左右孩子都要小。

　　算法：

　　1、从最后一个父结点开始，从后往前遍历树的所有二叉树的父节点，构造大顶堆；

　　2、整个数都是大顶堆，那么树的根节点肯定是数组中的最大值，将其与最后一个元素交换swap，这时可能会破坏大顶堆，需要重新构建大顶堆，然后再取树的根节点与最后一个点交换，依次类推……

代码如下：

 
相应的代码：
/*    杨氏矩阵：查找*/#include <stdio.h>#include <stdlib.h>#define M 4#define N 4int FindElement(int MatrixA[M][N], int element){    int i = 0, j = N - 1;    while(1)    {        while(MatrixA[i][j] >= element)        {            if(MatrixA[i][j] == element) return 1;            j--;            if(j < 0) return 0;        }        while(MatrixA[i][j] <= element)        {            if(MatrixA[i][j] == element) return 1;            i++;            if(i >= M) return 0;        }    }}int main(void){    int MatrixA[M][N] = {{1, 3, 4, 8},                         {3, 5, 6, 9},                         {6, 7, 10, 11},                         {7, 8, 12,15},                        };    int i = 0;    for(i = 1; i <= 15; i++)    {        printf("element: %-3d", i);        switch(FindElement(MatrixA, i))        {            case 0: printf("don't exist!\n"); break;            case 1: printf(" exist!\n"); break;            default: break;        }    }    return 0;}
此题目摘取自july CSDN网站：http://blog.csdn.net/v_july_v/article/details/11921021

注：本博客与博客园上的博客为同一博客主：http://www.cnblogs.com/bestDavid/
 
2楼zhizunwudi昨天 19:10
你好，第二个题中#define  EPSION  0.000001   n为什么定义为这个数啊，不是0.01吗？
Re: xuzewei_2昨天 19:27
回复zhizunwudin这个无所谓，要是我笔试的时候肯定写0.01，现在不是笔试，就想写多久写多少咯，这纠结这个啦。。
Re: zhizunwudi昨天 20:10
回复xuzewei_2n恩，不过这个方法确实好，我在网上看到的是用迭代的方法求的，呵呵
1楼shuyechengying昨天 17:25
那叫二分，而不是分治吧
Re: xuzewei_2昨天 17:45
回复shuyechengyingn改成二分法了。。
Re: xuzewei_2昨天 17:54
回复shuyechengyingn分治法又称二分法！
Re: shuyechengying昨天 18:07
回复xuzewei_2是吗？我看到的分治的算法都有将子问题的解合并的过程，二分没有。
Re: xuzewei_2昨天 19:09
回复shuyechengyingn好吧，个人感觉二分法属于分治法的范畴。。