2

次のように宣言された 2 次元配列を考えてみましょう。

#include <stdbool.h>

bool array[N1][N2];

この配列の各行がtrue同じ位置に正確に 1 つの値を持っているかどうかを知る必要があります。

たとえば、次は問題ありません。

{ 
  { 1, 0, 1, 0 },
  { 1, 0, 0, 1 },
  { 0, 0, 1, 1 }
}

これは正しくありません：

{ 
  { 1, 0, 1, 0 },
  { 1, 0, 1, 0 },
  { 0, 0, 1, 1 }
}

私はこれを試しました：

static uintmax_t hash(const bool *t, size_t n) 
{
    uintmax_t retv = 0U;
    for (size_t i = 0; i < n; ++i)
        if (t[i] == true)
            retv |= 1 << i;
    return retv;
}

static int is_valid(bool n) 
{ 
    return n != 0 && (n & (n - 1)) == 0;
}

bool check(bool t[N1][N2])
{
    uintmax_t thash[N1];

    for (size_t i = 0; i < N1; ++i)
        thash[i] = hash(t[i], N2);

    for (size_t i = 0; i < N1; ++i)
        for (size_t j = 0; j < N1; ++j)
            if (i != j && !is_valid(thash[i] & thash[j]))
                return 0;

    return 1;
}

しかし、それはでのみ機能しN1 <= sizeof(uintmax_t) * CHAR_BITます。それを解決するための最良の方法を知っていますか？

4

2 に答える 2

1

ビットを整数にパックしないでください。代わりに、隣接する 2 つの行iを調べi+1て合計!(a[i][j] ^ a[i+1][j])します (2 つの行のビットの XOR の NOT)。各行の合計は正確に 1 でなければなりません。

notbitwise ではなくlogical を使用していることに注意してくださいnot。-1s を取得したくありません (これは 0 以外のビット単位です)。

于 2012-11-01T19:16:12.227 に答える
1

N2 (列数) のサイズの別の配列を作成し、それを all に設定してからtrue、and各行の各列をそれで設定してみませんか。最後に、新しい配列に設定されたビットが 1 つだけあるかどうかを確認します。

bool array[N1][N2];  // this is initialized somehow
bool result[N2];
int i, j;

// initialize result array
for (j = 0; j < N2; ++j)
{
    result[j] = 1;
}

// Now go through the array, computing the result
for (i = 0; i < N1; ++i)
{
    for (j = 0; j < N2; ++j)
    {
        result[j] &= array[i][j];
    }
}

// At this point, you can check the result array.
// If your array is valid, then result should have only one '1' in it.
于 2012-11-01T19:22:45.623 に答える