3

次の (概念的には非常に単純な) 問題に遭遇し、そのためのコードを書きたいのですが、苦労しています。同じ長さ k の 2 つの行があるとします。各行の各セルは、0 または 1 のいずれかになります。

たとえば、k = 5 の次の行ペアを考えてみましょう: 01011, 00110

ここで、2 つの行が各セルで自由に値を交換できる場合、2^5 通りの行ペアの組み合わせが考えられます (そのうちのいくつかは一意ではない可能性があります)。たとえば、上記のデータから 00010、01111 を 1 つの可能な行ペアとして持つことができます。Delphi でコードを記述して、考えられるすべての行ペアを一覧表示したいと考えています。これは、一連の入れ子になった for ループを使用すると簡単に実行できます。ただし、k の値が実行時にしかわからない場合、必要なインデックス変数の数がわからないため、このアプローチをどのように使用できるかわかりません。k の値がわからないので、case ステートメントがどのように役立つかわかりません。

ネストされた for ループに代わるものがあることを願っていますが、ご意見をいただければ幸いです。ありがとう。

4

2 に答える 2

4

長さkの2 つのベクトルAとBが与えられた場合、 AまたはBから要素を選択して選択することにより、ベクトルA1とB1の新しいペアを生成できます。AまたはBから選択するという決定は、同じく長さkのビット ベクトルSによって決定されます。[0.. k ) のiについて、 S iが 0 の場合、 A iをA1 iに、B iをB1 iに格納します。S i の場合は 1 で、その逆です。

Delphi では、次のような関数で定義できます。

procedure GeneratePair(const A, B: string; S: Cardinal; out A1, B1: string);
var
  k: Cardinal;
  i: Cardinal;
begin
  Assert(Length(A) = Length(B));
  k := Length(A);
  Assert(k <= 32);

  SetLength(A1, k);
  SetLength(B1, k);
  for i := 1 to k do
    if (S and (1 shl Pred(i))) = 0 then begin
      A1[i] := A[i];
      B1[i] := B[i];
    end else begin
      A1[i] := B[i];
      B1[i] := A[i];
    end;
end;

バイナリで 0 から 2 k −1 まで数えると、 AとBの間で文字を交換するか交換しないかのすべての可能な組み合わせを表す一連のビット ベクトルが得られます。

ループを記述し、上記の関数を使用して 2 k 個の組み合わせをすべて生成できます。

A := '01011';
B := '00110';
for S := 0 to Pred(Round(IntPower(2, Length(A)))) do begin
  GeneratePair(A, B, S, A1, B1);
  writeln(A1, ', ', B1);
end;

これは、ネストされたループの 1 つのセットを効果的に使用します。外側のループは 0 から 31 までのループです。内側のループは 1 から までの関数内のループですk。ご覧のとおり、事前にkの値を知る必要はありません。

于 2013-09-06T19:29:02.593 に答える