11.1 En Fibonacci funktion med huskeværk
Den rekursive fib funktion, som kan programmeres således
long fib(int n){
long result;
if (n == 0)
result = 0;
else if (n == 1)
result = 1;
else
result = fib(n-1) + fib(n-2);
return result;
}lider af et alvorligt effektivitetsproblem. Hvert kald af fib(n) for n > 1 leder til to andre kald af fib. Mange af disse kald har allerede været udført en eller flere gange tidligere. Prøv f.eks. at danne dig et overblik over hvor mange gange fib(2) bliver kaldt når vi beregner fib(5).
Ideen i denne opgave er at huske på (lagre) værdien af fib(n), når den er beregnet første gang. Hvis vi efterfølgende kalder fib(n) igen, trækker vi værdien ud af lageret snarere end at genberegne fib(n) rekursivt. Denne teknik kaldes for memoisering. Her er det pseudoprogram vi har studeret:
long fib(long n){ /* working program: fib-memo.c - an exercise*/
long result;
Erklaer huskevaerk;
if (n == 0)
result = 0;
else if (n == 1)
result = 1;
else if (Vi allerede har beregnet vaerdien en gang)
result = den huskede vaerdi;
else {
result = fib(n-1) + fib(n-2);
Husk paa vaerdien;
}
return result;
}
int main(void) {
long i;
for(i = 0; i < 100; i++)
printf("Fib(%li) = %li\n", i, fib(i));
return 0;
}Modificer ovenstående versioner af fib, således at den lagrer værdien af fib(n) når udtrykket er beregnet. Og således at den udtrækker og returnerer en lagret værdi, i stedet for at gå i gang med en genberegning. Det er oplagt at allokere et array af element-typen long int til formålet. Overvej en anvendelse af en statisk lokal variabel!
Kald den oprindelige af fib og din nye variant af fib funktionen med alle heltal mellem n og 45, og vurder dermed effekten af memoiseringen.
Løsning
Her er min memoiserede fib funktion:
#include <stdio.h>
long fib(long n);
int main(void) {
long i;
for(i = 0; i < 100; i++)
printf("Fib(%li) = %li\n", i, fib(i));
return 0;
}
long fib(long n){
long result;
static long memo[100]; /* elements pre-initialized to 0 */
if (n == 0)
result = 0;
else if (n == 1)
result = 1;
else if (memo[n] != 0)
result = memo[n];
else {
result = fib(n-1) + fib(n-2);
memo[n] = result;
}
return result;
}
11.2 Palindromer
Et palindrom er en tekststreng, som læses ens både forfra og bagfra. Eksempelvis er strengen "regninger" et palindrom. Vi kan også sige at et palindrom er en tekststreng som er lig med sin egen strengomvending.
Skriv først en iterativ funktion int is_palindrome_iter(char *str), der afgør om str er et palindrom. En iterativ funktion er en funktion, som programmeres ved brug af en while-løkke eller en for-løkke. Funktionen skal returnere 1 hvis str er et palindrom, og 0 hvis str ikke er et palindrom.
Skriv dernæst en tilsvarende rekursiv udgave int is_palindrome_rec(char *str).
Den rekursive funktion skal løse nøjagtig det samme problem som den iterative funktion; Altså om parameteren str er et palindrom. Den skal gøre dette ved at undersøge om en bestemt (lidt mindre) delstreng af strengen er et palindrom. Hvis det hjælper dig, kan du overveje at indføre en hjælpefunktion til is_palindrome_rec, for at gøre dette.
Målet med denne opgave er at opnå viden og færdigheder i at arbejde med såvel rekursive som iterativt programmerede funktioner. Målet er endvidere at opnå yderligere viden og færdigheder i simpel programmering med tekststrenge.
Løsning
Du kan vælge at se en video hvor jeg diskuterer den iterative og rekursive løsning. Her er en løsning, som minder ganske meget om den løsning på palindrom problemet, der udvikles i videoen:
#include <stdio.h>
#include <string.h>
int is_palindrome_rec(char *str);
int is_palindrome_rec_len(char *str, int lgt);
int is_palindrome_iter(char *str);
int main(void) {
char str[100];
do{
printf("Enter string (the string exit will stop the program): ");
scanf("%s", str);
if (strcmp(str,"exit") != 0){
if (is_palindrome_iter(str))
printf("Iterative %s is a palindrome\n", str);
else
printf("Iterative: %s is NOT a palindrome\n", str);
}
if (strcmp(str,"exit") != 0){
if (is_palindrome_rec(str))
printf("Recursive: %s is a palindrome\n", str);
else
printf("Recursive: %s is NOT a palindrome\n", str);
}
}
while (strcmp(str,"exit") != 0);
return 0;
}
int is_palindrome_rec(char *str){
int lgt = strlen(str);
return is_palindrome_rec_len(str, lgt);
}
int is_palindrome_rec_len(char *str, int lgt){
if (lgt < 2)
return 1;
else
return str[0] == str[lgt-1] && is_palindrome_rec_len(str+1, lgt-2);
}
int is_palindrome_iter(char *str){
int i, j;
for(i = 0, j = strlen(str)-1; i < j; i++, j--)
if (str[i] != str[j])
return 0;
return 1;
}
11.3 Heltalsdivision og restuddragning med rekursive funktioner
Programmer en funktion
int quotient(int dividend, int divisor)
som beregner dividend / divisor ved brug af rekursion (ved gentagen subtraktion).
Skriv ligeledes en rekursiv funktion
int modulus(int dividend, int divisor)
som beregner resten, dividend % divisor.
Løsning
Her er min udgave af de to funktioner
#include <stdio.h>
int quotient(int dividend, int divisor);
int modulus(int dividend, int divisor);
int main(void) {
int a, b;
printf("Enter dividend and divisor: ");
scanf(" %d %d", &a, &b);
printf("%d / %d = %d\n", a, b, quotient(a, b));
printf("%d %% %d = %d\n", a, b, modulus(a, b));
return 0;
}
/* Calculate dividend / divisor - integer division
Precondition: divisor != 0 and both dividend and divisors are non-negative.
*/
int quotient(int dividend, int divisor){
if (dividend < divisor)
return 0;
else
return 1 + quotient(dividend - divisor, divisor);
}
/* Calculate dividend % divisor - integer remainder.
Precondition: divisor != 0 and both dividend and divisors are non-negative.
*/
int modulus(int dividend, int divisor){
if (dividend < divisor)
return dividend;
else
return modulus(dividend - divisor, divisor);
}
11.4 Opgave 1 side 587 i PSPD(8ed) - blob_count
Dette er hints til opgave 1 side 587 i Problem Solving and Program Design in C, 8ed (svarende til opgave 1 side 583 i 7ed).
Der findes en video som giver et oplæg til problemløsningen. Jeg anbefaler at I ser denne video forud for løsningen af opgaven.
Jeg synes det er mere naturligt at kalde funktionen blob_count i stedet for bogens forslag, blob_check.
Bogens grid, vist nederst side 587 (8ed), kan laves på denne måde:
int grid[5][5] = {
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 1},
{0, 1, 0, 1, 1},
}; Med denne opskrivning er det mest naturligt at x 'er lodret' (betegner rækker) og at 'y er vandret' (betegner søjler). Dette syn er altså lidt anderledes end bogens.
Bemærk at grid[0][0] er 1 (øverste venstre hjørne), grid[0][4] er 0 (øverste højre hjørne), grid[4][0] er 0 (nederste venstre hjørne), og at grid[4][4] er 1 (nederste højre hjørne).
Overvej nøje, hvordan du vil håndtere felter som falder uden for griddet (f.eks grid[-1][5]). Hint: Lad blob_count på sådanne felter returnere 0.
Som en centalt punkt i opgaven skal du besøge alle 8 naboer til et punkt i tabellen. Det kan være træls at gøre dette manuelt, nabo for nabo. Overvej hvordan dette kan gøres med (to nestede) for-løkker.
Vær sikker på at funktionen blob_count bliver rekursiv. Altså at funktionen kaldes rekursivt på alle 8 naboer af en celle. Ideen er at tælle blob størrelsen af eksempelvis celle (x+1,y+1) efter nøjagtig samme opskrift som blev anvendt til at tælle blob størrelsen af celle (x,y).
Som beskrevet i bogen er det nødvendigt at markere at en celle er talt. Dette gøres lettest ved at ændre 1-tallet til 0 i cellen. Dette ødelægger griddet. Jeg foreslår derfor at det givne grid kopieres over i et andet grid før kaldet af blob_count. På denne måde er det en kopi, som ødelægges, ikke originalen. Skriv gerne en copy_grid funktion, som udfører dette.
I main bør du indlæse et (x,y) punkt og kalde blob_count på (x, y). Gør gerne dette i en løkke, så du kan undersøge flere (x,y) punkter i samme kørsel af programmet.
Løsning
Herunder finder du en udgave af programmet. Der findes en video, som viser hvordan jeg har udviklet løsningen. Pt. er løsningen som udvikles i videoen en anelse anderledes end programmet herunder.
#include <stdio.h>
#define MAX_X 5
#define MAX_Y 5
int blob_count(int x, int y, int grid[MAX_X][MAX_Y]);
void copy_grid(int from_grid[5][5], int to_grid[MAX_X][MAX_Y]);
int main(void) {
int x, y;
int grid_original[MAX_X][MAX_Y] = {
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 1},
{0, 1, 0, 1, 1},
},
grid[MAX_X][MAX_Y];
do{
printf("Enter x and y (a negative x or y terminates): ");
scanf("%d %d", &x, &y);
copy_grid(grid_original, grid);
if (x >= 0 && y >= 0)
printf("blob check af (%d,%d): %d\n", x, y, blob_count(x,y,grid));
} while (x >= 0 && y >= 0);
return 0;
}
int blob_count(int x, int y, int grid[MAX_X][MAX_Y]){
if (x < 0 || y < 0 || x > MAX_X - 1 || y > MAX_Y - 1)
return 0;
else if (grid[x][y] == 1){
int sum, dx, dy;
grid[x][y] = 0; // Reset cell, in order not to count again
sum = 1; // Now counted.
for(dx = -1; dx <= 1; dx++)
for(dy = -1; dy <= 1; dy++)
sum += blob_count(x + dx, y + dy, grid);
return sum;
}
else // grid[x][y] == 0
return 0;
}
void copy_grid(int from_grid[MAX_X][MAX_Y], int to_grid[MAX_X][MAX_Y]){
int x, y;
for(x = 0; x < MAX_X; x++)
for(y = 0; y < MAX_Y; y++)
to_grid[x][y] = from_grid[x][y];
}
11.5 Rekursive udgaver af Euclids algoritme
I denne opgave vil vi programmere iterative beregninger med brug af rekursion. Funktionerne, som skal programmeres i denne opgave, skal altså følge det mønster vi har set i funktionen iterative_factorial (et program i lektionen om rekursion).
Vi har set iterative udgaver af Euclids algoritme i lektionen om gentagelse og løkker og vi har set en gcd funktion i lektionen om funktioner.
Programmer først en rekursiv udgave af den version af Euclids algoritme, der er baseret på gentagen restberegning.
Programmer dernæst en rekursiv udgave af den version af Euclids algoritme, der er baseret på gentagen subtraktion.
Løsning
Her er en rekursiv udgave af Euclids algoritme, der er baseret på gentagen restberegning:
#include <stdio.h>
int gcd(int a, int b);
int main(void) {
int i, j, result;
printf("Enter two non-negative integers: ");
scanf("%d %d", &i, &j);
result = gcd(i, j);
printf("GCD of %d and %d is %d\n\n", i, j, result);
return 0;
}
/* If a < b, then the first recursive call will be gcd(b, a).
This call will exchange the parameters such that, subsequently, a >= b */
int gcd(int a, int b){
if (b == 0)
return a;
else
return gcd(b, a % b);
}
Og her er, tilsvarende, er rekursiv udgave baseret på gentagen subtraktion:
#include <stdio.h>
int gcd(int a, int b);
int main(void) {
int i, j, result;
printf("Enter two non-negative integers: ");
scanf("%d %d", &i, &j);
result = gcd(i, j);
printf("GCD of %d and %d is %d\n\n", i, j, result);
return 0;
}
int gcd(int a, int b){
if (a == b)
return a;
else if (a > b)
return gcd(a - b, b);
else
return gcd(a, b - a);
}
Bemærk at begge de viste rekursive funktioner er halerekursive. Det er er bestemt ikke en tilfældighed. Iterative beregningsprocesser - programmeret med løkker - kan systematisk transformeres til halerekursive funktioner, hvor beregningens tilstand bliver parametre i funktionen.
Genereret: Onsdag 17. november 2021, 12:59:02