编程竞赛练习

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

EDIT我写这在阅读本incorrectly-的问题是打印出的长度为N的所有字符串具有k比特。留下这个为比赛的建议。

有比O(2^n)一个更好的解决方案，这里有一个提示 - 想想为k的人长度为N位串号的递推关系。令S是计算这些项目

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

中的单词数的函数，复发归结为 - 你可以加一点或不加一点。您可以使用记忆来快速运行此计算。你需要自己重新创建这些字符串，但是我把它作为一个练习。

有很多，你可以通过读书学习（算法导论和算法设计手册是好的），以获得“大画面”的算法。其他人有经验来发现这些算法何时适合这些问题，何时不适用，以及如何在这种情况下编写特别解决方案。我已经做了相当多的这些，不能说我擅长他们虽然有乐趣和好运:)

Answer 3

这里的一些代码，没有真正的限制（你可以删除递归，但它似乎像这是答案的要求）：

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 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

这里是一个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 6

这里是一个更通用的解决方案，它可以:-)

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 7

也许类似于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 8

有一本书：

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

我的一位朋友收到这样一本书（如价格为初级程序设计竞赛），并且是相当enthousiastic这件事，但我不知道是否它是这个（尽管它在亚马逊上的评价很高）。

准备最好的方法是只做旧的编程问题。检查过去的问题集，总会有一些问题总是存在的：有迷宫的东西，有动态编程的东西等。练习这些类型的问题，以便在实际竞争中快速解决问题。

此外，不要低估计划/组织参与编程比赛的数量。团队成员之间的良好互动（例如，挑选要解决的问题）非常重要。对于如何修复错误的程序也是一个很好的过程。

另一件事，你说你真的很紧张，并且害怕让你的团队失望。但是请记住，你是一个团队，。一起练习！如果你以三个人的身份去那里，你肯定会失去......（最好的输球方式：让一个队员声称有一个问题，他不会解决，但他确信他是'几乎那里';因此声称大量的电脑时间，并且什么都不解决......）

另外，想想你将如何工作。我个人最喜欢的是两个编码器和一个非编码器。这样一来，总有一个人使用计算机，而另一个编码人员可以与非编码人员讨论问题。 （通过编码员我是指实际键入代码的人，而不是在纸上写算法）

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