Le défi
Ecrire un programme ou une fonction qui prend deux entiers d'entrée, i
et j
, et produit leur plus grand commun diviseur; calculé en utilisant l' algorithme euclidien (voir ci-dessous).
Contribution
L'entrée peut être considérée comme une représentation sous forme de chaîne délimitée par des espaces i
et j
ou comme deux entiers distincts. Vous pouvez supposer que les nombres entiers seront inférieurs ou égaux à 10 000. Vous pouvez également supposer que les entiers en entrée ne seront pas premiers entre eux.
Répartition euclidienne
Le plus grand nombre entre i
et j
est divisé par le plus petit nombre de fois possible. Ensuite, le reste est ajouté. Ce processus est répété avec le reste et le numéro précédent, jusqu'à ce que le reste devienne 0
.
Par exemple, si l'entrée était 1599 650
:
1599 = (650 * 2) + 299
650 = (299 * 2) + 52
299 = (52 * 5) + 39
52 = (39 * 1) + 13
39 = (13 * 3) + 0
Le nombre final,, 13
est le plus grand commun diviseur des deux entiers d'entrée. Il peut être visualisé comme ceci:
Sortie
Votre sortie doit être la ventilation dans le formulaire ci-dessus, suivie d'une nouvelle ligne et du GCD. Il peut être sorti sur n'importe quel support.
Exemples
Contributions
18 27
50 20
447 501
9894 2628
Les sorties
27 = (18 * 1) + 9
18 = (9 * 2) + 0
9
50 = (20 * 2) + 10
20 = (10 * 2) + 0
10
501 = (447 * 1) + 54
447 = (54 * 8) + 15
54 = (15 * 3) + 9
15 = (9 * 1) + 6
9 = (6 * 1) + 3
6 = (3 * 2) + 0
3
9894 = (2628 * 3) + 2010
2628 = (2010 * 1) + 618
2010 = (618 * 3) + 156
618 = (156 * 3) + 150
156 = (150 * 1) + 6
150 = (6 * 25) + 0
6
Remarque: Les sorties ne doivent pas être espacées comme elles le sont ci-dessus. L'espacement est uniquement à des fins de clarté. Des parenthèses sont requises.
Prime
Si votre sortie est espacée comme ci-dessus, vous pouvez ajouter un bonus de -10% à votre score.
Réponses:
Pyth, 33 octets
Essayez-le en ligne: démonstration ou suite de tests
Explication:
la source
CJam,
464339 octetsEssayez-le en ligne dans l' interpréteur CJam .
Comment ça marche
la source
Python 2, 70
Une fonction récursive qui renvoie une chaîne multiligne. La fonction crée la première ligne, puis l'ajoute au résultat récursif avec la paire de nombres suivante dans l'algorithme euclidien. Une fois que le deuxième nombre est zéro, nous prenons la chaîne de l'autre nombre comme cas de base, ce qui entraîne son impression sur sa propre ligne à la fin.
Le formatage est effectué via la substitution de chaîne, en utilisant la division entière pour obtenir le multiplicande.
Un hoquet doit commencer par prendre le plus grand nombre et le plus petit. Commodément, si les nombres sont dans le mauvais ordre, la première étape de l'algorithme euclidien les retourne. Pour empêcher cette étape de s'afficher, n'ajoutez la ligne actuelle que si le premier nombre est au moins le second (l'égalité est nécessaire pour, disons
f(9,9)
).la source
awk,
7877Le tri de l'entrée par taille prend beaucoup d'octets: /
Cela se résume à ceci:
Sortie
Juste pour le plaisir, j'ai également fait une version correctement espacée, me donnant un score de 233 * 0,9 == 209,7 octets.
Mise à jour J'ai pu raccourcir cela de 285 octets et maintenant cela fonctionne pour des nombres arbitrairement longs si j'appelle gawk4 avec l'
-M
option.Mais j'ai toujours le sentiment d'avoir rencontré un blocage mental quelque part ...
Sortie (gawk4 appelé avec
awk -M -f code.awk
)Ajout de nouvelles lignes et d'onglets
Je peux enregistrer les longueurs des valeurs initiales pour x, y et x% y au début, car elles ne peuvent que raccourcir à chaque étape. Mais pour le facteur, je dois déterminer la longueur maximale avant d'imprimer quoi que ce soit, car sa longueur peut varier. J'utilise
$i
ici un tableau, car il enregistre deux caractères par rapport à l'utilisation d'un [i] à chaque fois.la source
C ++, compilateur GCC, 171 octets (-10%, donc 154 octets)
ok donc mon premier essai ..
conseils pour coder le golf appréciés.
PS Est-il nécessaire de compter les octets des fichiers d'en-tête standard et int main lors de l'utilisation de c ++? L'exclusion réduit de 50 octets
la source
T-SQL (2012+), 268 octets
Implémenté comme une fonction de table en ligne qui exécute un CTE récursif. Cela pourrait valoir la peine d'essayer de mettre en forme le bonus de 10%, mais cela devra attendre.
Explication et utilisation:
la source
Rév 1: Ruby, 86
Algorithme récursif, grâce au conseil de Doorknob.
Rév 0: Ruby, 93
Cela n'a vraiment pas bien fonctionné du tout. La
while
boucle prend trop de caractères, en particulier avec leend
. Je ne vois pas comment l'éviter. La récursivité nécessiterait une fonction nommée au lieu d'un lambda, qui consommerait également beaucoup de caractères.Appelez ça comme ceci:
la source
a=->i,j{...}
et appelera
viaa[1,2]
- mais vous ne savez pas si cela vous sauverait des caractères.f.call
.) Elle est en fait un peu plus courte, mais toujours loin de Python.PowerShell, 84
Un bloc de code récursif, stocké dans une variable. Invoquez-le avec
& $e num1 num2
, par exemple:Dans une forme plus lisible, il fait ce qui suit (nb. Pour un code plus clair, j'ai mis les noms de commandlet complets, plus d'espaces dans la chaîne et rendu les commandes de sortie du pipeline explicites):
Un ennui du point de vue du codegolf; PoSh n'a pas de division entière, 10/3 renvoie un Double, mais transforme le résultat en entier et il n'est pas toujours arrondi, il arrondit N.5 au nombre pair le plus proche - vers le haut ou vers le bas. Alors
[int](99/2) == 50
.Cela laisse deux choix maladroits:
C'est pourquoi je dois graver certains personnages en faisant:
A part ça, c'est le nombre de
J'ai également une version itérative qui, plutôt joliment, compte également 84 caractères:
Codeblock complètement anonyme, alors exécutez-le avec
la source
PHP, 118 octets
Essayez-le en ligne!
PHP, 131 octets
Essayez-le en ligne!
-4 octets remplacer
list(,$n,$m)=$argv
par les[,$n,$m]=$argv
besoins PHP> = 7.1la source
Japt ,
434241 octetsMes nouvelles "compétences" Japt semblent empirer, pas s'améliorer!
Essayez-le en ligne
la source
JavaScript (ES6),
7450626155 octetsEssayez-le
Explication
la source
JS, 151
la source
C, 83 octets
test et résultats
la source
Java 133
Il ne fait pas l'algorithme euclidien normal. Au lieu de cela, il utilise le module, puis calcule le 2e nombre à multiplier par lorsqu'il est imprimé. Vous pouvez également le raccourcir en le transformant en une expression lambda, mais je ne sais pas comment.
la source
public
, changer le secondprintln
enprint
et changerd!=0
end>0
. En outre, il donne actuellement une sortie incorrecte pour les premières lignes. Cela peut être corrigé en ajoutantif(d!=i)
devantSystem.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);
. Donc au total:void z(int i,int j){for(int d=1;d>0;i=j,j=d){d=i%j;if(d!=i)System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);}System.out.print(i);}
( 131 octets et correction de bugs)