編程競賽練習

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這件事，但我不知道是否它是這個（儘管它在亞馬遜上的評價很高）。

準備最好的方法是隻做舊的編程問題。檢查過去的問題集，總會有一些問題總是存在的：有迷宮的東西，有動態編程的東西等。練習這些類型的問題，以便在實際競爭中快速解決問題。

此外，不要低估計劃/組織參與編程比賽的數量。團隊成員之間的良好互動（例如，挑選要解決的問題）非常重要。對於如何修復錯誤的程序也是一個很好的過程。

另一件事，你說你真的很緊張，並且害怕讓你的團隊失望。但是請記住，你是一個團隊，。一起練習！如果你以三個人的身份去那裏，你肯定會失去......（最好的輸球方式：讓一個隊員聲稱有一個問題，他不會解決，但他確信他是'幾乎那裏';因此聲稱大量的電腦時間，並且什麼都不解決......）

另外，想想你將如何工作。我個人最喜歡的是兩個編碼器和一個非編碼器。這樣一來，總有一個人使用計算機，而另一個編碼人員可以與非編碼人員討論問題。 （通過編碼員我是指實際鍵入代碼的人，而不是在紙上寫算法）

祝你好運！更重要的是：玩得開心！