10

次の演習があります。 n0 から n7 までの数値は、バイナリ システムで表されるバイトです。タスクは、すべてのビットを下に落とすか、別のビットに出会った場合はその上にとどまることです。視覚的な例を次に示します。

ここに画像の説明を入力

n0 から n7 までのすべての数値に Bitwise OR を適用すると、常に n7 の正しい結果になることがわかりました。

n7 = n0 | n1 | n2 | n3 | n4 | n5 | n6 | n7;
Console.WriteLine(n7); // n7 = 236

残念ながら、残りのバイト n6、n5、n4、n3、n2、n1、n0 の正しい方法を思いつきません。あなたはなにか考えはありますか？

4

4 に答える 4

11

コレクションを N 回ループしない解決策を考え出したかったのですが、斬新な分割統治法を見つけたと思います。

int n0_, n1_, n2_, n3_, n4_, n5_, n6_, n7_;

// Input data
int n0 = 0;
int n1 = 64;
int n2 = 8;
int n3 = 8;
int n4 = 0;
int n5 = 12;
int n6 = 224;
int n7 = 0;

//Subdivide into four groups of 2 (trivial to solve each pair)
n0_ = n0 & n1;
n1_ = n0 | n1;

n2_ = n2 & n3;
n3_ = n2 | n3;

n4_ = n4 & n5;
n5_ = n4 | n5;

n6_ = n6 & n7;
n7_ = n6 | n7;

//Merge into two groups of 4
n0 = (n0_ & n2_);
n1 = (n0_ & n3_) | (n1_ & n2_);
n2 = (n0_ | n2_) | (n1_ & n3_);
n3 = (n1_ | n3_);

n4 = (n4_ & n6_);
n5 = (n4_ & n7_) | (n5_ & n6_);
n6 = (n4_ | n6_) | (n5_ & n7_);
n7 = (n5_ | n7_);

//Merge into final answer
n0_ = (n0 & n4);
n1_ = (n0 & n5) | (n1 & n4); 
n2_ = (n0 & n6) | (n1 & n5) | (n2 & n4);
n3_ = (n0 & n7) | (n1 & n6) | (n2 & n5) | (n3 & n4);
n4_ = (n0) | (n1 & n7) | (n2 & n6) | (n3 & n5) | (n4);
n5_ = (n1) | (n2 & n7) | (n3 & n6) | (n5);
n6_ = (n2) | (n3 & n7) | (n6);
n7_ = (n3 | n7);

このアプローチで必要なビット演算はわずか 56 回で、提供されている他のソリューションよりも大幅に少なくなります。

最終的な回答でビットが設定されるケースを理解することが重要です。たとえば、n5 の列に 3つ以上のビットが設定されている場合、その列は 1 になります。これらのビットは任意の順序で配置できるため、効率的にカウントすることはかなり困難です。

アイデアは、問題をサブ問題に分割し、サブ問題を解決してから、ソリューションをマージすることです。2 つのブロックをマージするたびに、ビットがそれぞれに正しく「ドロップ」されていることがわかります。これは、各段階で考えられるすべてのビット順列をチェックする必要がないことを意味します。

今まで気がつきませんでしたが、これは、マージ時にソートされたサブ配列を利用する Merge Sort と非常によく似ています。

于 2012-12-05T18:23:33.487 に答える
3

このソリューションでは、ビット単位の演算子のみを使用します。

class Program
{
    static void Main(string[] args)
    {
        int n0, n1, n2, n3, n4, n5, n6, n7;
        int n0_, n1_, n2_, n3_, n4_, n5_, n6_, n7_;

        // Input data
        n0 = 0;
        n1 = 64;
        n2 = 8;
        n3 = 8;
        n4 = 0;
        n5 = 12;
        n6 = 224;
        n7 = 0;

        for (int i = 0; i < 7; i++)
        {
            n0_ = n0 & n1 & n2 & n3 & n4 & n5 & n6 & n7;
            n1_ = (n1 & n2 & n3 & n4 & n5 & n6 & n7) | n0;
            n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
            n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
            n4_ = (n4 & n5 & n6 & n7) | n3;
            n5_ = (n5 & n6 & n7) | n4;
            n6_ = (n6 & n7) | n5;
            n7_ = n7 | n6;

            n0 = n0_;
            n1 = n1_;
            n2 = n2_;
            n3 = n3_;
            n4 = n4_;
            n5 = n5_;
            n6 = n6_;
            n7 = n7_;
        }

        Console.WriteLine("n0: {0}", n0);
        Console.WriteLine("n1: {0}", n1);
        Console.WriteLine("n2: {0}", n2);
        Console.WriteLine("n3: {0}", n3);
        Console.WriteLine("n4: {0}", n4);
        Console.WriteLine("n5: {0}", n5);
        Console.WriteLine("n6: {0}", n6);
        Console.WriteLine("n7: {0}", n7);
    }
}

ただし、すべての数値を再計算する必要がないため、単純化できます。反復ごとに、一番上の行が決定的に優れています。

私はこれを意味します：

class Program
{

    static void Main(string[] args)
    {
        int n0, n1, n2, n3, n4, n5, n6, n7;
        int n0_, n1_, n2_, n3_, n4_, n5_, n6_, n7_;

        n0 = 0;
        n1 = 64;
        n2 = 8;
        n3 = 8;
        n4 = 0;
        n5 = 12;
        n6 = 224;
        n7 = 0;

        n0_ = n0 & n1 & n2 & n3 & n4 & n5 & n6 & n7;
        n1_ = (n1 & n2 & n3 & n4 & n5 & n6 & n7) | n0;
        n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n0 = n0_;
        n1 = n1_;
        n2 = n2_;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n0: {0}", n0);
        n1_ = (n1 & n2 & n3 & n4 & n5 & n6 & n7) | n0;
        n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n1 = n1_;
        n2 = n2_;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n1: {0}", n1);
        n2_ = (n2 & n3 & n4 & n5 & n6 & n7) | n1;
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n2 = n2_;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n2: {0}", n2);
        n3_ = (n3 & n4 & n5 & n6 & n7) | n2;
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n3 = n3_;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n3: {0}", n3);
        n4_ = (n4 & n5 & n6 & n7) | n3;
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n4 = n4_;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n4: {0}", n4);
        n5_ = (n5 & n6 & n7) | n4;
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n5 = n5_;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n5: {0}", n5);
        n6_ = (n6 & n7) | n5;
        n7_ = n7 | n6;
        n6 = n6_;
        n7 = n7_;
        Console.WriteLine("n6: {0}", n6);
        n7_ = n7 | n6;
        n7 = n7_;
        Console.WriteLine("n7: {0}", n7);
    }
}
于 2012-11-29T17:30:31.890 に答える
2

各列の 1 ビットの数を数えます。次に、列をクリアし、下から正しい数の「トークン」を追加します。

于 2012-11-29T15:05:41.150 に答える
1

CodesInChaosの提案に基づく：

static class ExtensionMethods {
    public static string AsBits(this int b) {
        return Convert.ToString(b, 2).PadLeft(8, '0');
    }
}

class Program {
    static void Main() {
        var intArray = new[] {0, 64, 8, 8, 0, 12, 224, 0 };
        var intArray2 = (int[])intArray.Clone();
        DropDownBits(intArray2);

        for (var i = 0; i < intArray.Length; i++)
            Console.WriteLine("{0} => {1}", intArray[i].AsBits(),
                intArray2[i].AsBits());
    }

    static void DropDownBits(int[] intArray) {
        var changed = true;

        while (changed) {
            changed = false;
            for (var i = intArray.Length - 1; i > 0; i--) {
                var orgValue = intArray[i];
                intArray[i] = (intArray[i] | intArray[i - 1]);
                intArray[i - 1] = (orgValue & intArray[i - 1]);
                if (intArray[i] != orgValue) changed = true;
            }
        }
    }
}

使い方

シンプルに保ち、次の3つのニブルから始めましょう。

0) 1010
1) 0101
2) 0110

一番下の行から始めます（i = 2）。ビット単位で適用するか、上の行（i-1）を使用して、行2の0であるすべてのビットが行1の1の場合、1になるようにします。したがって、行1の1ビットを使用します。行2にフォールダウンします。

1) 0101
2) 0110

行2には「余地」（a）があるため、行1の右ビットが落ちる可能性があります0。したがって、行2は行2または行1になります。0110 | 0101これは0111です。

次に、行1から落ちたビットを削除する必要があります。そのため、行2と1の元の値に対して、ビット単位で実行します。したがって、に0110 & 0101なり0100ます。行2の値が変更されたため、はにchangedなりtrueます。これまでの結果は以下のとおりです。

1) 0100
2) 0111

iこれで、 = 2の内部ループが終了します。次にi1になります。次に、行0のビットを行1にフォールダウンさせます。

0) 1010
1) 0100

行1は、行1または行0の結果になります。0100 | 1010これは1110です。行0は、ビット単位の結果になり、これら2つの値で次のようになり0100 & 1010ます0000。また、現在の行が変更されました。

0) 0000
1) 1110
2) 0111

ご覧のとおり、まだ完成していません。それがwhile (changed)ループの目的です。2行目からやり直します。

行2= 0111 | 1110 = 1111、行1= 0111 & 1110 = 0110。行が変更されたので、も変更されましchangedたtrue。

0) 0000
1) 0110
2) 1111

次にi1になります。行1= 0110 | 0000 = 0110、行0= 0110 & 0000 = 0000。行1は変更されていませんが、の値はchangedすでに変更されており、そのままですtrue。

ループのこのラウンドでも、while (changed)何かが変更されたので、もう一度内側のループを実行します。

今回は、どの行も変更されないため、changedループfalseが終了しwhile (changed)ます。

于 2012-11-29T15:35:51.627 に答える