3

ジャグ配列のデカルト積を生成する方法を理解するのに問題があります。私はグーグルで検索しましたが、反復言語の意味を見つけることができないようです。だから私は自分でそれを理解しようとしていますが、私は障害にぶつかりました。問題をもう少し明確に定義しましょう

このような配列の配列があるとしましょう

A = { {1}, {2, 3}, {4, 5, 6} }

どうすればそこから

B = { {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6} }

編集：これは単なる例です。最初の配列には動的な数の配列を含めることができ、各配列は動的なサイズです。

xが外部配列の要素数であり、y []が長さxの動的配列である場合、要素には内部配列の要素数が含まれます。次に、AのxはBのyになり、BのxはAのyの乗法和になります（証明されていない、例から推測）

Aのxは動的であるため、関数は再帰的である必要があります。これが私の試みです。

int** cartesian (int** A, int x, int* y, int* newx, int* newy) {
  *newy = x;
  *newx = 1;
  for (int i = 0; i < x; i++)
    *newx *= y[i];
  int** B = malloc(sizeof(int) * *newx * *newy);

  int xi = 0;
  int* tmp_prod = malloc(sizeof(int) * x);
  recurse(x, 0, y, A, &xi, tmp_prod, B);
  free(tmp_prod);

  return B;
}

void recurse(int x, int xi, int* y, int** A, int* newx, int* temp_inner, int** B) {
  if (xi < x) {
    for (int i = 0; i < y[xi]; i++) {
      temp_inner[xi] = A[xi][i];
      recurse(x, xi + 1, y, A, newx, temp_inner, B);
    }
  } else {
    for (int i = 0; i < x; i++) {
      B[*newx][i] = temp_inner[i];
    }
    (*newx)++;
  }
}

これは私が得た限りです。再帰関数は、[recursionの深さ]の1つの要素の一時配列を構築し、maxdepthになると、そのBを割り当て、Bsイテレーターを増やし、バックトラックして、[recursionの深さ]の次の要素を選択します。 c。

問題はsegfaultsであり、その理由がわかりません。

4

2 に答える 2

1

あなたは反復的な実装を見つけることができないと言い始めたので、あなたの質問に対する一種の答えとして、私はそれを提供します。

セットと同じ数の整数を含む配列から始めます。それらはすべて 0 から始まります。各整数は 1 つのセットを表します。

const unsigned int x = 3;
unsigned int *ar = calloc(x, sizeof(unsigned int));

ここで、配列が走行距離計であるかのように上方向にカウントしますが、対応するセットの要素数に達すると各桁がロールオーバーします。

次に、配列のインデックスを使用してセットから要素を取得することで、要素を読み取ることができます。

{0, 0, 0} = {1, 2, 4}
{0, 0, 1} = {1, 2, 5}
...
{0, 1, 2} = {1, 3, 6}

そして 0, 1, 2 は、配列全体が再びロールオーバーする前の最後のものです。

于 2010-10-24T13:27:00.517 に答える
1

問題は、B を割り当てる方法にあります。int へのnewxポインターの配列として割り当ててから、各要素をnewy int の配列として割り当てる必要があります。

int** B = malloc(sizeof(int*) * *newx);
for (unsigned int i = 0 ; i < *newx; i++) {
   B[i] = malloc(sizeof(int) * *newy);
}

しかし、反復ソリューションを使用するという以前の回答を支持します。

于 2010-10-24T17:59:46.960 に答える