Programmation - Chaînes puissances
Le site UVa Online Judge regroupe des problèmes de plusieurs concours de programmation ouvert aux étudiants. Il propose de nombreux exercices de nature algorithmique dont la résolution se fait en écrivant un programme en C, C++ ou Java qui est ensuite vérifié automatiquement sur un ensemble de données test.
Pour illustrer certains points du cours, nous vous proposerons des problèmes issus de ce site. Après la création d'un compte, vous pourrez donc soumettre vos solutions au site UVa Online Judge puis envoyer à l'adresse vergnaud@di.ens.fr votre solution (ainsi qu'une courte justification théorique) lorsque celles-ci auront été acceptées.
Une introduction à la programmation en C peut être trouvée ici ou là.
Problème original : Power strings
Description
Étant données deux chaînes de caractères a et b, nous notons a*b leur concaténation. Par exemple si a="abc" et b="def" alors a*b="abcdef". En considérant la concaténation comme la multiplication, l'exponentiation par un entier positif est définie de la façon suivante : a^0 = "" (la chaîne vide) et a^(n+1) = a*a^n.
L'entrée consiste en plusieurs cas à traiter. Chaque cas à traiter est une ligne contenant une chaîne de caractères s. Pour chaque chaîne s, vous devez afficher la plus grand entier n tel que s=a^n pour une chaîne a. La longueur de s sera au moins 1 et au plus 1 million de caractères. Une ligne contenant un point suivra le dernier cas à traiter.
Exemple d'entrée
abcd aaaa ababab .
Exemple de sortie
1 4 3
