Voici le défi de février basé sur une réflexion par algorithme. Le but est de réduire l’amplitude d’un signal venant d’une suite de nombres que l’on ajoute.
Voici une suite de valeurs de départ [1, -6, -2, -1, 4, 4, -3]. A chaque instant vous ne pouvez prendre uniquement que la valeur la plus à droite ou la plus à gauche pour l’ajouter à la précédente. Au départ le signal est à 0. Le but est de faire en sorte que l’amplitude maximale soit la plus faible en ajoutant toutes les valeurs.
Par exemple si on prend comme valeurs [1, -6, -3, 4, 4, -2, -1] en les ajoutant dans ordre nous avons a+1, a-5, a-8, a-4, a, a-2, a-3 soit au maximum a-8 et a+1 et une amplitude minimale de 9.
Il faudra donc prendre les bonnes décisions pour les choix des valeurs extrêmes de droite et gauche pour avoir une suite dans un ordre bien précis. Pour [1, -6, -2, -1, 4, 4, -3] la solution est [-3, 4, 1, -6, 4, -1, -2] ce qui donne a-3, a+1, a+2, a-4, a, a-1, a-3 et une amplitude de 6. Plusieurs solutions sont possibles qui donne des amplitudes minimales identiques, aussi il faudra toujours sélectionner la valeur la plus à droite dans les choix avant de retourner le résultat final. (Essayez en commençant par 1).
Pour LabVIEW, les valeurs seront des entiers entre -99 et 99 et la liste d’entrée un tableau de maximum 50 valeurs. La sortie sera donc un tableau mis dans l’ordre ainsi qu’un indicateur avec l’amplitude minimale en entrée et sortie.
La valeur de vérification, autre que celle proposée en exemple sera donnée ultérieurement.
Vous pouvez vous servir du code joint comme point de départ (Version LabVIEW 2010)
Un Livre LabVIEW 2eme édition est à gagner. Le gagnant sera tiré au sort (basé sur les sorties du loto) sur les codes validés.
Envoyez votre code renommé Ch41_Amplitude_votre pseudo_ici.vi à emmanuel.roset@ni.com avant le 28 février. Et postez sur la communauté « code envoyé » pour vérifier la boite email en cas de non réception.
Bon défi remue-méninges
Bonjour à tous,
Voilà en effet un beau défi algorithmique ! J'ai déjà une petite question :
Si je comprends bien, on peut décaler les éléments du tableau d'entrée à souhait afin que l'amplitude finale soit minimale. Dans ce cas-là, quel est l'intérêt de pouvoir additionner à l'amplitude (à l'instant t) soit le chiffre tout à gauche, soit le chiffre tout à droite ? Autant les placer dans le bon ordre, de gauche à droite, directement, non ?
Et du coup je ne comprends pas trop la condition du choix de la "bonne" solution dans le cas de multiples solutions.
Voilà, merci d'avance pour les réponses et bonne chance !
Ca parait compliqué à la lecture mais en le faisant sur papier on se rend compte que c'est faisable car on ne prend que les extrêmes et et il n'y a pas à tout réorganiser.
Sebastien_D
Pour répondre a votre question, en effet en théorie on pourrait manipuler n'importe quel élément mais ce n'est pas ce qui est demandé. Il s'agit d'un exercice qui oblige a sélectionner soit l'élément le plus a droite soit le plus a gauche et à l'additionner au résultat précédent. Si on additionne plusieurs éléments négatifs de suite par exemple on va s'éloigner du minimal qui est zéro, mais stratégiquement cela peut être une bonne chose pour compenser une grosse valeur positive par la suite.
Bonjour,
Merci pour les précisions, je m'étais embarqué dans quelque chose de différent effectivement ! Une autre question me vient alors concernant ce passage :
"Plusieurs solutions sont possibles qui donne des amplitudes minimales identiques, aussi il faudra toujours sélectionner la valeur la plus à droite dans les choix avant de retourner le résultat final. (Essayez en commençant par 1)."
je ne suis pas sûr de bien comprendre ce passage. Si l'on reprned l'exemple donné (input [1, -6, -2, -1, 4, 4, -3], solution [-3, 4, 1, -6, 4, -1, -2]), on pourrait aussi noter la solution DDGGDDD (D=chiffre pris à droite, G=chiffre pris à gauche).
Qu'est ce que signifie "valeur la plus à droite" ? La solution avec le plus de "D" dans la combinaison ? Et s'il y en a plusieurs qui ont le même nombre de D (je ne sais pas si c'est possible, mais à priori oui), laquelle privilégier ?
Merci d'avance pour la réponse, je crois que j'aurai tout compris après 😄
Pas de soucis pour les questions et merci de relever le défi !
Si on commence par 1 et non pas par -3 au départ avec [1, -6, -2, -1, 4, 4, -3] le résultat serai [1, -3, 4, -6, 4, -1, -2] avec a+1, a-2, a+2, a-4, a, a-1, a-3 et donc une amplitude également de 6. Comme le résultat est identique il est demandé de choisir l'ordre qui privilégie le choix le plus à droite, idem pour les deux dernières valeurs -1, -2 qui sont égales à -2, -1.
Ceci pour permettra d'avoir le même résultat pour tous afin de comparer plus facilement les tableaux.
En fait il ne s'agit pas de la valeur maximale négative ou positive mais l'amplitude entre les extrêmes. Si on prend [1, -6, -2, -1, 4, 4, -3] l'amplitude résultante dans l'ordre est [+1, -5, -7, -8, -4, 0, -3] soit de +1 à -8 donc une amplitude de 9. Dans la solution on va de +2 à -4 donc l'amplitude est 6.
Chez moi le retour à la ligne ne pose pas de problème.
Bingo, j'ai une solution
Quelqu'un a-t-il une autre série de valeurs en entrée pour comparer les résultats en sortie????
@PhilB58, j'ai déjà un programme fonctionnel à 90% qui teste toutes les possibilités en brute-force et renvoie l'amplitude minimale et pour quelles combinaisons elle est atteinte. Il ne me reste pas grand chose à faire pour trouver LA bonne solution spécifiée dans les consignes. Mais avant de continuer, je voulais savoir, est ce que tu utilises la brute-force ( est dans ce cas là je finis mon programme) ou une méthode plus subtile (à laquelle je n'ai pas encore pensé du coup 😞 ).
En fait je viens de finir mon programme, et mes résultats lèvent une nouvelle question. Si j'avais bien compris, lorsqu'il y a plusieurs solution, il convient de choisir celle qui comporte le plus "d'additions par la droite" (je me suis peut-être trompé là-dessus, je ne suis pas sûr d'avoir bien interprété ce qu'Emmanuel avait dit "choisir l'ordre qui privilégie le choix le plus à droite").
Donc si je continue sur cette hypothèse, mon programme a trouvé une autre solution, qui est 1, -3, 4, -6, 4, -1, -2, qui a bien pour amplitude 6 et qui comporte 5 additions par la droite, comme la solution donnée par Emmanuel [-3, 4, 1, -6, 4, -1, -2].
Voilà, soit je n'ai toujours pas compris le but, soit il y a effectivement des doublons (voire des triplons, des quadruplons...) de solution !
Bon, j'ai crié bingo trop tôt
Je me suis fait une série de nombres (positifs et négatifs) et j'ai fait tourner mon programme, je n'obtiens pas la meilleure solution (trouvée mentalement), donc, je dois revoir ma copie et ajouter des critères dans les choix successifs.
De plus, l'info est dans un message d'Emmanuel mais je l'avais zappée, il faut privilégier TOUS les nombres les plus à droite, pour autant que la réduction d'amplitude reste maximale, j'ai donc encore du taf!
Sebastien_D, je ne sais pas à quoi tu fais allusion par "la brute-force", et non, je ne frappe pas sur mon ordi
Et pour ajouter une info, oui, sans doute existe-t-il des doublons, mais pas beaucoup à mon sans car le challenge impose de prendre les nombres les plus à droite, ça réduit grandement la marge de manoeuvre.
Par brute-force, j'entends, tester toutes les combinaisons possibles avec une séquence de N nombres (donc 2^N) jusqu'à trouver la bonne, sans réelle "intelligence" dans la recherche.
Une fois de plus, je pense que je n'ai pas compris le critère de sélection de la solution, mais d'après moi il y a (au moins) trois solutions pour l'exemple d'Emmanuel [1, -6, -2, -1, 4, 4, -3], qui sont
1, -3, 4, -6, -1, -2
1, -3, 4, -6, 4, -1, -2
-3, 4, 1, -6, 4, -1, -2
Les trois donnent une amplitude de 6, et utilisent toutes 5 additions par la droite (et donc 2 additions par la gauche). D'après ce que j'ai compris, il s'agit normalement de prendre la solution qui comporte le plus d'aditions par la droite, mais apparemment je me trompe complètement!
Pas évident en effet, d'autant plus que le tableau dans le Vi proposé est vertical, difficile dans ces conditions de trouver une valeur plus à droite que l'autre
Cela dit, il faut comprendre que les valeurs les plus à droite sont celles vers la fin du tableau d'entrée, enfin, si j'ai bien compris.
Pour la réponse, s'il en existe plusieurs, il faut préivilégier celle(s) qui commence(nt) par le dernier chiffre du tableau (condition élémentaire, le plus à droite), et ensuite, s'il y en a plusieurs (de solutions), celles(s) qui utilisent en addition de préférence les chiffres en fin de tableau (à droite donc), sachant qu'inévitablement, il faudra utiliser les chiffres en début de tableau (à gauche) à un moment ou un autre
Maintenant, la solution qui privilégie une addition en commencant à gauche et allant vers la droite ne donnera jamais un résultat acceptable de réduction de signal, sauf si les chiffres du tableau d'entrée sont déjà optimisés en terme de position.
Maintenant, j'ai peut-être pas tout compris non plus
Je pense qu'il ne faut pas chercher à faire encore plus complexe. Et il n'est pas possible de changer les positions des valeurs du tableau. (en effet gauche = haut dans l'exemple et droite = bas). En commencant par 1 les choix qui suivent sont uniquement de 2 valeurs possibles donc on choisi celle qui s'éloigne le moins du minimum possible. Puis en cas de choix identique sur le résultat du minimum en cours, choisir la valeur la plus a droite... Tout est comme fait à la main (et à l'esprit). Par contre la valeur de départ compte dans le choix le plus a droite ou pas.
Les essais par force brute peut marcher aussi mais je pense que le temps de recherche peut être beaucoup plus long.
Maintenant, il est encore possible d'optimiser avec les N+c (coups d'avance). Et ainsi voir si la valeur minimale est encore optimisable ou pas suivant les décisions faites N-c. Mais ceci sera compté comme un challenge optionnel. Le défi est remporté déjà si les valeurs de sortie sont identiques pour tous et comparables à coup sur. Il n'y a qu'une seule séquence de résultat pour cet algorithme.
J'espère avoir aidé
Bonjour Emmanuel,
ne pourrait-on pas prolonger ce challenge de 2 ou 3 jours, ce mois-ci étant plus court
J'ai eu du mal pour ce challenge, déjà qu'il n'est pas simple (enfin, je ne l'ai pas trouvé simple), mais j'ai eu une charge de travail très importante ce mois-ci, et je n'avais plus LabView chez moi, ayant changé de pc, je n'ai pu l'installer que ce we
J'ai une idée à essayer pour finaliser mon code, peut-être que j'y arriverai pas, mais pour aujourd'hui, faut oublier je n'aurai de toute façon pas le temps
Merci
Oui bien sur pas de problème, on repousse jusqu'à vendredi soir le 4. Le mois prochain il sera plus facile
Merci
J'espère y arriver, mais c'est pas encore certain, des fois, on a une idée qui se profile, mais pour concrétiser en terme de code, c'est pas toujours évident!
Mon code est bouclé, j'ai eu un peu de temps cet après-midi et je crois que je le tiens 🙂 avec priorisation des valeurs de droite 🙂 (ce fut l'aspect le plus difficile).
Désolé Michael.C, je n'ai pas repris mon vi avec moi (il est resté au boulot), je ne peux donc pas faire de test pour comparaison, mais ça m'aurais arrangé car, si mon code semble tenir la route, il reste un doute tout de même
On voit ça jeudi (je suis en congé demain), il me restera ce test comparatif, et puis aussi de la cosmétique, surtout pour le diagramme, le commenter correctement et passer le message pour que tout le monde comprenne ce que j'ai voulu faire 🙂
Mais curieusement, je trouve que le diagramme est plus simple que tout ce que j'ai essayé auparavant pour m'en sortir comme quoi, parfois, laisser de côté un peu pour décanter, c'est bénéfique
Voilà, j'ai testé avec d'autres valeurs d'entrée:
[5, -3, 1, 2, 3, -5, 6] et j'obtiens pour solution [6, 5, -5, 3, 2, -3, 1] avec une amplitude en entrée de 7 et en sortie de 5 (en ne tenant pas compte de la valeur 0 initiale puisque ne faisant pas partie du signal d'entrée, mais je peux corriger si nécessaire)
Une petite copie d'écran ...
En effet c'est troublant au début mais les valeurs résultantes sont toutes positives dans l'exemple et l'amplitude est le delta entre le min et le max de a. Pas évident à réaliser et a tester. J'ai hâte de voir le code
Houla, ne t'emballe pas trop, c'est peut-être moi qui ai tout faux
Je ne tiens pas compte du 0 initial, je fais peut-être déjà une erreur (Emmanuel pourrait lever le doute), puis je suis loin d'avoir épuisé toutes les possibilités en entrée, donc, je peux encore tomber sur un os!!!
Code envoyé
Non je suis sur que mon code est faux, j'ai une amplitude de sortie plus grande que l'amplitude de départ :D, et personnellement, je suis d'accord avec le fait qu'il ne faut pas tenir compte du zéro.
Attention tout de même, si je tiens compte du 0 initial, j'ai aussi une amplitude supérieure en sortie, donc, mon code est faux également!
Mais si tu n'en tiens pas compte et que ton amplitude est plus grande, oui, il doit y avoir un soucis quelque part.
PS: je suis content, on peut modifier un message maintenant, si j'avais su ça avant, j'aurais éviter les doublons successifs!! Enfin, le formum évolue, et en bien
Pas de gagnant pour ce challenge??
C'est quand le tirage au sort??
A priori j'ai reçu 2 codes. Celui de PhilB58 et celui de Michael C.
Exact ?
oui, je pense, j'avais fait une fouille pour recenser les code envoyés, j'étais étonne du peu
Bon, le tirage au sort va être facile alors
Michael C et Phil58. Comme vous avez beaucoup travaillé tous les deux (même si le code n'est pas parfait), et que je dispose de deux livres, alors vous méritez tous les deux un exemplaire.
Envoyez moi une adresse de livraison sur mon email : emmanuel.roset@ni.com
Maintenant les défis ont un autre gain avec un abonnement d'un an au magasine Programmez
Merci Emmanuel, c'est sympa
Je t'envoie mon adresse!!!