Cet exercice d'ALGORITHMIE est pour les CODEURS du forum

Soit la fonction getRandomNumberFromStream(stream) { ... }

L'argument stream est un flux de nombres entiers positifs, contenant au moins un nombre.

Grâce à la méthode stream.next() vous récupérez soit le nombre suivant, soit null si le stream est terminé.

Écrivez le code (ou pseudo-code) de la fonction telle qu'elle renvoie aléatoirement et avec équiprobabilité l'un des nombre du stream.

La complexité spatiale de la fonction doit être en O(1)

Bonne chancehttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

PS : si vous débutez vous pouvez ignorer la contrainte sur la complexité spatiale, mais l'exercice, déjà simpliste, devient alors trivialhttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

print(Hello world!)https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Le 21 juin 2021 à 20:13:45 LESJULFS a écrit :
print(Hello world!)https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Flemme mais une petite fonction récursive et ça marche tout seul.

On a le droit de faire une copie profonde de stream?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Le 21 juin 2021 à 20:15:15 Zelker4 a écrit :
Flemme mais une petite fonction récursive et ça marche tout seul.

Ah bon, avec une complexité spatiale en O(1) ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:16:30 Piola-Kirchhoff a écrit :
On a le droit de faire une copie profonde de stream?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Oui mais je vois pas à quoi ça pourrait te servirhttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:17:25 :

Le 21 juin 2021 à 20:15:15 Zelker4 a écrit :
Flemme mais une petite fonction récursive et ça marche tout seul.

Ah bon, avec une complexité spatiale en O(1) ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Pas vu l'exigence de complexité spatiale, du coup la même chose en utilisant une variable tampon et une boucle à la place de la récursivité.

[20:17:25] <navet-navrant>

Le 21 juin 2021 à 20:15:15 Zelker4 a écrit :
Flemme mais une petite fonction récursive et ça marche tout seul.

Ah bon, avec une complexité spatiale en O(1) ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:16:30 Piola-Kirchhoff a écrit :
On a le droit de faire une copie profonde de stream?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Oui mais je vois pas à quoi ça pourrait te servirhttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Je me sert de la copie pour calculer le nombre n d'entiers dans le flux puis je tire un nombre k entre 1 et n et applique la fonction k foishttps://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

return stream.next(stream);

L'op qui veut qu'on fasse ses devoirs a sa place

aléatoirement

tu veux dire pseudo-aléatoire ? ou alors c'est un piège ?

return stream.next();

Le 21 juin 2021 à 20:19:38 Piola-Kirchhoff a écrit :

[20:17:25] <navet-navrant>

Le 21 juin 2021 à 20:15:15 Zelker4 a écrit :
Flemme mais une petite fonction récursive et ça marche tout seul.

Ah bon, avec une complexité spatiale en O(1) ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:16:30 Piola-Kirchhoff a écrit :
On a le droit de faire une copie profonde de stream?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Oui mais je vois pas à quoi ça pourrait te servirhttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Je me sert de la copie pour calculer le nombre n d'entiers dans le flux puis je tire un nombre k entre 1 et n et applique la fonction k foishttps://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Comment tu calcules le nombre d'entiers dans le flux au juste ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

et si le stream est infini on est sensé faire quoi ?

[20:21:28] <navet-navrant>

Le 21 juin 2021 à 20:19:38 Piola-Kirchhoff a écrit :

[20:17:25] <navet-navrant>

Le 21 juin 2021 à 20:15:15 Zelker4 a écrit :
Flemme mais une petite fonction récursive et ça marche tout seul.

Ah bon, avec une complexité spatiale en O(1) ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:16:30 Piola-Kirchhoff a écrit :
On a le droit de faire une copie profonde de stream?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Oui mais je vois pas à quoi ça pourrait te servirhttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Je me sert de la copie pour calculer le nombre n d'entiers dans le flux puis je tire un nombre k entre 1 et n et applique la fonction k foishttps://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Comment tu calcules le nombre d'entiers dans le flux au juste ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

J'incrémente un compteur jusqu'à ce que next renvoie null, le O(1) est respectéhttps://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Le 21 juin 2021 à 20:21:28 :

Le 21 juin 2021 à 20:19:38 Piola-Kirchhoff a écrit :

[20:17:25] <navet-navrant>

Le 21 juin 2021 à 20:15:15 Zelker4 a écrit :
Flemme mais une petite fonction récursive et ça marche tout seul.

Ah bon, avec une complexité spatiale en O(1) ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:16:30 Piola-Kirchhoff a écrit :
On a le droit de faire une copie profonde de stream?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Oui mais je vois pas à quoi ça pourrait te servirhttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Je me sert de la copie pour calculer le nombre n d'entiers dans le flux puis je tire un nombre k entre 1 et n et applique la fonction k foishttps://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Comment tu calcules le nombre d'entiers dans le flux au juste ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Ben on les compte

C'est juste une variante à la con du Reservoir Sampling. Je ne perdrais pas mon temps là dessus.

Le 21 juin 2021 à 20:20:13 Thyristor a écrit :
L'op qui veut qu'on fasse ses devoirs a sa place

Ca fait belle lurette que j'ai plus de devoirs à fairehttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:21:03 GOSWELL a écrit :

aléatoirement

tu veux dire pseudo-aléatoire ? ou alors c'est un piège ?

Utilise Math.random() et casse pas les noisetteshttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:22:45 Erismature a écrit :
et si le stream est infini on est sensé faire quoi ?

Rien n'est infini à part l'univers et la bêtise humainehttps://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

L'auteur qui parle d'aléa

Pseudo-aléa

Ça veut dire quoi complexité spatiale de 1? On a le droit de declarer qu'une variable?