Je saisi un concours de programmation en quelques semaines et aborda les papiers antérieurs. Une question que je suis bloquée est d'appeler une fonction récursive qui calcule tous les entiers binaires possibles avec n chiffres, par exemple les entrées utilisateur 2, imprime le programme 00, 01, 10, 11. Quel est le meilleur moyen de faire face à cela? Comment est-ce fait?
En outre, c'est un concours ACM - y a-t-il d'utiliser des livres pour ces compétitions? Tout ce que je devrais certainement lire? C'est dans un mois! Je suis vraiment nerveux et je ne veux pas laisser mon équipe en bas.
8 Réponses :
une solution en Java:
Ah! N'utilisez jamais math.exp (2, n) pour un entier n . 1 << n est la bonne façon de le faire.
Ma mauvaise pensée paresseuse, corrigée maintenant.
edit J'ai écrit cela ayant lu la question de manière incorrecte - ceci imprime toutes les cordes de longueur n avec k bits. Laissant cela pour les conseils sur les concours.
Il y a une meilleure solution que le En mots, la récurrence se résume à cela - vous pouvez ajouter un peu ou non ajouter un peu. Vous pouvez utiliser la mémoisation pour que ce calcul fonctionne rapidement. Vous devez reproduire les cordes elles-mêmes, cependant, je laisse cela comme un exercice.
Il y a beaucoup de choses que vous pouvez apprendre en lisant des livres (l'introduction aux algorithmes et le manuel design d'algorithme sont de bonnes) pour obtenir les algorithmes «grandes images». Le reste a l'expérience de trouver lorsque ces algorithmes correspondent aux problèmes, quand ils ne le font pas et comment coder une solution ad-hoc quand c'est le cas. J'ai fait quelques-uns quelques-uns d'entre eux, je ne peux pas dire que je suis bon dessus, s'amuser et la bonne chance :) O (2 ^ n) , voici un indice - réfléchissez à la relation récurrence du nombre de cordes de bits de longueur n avec k ceux qui sont. Soit être une fonction qui compte le nombre de ces éléments
s (n, k) = s (n-1, k-1) + s (n-1, k)
Voici un certain code sans limitations réelles (vous pouvez supprimer la récursion, mais cela semblait être une exigence de réponse):
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);
}
}
Ce n'est pas Java mais c'est récursif.
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, "");
Voici une solution java récursive :)
Voici une solution plus générale, qui peut créer des listes non seulement de chiffres binaires, mais de tous les chiffres: -) éditer: lorsque vous utilisez mon (et la majeure partie de celle-ci est la conversion de la valeur iTable en une chaîne). Si nous pouvons vivre avec la sortie séparée par des virgules, nous pouvons utiliser un la sortie serait quelque chose comme Ceci: Son non récursif, mais au moins paresseux (juste à temps) produisant de la éléments.
producteurable , le code devient plus court: produit et le rendre même plus court: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0 , 1], [1, 1, 0], [1, 1, 1]] .
Peut-être que quelque chose comme celui de C ou C ++, la récursivité n'est pas vraiment nécessaire ou plus simple dans ce cas, mais si elle est posée ... L'algorithme est exactement ce que je ferais pour résoudre cela à la main. Allez de droite à gauche de la modification de 1 à 0 et propagez-le jusqu'à ce que vous trouviez un 0 0. Cela comptait à la base 2. En tant qu'exturifier, vous pouvez essayer cela dans la base 3 ou 4, ce n'est pas très différent.
#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);
}
Il y a un livre:
http://www.amazon.com/exec/obidos/isbn = 0387001638 / theinternationsCa /
Un de mes amis a reçu un tel livre (autant de prix pour un concours de programmation junior) et était assez enthousiaste à ce sujet, mais je ne suis pas sûr que ce soit celui-ci (bien que cela ait une bonne note sur Amazonon) .
Le meilleur moyen de préparer est de faire de vieux problèmes de programmation. Vérifiez les ensembles de problèmes passés, il y a toujours des problèmes qui sont toujours là: quelque chose avec un labyrinthe, quelque chose avec une programmation dynamique, etc. Pratiquez ces types de problèmes, vous pouvez donc les résoudre rapidement dans la concurrence réelle.
En outre, ne sous-estimez pas la quantité de planification / organisation qui participe à un concours de programmation. Une bonne interaction entre les membres de l'équipe (par exemple, en choisissant les exercices à résoudre) est vraiment important. Aussi un bon processus pour la manière de corriger les mauvais programmes.
Une autre chose, vous avez dit que vous êtes vraiment nerveux et craignez de laisser votre équipe. Mais rappelez-vous, Aussi, réfléchissez à la façon dont vous allez travailler. Mon préféré personnel est deux codeurs et un non-codeur. De cette façon, il y a toujours quelqu'un à l'aide de l'ordinateur, tandis que l'autre codeur peut discuter des problèmes avec le non-codeur. (par codeur, je veux dire quelqu'un qui aime réellement le code, au lieu d'écrire des algorithmes sur papier)
bonne chance! et plus important encore:
Vous venez d'imprimer les nombres de 0 à 2 ^ n - 1 en binaire ...
Imprimer toutes les bits pour 0 à 2 ^ N (2 alimentation N). C'est la version itérative la plus simple.
Utilisez les anciens exercices de TopCoder.com pour la pratique.