Løsningsforslag
Fra Hiofwiki
Innhold |
[rediger]
Gruppe X
Her følger mitt løsningsforslag:
[rediger]
Oppgave 5.1
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package algdat;
/**
*
* @author Lars Emil
*/
public class CircularQueue
{
private static final int DEFAULT_CAPACITY = 16;
E[] tabell = (E[]) new Comparable[DEFAULT_CAPACITY];
int forste = 0;
int nummer = 0;
public void enqueue(E element)
{
if(forste+nummer >= size())
{
if(nummer == size())
{
E[] tempArray = (E[]) new Comparable[tabell.length+DEFAULT_CAPACITY];
int temp = forste;
for(int i = 0; i < tabell.length; i++)
{
if(temp == size())
temp = 0;
tempArray[i] = tabell[temp];
temp++;
}
tabell = tempArray;
forste = 0;
tabell[forste+nummer] = element;
}
else
{
tabell[(forste+nummer)-size()] = element;
}
}
else
{
tabell[forste+nummer] = element;
}
nummer++;
}
public E dequeue()
{
if(isEmpty())
{
throw new UnderflowException("CircularQueue dequeue. The tabell is empty!");
}
E tmp = tabell[forste];
if(forste == size()-1 || nummer == 1)
{
forste = 0;
nummer--;
}
else
{
forste++;
nummer--;
}
return tmp;
}
public E forste()
{
return tabell[forste];
}
public boolean isEmpty()
{
return (nummer == 0);
}
public int size()
{
return tabell.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 nummerAvBilerN = 0, nummerAvBilerE = 0, nummerAvBilerS = 0, nummerAvBilerV = 0;
int totalnummerAvBilerN = 0, totalnummerAvBilerE = 0, totalnummerAvBilerS = 0, totalnummerAvBilerV = 0;
int totalTidN = 0, totalTidE = 0, totalTidS = 0, totalTidV = 0;
int maxQN = 0, maxQE = 0, maxQS = 0, maxQV = 0;
int ventN = 0, ventE = 0, ventS = 0, ventV = 0;
int nesteBilN = 0, nesteBilE = 0,nesteBilS = 0,nesteBilV = 0, nextLight = 0;
boolean vei = true;
CircularQueue<Integer> bilQN = new CircularQueue<Integer>();
CircularQueue<Integer> bilQE = new CircularQueue<Integer>();
CircularQueue<Integer> bilQS = new CircularQueue<Integer>();
CircularQueue<Integer> bilQV = new CircularQueue<Integer>();
Random generator = new Random();
for(int time = 0; time < MAX_TIME; time++)
{
if(nesteBilN == 0)
{
bilQN.enqueue(time);
nummerAvBilerN++;
totalnummerAvBilerN++;
if(maxQN<nummerAvBilerN)
{
maxQN++;
}
nesteBilN = generator.nextInt(ARRIVAL_MAIN)+1;
}
if(nesteBilS == 0)
{
bilQS.enqueue(time);
nummerAvBilerS++;
totalnummerAvBilerS++;
if(maxQS<nummerAvBilerS)
{
maxQS++;
}
nesteBilS = generator.nextInt(ARRIVAL_MAIN)+1;
}
if(nesteBilE == 0)
{
bilQE.enqueue(time);
nummerAvBilerE++;
totalnummerAvBilerE++;
if(maxQE<nummerAvBilerE)
{
maxQE++;
}
nesteBilE = generator.nextInt(ARRIVAL_SIDE)+1;
}
if(nesteBilV == 0)
{
bilQV.enqueue(time);
nummerAvBilerV++;
totalnummerAvBilerV++;
if(maxQV<nummerAvBilerV)
{
maxQV++;
}
nesteBilV = generator.nextInt(ARRIVAL_SIDE)+1;
}
nesteBilN--;
nesteBilS--;
nesteBilE--;
nesteBilV--;
if(vei)
{
if(!bilQN.isEmpty() && time > ventN)
{
totalTidN += (time - bilQN.dequeue());
nummerAvBilerN--;
ventN = time+1;
}
if(!bilQS.isEmpty() && time > ventS)
{
totalTidS += (time - bilQS.dequeue());
nummerAvBilerS--;
ventS = time+1;
}
if(nextLight == 0)
{
vei = false;
nextLight = LIGHT_TIME_SIDE_ROAD;
}
}
else
{
if(!bilQE.isEmpty() && time > ventE)
{
totalTidE += (time - bilQE.dequeue());
nummerAvBilerE--;
ventE = time+1;
}
if(!bilQV.isEmpty() && time > ventV)
{
totalTidV += (time - bilQV.dequeue());
nummerAvBilerV--;
ventV = time+1;
}
if(nextLight == 0)
{
vei = 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 " + totalnummerAvBilerN + "\n" +
" | |\n" +
"_____| |_____\n" +
totalnummerAvBilerV + " " +totalnummerAvBilerE + "\n" +
"_____ _____\n" +
" | | \n" +
" | |\n" +
" " + totalnummerAvBilerS);
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 " + totalTidN/totalnummerAvBilerN + "\n" +
" | |\n" +
"_____| |_____\n" +
totalTidV/totalnummerAvBilerV + " " + totalTidE / totalnummerAvBilerE + "\n" +
"_____ _____\n" +
" | | \n" +
" | |\n" +
" " + totalTidS/totalnummerAvBilerS);
}
}
[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>[] digitKoer = (CircularQueue<Integer>[])(new CircularQueue[10]);
for(int i = 0; i <= 5; i++)
digitKoer[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);
digitKoer[digit].enqueue(new Integer(list[j]));
}
nummer = 0;
for(int j = 0; j<= 5; j++)
{
while(!(digitKoer[j].isEmpty()))
{
numObj = digitKoer[j].dequeue();
list[nummer] = numObj.intValue();
nummer++;
}
}
}
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();
}
}
