#include <stdlib.h>
#include <stdio.h>
#define N 9 /* No. de nohs */
#define M 5 /* No. de saltos */
typedef struct node* link;
struct node {
int item;
link next;
};
/* Funcao principal */
int main() {
printf("==============================================\n"); printf(" PROBLEMA DE FLAVIO JOSEFO (lista circular) \n"); printf("==============================================\n");
int i; /* Contador */
int n = N; /* No. de nohs */
// link t = malloc(sizeof *t);
link t
= malloc(sizeof(link
)); link x = t;
/* Criacao do noh cabeca da lista circular:
ele aponta para si mesmo */
t->item = 1;
t->next = t;
printf("size of x: %d, size of link: %d\n", (sizeof *t
), (sizeof(link
)));
/* Preenchimento do restante da lista circular */
for (i = 2; i <= N; i++) {
x
= (x
->next
= malloc(sizeof *x
)); printf("x: %p, x->next: %p, t: %p\n", x
, x
->next
, t
); x->item = i;
x->next = t;
}
/* Eliminacao dos nohs */
while (x != x->next) {
for (i = 1; i < M; i++)
x = x->next;
x->next = x->next->next;
n--;
}
printf("Noh restante: %d\n", x
->item
);
return 0;
}
I2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RkaW8uaD4KCiNkZWZpbmUgTiA5ICAgICAvKiBOby4gZGUgbm9ocyAqLwojZGVmaW5lIE0gNSAgICAgLyogTm8uIGRlIHNhbHRvcyAqLwoKdHlwZWRlZiBzdHJ1Y3Qgbm9kZSogbGluazsKCnN0cnVjdCBub2RlIHsKICAgIGludCBpdGVtOwogICAgbGluayBuZXh0Owp9OwoKLyogRnVuY2FvIHByaW5jaXBhbCAqLwppbnQgbWFpbigpIHsKCXByaW50ZigiPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PVxuIik7CglwcmludGYoIiBQUk9CTEVNQSBERSBGTEFWSU8gSk9TRUZPIChsaXN0YSBjaXJjdWxhcikgXG4iKTsKCXByaW50ZigiPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PVxuIik7CglwcmludGYoIlxuIik7CgogICAgaW50IGk7ICAgICAgLyogQ29udGFkb3IgKi8KICAgIGludCBuID0gTjsgIC8qIE5vLiBkZSBub2hzICovCgovLyAgICBsaW5rIHQgPSBtYWxsb2Moc2l6ZW9mICp0KTsKICAgIGxpbmsgdCA9IG1hbGxvYyhzaXplb2YobGluaykpOwogICAgbGluayB4ID0gdDsKCiAgICAvKiBDcmlhY2FvIGRvIG5vaCBjYWJlY2EgZGEgbGlzdGEgY2lyY3VsYXI6CiAgICAgICBlbGUgYXBvbnRhIHBhcmEgc2kgbWVzbW8gKi8KICAgIHQtPml0ZW0gPSAxOwogICAgdC0+bmV4dCA9IHQ7CgogICAgcHJpbnRmKCJzaXplIG9mIHg6ICVkLCBzaXplIG9mIGxpbms6ICVkXG4iLCAoc2l6ZW9mICp0KSwgKHNpemVvZihsaW5rKSkpOwoKICAgIC8qIFByZWVuY2hpbWVudG8gZG8gcmVzdGFudGUgZGEgbGlzdGEgY2lyY3VsYXIgKi8KICAgIGZvciAoaSA9IDI7IGkgPD0gTjsgaSsrKSB7CiAgICAgICAgeCA9ICh4LT5uZXh0ID0gbWFsbG9jKHNpemVvZiAqeCkpOwogICAgICAgIHByaW50ZigieDogJXAsIHgtPm5leHQ6ICVwLCB0OiAlcFxuIiwgeCwgeC0+bmV4dCwgdCk7CiAgICAgICAgeC0+aXRlbSA9IGk7CiAgICAgICAgeC0+bmV4dCA9IHQ7CiAgICB9CgogICAgLyogRWxpbWluYWNhbyBkb3Mgbm9ocyAqLwogICAgd2hpbGUgKHggIT0geC0+bmV4dCkgewogICAgICAgIGZvciAoaSA9IDE7IGkgPCBNOyBpKyspCiAgICAgICAgICAgIHggPSB4LT5uZXh0OwogICAgICAgIHgtPm5leHQgPSB4LT5uZXh0LT5uZXh0OwogICAgICAgIG4tLTsKICAgIH0KCiAgICBwcmludGYoIk5vaCByZXN0YW50ZTogJWRcbiIsIHgtPml0ZW0pOwoKICAgIHJldHVybiAwOwp9
==============================================
PROBLEMA DE FLAVIO JOSEFO (lista circular)
==============================================
size of x: 16, size of link: 8
x: 0x5645b3f70290, x->next: (nil), t: 0x5645b3f70270
x: 0x5645b3f702b0, x->next: (nil), t: 0x5645b3f70270
x: 0x5645b3f702d0, x->next: (nil), t: 0x5645b3f70270
x: 0x5645b3f702f0, x->next: (nil), t: 0x5645b3f70270
x: 0x5645b3f70310, x->next: (nil), t: 0x5645b3f70270
x: 0x5645b3f70330, x->next: (nil), t: 0x5645b3f70270
x: 0x5645b3f70350, x->next: (nil), t: 0x5645b3f70270
x: 0x5645b3f70370, x->next: (nil), t: 0x5645b3f70270
Noh restante: 8