Java Assignment Help

[nve5009]

Hi,
I've been trying to figure out this problem for a while, but I am completely stumped. I have to do the following.

Farey fractions of level one are defined as sequence ( 0/1, 1/1). This sequence is extended in level two to form a sequence (0/1, 1/2, 1/1), sequence (0/1, 1/3, 1/2, 2/3, 1/1) at level three, sequence (0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1) at level four, so that each level n, a new fraction a + b / c + d is inserted between two neighbor fractions a/c and b/d only if c + d <= n. Write a program which for a number n entered by the user creates--by constantly extending it-- a linked list of fractions at level n and then displays them.

I have the following classes

Fraction Class:

public class Fraction 
{

	  int numerator;
	  int denominator;
	  public Fraction(int num, int den) 
	  {    
	    numerator = num;
	    denominator = den;
	  }
	  
	  //Outputs the fraction using the toString method.
	  public String toString()
		{
			return numerator + "/" + denominator;	
		}
	  
	  public int getNumerator()
		{
			return numerator;
		}
		
		//Stores the denominator
		public int getDenominator()
		{
			return denominator;
		}	
	  
	  //Calculates if the two fractions are equal using cross multiplication.
		public boolean equal(Fraction other)
		{
			if ((denominator * other.numerator) == (other.denominator * numerator))
				return true;
			else 
				return false;
		}
		
	 
}

Farey Class:

import java.util.Scanner;

public class Farey extends SLL <Fraction>
{
	
	public static void main(String[] args) 
	{
		int a, b, c, d;
		
		Scanner scan = new Scanner(System.in);
		System.out.println("Please enter the number of levels."); 
		int n = scan.nextInt();
	   
		
		System.out.println(n); 
		    
	    Fraction first = new Fraction(0, 1);
	    Fraction second = new Fraction(1, 1);

		SLLNode<Fraction> tmp = new SLLNode<Fraction>(null);
	    SLLNode<Fraction> p = new SLLNode<Fraction>(first);
	    p.next = new SLLNode(second);
		    
	    SLL<Fraction> list = new SLL<Fraction>();
	    list.addToHead(p.next.info);
	    list.addToHead(p.info);
		    
	    list.printAll();
	    //System.out.println(p.info.toString() + ", " + p.next.info.toString()); 
	
	
		
	    while (p.info != null)
	    {
	    	if (p.info.denominator != n - 1)
	    		{
	    		tmp = new SLLNode<Fraction>(list.deleteFromTail());
	    		}
	    	else if (p.info.denominator == n - 1 && p.info.numerator == 1)
	    	{
	    		
	    		
	    	}
	    		
	    		
	    }
	    
	    
	}

}

SLL Class:

public class SLL<T> {
    protected SLLNode<T> head, tail;
    public SLL() {
        head = tail = null;
    }
    public boolean isEmpty() {
        return head == null;
    }
    public void addToHead(T el) {
        head = new SLLNode<T>(el,head);
        if (tail == null)
            tail = head;
    }
    public void addToTail(T el) {
        if (!isEmpty()) {
            tail.next = new SLLNode<T>(el);
            tail = tail.next;
        }
        else head = tail = new SLLNode<T>(el);
    }
    public T deleteFromHead() { // delete the head and return its info; 
        if (isEmpty()) 
             return null;
        T el = head.info;
        if (head == tail)       // if only one node on the list;
             head = tail = null;
        else head = head.next;
        return el;
    }
    public T deleteFromTail() { // delete the tail and return its info;
        if (isEmpty()) 
             return null;
        T el = tail.info;
        if (head == tail)       // if only one node in the list;
             head = tail = null;
        else {                  // if more than one node in the list,
             SLLNode<T> tmp;    // find the predecessor of tail;
             for (tmp = head; tmp.next != tail; tmp = tmp.next);
             tail = tmp;        // the predecessor of tail becomes tail;
             tail.next = null;
        }
        return el;
    }
    public void delete(T el) {  // delete the node with an element el;
        if (!isEmpty())
            if (head == tail && el.equals(head.info)) // if only one
                 head = tail = null;       // node on the list;
            else if (el.equals(head.info)) // if more than one node on the list;
                 head = head.next;    // and el is in the head node;
            else {                    // if more than one node in the list
                 SLLNode<T> pred, tmp;// and el is in a nonhead node;
                 for (pred = head, tmp = head.next;  
                      tmp != null && !tmp.info.equals(el); 
                      pred = pred.next, tmp = tmp.next);
                 if (tmp != null) {   // if el was found;
                     pred.next = tmp.next;
                     if (tmp == tail) // if el is in the last node;
                        tail = pred;
                 }
            }
    }
    public void printAll() {
        for (SLLNode<T> tmp = head; tmp != null; tmp = tmp.next)
            System.out.print(tmp.info + ", ");                
    }
    public boolean isInList(T el) {
        SLLNode<T> tmp;
        for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next);
        return tmp != null;
    }
}

SLLNode Class:

public class SLLNode<T> {
    public T info;
    public SLLNode<T> next;
    public SLLNode() {
        this(null,null);
    }
    public SLLNode(T el) {
        this(el,null);
    }
    public SLLNode(T el, SLLNode<T> ptr) {
        info = el; next = ptr;
    }
}

The main class is the farey one. Ignore most of the code in that class, I was just making sure it was functional. The part I'm confused with is if the user inputs a large n, I would need to have to use p.next.next...next. I am missing a simpler way with dealing with this? I'm not really sure where to go from here. We are not supposed to change the SLL or SLLNode classes.

Thank you

[pbrockway2]

Are you required to extend (in the Java sense) SLL<T>? It seems more natural to define a fraction class and declare the farey sequence to be an instance of SLL<Fraction>.

public static void main(String[] args)
{
SLL<Fraction> farey = ...

(I would also hold off making the Fraction class more elaborate than a constructor and a couple of getters. Or I might investigate to see if the equals() method is needed or if these things are just ordered pairs.)

The next thing to work on would be code to move from one level to the next.

    /**
     * Takes a given farey sequence and returns a new one which is one level higher.
     */
private static SLL<Fraction> upLevel(SLL<Fraction> farey)
{
    // code here
}

Such a method could be used inside a loop of some sort to arrive - finally - at some level n.

At the heart of this method is the abililty to work along the list working on the elements one at a time. So, eg, if the list had 5 elements

* read the first element and write it to the sequence to be returned
* read the second. Does a new element need to be inserted (ie appended)? If so, do it. Then write the second element itself.
* read the third. Does a new element need to be inserted (ie appended)? If so, do it. Then write the third element itself.
* read the fourth. Does a new element need to be inserted (ie appended)? If so, do it. Then write the fourth element itself.
* read the fifth. Does a new element need to be inserted (ie appended)? If so, do it. Then write the fifth element itself.
* Observe that there is no next element. So return the new sequence that has been constructed.

Clearly some sort of loop process is involved in "walking along" the given sequence in this way. The implementation of this will not involve p.next.next.next... Rather it will resemble the for loop that the SLL itself uses to printAll().

----------

Anyway that's how I would attack this problem given that you can't change the SLL to make it more Java-like. Ie have it provide a straightforward method to iterate through the list and a way to insert elements, and remove the printAll() behaviour and the public node class.

[nve5009]

Thanks for the reply.

Yes we're supposed to use inheritance and include the "class farey extends SLL<Fraction>" statement. The way I was thinking of doing this was to create a temporary SLL and deleting the original then recreating the original adding to head and inserting the necessary new fractions where needed. However, I'm not sure how I would find where the new fractions would be placed without using many .next.next... functions. Would your solution work if using inheritance is necessary. :confused:

Thanks again!

[pbrockway2]

Would your solution work if using inheritance is necessary

It could be used in that context. But the context really is crazy: imagine how many classes there would have to be if every sequence imaginable were to have its own list subclass in this way...

The only difference I can see is that upLevel() would no longer be static and would no longer be passed an SLL<Fraction> argument. Instead it would work along its own contents.

As you say you would create a new temporary SLL<Fraction> (that's what I intended before). At the end of upLevel() the list's head and tail would be set equal to the temporary list's head and tail. This would effectively "copy" the temporary list's contents.

I'm repeating myself but the printAll() implementation provides an example of list traversal without having to go .next.next.next.etc from the head. upLevel() would involve a similar for loop: appending new list elements whereever they were needed.

[nve5009]

OK I think I understand what to do now. Thanks again for all your help.