Option 2 - Linked List - Josephus Problem Linked List Specification: Create a Templated/Generic Linked List....
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Option 2 - Linked List - Josephus Problem Linked List Specification: Create a Templated/Generic Linked List. This can be a Singly Linked List, a Singly Circular Linked List, a Doubly Linked List or a Doubly Circular Linked List. Any option is fine as long as it fits the required specification. Your linked list must have the following minimum specification: . Node<T> 。 Properties -data:T ■ -next:Node<T> 。 Methods +getData(): T ■ +setData(int):void ■ +getNext() : Node<T> ⚫ +setNext (Node<T>):void LinkedList<T> 。 Properties -size:int -head: Node<T> -tail:Node<T> 。 Methods: +addToFront (T):void +addToEnd (T):void +addAtIndex(value:T, index:int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ■ +deleteFront() : void ■ +deleteEnd():void ■+deleteIndex(int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ⚫ +deleteFirst(value:T): boolean • Finds and deletes the first matching value • Returns true if it worked, false if the value wasn't found ■ +empty():void ■ +contains(T): Boolean • Retuns true if the item is found in the list ■ +toString(): String • Return a string representing your LinkedList Extra credit Opportunity +5: Write a reverseList(): LinkedList<T> method that returns the singly linked list reversed. This is a common job interview challenge. Give an interface option to show it working. Josephus Problem: This is mathematical pattern problem based on a historical event: "There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom. The task is to choose the place in the initial circle so that you survive (are the last one remaining)." -- Wikipedia, http://en.wikipedia.org/wiki/Josephus problem Assume that the number of people in the circle may be any number between zero and one hundred. Assume that every Nth person around the circle is killed each turn, where N is an integer between one and twenty. Specifications: • Create an application in Java that uses a linked list to represent the circle of people, numbered from 1 to numberOfPeople. • Get the number of people and the skip value from the user via console input. Output the number of the individual that survives the mass execution. • Make sure you indicate if your skip value is inclusive or exclusive in your output. Inclusive: n 3-X0 0X00X ■ Every third person is killed with 2 skipped between 。 Exclusive: n-3-X000X000X Sample Output: ■ 3 people are skipped and the next is executed Welcome to the Josephus Problem. How many people in the circle (1100)? 5 Enter the number of people to skip between eliminations: 2 Running: Initial puzzle: 1-2-3-4-5 Eliminated #3 Remaining: 1-2-4-5 Eliminated #1 Remaining: 24-5 Eliminated #5 Remining: 2 - 4 Eliminated #2 Survivor: 4 Sample to help debug (note -inclusive, above example would be n = 5 and k = 3): https://www.geogebra.org/m/ExvvrBbR Option 2 - Linked List - Josephus Problem Linked List Specification: Create a Templated/Generic Linked List. This can be a Singly Linked List, a Singly Circular Linked List, a Doubly Linked List or a Doubly Circular Linked List. Any option is fine as long as it fits the required specification. Your linked list must have the following minimum specification: . Node<T> 。 Properties -data:T ■ -next:Node<T> 。 Methods +getData(): T ■ +setData(int):void ■ +getNext() : Node<T> ⚫ +setNext (Node<T>):void LinkedList<T> 。 Properties -size:int -head: Node<T> -tail:Node<T> 。 Methods: +addToFront (T):void +addToEnd (T):void +addAtIndex(value:T, index:int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ■ +deleteFront() : void ■ +deleteEnd():void ■+deleteIndex(int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ⚫ +deleteFirst(value:T): boolean • Finds and deletes the first matching value • Returns true if it worked, false if the value wasn't found ■ +empty():void ■ +contains(T): Boolean • Retuns true if the item is found in the list ■ +toString(): String • Return a string representing your LinkedList Extra credit Opportunity +5: Write a reverseList(): LinkedList<T> method that returns the singly linked list reversed. This is a common job interview challenge. Give an interface option to show it working. Josephus Problem: This is mathematical pattern problem based on a historical event: "There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom. The task is to choose the place in the initial circle so that you survive (are the last one remaining)." -- Wikipedia, http://en.wikipedia.org/wiki/Josephus problem Assume that the number of people in the circle may be any number between zero and one hundred. Assume that every Nth person around the circle is killed each turn, where N is an integer between one and twenty. Specifications: • Create an application in Java that uses a linked list to represent the circle of people, numbered from 1 to numberOfPeople. • Get the number of people and the skip value from the user via console input. Output the number of the individual that survives the mass execution. • Make sure you indicate if your skip value is inclusive or exclusive in your output. Inclusive: n 3-X0 0X00X ■ Every third person is killed with 2 skipped between 。 Exclusive: n-3-X000X000X Sample Output: ■ 3 people are skipped and the next is executed Welcome to the Josephus Problem. How many people in the circle (1100)? 5 Enter the number of people to skip between eliminations: 2 Running: Initial puzzle: 1-2-3-4-5 Eliminated #3 Remaining: 1-2-4-5 Eliminated #1 Remaining: 24-5 Eliminated #5 Remining: 2 - 4 Eliminated #2 Survivor: 4 Sample to help debug (note -inclusive, above example would be n = 5 and k = 3): https://www.geogebra.org/m/ExvvrBbR
Expert Answer:
Answer rating: 100% (QA)
Here is the completed code for this problem LinkedListjava LinkedList class public class LinkedList pointers to head and tail of the list private Node head private Node tail current size private int s... View the full answer
Related Book For
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer
Posted Date:
Students also viewed these programming questions
-
developing the Singly-Linked LinkedList data structure, which will implement the provided List interface. In doing so, you will writea variety of methods from each. You will also be creating your own...
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
Write a recursive program to draw plasma clouds, using the method suggested in the text.
-
The following information is available for Canadian Tire Corporation (in $ millions): ______________________2015_________2014_________2013 Inventory.............$ 1,764.5............$...
-
Indicate the impact of the following on the cash and operating cycles, respectively. Use the letter I to indicate an increase, the letter D for a decrease, and the letter N for no change. a. The...
-
By using six factor formula for \(k\), derive the Eqs. (7.93), (7.94) of Section 7.7.1. dkoo dp= k MB dM dB 8 + (7.93) 1+M B M B2
-
Analyze each transaction listed in the table that follows and place X's in the appropriate columns to indicate the transaction's classification and its effect on cash flows using the indirectmethod....
-
2. (24 Points) Find out the number of real roots of the cubic equation 23-6x+1=0. Justify your answer.
-
A small rock with mass 0.10 kg is released from rest at point. A, which is at the top edge of a large, hemispherical bowl with radius R=0.60 m (the figure (Figure 1)). Assume that the size of the...
-
Examine the economy of a low-income country (Afghanistan, Bangladesh, North Korea, Ukraine, etc.). Basic information such as location, population, industries, finance, climate, income, and a brief...
-
Competitive Product Markets Assume that markets are efficient, and that investment firms have decided to retire all portfolio managers and financial analysts, letting random choice via a computer...
-
Konyagi plc has an average daily cash balance of 10,500. Total cash needed for the year is 65,000. The interest rate is 3 per cent, and replenishing the cash costs 17 each time. What are the...
-
You have been hired to value a new 25-year callable, convertible bond. The bond has a 6.80 per cent coupon rate, payable annually. The conversion price is 150, and the equity currently sells for...
-
Efficient Markets Since 2005, all publicly listed European companies follow International Accounting Standards. This means that financial statements are based largely on market values instead of...
-
Vedant plc disburses cheques every 2 weeks that average 370,000 and take 7 days to clear. How much interest can the company earn annually if it delays transfer of funds from an interest-bearing...
-
What are the factors that compel a person to change his or her citizenship?
-
Repeat Exercise 16.6 using the t-test of the coefficient of correlation. Is this result identical to the one you produced in Exercise 16.6?
-
Implement the MemManager ADT shown at the beginning of Section 12.3. Do not use separate memory for the free list, but instead embed the free list into the memory pool as shown in Figure 12.12. Your...
-
Imagine that you are designing an application where you need to perform the operations Insert, Delete Maximum, and Delete Minimum. For this application, the cost of inserting is not important,...
-
Section 5.1 .1 claims that a full binary tree has the highest number of leaf nodes among all trees with n internal nodes. Prove that this is true. 5.1.1 The Full Binary Tree Theorem Some binary tree...
-
Consider a strictly increasing and strictly concave utility function \(u\) and suppose that there exist \(N\) risky assets whose returns \(\left(\tilde{r}_{1}, \ldots, \tilde{r}_{N} ight)\) admit the...
-
Given an arbitrary frontier portfolio \(w^{*}\), with \(w^{*} eq w^{\mathrm{MVP}}\), there exists a unique frontier portfolio \(w^{\mathrm{zc}}\) such that...
-
Consider a strictly increasing and strictly concave utility function \(u\) and suppose that there exist a risk free asset with return \(r_{f}>0\) and \(N\) risky assets whose returns...
Study smarter with the SolutionInn App