在 n 个二维数组中搜索

Question

你好 我需要在 n 个二维数组上实现以下逻辑。这里我考虑了 3 个一维数组

#include<stdio.h>
main()
{
    int a[4]={2,1,4,7},b[4]={3,-3,-8,0},c[4]={-1,-4,-7,6},sum,i,j,k,val=0;
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++) {
            for(k=0;k<4;k++) {
                sum = a[i]+b[j]+c[k];
                if(sum == val)
                printf("%d  %d  %d\n", a[i], b[j], c[k]);
            }
        }
    }

}

输出： 2 -8 6 ; 1 3 -4 ; 1 0 -1 <强>; 4 3 -7 ; 4 -3 -1 <强>; 4 0 -4 <强>; 7 -3 -4 <强>; 7 0 -7 <强>;

Answer 1

有关语法信息，请参阅维基百科中的 C 语法。

实际上，您需要使用 int array[3][4] = ... 创建一个 3 行 4 列的数组。稍后在代码中，将对当前 a、b 和 c 数组的访问替换为每种情况的固定行索引。

其余的实现留作练习，因为这对我来说听起来像是家庭作业。

Answer 2

好问题:-)
我不会发布完整的解决方案，因为问题似乎是家庭作业。只是一些提示......

我用递归解决了它：我使用的简化过程是在n数组中查找target的总和与查找a相同n-1 数组中 target - ONE_ELEMENT 的总和。

使用 3 个数组和目标为零的示例

find 3 elements with sum 0           in {2, 1, 4, 7}, {3, -3, -8, 0}, {-1, -4, -7, 6}
find 2 elements with sum 0 - 2 (-2)  in {3, -3, -8, 0}, {-1, -4, -7, 6}
find 1 elements with sum -2 - 3 (-5) in {-1, -4, -7, 6}              NOT FOUND
find 1 elements with sum -2 - -3 (1) in {-1, -4, -7, 6}              NOT FOUND
find 1 elements with sum -2 - -8 (6) in {-1, -4, -7, 6}              YAY! FOUND
...

---

为了使其轻松工作，我创建了一个数据数组的结构，并提出一种在递归函数的多次调用之间传递信息的方法（我使用了在辅助递归设置函数中分配的另一个数组）。

编辑了数组的结构

struct sizedarray {
  int *data;
  size_t nelems;
};

以及递归和辅助函数的原型

findtarget(int target, struct sizedarray *arrays, size_t narrays);
findtarget_recursive(int target, struct sizedarray *arrays, size_t narrays, size_t level, int *saved);

---

以添加工作解决方案

#include <stdio.h>
#include <stdlib.h>

/* struct to hold arrays with varying sizes */
struct sizedarray {
  int *data;
  size_t nelems;
};

void findtarget_recursive(int target,
                         struct sizedarray *arrays,
                         size_t narrays,
                         size_t level,
                         int *saved) {
  size_t k, j;
  struct sizedarray *curarray = arrays + level;

  /* if no arrays left to search return */
  if (level == narrays) {
    return;
  }
  /* if only 1 arrays do not recurse */
  if (level + 1 == narrays) {
    for (k = 0; k < curarray->nelems; k++) {
      if (curarray->data[k] == target) {
        /* print saved elements from previous arrays */
        for (j = 0; j < level; j++) {
          printf("%d ", saved[j]);
        }
        /* print current element from current array */
        printf("%d\n", curarray->data[k]);
      }
    }
    return;
  } else {
    /* when 2 or more arrays left, recurse */
    for (k = 0; k < curarray->nelems; k++) {
      saved[level] = curarray->data[k];
      findtarget_recursive(target - curarray->data[k],
                           arrays,
                           narrays,
                           level + 1,
                           saved);
    }
  }
}

int findtarget(int target, struct sizedarray *arrays, size_t narrays) {
  int *saved = NULL;
  saved = malloc(narrays * sizeof *saved);
  /* assume it worked, needs something when it fails */
  if (saved) {
    findtarget_recursive(target, arrays, narrays, 0, saved);
    free(saved);
  }
  return 0;
}

int main(void) {
  int a0[] = {2, 1, 4, 7};
  int a1[] = {3, -3, -8, 0};
  int a2[] = {-1, -4, -7, 6};
  int a3[] = {1, 5, 6, 7};
  int a4[] = {-10, -4, -1, 3, 8};
  int a5[] = {17, 18, 19, 20, 21, 22, 23, 24, 25};
  struct sizedarray arrays[6];
  int target = 0;

  arrays[0].data = a0; arrays[0].nelems = sizeof a0/sizeof *a0;
  arrays[1].data = a1; arrays[1].nelems = sizeof a1/sizeof *a1;
  arrays[2].data = a2; arrays[2].nelems = sizeof a2/sizeof *a2;

  findtarget(target, arrays, 3);

  arrays[3].data = a3; arrays[3].nelems = sizeof a3/sizeof *a3;
  arrays[4].data = a4; arrays[4].nelems = sizeof a4/sizeof *a4;
  arrays[5].data = a5; arrays[5].nelems = sizeof a5/sizeof *a5;

  puts("\n\nwith 6 arrays ...");
  findtarget(target, arrays, 6);

  return 0;
}