1

这是消费税：

你从一个空房间开始，一群 n 人在外面等着。在每一步，您可以允许一个人进入房间，也可以让一个人出去。你能安排一个 2 n步的序列，使得每个可能的人组合都只实现一次吗？

我的解决方案是：

我可以有一个包含n 个元素的位数组。每个元素的状态代表此人是否在房间内。因此，我们总共将在房间里有 2 n 个不同的人组合。

该算法可以是列出所有组合的标准回溯。

我只是想知道我的想法是太天真还是太简单了？

这个消费税有什么陷阱吗？

编辑：

对于有兴趣实施的人gray code，请参阅

http://yagni.com/graycode/

4

4 回答 4

12

该算法可以是列出所有组合的标准回溯。

您的解决方案“有效”，但如果实施得天真，它将需要超过 2 n 个步骤。

请参阅问题陈述中的以下句子：

在每一步，您可以允许一个人进入房间，也可以让一个人出去。

在您的解决方案中，当您列出所有位向量时，您可能会0111遵循1000这意味着三个人必须离开房间，一个人必须进入。

这需要 4 个步骤，而不是一个，因此您将获得超过 2 n 个步骤来运行所有组合。

但是，您可以排列您描述的位向量，使得两个连续向量之间只有一位不同。这就是所谓的格雷码。

这是维基百科文章中的一个示例：

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. 对于每个连续的向量，只有一位变化。

这意味着您将能够以精确的 2 n步迭代所有组合。

如何实现这样的序列生成器在 Wikipedia 页面中也有说明，但如果是练习，我建议你在偷看之前自己尝试一下；）

于 2012-05-12T10:46:01.240 回答
3

您正在寻找格雷码序列生成器。格雷码序列中的相邻值仅相差一位。

于 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 回答