# Thread: Josephus Problem

1. ## Josephus Problem

Hey Guys,I'm trying to solve the Josephus Problem using tree Represented List.I'm referring the book: Data Structures using C and C++ by Tenenbaum.Here is the link to the Google Book Preview (see pages 286 - 298) : Data Structures Using C - Aaro M Tenenbaum - Google Books Below is the code I wrote, It doesn't give me any errors but it doest work after I enter the names. Please help me out.

Code:
```#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXELTS 100
#define FALSE 0
#define TRUE 1
#define NUMNODES 2*MAXELTS - 1
#define BLANKS "                    "

struct nodetype {
char info[20];
int lcount;
int used;
} node[NUMNODES];

int k;

void buildtree(int n)
{
int d, f, i, p, power, size;
d = 0;
power = 1;
while (power < n) {
++d;
power *=2;
}
size = 2*n - 1;
for (i  = power-1; i < size; i++) {
printf("\nEnter Name\n");
scanf("%s", &node[i].info);
node[i].used = TRUE;
}
for (i = n-1; i < power-1; i++) {
printf("\nEnter Name\n");
scanf("%s",&node[i].info);
node[i].used = TRUE;
}
for (i=0; i < n-1; i++) {
node[i].used = TRUE;
node[i].lcount = 0;
strcpy(node[i].info, BLANKS);
}
for(i = n-1; i < size; i++) {
p = i;
while (p != 0) {
f = (p-1) / 2;
if (p % 2 != 0)
++node[f].lcount;
p = f;
}
}
}

int findelement(int k)
{
int p, r;

r = k;
p = 0;
while (strcmp(node[p].info, BLANKS) == 0)
if (r <= node[p].lcount)
p = p*2 + 1;
else {
r -= node[p].lcount;
p = p*2 +2;
}
return(p);
}

void delete(int p)
{
int b, f, q;

if (p == 0)
node[p].used = FALSE;
else {
f = (p-1) / 2;
if (p % 2 != 0) {
b = 2*f + 2;
--node[f].lcount;
}
else
b = 2*f + 1;
if (strcmp(node->info, BLANKS) != 0) {
strcpy(node[f].info, node[b].info);
node[b].used = FALSE;
}
node[p].used = FALSE;
q = f;
while (q != 0) {
f = (q-1) / 2;
if (q % 2 != 0) {
--node[f].lcount;
b = 2*f + 2;
}
else
b = 2*f + 1;
if (!node[b].used && strcmp(node[q].info, BLANKS) != 0) {
strcpy(node[f].info, node[q].info);
node[q].used = FALSE;
}
q = f;
}
}
}

int follower(int size, int m, int *pk)
{
int j;

j = k - 2 + m;
*pk = (j % size) + 1;
return(findelement(*pk));
}

int main()
{
int n, m, p, size;
struct nodetype node[NUMNODES];

printf("\nEnter the number of soldiers\n");
scanf("%d",&n);
printf("\nEnter the integer count\n");
scanf("%d",&m);
printf("\nEnter the names of the people in the circle,\nbeginning with the person from whom the count starts\n");
buildtree(n);
k = n + 1;
printf("The dead soldiers are:\n");
for (size=n;size>2;--size)
{
p = follower(size, m, &k);
printf("%s\n",node[p].info);
delete(p);
}
printf("The Survivor: %s\n", node[0].info);
}```

2. > #define BLANKS " "
How many characters does this have?

> char info[20];
How many characters will fit in this array?

Hint: did you remember to count the \0 at the end of the string ?

Popular pages Recent additions