Somme fixe de N nombres aléatoires

par methodiX Jeu 28 Fév - 22:11

Salut,

Qu'est-ce que vous proposer comme meilleur algorithme pour générer aléatoirement N nombres réels strictement positifs et distincts deux à deux, tels que leur somme est égale à un nombre X strictement positif connu d'avance ?

Exemple:
X = 10 et N=5 ==> trouver 5 réels X1, X2, X3, X4 et X5 tels que la somme est égale à X=10!

Je cherche le meilleur algorithme qui répond à cette question Smile

par suneddine Ven 29 Fév - 9:53

Code:: 0) début i=0; 1) Répéter n1=1+rand() mod 10; n2=1+rand() mod 10; n3=1+rand() mod 10; n4=1+rand() mod 10; n5=1+rand() mod 10; i=i+1; jusqu'à (n1+n2+n3+n4+n5=10); 3) écrire(i); 4) fin

par **Napoléon** Ven 29 Fév - 10:58

Mosa:
Ton algorithme est très basique. Il est non déterministe. C'est-à-dire, on peut montrer que la probabilité qu'il termine et trouve la solution n'est pas égale à 1 Wink

Donc, il nous servira comme algorithme de base pour le comparer avec les propositions ultérieures!

Merci MethodiX pour le Topic !

par Alkhawarizmi Ven 8 Mai - 13:15

methodiX a écrit:Salut,

Qu'est-ce que vous proposer comme meilleur algorithme pour générer aléatoirement N nombres réels strictement positifs et distincts deux à deux, tels que leur somme est égale à un nombre X strictement positif connu d'avance ?

Exemple:
X = 10 et N=5 ==> trouver 5 réels X1, X2, X3, X4 et X5 tels que la somme est égale à X=10!

Je cherche le meilleur algorithme qui répond à cette question

Un de ces nombres n'est pas aleatoire, comme il y a la contrainte de la somme. Je suggere l'algorithme suivant:

Choisit N-1 nombres aleatoires entre epsilon et X/N (et multiplie les par N apres).
Le dernier est X - (Somme des N-1 nombres).

Tu peux aussi choisir un nombre (naturel) aleatoire entre 0 et N-1 au debut, et celui la sera le dernier.

Hope it helps,
Al.

par **Napoléon** Ven 8 Mai - 16:06

J'ai pas bien saisi le principe de l'algorithme...
Epsilon? Est-ce que tu peux donner un petit exemple illustratif?

par Alkhawarizmi Ven 8 Mai - 16:33

nabiL a écrit:J'ai pas bien saisi le principe de l'algorithme...
Epsilon? Est-ce que tu peux donner un petit exemple illustratif?

Epsilon : Un nombre tres petit --- peut etre la precision de la machine. L'essentiel c'est qu'il ne soit pas nul pour ne pas tomber dans le probleme que methodiX a illustre auparavant.

Le principe est: Genere N-1 nimbres dont on sait que la somme ne va pas depasser X, le dernier doit etre fixe, c'est tout. Pas de magie Smile

Al.

par **Napoléon** Ven 8 Mai - 17:10

OK.

Applique ça au problème suivant: J choisis X = 10 et N=50.000, on veut générer N nombres réels dont la somme est X.

Ta solution si j'ai bien compris se résume par :

1) Générer N-1 nombres réels aléatoires dont la somme S est < X.
2) le Nième nombre sera: X - S.

Dans ce cas, la question devient : Quelle est la meilleure méthode qui génère N-1 nombres réels aléatoires dont la somme est inférieure à X.

Le problème n'est pas encore résolu Smile

à suivre!

par **Napoléon** Ven 8 Mai - 17:13

Pour être plus rigoureux, il faut évaluer la complexité algorithmique de la solution proposée.

par Alkhawarizmi Sam 9 Mai - 16:33

nabiL a écrit:OK.

Le problème n'est pas encore résolu

à suivre!

Je crois que t'as pas bien lu mon message. Genere N-1 nombres entre epsilon et X/N, pui multiplie par N. La somme est alors < X. Peut etre qu'il faut les generer meme entre epsilon et X/N - epsilon.

Al.

par methodiX Sam 9 Mai - 18:38

Il faut dire les choses clairement.

Soit {Xi} les N-1 nombres entre 0 et X/N.

Alors S = Somme(Xi,i=1..N-1) est entre 0 et X.(N-1)/N

Je ne vois pas l'utilité de multiplier par N comme les Xi tu l'as indiqué.

La somme dépassera X !!!

Je suis confus ! affraid

par Alkhawarizmi Sam 9 Mai - 23:44

methodiX a écrit:Il faut dire les choses clairement.

Soit {Xi} les N-1 nombres entre 0 et X/N.

Alors S = Somme(Xi,i=1..N-1) est entre 0 et X.(N-1)/N

Je ne vois pas l'utilité de multiplier par N comme les Xi tu l'as indiqué.

La somme dépassera X !!!

Je suis confus !

Oui t'as raison. Pas necessaire de multiplier par N. J'etais moi meme confus Smile

Al

par **Napoléon** Dim 10 Mai - 0:09

Un des inconvénients de cet algorithme est que tous les N-1 premiers Xi qu'il donne sont compris entre 0 et X/N.

Imagine que X et N sont égaux à 1000.

Alors, tu génères 999 réels entre 0 et 1.

Ce qui n'est pas "très aléatoire" !!!

De toute façon, l'algorithme répond à la question Wink

A+

par Alkhawarizmi Dim 10 Mai - 0:24

nabiL a écrit:Un des inconvénients de cet algorithme est que tous les N-1 premiers Xi qu'il donne sont compris entre 0 et X/N.

Imagine que X et N sont égaux à 1000.

Alors, tu génères 999 réels entre 0 et 1.

Ce qui n'est pas "très aléatoire" !!!

De toute façon, l'algorithme répond à la question

A+

Good point!

2eme essai (ma premiere idee, mais je ne sais pas pourquoi je pensais que l'autre etait meilleure)

Entrees X N comme en haut.
Z <- X
for i = 1 .. N-1
Xi <- random number between epsilon and Z
Z <- Z - Xi

XN = Z

Al.

par **Napoléon** Dim 10 Mai - 1:25

Il y a quelques points à discuter dans cette solution :

Imagine que X1 est proche de X, alors, X2, X3...XN vont être très petits. Ce qui est un peu particulier !!! Autrement dit, dès qu'un Xi est proche de Z, les valeurs restantes sont toutes très proches l'une de l'autre au voisinage de zéro.

par Alkhawarizmi Dim 10 Mai - 3:00

nabiL a écrit:Il y a quelques points à discuter dans cette solution :

Imagine que X1 est proche de X, alors, X2, X3...XN vont être très petits. Ce qui est un peu particulier !!! Autrement dit, dès qu'un Xi est proche de Z, les valeurs restantes sont toutes très proches l'une de l'autre au voisinage de zéro.

Je ne vois pas ton argument (s'il y en un). Si X1 est proche de X, les autres doivent --- par l'enonce -- etre ainsi. Je ne vois pas ou est le probleme. Peut etre tu peux proposer qqc, ou une raison valable pourquoi ca ne "devrait" pas etre comme ca.

Al.

par **Napoléon** Dim 10 Mai - 3:30

Ce sont de simples points que j'ai cités pour qu'on les discutent. Enfin, ceux qui veulent les discuter biensur.

Les réels que génère ton algorithme n°2 ont la forme suivante:

X1
X2 = X1 + Random(0,X-X1)
X3 = X2 + Random(0,X-X1-X2)
...

C'est en gros les termes de la suite :

Xn+1 = Xn + Random(0, X-X1-X2-...-Xn), pour n=1..n-2.

Je me demandais d'étudier la complexité de l'algorithme, et surtout son comportement aléatoire.

Ce n'est pas un argument que j'ai donné, c'est une invitation à discuter ... pour les intéressés.

A+

par moudhafer Mer 26 Mai - 3:27

bon un bon problem mais c pas trop difficile pour moi :p :p lool je rigole
bon comme on sait en informatique il y a tjrs le problem d'arrondis donc c presque impossible de resoudre cet algo en disant que les Xi sont des réels donc je vous propose mon algo( qui marche et qui fait le bon travail) je l'ai ecrit en C et je viens de le compiler et ca maaarche.c un algo recursif,et le principe est :
*si n=1 alors on retourne x
*sinon on tire un entier a entre 0 et X et on réappelle notre fonction sur n-1 et x-a
et c tttttttttttttt c trééés simple et vous vous cassez la tete pour rien depuis des mois hihihihihi
je vous laisse a démontrer qu'il est valide(il se termine + il fait le travail demandé)
et voila le code en c :
#include
#include
void f(int n,int x,int s){
int a;
if(n==1){
s=s+x;
printf("result final %d\\n",s);}
else{a=random()%x;
printf("%d\\n",a);
s=s+a;
f(n-1,x-a,s);}
}

int main(){
f(5,10000,0);
return 0;
}

et a propos la variable s je l'ai ajouté pour verifier Smile

)))
bon courage

par moudhafer Mer 26 Mai - 3:33

et voila des jeux d'essais
en donnant 999 :
salhi@salhi-laptop:~/Bureau/MOUDHAFER/tt/jeux$ gcc -Wall -o test test.c
salhi@salhi-laptop:~/Bureau/MOUDHAFER/tt/jeux$ ./test
478
59
303
154
5
result final 999

en donnant 34567
salhi@salhi-laptop:~/Bureau/MOUDHAFER/tt/jeux$ gcc -Wall -o test test.c
salhi@salhi-laptop:~/Bureau/MOUDHAFER/tt/jeux$ ./test
30251
2206
1677
215
218
result final 34567

je suis fort là nn? :p :p :p

par **Napoléon** Mer 26 Mai - 12:52

Bonjour,

Mais, je crois qu'on peut faire mieux Smile

Ton algorithme fait plus que le travail qu'on lui demande faire.

1) Les nombres que génère ton algo ont une tendance décroissante, donc, pas très "aléatoire", puisque tu les choisis aléatoirement entre 0 et X-k*a, avec k un nombre qui croit. 2) De plus, une solution récursive? est-ce vraiment nécessaire ? si tu prends un "n" très grand... la pile d'exécution du programme ?! La version non récursive est-elle simple ? Si oui, pourquoi avoir pensé à la solution récursive Smile

...

Des questions classiques, pour rigoler puisque tu as fini ton dernier message par ":p :p :p" lool.

par moudhafer Mer 26 Mai - 17:42

mdrrr franchement j'adore ce forum Wink

))
mais a propos la pile y a pas de probleeeeeeeeeeeeeeem pas du tt y a aucne contraint a propos la pile,car c'est une fonction recursive terminale Wink

)) tu sais c koi recursive terminale????c a dire c'est l'appel de la fonction qui se fait en dernier lieu,c a dire on commence par evaluer les arguments puis la fonction,ces versions terminales utilisent la pile comme une fonction imperative Wink

mais a propos le fait que mon algo retourne des entiers decroissants donc pa trés aléatoires t'as raison Smile

par **Napoléon** Mer 26 Mai - 18:34

Ce n'est la peine de me poser la question "tu sais ce que veut dire Récur..." parce que même si je ne le savais pas, mes sources d'informations seraient Wikipedia par exemple, et non pas les petites informations que tu postes... Smile

En contre partie je te donne une référence sur internet pour que tu révises un peu comment fonctionne une fonction récursive dans un programme exécutable:
http://cermics.enpc.fr/polys/oap/node143.html

Le recours à la pile est inévitable lorsqu'on appelle une fonction récursive avec des paramètres. Tu as évoqué le cas d'une fonction récursive qui ne se termine pas. Je ne parle pas de ce cas.
C'est une erreur de conception de l'algorithme avant d'être une erreur de programmation. Si tu as opté pour une approche récursive pour résoudre un problème, ça sous-entend que l'espace de recherche et le domaine des variables est bien fini, ou limité par un ensemble de contraintes qui constituent la condition d'arrêt de la récursivité.

La recherche du meilleur coup dans un jeu d'échec, peut être modélisé par la maximisation d'une fonction coût heuristique. Elle est souvent codé sous forme d'une fonction récursive (algorithmes min-max, élagage Alpha/Béta ... et d'autres algorithmes plus sophistiqués...). Si parce que l'algorithme répond en un temps raisonnable (selon la profondeur de recherche etc...), on ne se pose aucune question sur sa performance, alors, y aura plus de progrès informatique Smile

))

Bref, ... même si ton algorithme est valide... la récursivité soulève toujours un problème !!!

Je te défie d'exécuter ton algorithme en lui donnant comme X = un big int = 123456789321456789123456789, et comme N = 123456798032 nombres,
Fais une trace d'exécution par un débogueur ou un autre outil...
Et poste sur le forum que tu adores beaucoup combien de "octets" il exige pour fonctionner en bon état.

NB: il y a pas mal de classe C++ ou JAVA qui implémentent les Grands-nombres ou les Big Integer avec toutes les opérations qui leur sont associées (+, *, /, BigRandom(...) etc.)

Somme fixe de N nombres aléatoires 848511

Somme fixe de N nombres aléatoires 848511

par moudhafer Jeu 27 Mai - 1:17

hummm il parait que je t'ai énervé mon frere Sad

mais moi j'ai pas dit "est-ce que tu sais les fonctions recursives??" moi j'ai dit "est-ce que tu connais les fonctions recursives TERMINALES????" mais en lisant ta réponse je suis sure que tu connais pas,terminales c'est pas a dire que ça se termine!!! terminale c a dire que la derniere chose qui se fait c'est l'appel de la fonction.je t'explique : penons l'exemple pour calculer la puissance de x par y,essayons de l'ecrire en recursive non terminal on va ecrire
si(y=0)alors retourner 1
sinon retourner x*f(x,y-1)
par exemple pour calculer puis(4,3) on aura besoin d'empiler f(3,3) et 3 et f(2,3) et 3 et ......juska arriver au cas de base et là on commence à depiler et a la derniere qu'on fait ce sont les multiplications ,tiens la version terminale
define puiss (x y) :
define aux(a b s) :
si (a=0) alors retourner s
sinon retourner aux(a,b-1,s*a)
fin aux
aux(x,y,1)
fin puiss

la version terminale n'empile pas les appels de fonctions.et a propos les informations ce que je te donne ne sont pas petites hhhh moi jamais j'utilise l'internet si je "bug" Very Happy

j'espere que t'as commencé à comprendre les fonctions recursive TERMINALES,terminales ne veut pas dire ça se termine loooooooooooooooooool
et a propos essayons de lui donner un grand nombre je vais essayer et je te répondrai

par moudhafer Jeu 27 Mai - 1:19

aaa merde j'ai fait une erreur de frappe dans le test de la fonction auxiliaire c pas (a=0) c'est enfait (b=0) je suis désolé

par methodiX Jeu 27 Mai - 13:07

moudhafer a écrit:et a propos les bignumbers et leurs opérations et additions je les ai programmé ce semestre je fait une matiere qui s'appelle la programmation scientifique on a fait out ça(division eucludienne,division chinois,algorithme de karatsuba pour les grandes multiplications....)donc je crois pas que tu vas me montrer ça avec tout mon respect à tes connaissances,plutot aux connaissances de ton wikipédia

à vrai dire, ça ne m'intéresse pas si tu sais ou tu ignores les Big Int. C'est le dernier de mes/nos soucis ici.

Je commente uniquement le coté "scientifique" de ce que tu dis, et je reprends la thèse de @Nabil :

La récursivité dans le cas de cet exercice n'est pas justifiée. ça marche, OK. Mais rien n'empêche de la critiquer.

Si tu ne supportes pas être critiqué, alors, je te donne personnellemen 1 semaine de repos en te bannant du forum.

Par expérience, tu n'es pas le seul qui a tenté de polluer le forum avec son orgueil.

par methodiX Jeu 27 Mai - 17:19

Pas de pollution dans le forum !!!

par Contenu sponsorisé

Somme fixe de N nombres aléatoires

Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires

Re: Somme fixe de N nombres aléatoires