Bonjour,

si tu fais des recherches je crois que ca s'appelle le probleme de Josephus.

Merci Cauchy je ne savais pas ou chercher je vais me renseigner

A l'origine je crois que c'est une histoire où Josephus doit choisir doit choisir la bonne place pour pas etre tué un truc dans ce genre.

Oui j'ai lu ça mais je ne trovue toujours pas la solution ...

Pour N=7 et K=3 c'est pas plutot R=2?

Salut si tu connais un peu l'anglais (le texte est assez simple..), voila un site qui propose une solution simple --> ..


Bonne soirée,




David

Il y a peut etre moyen avec une récurrence sinon je pense pas qu'on ait une forme simple qui te donne pour N et K directement la solution.

Bonjour
Pour N=7 et K=3, alors in a bien  R = 3   ( et pas 2 )
A+

Bonjour,

pourtant si t'en elimine 1 sur 3 ca te donne :1-4-7-5-3-6-2 ?

Rebonjour

Pour le problème de joseph j'avais fais jadis 1  programme ( il y a bien 15 ans ) mais à mon avis pour cadrer  avec notre problème je devais faire K+1 à la place de K (ou 1 bug)
enfin soit ( je verrais + tard) faisons le  à la "main  "  
Pour N  =  42  et K =7 on a bien 37
Pour N=5 et K=2
on en laisse 1 entre et on barre (tue) le 2ème
Au 1er passage dans 1 2 3 4 5 on barre le 2 =>  il reste  1 3 4 5 et on redémarre à 3
Au 2ème passage dans 1 3 4 5 on barre le 4 => il  reste  1 3 5 et on redémarre à 5
Au 3ème passage dans  1 3 5 on barre le 5 => il  reste  3 5  et on redémarre à 3
Au 4ème passage dans 3 5  on barre le 5 => il  reste  3  ( et non 2)
enfin je pense
*
Pour N=7 et K=3 on fait pareil  on obtient successivement ; on en laisse 2 et on barre le  3ème
1 2 3 4 5 6 7 ;  
1 2 4 5 6 7 ;
1 2 4 5 7 ;
1 4 5 7 ;  
1 4  5 ;
1 4  ;
4
enfin je pense non??
quel problème
A+

Oui mais le problème dans mes exemples c'est que dans la consigne originale on numérone de 0 à N-1 mais le soucis n'est pas de savoir ça on s'en moque !


Le but est de construire un algorithme performant j'en ai fait un en C mais il ne passe pas les tests prologins car il consomme trop de mémoire

Voir algorithme
http://raphaello.univ-fcomte.fr/Java-Starter/19-TD11/TD11.htm#Ex1
A+

Bonjour

( au départ on avait numéroté depuis 1 jusque N)

Oui ok lorsque les numéros commencent à 0 et finissent à N-1 on a bien
Exemples:
N=5 et K=2, alors R=2
N=42 et K=7, alors R=37
N=7 et K=3, alors R=3
Malheureusement je n'ais le prg de Joseph qu' en Pascal et en Basic que je transmet.
cela ne veut pas dire que je sais l'expliquer

Voici  en TurboPascal le prg de Joseph
rem n commence à chanter. On enlève du cercle l'enfant sur lequel la chanson s'arrête
Begin
     Repeat
           clrscr
           writeln('Problème de Joseph');
           write(' nbre d'enfants ');
           readln(n);
           write(' nbre de syllables ');
           readln(m);
           pn:=1;
           i:=0;
           while pn<>n do
                 begin
                 pn:=pn+1 ;
                 i:=(i+m) MOD pn;
                 end;
           end;
           writeln(L'enfant qui reste porte le n°,i);
           writeln('Presser <1> pour continuer ');
           writeln('Presser <0> pour terminer ');
           read(q);
       until q=0
end;
end.

En basic ça donne

0 'Probleme de Joseph
20 '
30 '5/03/87
40 '
50 '==============
60 '
70 ' Ici on commence … 0 ...N-1
80 '
90 '
100 CLEAR : CLS
110 INPUT "Nombre d'enfants :"; N
120 INPUT "Nombre de syllabes : "; M
130 PRINT : PRINT
140 '
150 '---------------------
160 DIM A(N - 1), B(N - 1)
170 '---------------------
180 '
190 FOR I = 0 TO N - 1
200 A(I) = I: B(I) = I
210 NEXT I
220  '
230 IF NOT (N > 2) THEN GOTO 500
240 MT = M
250 FOR I = 0 TO N - 2
260 R = MT - INT(MT / N) * N
270 A(I) = B(R)
280 MT = MT + 1
290 NEXT I
300 FOR I = 0 TO N - 2
310 B(I) = A(I)
320 NEXT I
330 N = N - 1
340 GOTO 230
500  R = M - INT(M / 2) * 2
510 IF R = 0 THEN PRINT "le dernier est "; A(0) ELSE PRINT "le dernier est "; A(1)
520 PRINT : PRINT " voulez-vous recommencer (o/n) ? ";
530 A$ = INKEY$: IF A$ = "" THEN GOTO 530
540 IF A$ = "o" THEN GOTO 100 ELSE END


A+

:|

Chapeau bas GEO3 l'algorithme est d'une pertinence :|

int main(void) {
int n,m,pn,i=0;
scanf("%d %d",&n,&m);
for (pn=1;pn<=n;pn++) i=(i+m)%pn;
printf("%d\n",i);
system("pause");
exit(0);
}

En C ça donne ça  j'en reviens pas UNE SEULE LIGNE de traitement qui fait a peine N opérations :| je comprends toujours pas comment ça marche mais je vais m'y pencher

Si tu peux m'aider à comprendre le principa ça m'interesse beaucoup
(Etant donné la prise de tête qu'a entrainé ce problème, se solvant en une ligne ^^)

Bon courage gregTS
Moi j'en suis incapable
Je ne suis pas informaticien .
Je me débrouille 1 peu en  quickbasic ; j'ai oublié le pascal et je n'ai jamais fait du C
Bonne chance pour trouver 1 expert en langage C ( à mon avis un débutant aurait beaucoup de mal )
A+

Geo3 c'est moi qui ait écrit le programme en C ci-dessus (Je l'ai traduit depuis ton programme Pascal!) En Pseudocode ça dirait:


PLACE=0
Récuperer N et M

Pour i de 1 a n (inclus): PLACE=(PLACE+M) MODULO i

Retourner PLACE


Et c'est tout ! Là Ca devient possible de m'aider ou pas ?

Bonjour gregts ,

qu'est ce que tu ne comprend pas ce que ca fait ou bien le C?


En gros ca t'affiche celui qui est eliminé dans le cercle.

Tu rentres n le nombre de personnes et m combien de personnes tu sautes à chaque fois. Bien sur pour afficher i qui est la personne eliminée il faut prendre ca modulo n car tu es dans un cercle de n personnes et donc n+1=1,n+2=2 ca tourne...

Nan maintenant je comprends tout, c'est bien plus compliqué que ça en a l'air je vais donc publier un article sur un de mes sites expliquant ce problème et sa résolution car ça manque je trouve

Enfin tu verras je publierais tout cela je vais l'écrire de ce pas


Greg

Ok,

sinon cette ligne c'est pas plutot :for (pn=1;pn<=n;pn++) i=(i+m)%n;

que modulo pn?

Voila j'ai écrit un article qui détaille tout, j'espere que vous comprendrez mieux


http://mescours.info/maths-Le_probleme_de_Josephus-39.xhtml

T'inquietes pas j'avais compris j'ai deja eu ce truc en tp d'info au depart je pensais que tu voulais resoudre le probleme sans faire appel à de la programmation ce qui me semble bien plus complexe (peut etre possible dans des cas particuliers).

Sinon il est bien fait ton site tu tapes tout tes cours pfiou c'est du boulot

A plus