Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

défi algo

Posté par
barcelonais59
23-12-15 à 15:31

Bonjour  à tous !  Voilà le défi que je vous propose :
Elaborer une fonction prenant en paramètre une chaine de caractère :
cette fonction devra renvoyer une chaine utilisant les mêmes lettres que celle passée en paramètre et la chaine créée devra être immédiatement inférieure lexicographiquement.
Exemple :   f("cba") = "cab"               f("cbad") = "cadb"
On admettra que le paramètre n'est pas minimale, exemple : "ab", "abc", "abcd"

Posté par
Glapion Moderateur
re : défi algo 23-12-15 à 18:11

Citation :
immédiatement inférieure lexicographiquement.

Qu'est-ce que tu entends par là exactement ? c'est quoi la relation d'ordre sur les chaînes que tu utilises ?

Posté par
barcelonais59
re : défi algo 23-12-15 à 18:18

Merci Glapion, pour t'expliquer immédiatement inférieure lexicographiquement :
Si on remplace par des chiffres on a f(3214) = 3142
on prend 3142 car c'est l'entier le plus proche de 3214 et lui étant inférieur, en prenant exactement les mêmes chiffres que 3214 bien sûr

Posté par
Glapion Moderateur
re : défi algo 23-12-15 à 18:31

Si je comprends, tu veux dire que valeur("cbad") = 3214
et tu cherches une fonction telle que f(x)= valeur(x)-1 ? pour toute chaîne x="...."

parce que j'ai un peu de mal avec "3142 car c'est l'entier le plus proche de 3214 " ça c'est un scoop

et valeur("z") par exemple c'est 26 ? et valeur("zz") c'est quoi ? 2626 ? on colle les nombres même s'ils sont pas entre 0 et 9 ?

Citation :
On admettra que le paramètre n'est pas minimal

pas clair non plus.

Bref est-ce que tu peux définir plus précisément la relation d'ordre entre les chaînes ainsi que la fonction valeur(chaîne) et la fonction f que tu veux programmer parce que là je sens que je n'ai pas tout compris de ton cahier des charges.
(et tant que c'est pas complètement défini mathématiquement, on ne peut pas faire de programme)

Posté par
barcelonais59
re : défi algo 23-12-15 à 18:43

Si je remplace par des chiffres, c'est pour signifier l'ordre alphabétique. En gros imagine l'ensemble E des mots formés par exactement les memes lettres que x, tous ces mots (y compris x) ont une place dans le dictionnaire. Comment déteminer parmi E lequel est juste avant x.
Au passage je suis sûr de moi quand je dis "c'est l'entier le plus proche de 3214 et lui étant inférieur, en prenant exactement les mêmes chiffres" ce n'est pas un scoop

Posté par
Glapion Moderateur
re : défi algo 23-12-15 à 18:56

Bon, je comprends pas bien. Je passe mon tour. Peut-être quelqu'un d'autre comprendra mieux que moi et sera plus patient.

une piste quand même d'après ce que je comprends : tu génères toutes les chaînes qui ont les même lettres, pour chaque chaîne tu calcules sa valeur et tu renvoies celle qui a le plus faible écart négatif avec la chaîne initiale.

Posté par
barcelonais59
re : défi algo 23-12-15 à 18:59

Tu as bien compris, sauf que je cherche une fonction qui renvoie la chaine avec le plus faible écart négatif sans générer l'ensemble des chaînes qui seraient bien trop coûteux.

Posté par
Glapion Moderateur
re : défi algo 23-12-15 à 19:08

c'est pas l'ensemble des chaînes, c'est juste toutes les chaînes que l'on obtient par permutation de la première, il y en a n! , c'est pas très long pour une machine, même si la première chaîne est grande et vaut "anticonstitutionnellement".

Posté par
mathafou Moderateur
re : défi algo 23-12-15 à 19:22

Bonjour,

moi je comprends juste que on veut faire un bête tri sur les lettres de la chaine en les triant à partir de la fin de la chaine par ordre décroissant depuis la fin.
mais qu'on s'arrête au premier échange de lettres qu'on a fait lors de ce tri et qu'on ne va pas plus loin.

par exemples :

f("cbad") = "cadb"

par ordre lexicographique on a

abcd
...
cabd
cadb <---- f(x) le plus proche de cbad et juste avant par ordre lexicographique
cbad <---- x
cbda
...
dcba

cherchons à trier les lettres : en partant de la fin, le premier "dérangement" (deux lettres successives en ordre inverse) est

ad : OK, par ordre alphabétique
ba : dérangement donc je trie bad en adb

autre exemple plus démonstratif :
fcabde le premier dérangement est ca, je remplace le c par le plus petit de cabde qui est a,
c'est forcément la lettre qui suit le "pivot" c dans la chaine cabde puisque c'est le premier dérangement trouvé.

et je range le reste en ordre inverse : edcb en ordre de lettres décroissantes

facile puisque c'est juste inverser leur ordre actuel

faedcb

le suivant par ordre lexicographique de faedcb est bien fcabde


sauf erreurs de croisement d'yeux
y a plus qu'à ...

Posté par
mathafou Moderateur
re : défi algo 23-12-15 à 19:28

erreurs de croisement d'yeux il y a bien, mais bon l'idée est là ...
faut juste un peu peaufiner avec quoi on échange le pivot dans le tri de ce qui est à sa droite.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !