Løsningsforslag 5
Fra Hiofwiki
Innhold |
[rediger]
Gruppe 118
Beklager hvis det er litt uoversiktlig.
Jeg skal prøve å få lagt inn noen komentarer etterhvert.
[rediger]
Oppgave 5.1
/**
*
* @author Lars Emil
*/
public class CircularQueue <E extends Comparable<? super E>> implements Queue<E>
{
private static final int DEFAULT_CAPACITY = 16;
E[] array = (E[]) new Comparable[DEFAULT_CAPACITY];
int first = 0;
int num = 0;
public void enqueue(E element)
{
if(first+num >= size())
{
if(num == size())
{
E[] tempArray = (E[]) new Comparable[array.length+DEFAULT_CAPACITY];
int temp = first;
for(int i = 0; i < array.length; i++)
{
if(temp == size())
temp = 0;
tempArray[i] = array[temp];
temp++;
}
array = tempArray;
first = 0;
array[first+num] = element;
}
else
{
array[(first+num)-size()] = element;
}
}
else
{
array[first+num] = element;
}
num++;
}
public E dequeue()
{
if(isEmpty())
{
throw new UnderflowException("CircularQueue dequeue. The array is empty!");
}
E tmp = array[first];
if(first == size()-1 || num == 1)
{
first = 0;
num--;
}
else
{
first++;
num--;
}
return tmp;
}
public E first()
{
return array[first];
}
public boolean isEmpty()
{
return (num == 0);
}
public int size()
{
return array.length;
}
}
public class UnderflowException extends RuntimeException
{
public UnderflowException( String message ) {
super(message);
}
}
[rediger]
Oppgave 5.2
/**
*
* @author Lars Emil
*/
import java.util.Random;
public class Oppgave2 {
static final int MAX_TIME = 7200;
static final int LIGHT_TIME_MAIN_ROAD = 250;
static final int LIGHT_TIME_SIDE_ROAD = 150;
static final int ARRIVAL_MAIN = 20;
static final int ARRIVAL_SIDE = 40;
public static void main(String[] args)
{
int numberOfCarsN = 0, numberOfCarsE = 0, numberOfCarsS = 0, numberOfCarsV = 0;
int totalNumberOfCarsN = 0, totalNumberOfCarsE = 0, totalNumberOfCarsS = 0, totalNumberOfCarsV = 0;
int totalTimeN = 0, totalTimeE = 0, totalTimeS = 0, totalTimeV = 0;
int maxQN = 0, maxQE = 0, maxQS = 0, maxQV = 0;
int waitN = 0, waitE = 0, waitS = 0, waitV = 0;
int nextCarN = 0, nextCarE = 0,nextCarS = 0,nextCarV = 0, nextLight = 0;
boolean road = true;
CircularQueue<Integer> carQN = new CircularQueue<Integer>();
CircularQueue<Integer> carQE = new CircularQueue<Integer>();
CircularQueue<Integer> carQS = new CircularQueue<Integer>();
CircularQueue<Integer> carQV = new CircularQueue<Integer>();
Random generator = new Random();
for(int time = 0; time < MAX_TIME; time++)
{
if(nextCarN == 0)
{
carQN.enqueue(time);
numberOfCarsN++;
totalNumberOfCarsN++;
if(maxQN<numberOfCarsN)
{
maxQN++;
}
nextCarN = generator.nextInt(ARRIVAL_MAIN)+1;
}
if(nextCarS == 0)
{
carQS.enqueue(time);
numberOfCarsS++;
totalNumberOfCarsS++;
if(maxQS<numberOfCarsS)
{
maxQS++;
}
nextCarS = generator.nextInt(ARRIVAL_MAIN)+1;
}
if(nextCarE == 0)
{
carQE.enqueue(time);
numberOfCarsE++;
totalNumberOfCarsE++;
if(maxQE<numberOfCarsE)
{
maxQE++;
}
nextCarE = generator.nextInt(ARRIVAL_SIDE)+1;
}
if(nextCarV == 0)
{
carQV.enqueue(time);
numberOfCarsV++;
totalNumberOfCarsV++;
if(maxQV<numberOfCarsV)
{
maxQV++;
}
nextCarV = generator.nextInt(ARRIVAL_SIDE)+1;
}
nextCarN--;
nextCarS--;
nextCarE--;
nextCarV--;
if(road)
{
if(!carQN.isEmpty() && time > waitN)
{
totalTimeN += (time - carQN.dequeue());
numberOfCarsN--;
waitN = time+1;
}
if(!carQS.isEmpty() && time > waitS)
{
totalTimeS += (time - carQS.dequeue());
numberOfCarsS--;
waitS = time+1;
}
if(nextLight == 0)
{
road = false;
nextLight = LIGHT_TIME_SIDE_ROAD;
}
}
else
{
if(!carQE.isEmpty() && time > waitE)
{
totalTimeE += (time - carQE.dequeue());
numberOfCarsE--;
waitE = time+1;
}
if(!carQV.isEmpty() && time > waitV)
{
totalTimeV += (time - carQV.dequeue());
numberOfCarsV--;
waitV = time+1;
}
if(nextLight == 0)
{
road = true;
nextLight = LIGHT_TIME_MAIN_ROAD;
}
}
nextLight--;
}
System.out.println("Ankomstfrekvens hovedvei: " + 0 + "-" + ARRIVAL_MAIN + "sek");
System.out.println("Ankomstfrekvens sidedvei: " + 0 + "-" + ARRIVAL_SIDE + "sek");
System.out.println("Lysskifte-frekvens hovedvei: " + LIGHT_TIME_MAIN_ROAD + "sek");
System.out.println("Lysskifte-frekvens hovedvei: " + LIGHT_TIME_SIDE_ROAD + "sek");
System.out.println("--------------------");
System.out.println("Totalt antall biler: " + "\n " + totalNumberOfCarsN + "\n" +
" | |\n" +
"_____| |_____\n" +
totalNumberOfCarsV + " " +totalNumberOfCarsE + "\n" +
"_____ _____\n" +
" | | \n" +
" | |\n" +
" " + totalNumberOfCarsS);
System.out.println("--------------------");
System.out.println("Max antall biler i kø: " + "\n " + maxQN + "\n" +
" | |\n" +
"_____| |_____\n" +
maxQV + " " +maxQE + "\n" +
"_____ _____\n" +
" | | \n" +
" | |\n" +
" " + maxQN);
System.out.println("--------------------");
System.out.println("Gjennomsnittlig ventetid: " + "\n " + totalTimeN/totalNumberOfCarsN + "\n" +
" | |\n" +
"_____| |_____\n" +
totalTimeV/totalNumberOfCarsV + " " + totalTimeE / totalNumberOfCarsE + "\n" +
"_____ _____\n" +
" | | \n" +
" | |\n" +
" " + totalTimeS/totalNumberOfCarsS);
}
}
[rediger]
Oppgave 5.3
/**
*
* @author Lars Emil
*/
public class Oppgave3 {
public static void main(String[] args) {
int [] list = {2452, 1230, 5441, 4200, 2345, 4315};
String temp;
Integer numObj;
int digit, num;
CircularQueue<Integer>[] digitQueues = (CircularQueue<Integer>[])(new CircularQueue[10]);
for(int i = 0; i <= 5; i++)
digitQueues[i] = new CircularQueue<Integer>();
for(int i = 0; i <= 3; i++)
{
for(int j = 0; j < list.length; j++)
{
temp = String.valueOf(list[j]);
digit = Character.digit (temp.charAt(3-i), 10);
digitQueues[digit].enqueue(new Integer(list[j]));
}
num = 0;
for(int j = 0; j<= 5; j++)
{
while(!(digitQueues[j].isEmpty()))
{
numObj = digitQueues[j].dequeue();
list[num] = numObj.intValue();
num++;
}
}
}
for(int i = 0; i < list.length; i++)
System.out.println(list[i]);
}
}
[rediger]
Oppgave 5.4
/**
*
* @author Lars Emil
*/
public class SortertListe<T extends Comparable<? super T>> {
private Node<T> start;
private int antall;
public int hentAntall()
{
return antall;
}
/**
* Fjerner og returnerer minste verdi i listen
* @return minste verdi i listen
*/
public T fjernMinste(){
T minste;
minste = start.verdi;
start = start.neste;
antall--;
return minste;
}
/**
* Skriver listen i stigende rekkefølge
*/
public void skriv() {
Node<T> skrivUt = start;
for(int i = 0; i < antall; i++)
{
System.out.println(skrivUt.verdi);
skrivUt = skrivUt.neste;
}
}
/**
* Lars sin med while
*/
public void skriv()
{
Node<T> node = start;
while(node != null)
{
System.out.println(node.verdi);
node = node.neste;
}
}
/**
* Setter inn en ny verdi på riktig plass i den lenkede listen
* @param verdi verdien som skal settes inn
*/
public void settInn(T verdi){
Node<T> node;
node = start;
boolean lagtTil = false;
if(verdi.compareTo(node.verdi) > 0)
{
Node<T> nynode = new Node(verdi, start);
start = nynode;
lagtTil = true;
}
while(node.neste != null && !lagtTil)
{
if(verdi.compareTo(node.neste.verdi) < 0)
{
Node<T> nynode = new Node(verdi, node.neste);
node.neste = nynode;
lagtTil = true;
}
}
if(!lagtTil)
{
node.neste = new Node(verdi, null);
}
antall++;
}
/**
* Fletter denne listen sammen med listen gitt som parameter
* og returnerer resultatet som en ny SortertListe
* @return ny Ny SortertListe
*/
public SortertListe<T> flett(SortertListe<T> l){
Node<T> node = l.start;
Node<T> node2 = start;
SortertListe<T> nyliste = new SortertListe<T>();
Node<T> nynode = nyliste.start;
while(node != null && node2 != null)
{
if(node.verdi.compareTo(node2.verdi) < 0)
{
nynode.neste = new Node(node.verdi, null);
node = node.neste;
}
else
{
nynode.neste = new Node(node.verdi, null);
node2 = node2.neste;
}
}
return nyliste;
}
/**
* Lars sin
*/
public SortertListe<T> flett(SortertListe<T> liste)
{
Node<T> node1 = l.start;
Node<T> node2 = start;
Node<T> nynode = new Node(null, null);
SortertListe<T> nyliste = new SortertListe<T>();
nyliste.start = nynode;
while(node1 != null || node2 != null)
{
nynode.neste = new Node(null, null);
if(node2 == null || node1.verdi.compareTo(node2.verdi) < 0)
{
nynode.verdi = node1.verdi;
node1 = node1.neste;
}
else if(node1 == null || node2.verdi.compareTo(node1.verdi) < 0)
nynode.verdi = node2.verdi;
node2 = node2.neste;
}
nynode = nynode.neste;
}
return nyliste
}
/**
* Klassen Node representerer en node i den lenkede listen
*/
private class Node<T>
{
private T verdi;
private Node<T> neste;
public Node(T verdi, Node<T> neste)
{
this.verdi = verdi;
this.neste = neste;
}
}// slutt class Node
}//slutt class SortertListe
/**
*
* @author Lars Emil
*/
public class ListePrioritetsQueue<T extends Comparable<? super T>> implements PrioritetsQueue<T>{
SortertListe<T> liste;
public void settInn(T verdi)
{
liste.settInn(verdi);
}
public T taUt()
{
return liste.fjernMinste();
}
public int antall()
{
return liste.hentAntall();
}
}
