Práctica para programar la competencia

Question

Estoy entrando a una competencia de programación en pocas semanas y he estado abordando documentos anteriores. Una pregunta en la que estoy atascado es llamar a una función recursiva que calcula todos los enteros binarios posibles con n dígitos, por ejemplo, las entradas de usuario 2, el programa imprime 00, 01, 10, 11. ¿Cuál es la mejor manera de abordar esto? ¿Cómo se hace?

Además, es una competencia de ACM - ¿hay alguna necesidad de libros de estudio para estos concursos? ¿Algo que definitivamente debería leer? ¡Es en un mes! Estoy realmente nervioso y no quiero decepcionar a mi equipo.

Answer 1

Una solución en Java:

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

Answer 2

EDITAR de escribir este después de haber leído la pregunta incorrectly- esto está imprimiendo todas las cadenas de longitud N con k bits. Dejando esto para el asesoramiento en concursos.

Existe una mejor solución que el O(2^n), aquí hay una sugerencia: piense en la relación de recurrencia del número de cadenas de bits de la longitud N con k unos. Sea S una función que cuenta el número de estos elementos

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

En palabras, la recurrencia se reduce a esto - se puede añadir un poco o no añadir un poco. Puede usar la memorización para hacer que este cálculo se ejecute rápidamente. Sin embargo, necesitas reproducir las cuerdas, lo dejo como ejercicio.

Puede aprender mucho leyendo libros (los manuales de Introducción a Algoritmos y Diseño de Algoritmos son buenos) para obtener los algoritmos de 'gran imagen'. El resto es tener la experiencia para encontrar cuándo esos algoritmos se ajustan a los problemas, cuándo no y cómo codificar una solución ad-hoc cuando este es el caso. He hecho bastantes de estos, no puedo decir que soy bueno con ellos, diviértanse y buena suerte :)

Answer 3

aquí hay un código sin limitaciones reales (puede eliminar la recursión pero parecía que era un requisito de la respuesta):

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

Esto no es java pero es recursivo.

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

Aquí es una solución recursiva 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

Aquí es una solución más general, lo que puede crear listas no sólo de dígitos binarios, pero de ningún dígito :-)

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); 
    } 

} 

---

Editar: al usar mi ProductIterable, el código se hace más corta:

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(); 
    } 
} 

(y la mayor parte es la conversión del Iterable en una cadena). Si podemos vivir con la salida separada por comas, podemos usar un ProductList y que sea aún más corto:

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

La salida sería algo como esto: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]].

No es recursiva, pero al menos floja (justo a tiempo) produce los elementos.

Answer 7

Tal vez algo así en C o C++, la recursividad no es realmente necesaria o más simple en este caso, pero si se pregunta ... El algoritmo es exactamente lo que haría para resolver esto a mano. Ve de derecha a izquierda cambiando de 1 a 0 y propagando el acarreo hasta que encuentres un 0. Eso está contando en la base 2. Como ejercicio puedes intentarlo en la base 3 o 4, no es muy diferente.

#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); 
} 

Para prepararse para la competencia, revisar los documentos anteriores es una buena idea. Pero básicamente debes escribir todo el código que puedas. También debe entrenarse para implementar algoritmos clásicos (árboles, géneros, implementación de gráficos y buscar la mejor ruta, listas, 8 reinas, etc.) mientras puede pedir ayuda. Un mes no es realmente una gran cantidad de tiempo, por lo que probablemente debas centrarte en comprender muy bien algunos problemas clásicos.

También me gustaría acostumbrarme a las pruebas unitarias, esto evitará proponer respuestas incorrectas que se penalizan en dichas pruebas competitio y unitarias y la ayuda de TDD para enfocarse en los problemas de todos modos y evitar perder su tiempo.

Answer 8

hay un libro:

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

Un amigo mío recibió un libro de este tipo (como el precio para un concurso de programación junior), y era bastante entusiasta sobre ello, pero no estoy seguro de si es este (aunque tiene una buena calificación en Amazon).

La mejor manera de prepararse es simplemente hacer viejos problemas de programación. Verifique los conjuntos de problemas anteriores, siempre hay algunos problemas que siempre están ahí: algo con un laberinto, algo con programación dinámica, etc. Practique este tipo de problemas para que pueda resolverlos rápidamente en la competencia real.

Además, no subestime la cantidad de planificación/organización que implica participar en un concurso de programación. Una buena interacción entre los miembros del equipo (por ejemplo, al elegir qué ejercicios resolver) es realmente importante. También es un buen proceso para la reparación de programas incorrectos.

Otra cosa, dijiste que estás muy nervioso y te da miedo decepcionar a tu equipo. Pero recuerda, eres un equipo. Practica juntos! Si vas allí como tres personas, estás seguro de perder ... (la mejor manera de perder: haz que un miembro del equipo reclame un cierto problema, que no va a resolver, pero de lo que está convencido es 'casi allí'; por lo tanto, reclama mucho tiempo de la computadora y no resuelve nada ...)

Además, piense en cómo va a trabajar. Mi favorito personal es dos codificadores y uno no codificador. De esa manera, siempre hay alguien que usa la computadora, mientras que el otro codificador puede discutir los problemas con el que no codifica. (Por codificador me refiero a alguien que realmente escribe el código, en lugar de simplemente escribir algoritmos en papel)

¡Buena suerte! y más importante: ¡Diviértete!