编程竞赛实践

Question

我将在几周后参加一个编程竞赛，并且一直在处理过去的论文。我遇到的一个问题是调用一个递归函数来计算所有可能的n位二进制整数，例如用户输入2，程序输出00，01，10，11。解决这个问题的最好方法是什么？它是如何做到的？

另外，这是一个ACM竞赛--有没有这些竞赛必须学习的书籍？有什么我一定要读的吗？只有一个月了！我真的很紧张，不想让我的团队失望。

Answer 1

Java中的一个解决方案：

for(int i = 0; i < 1 << n; i++)
  {
  System.out.println(Integer.toBinaryString(i));
  }

Answer 2

下面是一些没有实际限制的代码(您可以删除递归，但这似乎是答案的一个要求)：

public class Bits {
  public static void f(String prefix, int n) {
    if (n == 0) {
      System.out.println(prefix);
      return;
    }
    f(prefix + "0", n - 1);
    f(prefix + "1", n - 1);
  }
  public static void main(String [] argv) {
    f("", 5);
  }
}

Answer 3

也许在C或C++中类似的东西，在这种情况下递归性并不是真正必要的或更简单的，但如果问它...这个算法正是我手动解决这个问题所要做的。从右到左，将1改为0，并传播进位，直到找到0。这是在基数2中计数，作为练习，你可以在基数3或4中尝试，它没有太大区别。

#include <stdio.h>
#include <malloc.h>

void f(char *buffer, int max){
    int i;
    printf("%s, ", buffer);
    for (i = max-1 ; buffer[i] == '1' ; i--){
        buffer[i] = '0';
    }
    if (i < 0) return;
    buffer[i] = '1';
    f(buffer, max);
}

int main(int argc, char ** argv){
    int max = atoi(argv[1]);
    char buffer[32];
    int i;
    for (i = 0; i < max ; i++){
        buffer[i] = '0';
    }
    buffer[max] = 0;
    f(buffer, max);
}

为了准备比赛，回顾过去的论文是一个好主意。但基本上你应该写尽可能多的代码。您还应该训练以实现经典算法(树、排序、图实现和搜索最佳路径、列表、8皇后等)。而你可以寻求帮助。一个月并不是很长的时间，所以你可能应该专注于真正理解一些经典问题。

我还建议习惯于单元测试，这将避免提出不正确的答案，这将在这种竞争中受到惩罚，单元测试和TDD有助于无论如何都专注于问题，避免浪费时间。