In de voorbeelden werden twee verschillende oplossingsmethodes bekeken voor het bepalen van het aantal priemgetallen kleiner dan een gegeven waarde n. Werk beide methodes uit voor n = 10.
n = 10
1: p <- 2
2: aantal <- 0
3: ? p < n ? 2 < 10 ~> Waar
4: deler <- 2
5: ? (deler < p) EN (p MOD deler ≠ 0) ? 2 < 2 ~> Vals
8: ? deler = p ? 2 = 2 ~> Waar
9: aantal <- 1
11: p <- 3
3: ? p < n ? 3 < 10 ~> Waar
4: deler <- 2
5: ? (deler < p) EN (p MOD deler ≠ 0) ? (2 < 3) EN (3 MOD 2 ≠ 0) ~> Waar
6: deler <- 3
5: ? (deler < p) EN (p MOD deler ≠ 0) ? (3 < 3) ~> Vals
8: ? deler = p ? 3 = 3 ~> Waar
9: aantal <- 2
11: p <- 4
3: ? p < n ? 4 < 10 ~> Waar
4: deler <- 2
5: ? (deler < p) EN (p MOD deler ≠ 0) ? (2 < 4) EN (4 MOD 2 ≠ 0) ~> Vals
8: ? deler = p ? 2 = 4 ~> Vals
11: p <- 5
...Als je wilt mag je dit tot
n = 10doen, maar ik ga dat niet doen. :)
Schrijf een alternatieve versie van Algoritme 1.17 voor het bepalen van het aantal priemgetallen kleiner dan n, waarbij de verbeteringen uit de opmerking werden aangebracht.
telPriemgetallen (I: n: geheel getal) : aantal: geheel getal
* Preconditie: n is een natuurlijk getal.
* Postconditie: het aantal priemgetallen kleiner dan n werd geretourneerd.
* Gebruikt: /
BEGIN
ALS n ≤ 2
aantal <- 0
ANDERS
p <- 3
aantal <- 1
ZOLANG (p < n) DOE
deler <- 3
ZOLANG (((deler . deler) ≤ p) EN (p MOD deler ≠ 0)) DOE
deler <- deler + 2
EINDE ZOLANG
ALS ((deler . deler) > p) DAN
antal <- aantal + 1
EINDE ALS
p <- p + 2
EINDE ZOLANG
EINDE ALS
RETOUR aantal
EINDESchrijf een algoritme met 2 gehele getallen als invoer. Als het eerste getal groter is dan het tweede dan wordt het verschil berekend, anders de som. Het resultaat wordt geretourneerd als uitvoerparameter.
berekenOefening3 (I: a, b: geheel getal) : resultaat: geheel getal
* Preconditie: de waarden a en b zijn gehele getallen
* Postconditie: voor a > b werd a - b berekend, in het andere geval werd a + b berekend.
* Gebruikt: /
BEGIN
ALS a > b
resultaat <- (a - b)
ANDERS
resultaat <- (a + b)
EINDE ALS
RETOUR resultaat
EINDEHet algoritme van Euclides beschrijft een methode om de grootste gemene deler (ggd) van twee positieve gehele getallen te bepalen.
Algoritme uitleg:
ggd(a, b)? (a ≥ b) Omdraaien indien niet zo.
a = b x q + r o ≤ r ≤ b
ggd(a, b) = ggd(b, r)
ggd(a, 0) = a
Oefeningen:
Oefening a)
ggd(273, 110)
273 = 110 x 2 + 53
110 = 53 x 2 + 4
53 = 4 x 13 + 1
4 = 1 x 4 + 0
ggd(273, 110) = ggd(110, 53) = ggd(53, 4) = ggd(4, 1) = ggd(1, 0) = 1
Oefening b)
ggd(1400, 220)
1400 = 220 x 6 + 80
220 = 80 x 2 + 60
80 = 60 x 1 + 20
60 = 20 x 3 + 0
ggd(1400, 220) = ggd(220, 80) = ggd(80, 60) = ggd(60, 20) = ggd(20, 0) = 20
Algoritme:
berekenGgd (I: a, b: gehele getallen) : resultaat: geheel getal
* Preconditie: a en b zijn natuurlijke getallen.
* Postconditie: ggd van a en b werd berekend.
* Gebruikt: /
BEGIN
ALS (b > a) DAN
tmp <- a
a <- b
b <- tmp
EINDE ALS
ZOLANG b ≠ 0 DOE
r <- a MOD b
a <- b
b <- r
EINDE ZOLANG
resultaat <- a
RETOUR resultaat
EINDESchrijf algoritmen voor het berekenen van de gevraagde sommen. In elk van de gevallen is n de invoerparameter.
Oefening a)
berekenSom(I: n: geheel getal) : som: geheel getal
* Preconditie: n is een natuurlijk getal
* Postocnditie: de som werd berekend
* Gebruik: /
BEGIN
som <- 0
VOOR i = 1 TOT n DOE
som <- som + i
EINDE VOOR
RETOUR som
EINDEOefening b)
berekenSom(I: n: geheel getal) : som: geheel getal
* Preconditie: n is een natuurlijk getal
* Postocnditie: de som werd berekend
* Gebruik: /
BEGIN
som <- 0
VOOR i = 1 TOT n DOE
VOOR j = 1 TOT n DOE
som <- som + (i . j)
EINDE VOOR
EINDE VOOR
RETOUR som
EINDEOefening c)
berekenSom(I: n: geheel getal) : som: geheel getal
* Preconditie: n is een natuurlijk getal
* Postocnditie: de som werd berekend
* Gebruik: /
BEGIN
som <- 0
VOOR i = 1 TOT n DOE
VOOR j = i TOT n DOE
som <- som + (i . j)
EINDE VOOR
EINDE VOOR
RETOUR som
EINDESchrijf een methode maakMatrix voor het genereren van een matrix A van de orde m × n, met alle elementen onder de diagonaal gelijk aan m, alle elementen op de diagonaal gelijk aan m + n en alle elementen boven de diagonaal gelijk aan n.
De input van de methode is de dimensie van A, het aantal rijen m en het aantal kolommen n. De output moet de matrix A zijn, opgebouwd volgens de zonet geformuleerde regels.
Voorbeeld:
maakMatrix(3, 4)
Resultaat:
7 4 4 4
3 7 4 4
3 3 7 4
Met coordinaten:
(0, 0) (0, 1) (0, 2) (0, 3)
(1, 0) (1, 1) (1, 2) (1, 3)
(2, 0) (2, 1) (2, 2) (2, 3)Uitwerking in code:
maakMatrix(I: m, n: gehele getallen): A: array[][] van gehele getallen.
* Preconditie: m, n zijn natuurlijke getallen
* Postconditie: een array A werd gemaakt
* Gebruikt: /
BEGIN
A <- maak nieuwe array met m rijen en n kolommen
VOOR i = 0 TOT (m - 1) DOE
VOOR j = 0 TOT (n - 1) DOE
ALS i = j DAN
A[i][j] <- (m + n)
ANDERS
ALS i > j DAN
A[i][j] <- m
ANDERS
A[i][j] <- n
EINDE ALS
EINDE ALS
EINDE VOOR
EINDE VOOR
RETOUR A
EINDEDe methode van Gauss is een methode voor het oplossen van een lineair (n × m)-stelsel S. Algoritme 1.19 beschrijft de methode van Gauss voor reguliere (n × n)-stelsels, dit zijn stelsels met steeds juist een oplossing.
oefening b)
//Oefening 9b
//De determinant van een vierkante matrix a berekenen
//mbv de methode van Gauss
public static double berekenDeterminant(double[][] a)
{
double det = 1;
//het aantal rijen van de matrix bepalen
//is gelijk aan het aantal kolommen (vierkante matrix)
int n = a.length;
double factor;
//de triangularisatiefase
for (int k = 0; k < n - 1; k++)
{
for (int i = k + 1; i < n; i++)
{
factor = a[i][k] / a[k][k];
for (int j = k + 1; j < n; j++)
{
a[i][j] -= factor * a[k][j];
}
}
}
for (int i = 0; i < a.length; i++)
{
det *= a[i][i];
}
return det;
}oefening c)
//Oefening 9c
//de inverse matrix bepalen van een reguliere matrix
//mbv de methode van Gauss
public static double[][] berekenInverseMatrix(double[][] matrix)
{
//de orde van de matrix bepalen
int n = matrix.length;
double[][] matrixAb = new double[n][2 * n];
double factor, r;
// Maak de verhoogde matrix, van de matrix + eenheidsmatrix
for (int i = 0; i < matrixAb.length; i++)
{
for (int j = 0; j < matrixAb[i].length; j++)
{
if (j < n) {
matrixAb[i][j] = matrix[i][j];
} else {
matrixAb[i][j] = ((j - n) == i) ? 1 : 0;
}
}
}
n = matrixAb.length;
//de triangularisatiefase
for (int k = 0; k < n - 1; k++)
{
for (int i = k + 1; i < n; i++)
{
factor = matrixAb[i][k] / matrixAb[k][k];
for (int j = k + 1; j < 2 * n; j++)
{
matrixAb[i][j] -= factor * matrixAb[k][j];
}
}
}
double[][] inverse = new double[n][n];
//achterwaartse substitutie
for (int k = 0; k < n; k++)
{
inverse[n - 1][k] = matrixAb[n - 1][n + k] / matrixAb[n - 1][n - 1];
for (int i = n - 2; i >= 0; i--)
{
r = 0;
for (int j = i + 1; j < n; j++)
{
r += matrixAb[i][j] * inverse[j][k];
}
inverse[i][k] = (matrixAb[i][n + k] - r) / matrixAb[i][i];
}
}
return inverse;
}