Skip to main content

Josephus Problem using Queue

//Josephus.java
//Out of  n members, every m'th person will be eliminated
import java.io.*;

//Stack---------------
class Node<T> {
    T value;
    Node<T> link;
}

class Stack<T> {
    Node<T> top;
    public Stack() {
        top = null;
    }
    public void push(T item) {
        Node<T> n = new Node<T>();
        n.value = item;
        n.link = top;
        top = n;
    }
    public T pop() {
        T item;
        item = top.value;
        Node<T> n = top;
        n = null;
        top = top.link;
        return item;
    }
    public void display() {
        Node<T> n = top;
        System.out.print("(top)");
        while (n != null) {
            System.out.print(" ->" + n.value);
            n = n.link;
        }
        System.out.println();
    }
}

// Queue---------------------------
class Queue<T> {
    Node<T> front, rear;
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();
    public Queue() {
    }
    public void add(T item) {
        while (s2.top != null)
            s1.push(s2.pop());
        s1.push(item);
        rear = s1.top;
        while (s1.top != null)
            s2.push(s1.pop());
        front = s2.top;
    }
    public T remove() {
        T item = s2.pop();
        front = s2.top;
        return item;
    }
    public void display() {
        Node<T> n = s2.top;
        System.out.print("(front)");
        while (n != null) {
            System.out.print(" <-" + n.value);
            n = n.link;
        }
        System.out.println(" <-(rear)");
    }
}

// Josephus Problem-------------------
public class Josephus {
    public static void main(String[] args) throws IOException {
        Queue<Integer> q = new Queue<Integer>();
        Queue<Integer> q1 = new Queue<Integer>();
        int n, m, i;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter no. of members (n) : ");
        n = Integer.parseInt(br.readLine());
        System.out.println("Enter the elimination number (m) : ");
        m = Integer.parseInt(br.readLine());
        for (i = 1; i <= n; i++)
            q.add(i);
        Node<Integer> node = q.front;
        int l, k = 0;
        while (k != n - 1) {
            for (i = 1; i < m; i++)
                q.add(q.remove());
            l = q.remove();
            q1.add(l);
            k++;
        }
        System.out.println("Order of elimination is : ");
        while (q1.front != null)
            System.out.print(q1.remove() + ",");
        System.out.println("nWinner is : " + q.remove());
    }
}

Comments

Popular posts from this blog

Ubuntu: Access a usb flash drive from the terminal

    1. Find what the drive is called You'll need to know what the drive is called to mount it. To do that fire off: sudo fdisk -l You're looking for a partition that should look something like:   /dev/sdb1 . Remember what it's called. 2. Create a mount point Create a new directory in   /media   so you can mount the drive onto the filesystem: sudo mkdir /media/usb 3. Mount! sudo mount /dev/sdb1 /media/usb When you're done, just fire off: sudo umount /media/usb Source: StackOverflow

Code for Php based online Treasure Hunt

Hello guys. Some time back I organized an online treasure hunt as part of an event at my college. I thought of sharing the code with you, as you might find it useful. So, I uploaded it on github and here is the link to my repository. Download it from here , and enjoy organizing the game

OS X 10.8 Mountain Lion bootable USB (without MAC)

Download the raw file from here . How to use: 1 - Copy the .raw file to an USB stick using  SUSE Studio Image Writer . If you have error during copy, eject and re-connect the pen drive. When Windows asks if you want to format it, cancel and run Image Writer again. If the problem persists, disable your anti-virus software, it may be blocking raw write to the drive. Another Image Writer for Windows, if SUSE doesn't work https://launchpad.net/win32-image-writer/+download 2 - Boot the USB drive and install. If you need, type  boot options , for example: -v (verbose boot) [default] -x (safe) -s (single user) GraphicsEnabler=yes (enable graphics card drivers) [default] USBBusFix=yes (fix problems with USB devices) npci=0x2000 (use if boot stops at "PCI configuration begin") cpus=1 If you need, use  TransMac  to remove kexts which are causing problems (System/Library/Extensions) and use the flag -f (ignore caches) at boot, or remove /System/Library/Ca