Cet exercice d'ALGORITHMIE est pour les CODEURS du forum

Le 21 juin 2021 à 20:23:05 Piola-Kirchhoff a écrit :

[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

Ok donc tu as le nombre d'éléments du stream et après tu fais quoi au juste ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

Le 21 juin 2021 à 20:25:50 QueLouisFerdin_ a écrit :
Ça veut dire quoi complexité spatiale de 1? On a le droit de declarer qu'une variable?

ça veut dire que l'espace mémoire que tu vas occuper ne doit pas dépendre de la taille des entrées

Le 21 juin 2021 à 20:23:58 :

Le 21 juin 2021 à 20:20:13 Thyristor a écrit :
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

Quand on dit "stream" c'est en général une liste infinie, sinon on dit juste "liste"

je suppose que ce que tu attends c'est en gros :

res = stream.next()

n = 1

new = stream.next()

while (new ≠ null)

  n = n+1

  if rand() ≤ 1/n then res = new

  new = stream.next()

return res

où rand() est dans [0,1]

r=random()*stream.count

for i in r-1
stream.next()

nbr=steam.next()

ecris depuis mon Phone dans mon 9m2 du crous paz

[20:27:45] <navet-navrant>

Le 21 juin 2021 à 20:23:05 Piola-Kirchhoff a écrit :

[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

Ok donc tu as le nombre d'éléments du stream et après tu fais quoi au juste ?https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png

k=math.randint(1,n)
for i in range(k):
machin=next(stream)
https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Le 21 juin 2021 à 20:28:53 Erismature a écrit :

Le 21 juin 2021 à 20:23:58 :

Le 21 juin 2021 à 20:20:13 Thyristor a écrit :
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

Quand on dit "stream" c'est en général une liste infinie, sinon on dit juste "liste"

je suppose que ce que tu attends c'est en gros :

res = stream.next()

n = 1

new = stream.next()

while (new ≠ null)

  n = n+1

  if rand() ≤ 1/n then res = new

  new = stream.next()

return res

où rand() est dans [0,1]

oui c'est ça gghttps://image.noelshack.com/fichiers/2021/24/3/1623873044-gandalf-removebg-preview.png

C'est pas du O(1) ça

[20:28:53] <Erismature>

Le 21 juin 2021 à 20:23:58 :

Le 21 juin 2021 à 20:20:13 Thyristor a écrit :
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

Quand on dit "stream" c'est en général une liste infinie, sinon on dit juste "liste"

je suppose que ce que tu attends c'est en gros :

res = stream.next()

n = 1

new = stream.next()

while (new ≠ null)

 n = n+1

 if rand() ≤ 1/n then res = new

 new = stream.next()

return res

où rand() est dans [0,1]

Ah oui bien vu

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

Le 21 juin 2021 à 20:31:48 Dezaide a écrit :
C'est pas du O(1) ça

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

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

J'ai le droit d'utiliser Bootstrap ?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Le 21 juin 2021 à 20:34:32 Suliko a écrit :
J'ai le droit d'utiliser Bootstrap ?https://image.noelshack.com/fichiers/2016/50/1481994659-mathematicienrisitas.png

Rien ne te l'interdit.https://image.noelshack.com/fichiers/2016/34/1472411294-yeux2.png