b) 0
c) 0.4
z (1) = 3 z (2) = 3 f(x, y) = 7 z (3) = 3
struct Intervall {
int forsta;
int sista;
};
typedef struct Intervall Intervall; // Om man vill!
b) (1p)
Intervall intervallet = { 0, 5 };
c) (2p)
void visa_intervall(Intervall i) {
printf("Intervallets första tal: %d\n", i.forsta);
printf("Intervallets sista tal: %d\n", i.sista);
}
d) (2p)
void visa_tal(Intervall i) {
printf("[ ");
for (int tal = i.forsta; tal <= i.sista; ++tal)
printf("%d ", tal);
printf("]");
}
e) (1p)
int langd(Intervall i) {
return i.sista - i.forsta;
}
f) (1p)
int antal_tal(Intervall i) {
return i.sista - i.forsta + 1;
}
g) (2p)
// Delmängd:
// Det första intervallet måste börja efter att det andra börjar,
// och det första intervallet måste sluta innan det andra slutar.
// (Eller på samma tal.)
int delmangd(Intervall delen, Intervall hela) {
return delen.forsta >= hela.forsta && delen.sista <= hela.sista;
}
h) (3p)
// Överlappande:
// Om det första intervallet slutar innan det andra börjar,
// eller om det andra intervallet slutar innan det första börjar,
// är de INTE överlappande.
int overlappande(Intervall i1, Intervall i2) {
return !(i1.sista < i2.forsta || i2.sista < i1.forsta);
}
i) (4p)
// Den här funktionen TILLÅTER att man skriver ett korrekt heltal
// följt av skräp, till exempel "17 Kalle" eller "17.2". Skräpet
// ignoreras.
Intervall las_intervall(void) {
Intervall i;
int ordning_ok = 0;
while (!ordning_ok) {
int forsta_ok = 0;
while (!forsta_ok) {
printf("Ange intervallets första tal: ");
if (scanf("%d", &i.forsta) != 1) {
printf("Inte ett riktigt heltal. Försök igen!\n");
}
else
forsta_ok = 1;
while (getchar() != '\n')
;
}
int sista_ok = 0;
while (!sista_ok) {
printf("Ange intervallets sista tal: ");
if (scanf("%d", &i.sista) != 1) {
printf("Inte ett riktigt heltal. Försök igen!\n");
}
else
sista_ok = 1;
while (getchar() != '\n')
;
}
if (i.forsta > i.sista)
printf("Sista talet får inte vara mindre än det första. Försök igen!\n");
else
ordning_ok = 1;
}
return i;
}
j) (2p)
int main(void) {
Intervall i1 = las_intervall();
Intervall i2 = las_intervall();
if (antal_tal(i1) > antal_tal(i2))
visa_intervall(i1);
else
visa_intervall(i2);
}
Som bonus bifogas lite testkod för intervallfunktionerna delmangd och overlappande. Två intervall kan förhålla sig till varandra på, om jag räknat rätt, tjugofyra olika sätt, om man betraktar intervall med ett enda tal som ett specialfall som ska testas.
struct Testfall {
struct Intervall i1;
struct Intervall i2;
int delmangd;
int overlappande;
};
typedef struct Testfall Testfall;
Testfall testfall[] = {
{ { 10, 20 }, { 30, 40 }, 0, 0 },
{ { 10, 20 }, { 15, 40 }, 0, 1 },
{ { 10, 20 }, { 20, 40 }, 0, 1 },
{ { 10, 20 }, { 15, 20 }, 0, 1 },
{ { 10, 20 }, { 15, 17 }, 0, 1 },
{ { 10, 20 }, { 10, 20 }, 1, 1 },
{ { 10, 20 }, { 5, 15 }, 0, 1 },
{ { 10, 20 }, { 5, 10 }, 0, 1 },
{ { 10, 20 }, { 10, 15 }, 0, 1 },
{ { 10, 20 }, { 5, 25 }, 1, 1 },
{ { 10, 20 }, { 3, 7 }, 0, 0 },
{ { 10, 20 }, { 5, 5 }, 0, 0 },
{ { 10, 20 }, { 10, 10 }, 0, 1 },
{ { 10, 20 }, { 15, 15 }, 0, 1 },
{ { 10, 20 }, { 20, 20 }, 0, 1 },
{ { 10, 20 }, { 25, 25 }, 0, 0 },
{ { 5, 5 }, { 10, 20 }, 0, 0 },
{ { 10, 10 }, { 10, 20 }, 1, 1 },
{ { 15, 15 }, { 10, 20 }, 1, 1 },
{ { 20, 20 }, { 10, 20 }, 1, 1 },
{ { 25, 25 }, { 10, 20 }, 0, 0 },
{ { 5, 5 }, { 10, 20 }, 0, 0 },
{ { 10, 10 }, { 10, 10 }, 1, 1 },
{ { 10, 10 }, { 5, 5 }, 0, 0 },
};
void testa(void) {
printf("Testar intervallfunktioner...\n");
int n = sizeof(testfall) / sizeof(testfall[0]);
for (int i = 0; i < n; ++i) {
struct Intervall i1 = testfall[i].i1;
struct Intervall i2 = testfall[i].i2;
int forvantat_delmangd = testfall[i].delmangd;
int forvantat_overlappande = testfall[i].overlappande;
int observerat_delmangd = delmangd(i1, i2);
int observerat_overlappande = overlappande(i1, i2);
if (observerat_overlappande != forvantat_overlappande)
printf("Fel i testfall %d: overlappande var %d, borde vara %d.\n",
i + 1, observerat_overlappande, forvantat_overlappande);
if (observerat_delmangd != forvantat_delmangd)
printf("Fel i testfall %d: delmangd var %d, borde vara %d.\n",
i + 1, observerat_delmangd, forvantat_delmangd);
}
printf("Test av intervallfunktioner klart.\n");
}
#include <stdlib.h>
#include <stdio.h>
/* Diverse programkod för intervall från tidigare uppgifter */
typedef struct Link Link;
struct Link {
Intervall intervallet;
Link *next;
};
struct Link *first = NULL;
int main(void) {
printf("Hur många intervall? ");
int antal_intervall;
scanf("%d", &antal_intervall);
for (int i = 0; i < antal_intervall; ++i) {
Link *link = malloc(sizeof(Link));
link->intervallet = las_intervall();
link->next = first;
first = link;
}
int langsta_langden = -1;
Intervall langsta_intervallet;
Link *p = first;
while (p != NULL) {
if (langd(p->intervallet) > langsta_langden) {
langsta_langden = langd(p->intervallet);
langsta_intervallet = p->intervallet;
}
p = p->next;
}
printf("Längsta intervallet:\n");
visa_intervall(langsta_intervallet);
}
#include <stdlib.h>
#include <stdio.h>
/* Diverse programkod för intervall från tidigare uppgifter */
int main(void) {
printf("Hur många intervall? ");
int antal_intervall;
scanf("%d", &antal_intervall);
FILE *tsut = fopen("intervall.txt", "w");
if (tsut == NULL) {
printf("Kunde inte skriva filen 'intervall.txt'.\n");
exit(EXIT_FAILURE);
}
for (int i = 0; i < antal_intervall; ++i) {
Intervall intervallet = las_intervall();
fprintf(tsut, "%d %d\n", intervallet.forsta, intervallet.sista);
}
fclose(tsut);
return 0;
}
#include <stdlib.h>
#include <stdio.h>
/* Diverse programkod för intervall från tidigare uppgifter */
int main(void) {
FILE *tsin = fopen("intervall.txt", "r");
if (tsin == NULL) {
printf("Kunde inte läsa filen 'intervall.txt'.\n");
exit(EXIT_FAILURE);
}
int langsta_langden = -1;
Intervall langsta_intervallet;
Intervall detta_intervall;
while (fscanf(tsin, "%d %d", &detta_intervall.forsta, &detta_intervall.sista) != EOF) {
if (langd(detta_intervall) > langsta_langden) {
langsta_langden = langd(detta_intervall);
langsta_intervallet = detta_intervall;
}
}
fclose(tsin);
printf("Längsta intervallet:\n");
visa_intervall(langsta_intervallet);
return 0;
}
Den länkade listan i uppgift 4 lagras i primärminnet. Visserligen används virtuellt minne, och om primärminnet blir fullt kan delar av innehållet mellanlagras på sekundärminne, men för enkelhets skull ignorerar vi det.
Hur mycket plats tar då ett intervall i den länkade listan? En listlänk-struct består av intervallet, som består av två heltal, och en pekare till nästa länk. Heltal idag brukar vara 32 bitar, dvs 4 byte. Pekare idag brukar vara 64 bitar, dvs 8 byte. Alltså tar en listlänk upp 16 byte. Det får plats 8 * 109 / 16 = 500 miljoner listlänkar i primärminnet.
(På riktigt går det förstås inte att fylla hela primärminnet enbart med listlänkar. I minnet finns också operativsystemet, programmet, funktionsbibliotek, malloc-systemets interna datastrukturer, och andra program. Men för enkelhets skull ignorerar vi det.)
Filen i uppgift 5 och 6 lagras på sekundärminnet. Bara ett enda intervall i taget behöver lagras i primärminnet, så det är sekundärminnet som begränsar. Jag har använt en textfil i lösningsförslaget, och där upptar varje (vanligt) tecken, till exempel en siffra, en byte. En rad som 0 5 tar, inklusive (beroende på system) ett radslutstecken, upp 4 byte. Eftersom vi vill kunna ha intervall inte bara med ensiffriga tal, kan vi säga 8 byte per rad. Det får plats 1012 / 8 = 125 miljarder intervall.
(På riktigt går det förstås inte att fylla hela sekundärminnet enbart med dessa intervallrader. Men för enkelhets skull ignorerar vi det.)
Svar: Uppgift 4, med en länkad lista, kan hantera ungefär 500 miljoner intervall. Uppgift 5 och 6, med en textfil, kan hantera ungefär 125 miljarder intervall.
Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 8 juni 2017