Josephus Problem

This is a discussion on Josephus Problem within the C Programming forums, part of the General Programming Boards category; Hey Guys,I'm trying to solve the Josephus Problem using tree Represented List.I'm referring the book: Data Structures using C and ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Location
    Bangalore, India, India
    Posts
    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);
    }
    Last edited by sankarm; 10-25-2012 at 12:30 AM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    > #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 ?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Josephus Problem
    By GCNDoug in forum C++ Programming
    Replies: 0
    Last Post: 05-12-2008, 07:47 AM
  2. Please , i need help with this Josephus Problem
    By Haytham in forum C Programming
    Replies: 17
    Last Post: 04-07-2007, 07:28 PM
  3. The Josephus Problem
    By Nakeerb in forum C++ Programming
    Replies: 5
    Last Post: 11-21-2002, 07:43 AM
  4. Josephus problem
    By ihsir in forum C++ Programming
    Replies: 2
    Last Post: 07-09-2002, 10:21 PM
  5. Josephus problem
    By Unregistered in forum C++ Programming
    Replies: 11
    Last Post: 12-07-2001, 08:24 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21