我有一个包含 100 个元素的数组。数组元素是一组 1 和 0。例如:
Array[100] = {0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,....,1}
我需要找到所有零窗口(间隙)并随机选择其中一个。间隙的大小(所需)根据 1 到 20 之间的均匀分布进行选择。
needed = op_dist_load ("uniform_int", 1, 20);
例如,如果我们假设Array[100]中其余元素等于1,如您所见,我有8个零窗口(窗口大小=2)。我需要找到他们。
find_gap_randomly
函数选择 2 个连续的零元素(具有 2 个零元素的子数组意味着我的程序中存在间隙)。对于在不使用随机库的情况下用 C 语言编写 find_gap_randomly(int need)
函数的代码(最好是用于 OPNET 模拟器),您有什么建议吗?
static void find_gap_randomly(int needed)
{
//The macros “FIN” and “FOUT” are used in OPNET functions to enable the OPNET
//debugging kernel to print out function information.
FIN(find_rr_gap());
/* ... */
FOUT;
}
最佳答案
如果您仍在努力寻找 Array
中的差距 ,(间隙定义为至少 needed
长度的连续零元素的数量),那么找到所有间隙的一个简单、直接的方法是移动一个“滑动- needed
的窗口”沿着数组向下长度检查窗口内的所有值是否为零。如果它们都为零,则说明您找到了间隙,如果没有,则移至Array
中的下一个索引。并重复。
这个概念相当简单,但图片可能会有所帮助(或尝试的图片)
+-------+
| | <= window to slide over array
| |
+---+---+---+---+---+---+---+---+...
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | <= array values
+---+---+---+---+---+---+---+---+...
0 1 2 3 4 5 6 7 8 <= array indexes
| |
+-------+
如上所示,您拥有 Array
的前九个元素。显示,以及下面每个元素的相应索引。自从你的needed
是 2
你有一个跨越 2-elements
的窗口您将从 Array
的开头移动到结尾检查其中的值。这可以简单地通过两个嵌套循环来完成,外循环循环 while i = needed; i < num_elements; i++
然后内循环从 j = i - needed; j < i; j++
迭代。
捕获 Array
中的差距是,您使用第二个数组(我称为 gaps
),其中包含与 Array
相同数量的元素初始化为全零。当您找到Array
内的区域时哪里有needed
连续元素的数量,您只需增加 gaps[j]++;
将值设置为 gaps[j]
来自0
至1
。 (根据 j
的范围,如果 gaps[i-needed]++;
超出范围,您可能需要增加 j
。
当您完成从头到尾移动滑动窗口后,gaps
值为 1
在间隙开始位于 Array
的每个索引处.
实现滑动窗口的简单函数可以这样编写:
/** find_gaps locates each sequence of all zero within 'array' of
* at least 'needed' length, the corresponding index within 'gaps'
* is incremented to identify the start of each gap, returns the
* number of gaps of 'needed' length in 'array'.
*/
int find_gaps (int *gaps, int *arr, int nelem, int needed)
{
int ngaps = 0; /* count of gaps found */
/* add code to validate parameters here */
memset (gaps, 0, nelem * sizeof *gaps); /* zero gaps array */
for (int i = needed; i < nelem; i++) { /* loop needed to end */
for (int j = i - needed; j < i; j++) { /* loop previous needed */
if (arr[j] != 0) /* if non-zero value, get next in array */
goto next; /* lowly 'goto' works fine here */
}
gaps[i-needed]++; /* increment index in gaps */
ngaps++; /* increment no. of gaps found */
next:;
}
return ngaps; /* return no. of gaps found */
}
(注意:内部循环可以替换为 memcmp
以检查所有字节是否设置为零以定位间隙)
查看find_gaps
的操作上面,使用图表作为指导,并确保您准确理解正在发生的事情。如果没有,请告诉我。
将其全部放在一个简短的示例中,该示例采用 needed
作为程序的第一个参数(如果没有给出参数,则默认使用 2
),您可以执行如下操作:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
/** find_gaps locates each sequence of all zero within 'array' of
* at least 'needed' length, the corresponding index within 'gaps'
* is incremented to identify the start of each gap, returns the
* number of gaps of 'needed' length in 'array'.
*/
int find_gaps (int *gaps, int *arr, int nelem, int needed)
{
int ngaps = 0; /* count of gaps found */
/* add code to validate parameters here */
memset (gaps, 0, nelem * sizeof *gaps); /* zero gaps array */
for (int i = needed; i < nelem; i++) { /* loop needed to end */
for (int j = i - needed; j < i; j++) { /* loop previous needed */
if (arr[j] != 0) /* if non-zero value, get next in array */
goto next; /* lowly 'goto' works fine here */
}
gaps[i-needed]++; /* increment index in gaps */
ngaps++; /* increment no. of gaps found */
next:;
}
return ngaps; /* return no. of gaps found */
}
int main (int argc, char **argv) {
int array[] = { 0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,
0,1,1,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1 },
nelem = sizeof array / sizeof *array, /* number of elements */
gaps[nelem], /* a VLA is fine here C99+, otherwise allocate */
ngaps = 0, /* no. of gaps found */
needed = argc > 1 ? strtol (argv[1], NULL, 0) : 2; /* (default: 2) */
if (errno) { /* validate strtol conversion succeeded */
perror ("strtol-argv[1]");
return 1;
}
/* find the number of gaps, storing beginning index in 'gaps' array */
ngaps = find_gaps (gaps, array, nelem, needed);
printf ("gaps found: %d\n", ngaps); /* output number of gaps */
for (int i = 0; ngaps && i < nelem; i++) /* output index of gaps */
if (gaps[i])
printf (" gap at array[%2d]\n", i);
return 0;
}
(注意:您应该添加检查 needed
是否小于 nelem
,但这和任何其他验证都留给您作为练习)
示例使用/输出
$ ./bin/findgaps
gaps found: 11
gap at array[ 0]
gap at array[ 9]
gap at array[10]
gap at array[11]
gap at array[12]
gap at array[18]
gap at array[19]
gap at array[25]
gap at array[26]
gap at array[32]
gap at array[37]
检查至少 3 个零的间隙:
$ ./bin/findgaps 3
gaps found: 5
gap at array[ 9]
gap at array[10]
gap at array[11]
gap at array[18]
gap at array[25]
有多种方法可以解决这个问题,但是滑动窗口可能是最直接的方法之一,并且滑动窗口在 C 中还有许多其他应用程序,因此非常值得将其添加到您的工具箱中。如果您还有其他问题,请告诉我。
关于c - 如何在 C 中随机找到具有一些连续元素的子数组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50981510/