编程竞赛练习

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 无论如何都有助于专注于问题并避免浪费时间。

Answer 4

这不是java，但它是递归的。

function getBinaryDigitForPosition(currentLevel, currentNumberAsString) {

  // if this were anything but binary I'd put these into an array and iterate thru
  firstNumber = currentNumberAsString + "0";
  secondNumber = currentNumberAsString + "1";

  if (currentLevel == 1) {
    print firstNumber + ", " + secondNumber;
  } else {
    // same iteration here as I mentioned above
    getBinaryDigitForPosition(currentLevel - 1, firstNumber);
    getBinaryDigitForPosition(currentLevel - 1, secondNumber);
  }

}

// calling the function initially:
// make sure that userInputNumberOfDigits is >= 1

getBinaryDigitForPosition(userInputNumberOfDigits, "");

Answer 5

编辑 我在错误地阅读问题后写了这篇文章 - 这是打印出长度为 N 的所有字符串，其中包含 k 位。将此留给有关比赛的建议。

有一个比 O(2^n) 更好的解决方案，这里有一个提示 - 考虑长度为 N 的位串数量与 k 个的递推关系。设 S 是一个计算这些项目数量的函数

S(N,k) = S(N-1,k-1) + S(N-1,k)

换句话说，递归式归结起来就是——你可以加一点，也可以不加一点。您可以使用记忆功能使计算快速运行。不过，您需要重现字符串本身，我将其作为练习。

通过阅读书籍（《算法导论》和《算法设计》手册都是不错的），您可以学到很多东西，以获得“大局”算法。剩下的就是拥有经验来发现这些算法何时适合问题，何时不适合，以及在这种情况下如何编写临时解决方案。我已经做了很多这样的事情，但不能说我很擅长，祝你玩得开心，祝你好运:)

Answer 6

这是一个java递归解决方案:)

 public class BinaryIntegers {

    public static void main(String[] args) {
        int numberOfBits = 10; // For instance.
        printBinaryNumbers(numberOfBits);
    }

    private static void printBinaryNumbers(int numberOfBits) {
        recursivePrint("", numberOfBits);
    }

    private static void recursivePrint(String current, int numberOfBitsLeft){
        if(numberOfBitsLeft==0)
            System.out.println(current);
        else{
            recursivePrint(current + "0", numberOfBitsLeft-1);
            recursivePrint(current + "1", numberOfBitsLeft-1);
        }
    }
}

Answer 7

这是一个更通用的解决方案，它不仅可以创建二进制数字的列表，还可以创建任何数字的列表:-)

package de.fencing_game.paul.examples;

import java.util.Arrays;


public class AllNaryNumbers {


    private static void printAll(String prefix, Iterable<String> digits,
                                int length)
    {
        if(length == 0) {
            System.out.println(prefix);
            return;
        }
        for(String digit : digits) {
            printAll(prefix + digit, digits, length-1);
        }
    }

    private static void printNumbers(int length, Iterable<String> digits) {
        printAll("", digits, length);
    }

    private static void printBinary(int length) {
        printNumbers(length, Arrays.asList("0", "1"));
    }

    public static void main(String[] params) {
        if(params.length == 0) {
            printBinary(5);
            return;
        }
        int len = Integer.parseInt(params[0]);
        if(params.length == 1) {
            printBinary(len);
            return;
        }
        Iterable<String> digits =
            Arrays.asList(params).subList(1, params.length);
        printNumbers(len, digits);
    }

}

---

编辑：当使用我的 ProductIterable，代码变得更短：（

private static void printNumbers(int length, Iterable<String> digits)
{
    for(List<String> number :
            new ProductIterable<String>
            (Collections.nCopies(length, digits))) {
        for(String digit : number) {
            System.out.print(digit);
        }
        System.out.println();
    }
}

其中大部分是将 Iterable 转换为字符串）。如果我们可以接受逗号分隔的输出，我们可以使用 ProductList 并使其更短：

private static void printNumbers(int length, List<String> digits)
{
    System.out.println(new ProductList<String>
                       (Collections.nCopies(length, digits)));
}

输出将如下所示：[[0, 0, 0], [ 0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]。

它不是递归的，但至少是惰性（及时）生成元素的。

Answer 8

有一本书：

http://www.amazon.com/exec/obidos /ISBN=0387001638/theinternationscA/

我的一个朋友收到了这样一本书（作为初级编程竞赛的价格），并且对它非常热情，但我不确定是否是这本书（虽然它在亚马逊上确实有很好的评价）。

最好的准备方法就是做旧的编程问题。检查过去的习题集，总有一些问题是一直存在的：有迷宫的问题、有动态规划的问题等等。练习这些类型的问题，这样你就可以在真正的比赛中快速解决它们。

另外，不要低估参加编程竞赛所需的计划/组织量。团队成员之间的良好互动（例如，选择要解决的练习）非常重要。这也是修复错误程序的一个很好的过程。

还有一件事，你说你真的很紧张，害怕让你的团队失望。但请记住，你们是一个团队。一起练习！！如果你们三个人一起去那里，你们肯定会输……（输的最佳方式：让一名团队成员提出某个问题，他不会解决这个问题，但是他确信自己“快到了”；因此占用了大量的计算机时间，但什么也没解决……）

此外，考虑一下你将如何工作。我个人最喜欢的是两名编码员和一名非编码员。这样，总会有人使用计算机，而另一个编码员可以与非编码员讨论问题。 （我所说的编码员是指实际输入代码的人，而不是仅仅在纸上编写算法的人）

祝你好运！更重要的是：玩得开心！