[Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

pierrejean · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Re

Ayant suivi un peu le fil je m'apercois qu'il peut y avoir option sur le nombre de survivants
Dans ce cas une fonction derivée a tester

Code:

Function Flavius3(soldats As Integer, intervalle As Integer, restant As Integer, Optional debut As Integer = 2) As String
For n = 1 To soldats
 cercle = cercle & Format(n, "000") & ","
Next n
 posel = (debut + intervalle - 2) * 4 + 1
 el = Mid(cercle, posel, 4)
While Len(cercle) > restant * 4
 cercle = Replace(cercle, el, "")
If posel + (intervalle - 1) * 4 > Len(cercle) Then
 posel = posel + (intervalle - 1) * 4 - Len(cercle)
Else
 posel = posel + (intervalle - 1) * 4
End If
el = Mid(cercle, posel, 4)
Wend
For n = 0 To UBound(Split(cercle, ",")) - 1
cercle1 = cercle1 & CInt(Split(cercle, ",")(n)) & ","
Next n
Flavius3 = Left(cercle1, Len(cercle1) - 1)
End Function

ROGER2327 · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Bonjour à tous

A pierrejean :

Je partage votre souci du détail. Il convient effectivement de pouvoir choisir, outre le nombre de participants à la tragédie et le pas du sinistre comptage, le point de départ du comptage, et éventuellement une liste plus ou moins longue de survivants. (Dans le problème posé au départ, le comptage commence au deuxième participant, et on veut connaître les deux derniers visés : c'est du moins ce que j'ai déduit du lien indiqué par Staple1600.)
Je trouve les mêmes résultats que vous avec votre dernière fonction.
Mais je m'aperçois qu'il y a encore une petite incertitude. Exemple :

=Flavius3(41;3;3;2)

renvoie 17,32,36. Il s'agit bien des trois derniers survivants, mais, si le massacre doit continuer, lequel des trois est la prochaine victime ? Et en poussant les choses au pire, lequel devra se suicider ?
Réponse : la prochaine victime est le numéro 36 ; le dernier survivant est le numéro 32.
Il faudrait, pour préciser cela, que la réponse fût non pas 17,32,36 mais 36,17,32.

Pour ma part, je vois cela comme suit :

Code:

[COLOR="DarkSlateGray"]Function Flavius(n As Integer, m As Integer, Optional r As Integer = 2, Optional k As Integer = 2) As String
Dim Coll As New Collection
   Application.Volatile
   If n > 0 And m > 0 Then
      Do
         Coll.Add Coll.Count + 1
      Loop While Coll.Count < n
      Do While Coll.Count
         k = 1 + (k + m - 2) Mod Coll.Count
         If Coll.Count <= r Then Flavius = Flavius & IIf(Flavius = "", "", ", ") & Coll(k)
         Coll.Remove k
      Loop
   End If
End Function[/COLOR]

Alors

=Flavius(41;3;3;2)

renvoie 36, 17, 32.
A titre indicatif :

=Flavius(41;3;41;2)

renvoie 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 2, 6, 11, 15, 20, 24, 29, 33, 38, 1, 8, 14, 21, 27, 35, 41, 9, 18, 30, 39, 12, 26, 3, 23, 5, 36, 17, 32.
A vous lire,

Cordialement,
ROGER2327
#2051

pierrejean · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Re

Je suis deja bien heureux d'avoir pu pondre (non sans difficultés) une macro qui tourne !!

quant a cette ligne elle me laisse carrement coi

Code:

[COLOR=#2f4f4f] k = 1 + (k + m - 2) Mod Coll.Count[/COLOR]

Bravo encore

Staple1600 · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Bonsoir à tous

Heureux de vous voir si nombreux dans ce fil.

Bravo pour vos contributions.

Je vois que vos neurones cogitent fort

Je vais essayer de trouver plus de documentation sur le sujet.

(Que l'on puisse tomber d'accord sur les résultats à trouver )

EDITION :Voici par exemple ce lien : FLAVIUS

Vous pourrez vérifier vos résultats .

ROGER2327 · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Re...

pierrejean à dit:
(...)
quant a cette ligne elle me laisse carrement coi

Code:

[COLOR=#2f4f4f] k = 1 + (k + m - 2) Mod Coll.Count[/COLOR]

(...)

Oserais-je dire qu'il n'y a pas de quoi ?
J'ose !
Ce qui peut dérouter est la concision de la formule. En fait, si j'explique sa construction, elle sera beaucoup moins déroutante.
Je veux éliminer un pauvre bougre tout les m individus.
A première vue, il suffit de prendre

k = k + m

tout seul, ce qui incrémente k de m en m pour aller piquer dans la liste des pauvres gens le numéro de celui qui doit mourir. Mais comme on raccourcit la liste de 1 à chaque boucle (Coll.Remove k), il convient d'incrémenter seulement de m - 1.
On prendra donc

k = k + m -1

A plus ou moins long terme, k risque de dépasser le nombre de candidats :
L'idée est donc de dire que si lors du calcul de k on obtient une valeur supérieure au nombre de candidats restant dans la liste (ce nombre étant évidemment Coll.Count), on remplace k par

k = 1 + (k-1) Mod Coll.Count

pour reprendre le comptage au début de la liste. (Le 1 et le -1 sont nécessaires car on ne compte pas à partir de 0. Ce serait plus simple si nos bonshommes étaient numérotés de 0 à n-1 plutôt que de 1 à n.)
En groupant ce remplacement avec l'incrémentation de m-1, on obtient

k = 1 + (k + m - 2) Mod Coll.Count

.

On peut voir cela en écrivant par exemple :

Code:

[B][COLOR="DarkSlateGray"]Function Flavius(n As Integer, m As Integer, Optional r As Integer = 2, Optional k As Integer = 2) As String
Dim Coll As New Collection
   Application.Volatile
   If n > 0 And m > 0 Then
      [COLOR="Red"]m = m - 1[/COLOR]
      Do
         Coll.Add Coll.Count + 1
      Loop While Coll.Count < n
      Do While Coll.Count
         [COLOR="Red"]k = k + m[/COLOR]
         [COLOR="Red"]If k > Coll.Count Then k = 1 + (k - 1) Mod Coll.Count[/COLOR]
         If Coll.Count <= r Then Flavius = Flavius & IIf(Flavius = "", "", ", ") & Coll(k)
         Coll.Remove k
      Loop
   End If
End Function[/COLOR][/B]

C'est sûrement plus long, mais aussi plus clair : Je crois que c'est le regroupement des trois lignes rouges qui rend la compréhension difficile.
Est-ce plus clair ?

ROGER2327
#2053

ROGER2327 · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Re...

Staple1600 à dit:
Bonsoir à tous
Heureux de vous voir si nombreux dans ce fil.
Bravo pour vos contributions.
Je vois que vos neurones cogitent fort
Je vais essayer de trouver plus de documentation sur le sujet.
(Que l'on puisse tomber d'accord sur les résultats à trouver )
EDITION :Voici par exemple ce lien : FLAVIUS

Vous pourrez vérifier vos résultats .

Il me semble qu'il n'y a plus de doute sur les résultats : chacun peut décider de choisir la première victime comme il l'entend (c'est une histoire très triste, en fait...) puisque pierrejean le premier, votre serviteur un peu plus tard, ont déposé des fonctions paramétrables à souhait.
Si l'on s'en tient à votre référence initiale (Flavius Josèphe), le premier éliminé est le numéro 4 : on compte 3 à partir du numéro 2.
Il suffit d'écrire ma formule avec 2 comme quatrième paramètre :=Flavius(41;3;3;2). Résultat : 36, 17, 32.
Si l'on veut des résultats conformes à votre nouveau lien (The Josephus Game), on voit que le premier éliminé est le numéro 3 : on compte 3 à partir du numéro 1.
Il suffit d'écrire ma formule avec 1 comme quatrième paramètre :=Flavius(41;3;3;1). Résultat : 35, 16, 31.
Vous pouvez démarrer le comptage à partir du vingtième, par exemple : =Flavius(41;3;3;20). Résultat : 13, 35, 9.
Peut-être manque-t-il encore un paramètre : pourquoi ne tournerions nous pas dans le sens inverse ?
Donc... A suivre ! (Peut-être...)

Cordialement,
ROGER2327
#2054

Staple1600 · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Bonsoir Roger2327, le fil, l forum

Merci pour votre code et vos explications limpides

Maintenant, le challenge* pourrait être de trouver la fonction la plus courte ou le code VBA le plus concis.

*: même si cela est vain et inutile (mais comme nous sommes dans le salon

)

(Je suis en train de finaliser un classeur qui reprendra toutes vos propositions )

EDITION

Ça recommence Excel plante quand j'ajoute dans une cellule une Données/Validation

(j'avais mis dans VBA les trois fonction vba présentes dans le fil )
(et malheur je n'avais pas enregistré mon classeur

)

J'y retourne

Staple1600 · 4 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Re

Je ne comprends pas pourquoi le fichier plante et tue mon Excel
(sans doute à cause du sujet traité dans le fil

)
Donc attention avec ce fichier
Chez moi sous Excel 2000, si j'essaye d'utiliser les spinbuttons et cie
Crash . (Excel ne réponds pas et Windows ferme le programme )
Donc à tester avec ce seul fichier d'ouvert.
EDITION : (Il semblerait que c'est la fonction de pierrejean qui tue les soldats et en bonus Excel aussi

)
(à vérifier)

Pierrejean (sauf erreur de ma part), c'est bien ta fonction non ?
(ou alors VBA n'aime avoir plusieurs éxécuteurs des basses oeuvres en même temps

? )

EDITION 2:
une autre source fort complète

avec à la fin un programme en langage Maple

ROGER2327 · 5 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Suite...

Il manquait la possibilité de faire le sale boulot en parcourant le cercle en sens inverse. Voici une proposition pour ce faire :

Code:

[COLOR="DarkSlateGray"][B]Function Flavius(n As Integer, m As Integer, Optional r As Integer = 2, Optional k As Integer = 2) As String
Dim Coll As New Collection
   Application.Volatile
   If n > 0 And m <> 0 And r > 0 And k > 0 Then
      k = 1 + (k + (m > 0)) Mod n
      Do
         Coll.Add Coll.Count + 1
      Loop While Coll.Count < n
      Do While Coll.Count
         k = 1 + (Coll.Count + k + m Mod Coll.Count + (m > 0) - 1) Mod Coll.Count
         If Coll.Count <= r Then Flavius = Flavius & IIf(Flavius = "", "", ", ") & Coll(k)
         Coll.Remove k
      Loop
   End If
End Function[/B][/COLOR]

Exemple :
Pour aller de trois en trois en trois en sens inverse, inscrire le pas (deuxième paramètre) en tant que nombre négatif. Ainsi, =Flavius(41;-3;41;1) renvoie
40, 37, 34, 31, 28, 25, 22, 19, 16, 13, 10, 7, 4, 1, 38, 33, 29, 24, 20, 15, 11, 6, 2, 36, 30, 23, 17, 9, 3, 35, 26, 14, 5, 32, 18, 41, 21, 39, 8, 27, 12,
tandis que =Flavius(41;3;41;1) renvoie la réponse symétrique
3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 1, 5, 10, 14, 19, 23, 28, 32, 37, 41, 7, 13, 20, 26, 34, 40, 8, 17, 29, 38, 11, 25, 2, 22, 4, 35, 16, 31.
(La symétrie est évidente : on voit que la somme des nombres de même rang dans les deux suites est 43.)

Le lien donné par Staple1600 dans le message précédent est très intéressant, mais fait appel à un assez sérieux bagage mathématique ! Il y a intérêt à sortir papier/crayon et à prévoir un certain temps pour voir clairement la chose...
(Je ne crois pas que je m'aventurerai là-dedans.)

Bonne nuit,
ROGER2327
#2055

Staple1600 · 5 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Re à tous

Suite

Voici une petite compil de choses glanées sur le world wild web

(Les maths c'est les autres, la mise en forme et la macro du "fainéant" c'est moi)

Pour poursuivre, je pensais(suite à diverses lectures)

à une solution utilisant une notation "binaire" *

J'aimerai aussi (mais je ne sais pas faire), créer un graphique *
(ou quelque chose proche de ce qu'avait réaliser Roger2327 dans mon fil
relatif à la fourmi de Langton) à partir du tableau généré par la macro dans la présente pièce jointe.

(* histoire de remplir des cellules et encore des cellules

)

PS: Roger2327, quel talent !

J'eusse aimé vous avoir comme professeur de maths au lycée
(ou mieux comme instituteur

)

pierrejean · 5 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Salut aux noctambules

@ Staple
C'est en effet ma macro qui fait planter Excel
Je vais essayer de resoudre

pierrejean · 5 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Re

@ Staple

Voici la version de ton fichier TestJ.FLAVIUS qui ne fait plus planter EXCEL (toutes mes excuses)
L'explication est la suivante :
Mon raisonnement ne tenait pas compte du fait que les soldats de l'epoque de Flavius pouvaient encore compter de 4 en 4 en n'etant plus que 3
A la reflexion , c'est plutot parceque mon algorithme voit les soldats en ligne et non en cercle

Staple1600 · 5 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Bonsoir à tous

Merci pour la correction, Pierrejean.

Ls soldats continuent de s'entretuer au sein des cellules de notre chiffrier favori

Guest · 5 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Bonsoir le fil,

Les gars, je vous aime bien mais là je suis dépassé!

L'agrafe, t'aurais pas ôte chosse que des math, pour mon neurone qui ressemble plus à un fil dentaire qu'à une dentrite

Amusez-vous bien.

A+++

Staple1600 · 5 Novembre 2009

Re : [Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

Bonsoir

Hasco (salute

)

J'essaierai de trouver autre chose de plus "excellien" , promis.

Mais ce ne sera pas dans le salon.

Effectuez une recherche sur Excel Downloads...

[Maths] Challenge - trouver algorithme à propos du cercle de Josephus Flavius

pierrejean

XLDnaute Barbatruc

ROGER2327

XLDnaute Barbatruc

pierrejean

XLDnaute Barbatruc

Staple1600

XLDnaute Barbatruc

ROGER2327

XLDnaute Barbatruc

ROGER2327

XLDnaute Barbatruc

Staple1600

XLDnaute Barbatruc

Staple1600

XLDnaute Barbatruc

ROGER2327

XLDnaute Barbatruc

Staple1600

XLDnaute Barbatruc

pierrejean

XLDnaute Barbatruc

pierrejean

XLDnaute Barbatruc

Pièces jointes

Staple1600

XLDnaute Barbatruc

Guest

Guest

Staple1600

XLDnaute Barbatruc

Membres actuellement en ligne

Partager cette page

Tutos vidéos

Statistiques des forums