Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).
Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.
Skiladagur: þriðjudaginn 28. febrúar fyrir kl 16:00
Útfærið counting sort með hjálp fylkis sem telur tíðni gilda.
public class CountingSort
{
// Notkun: csort(f, max);
// Fyrir: Allar tölur í f eru á bilinu [0,max]
// Eftir: Búið er að raða f í vaxandi röð
public static void csort(int[] f, int max)
{
}
public static void main(String[] args)
{
int[] f = {6,1,4,2,1,7,3,7,0,10,1};
int[] e = {0,1,1,1,2,3,4,6,7,7,10};
csort(f, 10);
for (int i = 0; i < f.length; i++)
{
System.out.println(f[i]);
if (f[i] != e[i])
{
System.out.printf("Test failed: expected %d got %d\n", e[i], f[i]);
return;
}
}
System.out.printf("Test passed.\n");
}
}
#include <stdio.h>
#define NELEMS(x) (sizeof(x) / sizeof(x[0]))
// Notkun: csort(f, n, max);
// Fyrir: Allar tölur í f[0..n-1] eru á bilinu [0,max]
// Eftir: Búið er að raða f[0..n-1] í vaxandi röð
void csort(int *f, int n, int max)
{
// ...
}
int main(void)
{
int f[] = {6,1,4,2,1,7,3,7,0,10,1};
int e[] = {0,1,1,1,2,3,4,6,7,7,10};
int i;
csort(f, NELEMS(f), 10);
for (i = 0; i < NELEMS(f); i++)
{
printf("%d\n", f[i]);
if (f[i] != e[i])
{
printf("Test failed: expected %d got %d\n", e[i], f[i]);
return 1;
}
}
printf("Test passed.\n");
return 0;
}
Útfærið fall fyrir radix sort fyrir heiltölur með hjálp biðraða. Biðraðaútfærslu má finna hér fyrir neðan. Röðunarfallið skal taka eina biðröð sem viðfang og þegar snúið er til baka skal sú biðröð vera í vaxandi röð.
Útfærslan skal virka þannig að farnar eru nokkrar umferðir í lykkju, ein umferð fyrir hvern mögulegan tölustaf í inntaksgildunum frá hægri til vinstri. Þið megið gefa ykkur þá forsendu að gildin séu milli 0 og 999.
Í hverri umferð lykkjunnar gerið þið eftirfarandi:
Í lykkjunni þá er aðalbiðröðin (sú sem var tekin inn sem viðfang) tæmd yfir í 10 biðraðir eftir gildi tölustafsins sem er undir skoðun og síðan eru þær biðraðir tæmdar yfir í aðalbiðröðina aftur (og þá er búið að koma tölunum í röð skv. næsta tölustaf, enda eru biðraðirnar tæmdar í röð, þ.a. fyrst er q[0] tæmd, sem inniheldur 0-tölustaf í því sæti sem er undir skoðun, svo q[1], etc).
Forritið skal innihalda prófunarforrit í main sem raðar 10000 slembigildum og athugar hvort niðurstaðan er í réttri röð. Forritið skal síðan skrifa "Test passed" ef rétt er raðað, en annars "Test failed".
Þið megið leysa verkefnið í C eða Java. Skrifið notkunarlýsingu fyrir radix sort fallið ykkar og skrifið fastayrðingu fyrir sérhverja lykkju í radix sort fallinu.
import java.util.Random;
public class RadixSort
{
// Notkun: rsort(q);
// Fyrir: ???
// Eftir: Búið er að raða q í vaxandi röð
@SuppressWarnings("unchecked")
public static void rsort(Queue<Integer> q)
{
Queue<Integer>[] r = new Queue[10];
for (int i = 0; i < 10; i++)
r[i] = new Queue<Integer>();
// ...
}
// Notkun: b = isSorted(q);
// Fyrir: Ekkert
// Eftir: b er satt þþaa. ef q var í vaxandi röð.
// Ef b er satt þá er q jafnframt tóm, en
// ef b er ósatt þá er innihald q óskilgreint.
public static boolean isSorted(Queue<Integer> q)
{
if (q.isEmpty())
return true;
int last = q.get();
while (!q.isEmpty())
{
int x = q.get();
if (x < last)
return false;
last = x;
}
return true;
}
public static void main(String[] args)
{
Random g = new Random();
Queue<Integer> q = new Queue<Integer>();
for (int i = 0; i < 10000; i++)
q.put(g.nextInt(1000));
rsort(q);
if (isSorted(q))
System.out.println("Test passed");
else
System.out.println("Test failed");
}
}
public class test
{
public static void main(String[] args)
{
int a = 123;
int v = 1;
for (int n = 0; n != 3; n++)
{
// v = 10^n
// Búið er að prenta út síðustu n tölustafi
// tölunnar a.
// 0 <= n <= 3.
int d = (a/v)%10;
System.out.println(d);
v *= 10;
}
}
}
public class Queue<T>
{
// Biðröðin inniheldur n gildi.
// Gildin eru í hringlista þar sem last bendir
// á aftasta hlekk, aftasti hlekkur bendir
// fremsta hlekk, sem bendir aftur á næstfremsta
// og svo koll af kolli. Ef biðröðin er tóm þá
// er last == null (og n==0 einnig, að sjálfsögðu).
private Node last;
private int n;
private class Node
{
private T value;
private Node next;
}
// Notkun: q = new Queue<T>();
// Fyrir: Ekkert
// Eftir: q er ný tóm biðröð gilda af tagi T
public Queue()
{
last = null;
n = 0;
}
// Notkun: b = q.isEmpty();
// Fyrir: Ekkert
// Eftir: b er satt þþaa. q er tóm
public boolean isEmpty()
{
return last == null;
}
// Notkun: n = q.count();
// Fyrir: Ekkert
// Eftir: n er fjöldi gilda í q
public int count()
{
return n;
}
// Notkun: x = q.peek();
// Fyrir: q er ekki tóm
// Eftir: x er stakið sem er fremst í q
public T peek()
{
return last.next.value;
}
// Notkun: q.put(x);
// Fyrir: Ekkert
// Eftir: Búið er að bæta x aftast í q
public void put(T value)
{
Node p = new Node();
p.value = value;
if (last == null)
p.next = p;
else
{
p.next = last.next;
last.next = p;
}
last = p;
n++;
}
// Notkun: x = q.get();
// Fyrir: q er ekki tóm
// Eftir: Búið er að fjarlægja fremsta
// gildið úr q og það er x.
public T get()
{
T value = last.next.value;
if (last.next == last)
last = null;
else
last.next = last.next.next;
n--;
return value;
}
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "queue.h"
// Notkun: rsort(q);
// Fyrir: ???
// Eftir: Búið er að raða q í vaxandi röð
void rsort(struct queue *q)
{
struct queue r[10];
int i;
for (i = 0; i < 10; i++)
queue_init(&r[i]);
// ...
}
// Notkun: b = isSorted(q);
// Fyrir: Ekkert
// Eftir: b er satt þþaa. ef q var í vaxandi röð.
// Ef b er satt þá er q jafnframt tóm, en
// ef b er ósatt þá er innihald q óskilgreint.
int is_sorted(struct queue *q)
{
if (queue_empty(q))
return 1;
int last = queue_get(q);
while (!queue_empty(q))
{
int x = queue_get(q);
if (x < last)
return 0;
last = x;
}
return 1;
}
int main(void)
{
struct queue q;
int i;
srand(time(NULL));
queue_init(&q);
for (i = 0; i < 10000; i++)
queue_put(&q, rand() % 1000);
rsort(&q);
if (is_sorted(&q))
printf("Test passed\n");
else
printf("Test failed\n");
return 0;
}
#ifndef __QUEUE_H
#define __QUEUE_H
struct item
{
int value;
struct item *next;
};
struct queue
{
// Ef biðröðin er tóm þá er head==tail==null og n==0.
// Annars bendir head á hlekk (struct item) sem inniheldur
// fremsta gildið og last bendir á hlekk sem inniheldur aftasta
// gildið og milli þeirra eru hin gildin, tengd saman
// á hefðbundinn hátt fyrir eintengdan lista.
// Breytan n inniheldur ávallt fjölda gilda í listanum.
struct item *head;
struct item *tail;
int n;
};
extern void queue_init(struct queue *q);
extern void queue_put(struct queue *q, int value);
extern int queue_get(struct queue *q);
extern int queue_empty(struct queue *q);
extern int queue_count(struct queue *q);
extern int queue_peek(struct queue *q);
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"
void queue_init(struct queue *q)
{
q->head = NULL;
q->tail = NULL;
q->n = 0;
}
void queue_put(struct queue *q, int value)
{
struct item *p = malloc(sizeof(struct item));
p->value = value;
p->next = NULL;
if (q->tail == NULL)
q->head = p;
else
q->tail->next = p;
q->tail = p;
q->n++;
}
int queue_get(struct queue *q)
{
int value = q->head->value;
struct item *old = q->head;
q->head = q->head->next;
free(old);
if (q->head == NULL)
q->tail = NULL;
q->n--;
return value;
}
int queue_empty(struct queue *q)
{
return q->n == 0;
}
int queue_count(struct queue *q)
{
return q->n;
}
int queue_peek(struct queue *q)
{
return q->head->value;
}
Skrifið mergesort fyrir biðraðir í C eða Java. Þið fáið mergesort aðferðina sjálfa gefna, en þið eigið að útfæra aðferðirnar sem vantar í beinagrindina hér fyrir neðan (split og merge).
Sækið skrána ospd-random.txt sem inniheldur sömu gögn og ospd.txt skráin úr síðasta verkefni nema í handahófskenndri röð. Notið forritið til að raða gögnunum í henni (með shell redirection eins og er sýnt fyrir neðan) og athugið hvort úttakið sé í vaxandi röð.
hhg@hhg:~/t2/V7/d3$ java Mergesort < ospd-random.txt aa aah aahed aahing aahs aal aalii aaliis aals aardvark aardwolf [..] zymogram zymology zymosan zymosans zymoses zymosis zymotic zymurgy zyzzyva zyzzyvas hhg@hhg:~/t2/V7/d3$
import java.util.Scanner;
public class Mergesort
{
// Notkun: split(q,q1,q2);
// Fyrir: q1 og q2 eru tómar biðraðir, sem hver um sig
// hefur pláss fyrir helming gilda úr q (þ.e.
// fyrir (q.count()+1)/2 gildi).
// Eftir: Búið er að fjarlægja öll gildi úr q og setja
// helming þeirra í q1 og hinn helminginn í q2
// (það gæti munað einum í fjölda staka, ef
// fjöldinn er oddatala).
static public void split(Queue<String> q, Queue<String> q1, Queue<String> q2)
{
// ...
}
// Notkun: merge(q1,q2,q);
// Fyrir: q er tóm biðröð, q1 og q2 eru biðraðir, sem
// innihalda gildi, sem eru í vaxandi röð frá
// fremsta til aftasta.
// q hefur pláss fyrir öll gildin í q1 og q2.
// Eftir: q1 og q2 eru tómar, gildin úr þeim eru í q í
// vaxandi röð frá fremsta til aftasta.
static public void merge(Queue<String> q1, Queue<String> q2, Queue<String> q)
{
// ...
}
// Notkun: msort(q);
// Eftir: Búið er að raða gildunum í q í vaxandi röð
static public void msort(Queue<String> q)
{
if (q.count() < 2)
return;
Queue<String> q1 = new Queue<String>();
Queue<String> q2 = new Queue<String>();
split(q,q1,q2);
msort(q1);
msort(q2);
merge(q1,q2,q);
}
// Notkun: main(args);
// Fyrir: Aðalinntak inniheldur einungis strengi.
// Eftir: Búið er að lesa allar línur af aðalinntaki
// og skrifa þær í vaxandi röð á aðalúttak.
public static void main(String[] args)
{
Queue<String> q = new Queue<String>();
Scanner scan = new Scanner(System.in);
while (scan.hasNext())
{
q.put(scan.nextLine());
}
msort(q);
while (!q.isEmpty())
{
System.out.println(q.get());
}
}
}
public class Queue<T>
{
// Biðröðin inniheldur n gildi.
// Gildin eru í hringlista þar sem last bendir
// á aftasta hlekk, aftasti hlekkur bendir
// fremsta hlekk, sem bendir aftur á næstfremsta
// og svo koll af kolli. Ef biðröðin er tóm þá
// er last == null (og n==0 einnig, að sjálfsögðu).
private Node last;
private int n;
private class Node
{
private T value;
private Node next;
}
// Notkun: q = new Queue<T>();
// Fyrir: Ekkert
// Eftir: q er ný tóm biðröð gilda af tagi T
public Queue()
{
last = null;
n = 0;
}
// Notkun: b = q.isEmpty();
// Fyrir: Ekkert
// Eftir: b er satt þþaa. q er tóm
public boolean isEmpty()
{
return last == null;
}
// Notkun: n = q.count();
// Fyrir: Ekkert
// Eftir: n er fjöldi gilda í q
public int count()
{
return n;
}
// Notkun: x = q.peek();
// Fyrir: q er ekki tóm
// Eftir: x er stakið sem er fremst í q
public T peek()
{
return last.next.value;
}
// Notkun: q.put(x);
// Fyrir: Ekkert
// Eftir: Búið er að bæta x aftast í q
public void put(T value)
{
Node p = new Node();
p.value = value;
if (last == null)
p.next = p;
else
{
p.next = last.next;
last.next = p;
}
last = p;
n++;
}
// Notkun: x = q.get();
// Fyrir: q er ekki tóm
// Eftir: Búið er að fjarlægja fremsta
// gildið úr q og það er x.
public T get()
{
T value = last.next.value;
if (last.next == last)
last = null;
else
last.next = last.next.next;
n--;
return value;
}
}
#include <stdio.h>
#include <string.h>
#include "queue.h"
// Notkun: split(q,q1,q2);
// Fyrir: q1 og q2 eru tómar biðraðir, sem hver um sig
// hefur pláss fyrir helming gilda úr q (þ.e.
// fyrir (queue_count(q)+1)/2 gildi).
// Eftir: Búið er að fjarlægja öll gildi úr q og setja
// helming þeirra í q1 og hinn helminginn í q2
// (það gæti munað einum í fjölda staka, ef
// fjöldinn er oddatala).
static void split(struct queue *q, struct queue *q1, struct queue *q2)
{
// ...
}
// Notkun: merge(q1,q2,q);
// Fyrir: q er tóm biðröð, q1 og q2 eru biðraðir, sem
// innihalda gildi, sem eru í vaxandi röð frá
// fremsta til aftasta.
// q hefur pláss fyrir öll gildin í q1 og q2.
// Eftir: q1 og q2 eru tómar, gildin úr þeim eru í q í
// vaxandi röð frá fremsta til aftasta.
void merge(struct queue *q1, struct queue *q2, struct queue *q)
{
// ...
}
// Notkun: msort(q);
// Fyrir: Ekkert
// Eftir: Búið er að raða q í vaxandi röð
void msort(struct queue *q)
{
if (queue_count(q) < 2)
return;
struct queue q1;
struct queue q2;
queue_init(&q1);
queue_init(&q2);
split(q, &q1, &q2);
msort(&q1);
msort(&q2);
merge(&q1, &q2, q);
}
int main(void)
{
char line[4096];
struct queue q;
char *p;
queue_init(&q);
while (1)
{
if (fgets(line, sizeof(line), stdin) == NULL)
break;
if ((p = strchr(line, '\n')))
*p = 0;
queue_put(&q, strdup(line));
}
msort(&q);
while (!queue_empty(&q))
printf("%s\n", queue_get(&q));
return 0;
}
#ifndef __QUEUE_H
#define __QUEUE_H
struct item
{
char *value;
struct item *next;
};
struct queue
{
// Ef biðröðin er tóm þá er head==tail==null og n==0.
// Annars bendir head á hlekk (struct item) sem inniheldur
// fremsta gildið og last bendir á hlekk sem inniheldur aftasta
// gildið og milli þeirra eru hin gildin, tengd saman
// á hefðbundinn hátt fyrir eintengdan lista.
// Breytan n inniheldur ávallt fjölda gilda í listanum.
struct item *head;
struct item *tail;
int n;
};
extern void queue_init(struct queue *q);
extern void queue_put(struct queue *q, char *value);
extern char *queue_get(struct queue *q);
extern int queue_empty(struct queue *q);
extern int queue_count(struct queue *q);
extern char *queue_peek(struct queue *q);
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"
void queue_init(struct queue *q)
{
q->head = NULL;
q->tail = NULL;
q->n = 0;
}
void queue_put(struct queue *q, char *value)
{
struct item *p = malloc(sizeof(struct item));
p->value = value;
p->next = NULL;
if (q->tail == NULL)
q->head = p;
else
q->tail->next = p;
q->tail = p;
q->n++;
}
char *queue_get(struct queue *q)
{
char *value = q->head->value;
struct item *old = q->head;
q->head = q->head->next;
free(old);
if (q->head == NULL)
q->tail = NULL;
q->n--;
return value;
}
int queue_empty(struct queue *q)
{
return q->n == 0;
}
int queue_count(struct queue *q)
{
return q->n;
}
char *queue_peek(struct queue *q)
{
return q->head->value;
}
Gefið er svæði f[i..j-1] og tala s sem er sæti innan svæðisins. Skrifið fall í C eða Java sem skiptir fylkinu í tvö svæði þ.a.
f[i..k-1] <= f[k] <= f[k+1..j-1] f[k] er gildið sem var upphaflega í f[s]
Þá er búið að koma gildi í sæti k sem ætti heima þar ef fylkinu væri raðað. Þetta eina gildi er í sínu endanlega sæti, öll minni gildi (<=) eru í neðra svæðinu, f[i..k-1], í engri sérstakri röð, og öll stærri gildi (>=) eru í efra svæðinu, f[k+1..j-1], í engri sérstakri röð.
Notandi fallsins gefur upp svæði f[i..j-1] og sæti s með gildi til að skipta eftir. Fallið skilar að lokum nýju sæti k þar sem upphaflega f[s] gildið endaði eftir skiptinguna.
Fallið á að vera O(N) þar sem N er stærð svæðisins. Skrifið fastayrðingu fyrir sérhverja lykkju í partition fallinu.
import java.util.Random;
public class Partition
{
// Notkun: k = partition(f,i,j,s);
// Fyrir: f[i..j-1] er löglegt svæði í f,
// i <= s < j
// f[s] er pivot gildi til að skipta eftir
// Eftir: Búið er að víxla gildum í svæðinu þ.a.
// f[i..k-1] <= f[k] <= f[k+1..j-1]
// Gildið í sæti k var upphaflega í sæti s.
public static int partition(int[] f, int i, int j, int s)
{
}
private static void swap(int[] f, int a, int b)
{
int tmp = f[a];
f[a] = f[b];
f[b] = tmp;
}
// Notkun: b = is_partitioned(f,i,j,k)
// Fyrir: f[i..j-1] er svæði í fylkinu f, i <= k < j
// f[i..j-1] má vera óraðað.
// Eftir: b er satt þþaa. að
// f[i..k-1] <= f[k] <= f[k+1..j-1].
static boolean is_partitioned(int[] f, int i, int j, int k)
{
for (int n = i; n != k; n++)
if (f[n] > f[k])
return false;
for (int n = k; n != j; n++)
if (f[n] < f[k])
return false;
return true;
}
public static void main(String[] args)
{
Random g = new Random();
for (int n = 0; n < 5; n++)
{
System.out.printf("Test %d:\n", n);
int[] f = {62,88,59,94,4,71,26,17,44,28,37,44,64,25,73,21,23,35,49,23};
int r = g.nextInt(f.length);
System.out.printf("[+] Partition by f[%d] = %d\n", r, f[r]);
System.out.printf("\t");
for (int i = 0; i < f.length; i++)
{
if (i == r)
System.out.printf("[%02d] ", f[i]);
else
System.out.printf("%02d ", f[i]);
}
System.out.println();
int k = partition(f, 0, f.length, r);
System.out.printf("[+] Partitioned. Pivot rests at f[%d] = %d\n", k, f[k]);
System.out.printf("\t");
for (int i = 0; i < f.length; i++)
{
if (i == k)
System.out.printf("[%02d] ", f[i]);
else
System.out.printf("%02d ", f[i]);
}
System.out.println();
System.out.printf("[+] Checking post condition: f[%d..%d] <= f[%d] <= f[%d..%d]\n", 0, k-1, k, k+1, f.length-1);
if (is_partitioned(f, 0, f.length, k))
System.out.printf("[+] PASSED\n");
else
System.out.printf("[-] FAILED\n");
System.out.println();
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NELEMS(x) (sizeof(x) / sizeof(x[0]))
static void swap(int *f, int a, int b)
{
int tmp = f[a];
f[a] = f[b];
f[b] = tmp;
}
// Notkun: k = partition(f,i,j,s);
// Fyrir: f[i..j-1] er löglegt svæði í f,
// i <= s < j
// f[s] er pivot gildi til að skipta eftir
// Eftir: Búið er að víxla gildum í svæðinu þ.a.
// f[i..k-1] <= f[k] <= f[k+1..j-1]
// Gildið í sæti k var upphaflega í sæti s.
int partition(int *f, int i, int j, int s)
{
// ...
}
// Notkun: b = is_partitioned(f,i,j,k)
// Fyrir: f[i..j-1] er svæði í fylkinu f, i <= k < j
// f[i..j-1] má vera óraðað.
// Eftir: b er satt þþaa. að
// f[i..k-1] <= f[k] <= f[k+1..j-1].
static int is_partitioned(int *f, int i, int j, int k)
{
int n;
for (n = i; n != k; n++)
if (f[n] > f[k])
return 0;
for (n = k; n != j; n++)
if (f[n] < f[k])
return 0;
return 1;
}
int main(void)
{
int i, n;
srand(time(NULL));
for (n = 0; n < 5; n++)
{
printf("Test %d:\n", n);
int f[] = {62,88,59,94,4,71,26,17,44,28,37,44,64,25,73,21,23,35,49,23};
int r = rand() % NELEMS(f);
printf("[+] Partition by f[%d] = %d\n", r, f[r]);
printf("\t");
for (i = 0; i < NELEMS(f); i++)
{
if (i == r)
printf("[%02d] ", f[i]);
else
printf("%02d ", f[i]);
}
printf("\n");
int k = partition(f, 0, NELEMS(f), r);
printf("[+] Partitioned. Pivot rests at f[%d] = %d\n", k, f[k]);
printf("\t");
for (i = 0; i < NELEMS(f); i++)
{
if (i == k)
printf("[%02d] ", f[i]);
else
printf("%02d ", f[i]);
}
printf("\n");
printf("[+] Checking post condition: f[%d..%d] <= f[%d] <= f[%d..%d]\n", 0, k-1, k, k+1, NELEMS(f)-1);
if (is_partitioned(f, 0, NELEMS(f), k))
printf("[+] PASSED\n");
else
printf("[-] FAILED\n");
printf("\n");
}
return 0;
}