Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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 = 13;
- System.out.println("Enter the elimination number (m) : ");
- m = 7;
- 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());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement