Discussion :

[chianli]

bonjour à tous

j'essaie d'implémenter un algorithme de génération de nombre aléatoire en C et pour cela je dois lire une fonction de répartition de probabilité à l'envers
cad que j'ai un tableau avec un certain nombre de valeurs de cette fonction et je dois lui demander "quel indice x possède le nombre y ?" (sachant que c'est une fonction strictement croissante et continue donc bijective)

je voulais savoir s'il existait une manière élégante de résoudre ce genre de problème (je suis novice en C)
j'avais pensé écrire le tableau inverse (l'indice du premier devient la valeur du second et la valeur du premier devient l'indice du second), mais je ne suis pas sûr que ce soit une bonne idée...

merci de votre aide

chianli

[Gruik]

Salut,

C'est un probleme d'algo et non de C, reviens nous voir quand tu auras l'algo et que tu auras des problemes pour l'implementer en C.

[Zavonen]

Situer y par rapport à des yi du tableau.
Si la fonction est monotone croissante y doit être dans au plus un intervalle yi,yi+1
Ensuite faire un interpolation linéaire (une règle de 3)
(y-yi)/(yi+1-yi) = (x-xi)/xi+1 - xi)
à résoudre en x donc.

[chianli]

désolé de m'être trompé de forum
mais il est vrai que si j'ai du mal à coder, c'est que finalement mon algo n'est pas très clair dans ma tête

merci Zavonen pour la formule, je l'avais déjà mais je pense que je l'utilisais mal.

pour retrouver le x dont tu parles, quelle est la méthode la plus efficace pour scanner le tableau ?

j'en imagine deux pour l'instant :
- scanner le tableau dans l'ordre croissant des indice et s'arrêter quand le on trouve le couple yi et yi+1 qui encadre y
ou
- scanner le tableau en partant du milieu et partir en dessous si le yi trouvé est trop grand ou au dessus s'il est trop petit et réduire à chaque fois la "grandeur" du saut de moitié (je ne sais pas si cette 2e méthode est très claire...)

merci de votre aide

chianli

[Zavonen]

- scanner le tableau en partant du milieu et partir en dessous si le yi trouvé est trop grand ou au dessus s'il est trop petit et réduire à chaque fois la "grandeur" du saut de moitié (je ne sais pas si cette 2e méthode est très claire...)

C'est ce qu'on appelle la dichotomie, et c'est adapté à ce cas.

[chianli]

ok merci !

PS : comme vous avez pu le constater, je suis newbie...