Satisfactory

[invite156cfd77]

Bonjour,

Je me suis mis à un nouveau jeu vidéo : Satisfactory (un excellent jeu de construction en 3D première personne en accès anticipé pour les curieux - équivalent 3D de factorio).

Dans ce jeu, le but est de construire une usine, pour ce faire on exploite les ressources naturelles à notre disposition et on les amène à des machines qui produisent des produits retravaillés eux même acheminés à d'autres machines etc etc.
Par exemple : Il est possible d'exploiter du minerai de fer et de l’acheminer via des convoyeurs à des fonderies pour fabriquer des lingots de fer.

On peut vouloir répartir en parts égales le minerai fer dans chacune des fonderies pour optimiser leur fonctionnement, le jeu met donc à disposition des joueurs des séparateurs et regroupeurs de convoyeurs. Seulement voilà, les séparateurs divisent obligatoirement soit en 2 soit en 3 parts égales et les regroupeurs somment soit 2 soit 3 convoyeurs en un seul.

Mettons que l'on veuille répartir un flux de minerai de fer en 5 parts égales, comment procéder ?

Je vous laisser y réfléchir 2 min, et je vous donne la solution, puis la question qui arrive (bientôt).

 Cliquez pour afficher

Pour faire 5 parts égal, il "suffit" de diviser le flux initial en 2 puis chaque résultantes en 3, ce qui donnes 6 flux sortants égaux, l'astuce repose alors sur le fait d'envoyer l'un de ces 6 flux en entrée avec le flux initial via un regroupeur.
Cette solution est donc itérative et tend vers un rapport de 1/5 à la fin.
J'ai essayé de représenter la chose en mode diagramme d'automatique, parce que je trouvais que l'outil s'y prêtait bien, mais en équation ça donne quelque chose comme cela :
e(t=0) = A
e(t+1) = A + 1/6 e(t)
s_i(t=0) = A/6
s_i(t+1) = e(t+1)/6 = A/6 + A/36
s_i(t+2) = e(t+2)/6 = (A + A/6 + A/36)/6 = A/6+A/36+A/260

s_i(t+n) = somme_(1,n) [A/6^n] qui devrait converger vers A/5

Y 'a t'il un moyen de formaliser proprement tout cela et de déduire ou trouver d'autre arrangement, mettons que je veuille maintenant diviser mon flux en 11 (on divise en 2x2=4 puis en 3 et on refait la même manip) ?

Merci,
-----

[Médiat]

Bonjour,

11 = 2*2*3 -1

D'une façon générale, pour découper en n parts, il suffit de trouver le plus petit nombre qui soit de la forme

[invite51d17075]

probablement...
mon souci est que je ne comprend pas du tout le lien entre :

On peut vouloir répartir en parts égales le minerai fer dans chacune des fonderies pour optimiser leur fonctionnement, le jeu met donc à disposition des joueurs des séparateurs et regroupeurs de convoyeurs. Seulement voilà, les séparateurs divisent obligatoirement soit en 2 soit en 3 parts égales et les regroupeurs somment soit 2 soit 3 convoyeurs en un seul

et "l'organisation" que tu proposes en solution
( même si la somme que tu indiques converge bien vers 1/5 )

[invite156cfd77]

Bonjour,

11 = 2*2*3 -1

D'une façon générale, pour découper en n parts, il suffit de trouver le plus petit nombre qui soit de la forme

Effectivement, je me disais la même chose dans le bus, mais comment fait-on pour trouver le plus petit nombre ? pour 11 c'est assez immédiat, mais comment fait-on avec 2743 ?

Ansset, pour reformuler : Comment diviser en 5 parts égales une quantité en utilisant uniquement des divisions par 2 ou 3 et des additions ?

[A voir en vidéo sur Futura]

[Médiat]

Dans le pire des cas n'importe quelle puissance de 2 (ou de 3) supérieure à n convient (mais la convergence n'est pas optimum), sinon un petit algorithme donne une meilleure solution, pour 2743 je prendrais

[invite156cfd77]

Heureusement le jeu ne me demande pas d'aller à ces niveaux là, mais dans l'idée si je voulais être optimale je devrais utiliser un algorithme de recherche ?

Pour pimenter un peu le truc, le jeu propose plusieurs convoyeurs avec des vitesses de transport différentes, de fait on peut forcer les séparateurs à distribuer un flux en parts non égales : par exemple :

un flux de 450 peut être réparti en trois flux respectifs de 60 / 120 / 270, ou en deux flux 60/390 ou 120/330, ou 60/60/390, etc... Les vitesses disponibles sont 60, 120 , 270 et le maximum 450.
Avec cela, il est possible de diviser en 5 parts égales sans avoir recours à une technique récursive : un exemple simple avec un flux de 300 que l'on divise successivement en 60/60/180 et le 180 en 60/60/60.

Dans ces conditions, comment déterminer s'il est possible de diviser en n parts égales sans utiliser de récursivité ? Intuitivement j'ai l'impression que seuls les flux initiaux transportant k × n × vitesses ou k vaut soit 2 soit 3 sont possibles, mais peut-être n'est ce pas le cas ?