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

作者：金沙澳门官网发布：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发布于金沙澳门官网,转载请注明出处：一步一步写算法，之数据采取

关键词：