6

我想知道如何打印 n 个 1 和 0 的组合。组合的数量n是用户定义的。预期的输出是；

n=1；

0,1

n=2；

00,01,10,11

n=3；

000,001,010,011,100,101,110,111

等等……等等……

输出将具有2^n多种组合（其中 n 是单个组合中的预期位数）。

如何在不使用任何内置函数的情况下做到这一点？这个问题与语言无关，是针对算法的。

4

4 回答 4

13

您可以枚举所有数字，直到2^n - 1二进制。这将使您获得相同的组合。

n = 2枚举直到2^3 - 1=7 转换为二进制：

000 --> 0
001 --> 1
010 --> 2
011 --> 3
100 --> 4
101 --> 5
110 --> 6
111 --> 7

编辑：也修复了位数。这有效

#include <stdio.h>
#define LENGTH 3
void print_binary(int n)
{
        int bit = 1<<LENGTH - 1;
        while ( bit ) {
        printf("%d", n & bit ? 1 : 0);
        bit >>= 1;
        }
        printf("\n");
}
int main(){
    int n = 1<<LENGTH, i; 
    for(i=0;i<n;i++)
        print_binary(i);
}
于 2013-01-31T18:24:56.860 回答
3

如果你不关心速度和内存，你冷使用递归，这会导致一个小而短的解决方案：

public static void print01PermutationsUpToLength(final String currentString, final int upTo) {
    if (upTo == 0) {
        System.out.println(currentString);
        return;
    }
    print01PermutationsUpToLength(currentString + "0", upTo - 1);
    print01PermutationsUpToLength(currentString + "1", upTo - 1);
}

（java。显然，这可以在允许递归和按值调用或字符串副本的每种语言中完成）

如果你不喜欢这个String参数，你可以添加一个 start 函数：

public static void print01PermutationsUpToLength(final int upTo) {
    print01PermutationsUpToLength("", upTo);
}

结果：

final int upToLength = 3;
print01PermutationsUpToLength(upToLength);
000
001
010
011
100
101
110
111

可以根据需要更改格式，这只是为了更好地查看结果。如果您切换字符串构造 ( )
的部分，则可以更改顺序。currentString + "0"

于 2013-01-31T21:29:58.313 回答
2 
void print_digit(int n,int digits)
{
   int i;
   for(i=0;i<digits;i++)
   { 
       if(n&(1<<(digits-i-1)))
       {
           putchar('1');
       }
       else
       {
           putchar('0');
       }
   }
}

print all_digits(int e)
{
   for(i=0;i<(1<<e);i++)
   {
        print_digit(i,e);
        putchar('\n');
   }
   fflush(stdout);
}
于 2013-01-31T18:42:44.267 回答
0

这是我对这个问题的看法。给定一个字符数组，并且您想使用整个数组找到它的 k 个组合。为了解决这个问题，我们的数组包含：['0','1']。

假设我们有一个char set[] = new {'0','1'};

以下方法将为您提供任意数量的零和一组合。我已经用 0 和 1 的组合以及 50 个字符的数据集对其进行了测试。

public  void printLengthRec(char[] inputSet, String prefix, int k) {
    int sizeOfInputArray=inputSet.length;
    //TerminationCase: k is 0, print prefix
    if (k == 0) {
        System.out.println(prefix);
        return;
    }    
    // One by one add all characters from set and recursively 
    // call for k equals to k-1
    for (int i = 0; i < 2; ++i) {
        // Next character of input added
        String newPrefix = prefix + set[i]; 
        printLengthRec(inputSet, newPrefix, k - 1); 
    }
}
于 2016-04-09T15:50:44.773 回答