一步一步写算法,之数据采取

作者: 金沙澳门官网  发布:2019-11-15

 

 

【 注脚:版权全体,款待转发,请勿用于商业用项。  联系信箱:feixiaoxing @163.com】

【 注脚:版权全数,应接转发,请勿用于商业用场。  联系信箱:feixiaoxing @163.com】

 

 

    在数学中,有大器晚成部分数目接收的从头到尾的经过。举例来讲,有像这种类型后生可畏组数据:1、2、3、4。今后大家准备从当中筛选出1个数据,那么有二种接纳呢?结果应当是1、2、3、4;那么后生可畏旦接纳2个数据吧,怎么选呢?那么结果应当是12、13、14、15。就那样推算,大家还是能筛选出3个数据、4个数据的情事。

 

 

 

    那么,在前后相继方面应该怎么表示呢?其实能够使用递归的不二等秘书技。请我们和自己一块计算一下:

 

 

    要是大家有三个1亿个数据,当中多少的范围是0~1亿,也正是100M的数量。可是那几个数组中丢了一些多少,比方说少了5呀,少了10呀,那么有怎么着方法能够把这么些遗失的多少找回来呢?这么些题目轻巧,不过它能够扶助咱们实行思路,不断增高算法的运维作用。

    如若急需从1、2、3、4中选取多个数据,那么是还是不是先从1发轫,然后再2、3、4中筛选二个数码,那样可以有12、13、14三种情形。接着呢,大家从2上马,上面还行的数据独有从3、4中接收了,1不能够选拔了,不然会时有发生重复选项。由此及彼,那大家从4发轫的时候,发现4背后未有数据的时候,这个时候迭代终止。

 

 

    对于这些主题材料,大家三个最简便的思绪就是对生机勃勃豆蔻梢头数据举办flag判定,然后挨门逐户输出数据。

    筛选2个数据如此,那么筛选n个数据是否也是那样吗?首先选出首个数据,那么剩下来的数量只可以从那一个数额背后地方上马选取,假设筛选出n-1个数据,那么表示n个数据存在,继续搜索到,直到n-1个数据选不出来截至;接着大家移动率先个数据的岗位,雷同须求在当前多少的后面筛选n-1个数据。就这样类推,要是我们开掘日前数量背后连n-1个数据都还没了,那么表示递归就一病不起了。

 

 

 

    上面我们就足以书写代码了。

copy to clipboardprint?void get_lost_number(int data[], int length) 

 

    a) 定义全局空间和打字与印刷函数,保存已经遍历的数额

    int index; 

 

 

 

    assert(NULL != data && 0 != length); 

static int gAllData[MAX_NUMBER]= {0}; 

    unsigned char* pFlag = (unsigned char*)malloc(length * sizeof(unsigned char)); 

static int gTotal = 0; 

    memset(pFlag, 0, length * sizeof(unsigned char)); 

 

 

void print(int pData[], int length) 

    for(index = 0; index < length; index ++){ 

        if(0 == pFlag[data[index]]) 

    int index; 

            pFlag[data[index]] = 1; 

 

    } 

    for(index = 0; index < length; index++) 

 

        printf("%d", pData[index]); 

    for(index = 0; index < length; index++){ 

 

        if(0 == pFlag[index]) 

    printf("n"); 

            printf("%dn", index); 

    } 

static int gAllData[MAX_NUMBER]= {0};

 

static int gTotal = 0;

    free(pFlag); 

 

    return; 

void print(int pData[], int length)

{

void get_lost_number(int data[], int length)

       int index;

{

 

       int index;

       for(index = 0; index < length; index++)

 

              printf("%d", pData[index]);

       assert(NULL != data && 0 != length);

 

       unsigned char* pFlag = (unsigned char*)malloc(length * sizeof(unsigned char));

       printf("n");

       memset(pFlag, 0, length * sizeof(unsigned char));

}    b卡塔尔起初数据的迭代

 

 

       for(index = 0; index < length; index ++){

 

              if(0 == pFlag[data[index]])

void traverse(int pData[], int length, int number) 

                     pFlag[data[index]] = 1;

       }

    int index; 

 

    if(0 == length) 

       for(index = 0; index < length; index++){

        return; 

              if(0 == pFlag[index])

     

                     printf("%dn", index);

    for(index = 0; index < length; index++){ 

       }

        gAllData[gTotal ++] = pData[index]; 

 

 

       free(pFlag);

        if(1 == number) 

       return;

            print(gAllData, gTotal); 

}    大概朋友也看出了,上边的代码需求分配和原来数据生龙活虎致length的空间。其实大家得以用bit实行会见标识的设定,所以大家提请的上空还足以减掉。

        else 

 

            traverse(pData + (index + 1), length - (index + 1), number -1); 

 

 

copy to clipboardprint?void get_lost_number(int data[], int length) 

        gAllData[-- gTotal] = 0; 

    } 

    int index; 

     

void traverse(int pData[], int length, int number)

    assert(NULL != data && 0 != length); 

{

    unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3); 

       int index;

    memset(pFlag, 0, length * sizeof(unsigned char)); 

       if(0 == length)

     

              return;

    for(index = 0; index < length; index ++){ 

      

        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8)))) 

       for(index = 0; index < length; index++){

            pFlag[data[index] >> 3] |= 1 << (data[index] % 8); 

              gAllData[gTotal ++] = pData[index];

    } 

 

     

              if(1 == number)

    for(index = 0; index < length; index++){ 

                     print(gAllData, gTotal);

        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8)))) 

              else

            printf("%dn", index); 

                     traverse(pData + (index + 1), length - (index + 1), number -1);

    } 

 

     

              gAllData[-- gTotal] = 0;

    free(pFlag); 

       }

    return; 

}    c卡塔 尔(英语:State of Qatar)编写测验用例,验证结果

void test() 

void get_lost_number(int data[], int length)

{

    int data[] = {1, 2, 3, 4, 5, 6}; 

       int index;

    memset(gAllData, 0, sizeof(int) * MAX_NUMBER); 

      

    traverse(data, sizeof(data)/sizeof(int), 4); 

       assert(NULL != data && 0 != length);

       unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);

void test()

       memset(pFlag, 0, length * sizeof(unsigned char));

{

      

       int data[] = {1, 2, 3, 4, 5, 6};

       for(index = 0; index < length; index ++){

       memset(gAllData, 0, sizeof(int) * MAX_NUMBER);

              if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))

       traverse(data, sizeof(data)/sizeof(int), 4);

                     pFlag[data[index] >> 3] |= 1 << (data[index] % 8);

}

       }

   注:我们可以通过不停改正数组data和数值number的方式,验证打印出来的数目和我们和好总计的结果是还是不是有出入。

      

证明:版权全数,招待转发,请勿用于商业用项。 联系信箱:feixiaoxing @163.com】 在数学中,有风度翩翩对数据选择的从头到尾的经过。譬世尊讲,有...

       for(index = 0; index < length; index++){

              if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))

                     printf("%dn", index);

       }

      

       free(pFlag);

       return;

}    上面的代码已经在半空中方面装有减小,那么有如何格局并行运算这几个数据吧?

copy to clipboardprint?void get_lost_number(int data[], int length) 

    int index; 

    RANGE range[4] = {0}; 

     

    assert(NULL != data && 0 != length); 

    unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3); 

    memset(pFlag, 0, length * sizeof(unsigned char)); 

 

    range[0].start = 0,               range[0].end = length >> 2; 

    range[1].start = length >> 2 ,    range[1].end = length >> 1; 

    range[2].start = length >> 1 ,    range[2].end = length >> 2 * 3; 

    range[3].start = length >> 2 * 3, range[3].end = length; 

 

#pragma omp parallel for  

    for(index = 0; index < 4; index ++){ 

        _get_lost_number(data, range[index].start, range[index].end, pFlag); 

    } 

     

    for(index = 0; index < length; index++){ 

        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8)))) 

            printf("%dn", index); 

    } 

     

    free(pFlag); 

    return; 

void get_lost_number(int data[], int length)

{

       int index;

       RANGE range[4] = {0};

      

       assert(NULL != data && 0 != length);

       unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);

       memset(pFlag, 0, length * sizeof(unsigned char));

 

       range[0].start = 0,               range[0].end = length >> 2;

       range[1].start = length >> 2 ,    range[1].end = length >> 1;

       range[2].start = length >> 1 ,    range[2].end = length >> 2 * 3;

       range[3].start = length >> 2 * 3, range[3].end = length;

 

#pragma omp parallel for

       for(index = 0; index < 4; index ++){

              _get_lost_number(data, range[index].start, range[index].end, pFlag);

       }

      

       for(index = 0; index < length; index++){

              if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))

                     printf("%dn", index);

       }

      

       free(pFlag);

       return;

}    为了多核的并行总括,我们增多了子函数_get_lost,大家特别添补完整。

 

 

copy to clipboardprint?typedef struct _RANGE 

    int start; 

    int end; 

}RANGE; 

 

void _get_lost_number(int data[], int start, int end, unsigned char pFlag[]) 

    int index; 

 

    for(index = start; index < end; index++){ 

        if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8)))) 

            pFlag[data[index] >> 3] |= 1 << (data[index] % 8); 

    } 

typedef struct _RANGE

{

       int start;

       int end;

}RANGE;

 

void _get_lost_number(int data[], int start, int end, unsigned char pFlag[])

{

       int index;

 

       for(index = start; index < end; index++){

              if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))

                     pFlag[data[index] >> 3] |= 1 << (data[index] % 8);

       }

}

干活总结:

 

    (1卡塔 尔(英语:State of Qatar)代码的优化是足以持续扩充得,然则不见得适用于具备的景色

 

    (2卡塔 尔(英语:State of Qatar)这两天的cpu已经起来从2核->4核->8核转换,朋友们在或者的状态下尽大概多调控一些多核编制程序的文化。

申明:版权全部,招待转发,请勿用于商业用场。 联系信箱:feixiaoxing @163.com】 假使大家有三个1亿个数据,当中多少的节制是0~1亿,也...

本文由金沙澳门官网送注册58发布于金沙澳门官网,转载请注明出处:一步一步写算法,之数据采取

关键词:

上一篇:多边形游戏
下一篇:敌兵布阵