1

物品税は次のとおりです。

あなたは空の部屋と外で待っているn人のグループから始めます。各ステップで、1人を部屋に入れるか、1人を外に出すことができます。2 nステップのシーケンスを配置して、考えられるすべての人の組み合わせが1回だけ達成されるようにすることはできますか？

私の解決策は次のとおりです。

n個の要素を持つビット配列を持つことができます。各要素のステータスは、この人が部屋にいるかどうかを表します。つまり、部屋には2n種類の人の組み合わせがあります。

アルゴリズムは、すべての組み合わせをリストするための標準的なバックトラックにすることができます。

私の考えがあまりにも素朴なのか単純なのか疑問に思っていますか？

この物品税に罠はありますか？

編集：

の実装に興味のある方はgray code、をご覧ください。

http://yagni.com/graycode/

4

4 に答える 4

12

アルゴリズムは、すべての組み合わせをリストするための標準的なバックトラックにすることができます。

ソリューションは「機能」しますが、単純に実装すると、2nステップ以上が必要になります。

問題ステートメントの次の文を参照してください。

各ステップで、1人を部屋に入れるか、1人を外に出すことができます。

0111あなたの解決策では、すべてのビットベクトルをリストすると、おそらくその後に続くでしょう1000。つまり、3人が部屋を出て、1人が入る必要があります。

これには1つではなく、4つのステップが必要です。したがって、すべての組み合わせを実行するには、2nを超えるステップが必要になります。

ただし、2つの連続するベクトル間で1ビットのみが異なるように、記述したビットベクトルを配置することができます。これはグレイコードと呼ばれるものです。

ウィキペディアの記事の例を次に示します。

Dec  Gray   Binary
 0   000    000
 1   001    001
 2   011    010
 3   010    011
 4   110    100
 5   111    101
 6   101    110
 7   100    111

どのように注意してください

  1. すべてのビットベクトルがカバーされ、
  2. 連続するベクトルごとに、1ビットだけが変化します。

これは、すべての組み合わせを正確に2nステップで繰り返すことができることを意味します。

このようなシーケンスジェネレーターの実装方法はウィキペディアのページでも説明されていますが、演習の場合は、覗く前に自分で試してみることをお勧めします;）

于 2012-05-12T10:46:01.240 に答える
3

グレイコードシーケンスジェネレーターを探しています。グレイコードシーケンスの隣接する値は、1ビットだけ異なります。

于 2012-05-12T10:42:07.540 に答える
1

グレイコードシーケンス生成の作業コードは次のとおりです

// Binary Reflected Gray Code
void brgc( int *a, int n, int idx, int reflect )
{
    if ( n == idx ) {
        printIntArr( a, n );
    } else {
        a[ idx ] = reflect;
        brgc( a, n, idx + 1, 0 );
        a[ idx ] = !reflect;
        brgc( a, n, idx + 1, 1 );
    }
}

int main( int argc, char *argv[] )
{
    if ( argc != 2 ) {
        printf( "Usage...\n" );
        return -1;
    }
    int n = atoi( argv[ 1 ] );
    int *a = malloc( sizeof( int ) * n );
    brgc( a, n, 0, 0 );
}
于 2015-02-25T02:20:59.440 に答える
0 
/ package whatever; // don't place package name! /

import java.util.*;
import java.lang.*;
import java.io.*;

/ Name of the class has to be "Main" only if the class is public. /
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int numberofPeople=3;
        int size = 1<<numberofPeople;
        for(int i=0;i<size;i++)
        {
            int num = i^(i>>1);
            System.out.println(Integer.toBinaryString(num));
        }
    }
}
于 2015-11-26T07:32:32.560 に答える