Opgaver og løsninger
Funktioner

På mange måder er funktionen solveQuadraticEquation fra programmet på den tilhørende slide en god løsning på at finde rødderne i den generelle andengradsligning a x² + b x + c = 0. Dog udestår, som omtalt på tilhørende slide, en tilfredsstillende løsning på aflevering af outputtet: Antallet af rødder og rødderne selv. Men det kommer lidt senere i kurset.

I denne opgave vil vi nedbryde problemløsningen endnu mere, og vi vil på systematisk vis programmere C funktioner som løser disse delproblemer. Målet med opgaven er altså primært på at anvende ideerne om trinvis forfinelse og top-down programmering. Dette indebærer delmål om programmering af funktioner med inputparametre, brug af prototyper af funktioner, og brug af return til formidling af output fra en funktion.

Programmer hvert af følgende delproblemer som en separat funktion:

• Beregning af diskriminanten.
• Beregningen af første rod, under forudsætning af at den findes.
• Beregningen af anden rod, under forudsætning af at den findes.

Hvis der kun er én rod, anses første og anden rod for at være ens. Hvis der ikke findes rødder må de to sidstenævnte funktioner ikke kaldes.

Find gode navne til funktionerne, der løser ovenstående tre delproblemer, og forsyn funktionerne med relevante input parametre. Funktionernes output skal formidles via funktionernes returværdi.

Omskriv programmet så det kalder de tre funktioner. Vær sikker på at du bibeholder funktionen solveQuadraticEquation.

Programmer endvidere main således at solveQuadraticEquation kaldes i en løkke. I denne løkke skal de tre koeficienter a, b og c indlæses. Afslut løkken når alle de tre indlæste koeficienter a, b og c er lig med 0. Dette kan gøres med en sentinel-controlled loop. Løs ligningen (inden i løkken) i de tilfælde, hvor det giver mening.

Vær sikker på at du organiserer dit C program ud fra de anbefalinger vi har set om top-down programmering ved trinvis forfinelse.

I denne opgave bedes du programmere det hele i én C fil. Der skal således ikke laves en header fil med prototyper.

Her er et bud på den ønskede, trinvise forfinelse af solveQuadraticEquation:

#include <stdio.h>
#include <math.h>

void solveQuadraticEquation(double a, double b, double c);
double discriminant(double a, double b, double c);
double root1(double a, double b, double discr);
double root2(double a, double b, double discr);

int main(void) {
  double a, b, c;
  printf("Enter coeficients a, b, and c: ");
  scanf("%lf %lf %lf", &a, &b, &c);
  while (!((a == 0) && (b == 0) && (c == 0))){
    if (a != 0)
      solveQuadraticEquation(a, b, c);  
    else
      printf("Coeficent a is not allowed to be 0\n");

    printf("Enter coeficients a, b, and c: ");
    scanf("%lf %lf %lf", &a, &b, &c);
  }

  return 0;
}

void solveQuadraticEquation(double a, double b, double c){
  double d;

  d = discriminant(a, b, c); 

  if (d < 0)
    printf("No roots\n");
  else if (d == 0)
    printf("One root: %f\n", root1(a, b, d));
  else 
    printf("Two roots: %f and %f\n",
           root1(a, b, d), root2(a, b, d));
}   

double discriminant(double a, double b, double c){
  return b * b - 4 * a * c;
}

double root1(double a, double b, double discr){
  return  (-b + sqrt(discr))/(2*a);
}

double root2(double a, double b, double discr){
  return  (-b - sqrt(discr))/(2*a);
}

Denne opgave giver dig blandt andet træning i programmering af et C program, der anvender en header file (.h fil) og en tilhørende .c fil. I denne opgaven kalder vi en funktion, som allerede er skrevet. I senere opgaver skal du selv i gang med at skrive dine funktioner.

Du skal skrive et program med en main funktion der udskriver de første n primtal. Skriv dit program i en fil der hedder test-primes.c. Der ønskes følgende output hvis n er 100:

  prime 1: 2
  prime 2: 3
  prime 3: 5
  prime 4: 7
  prime 5: 11
  prime 6: 13
  prime 7: 17
  prime 8: 19
  prime 9: 23
  prime 10: 29
  ...
  prime 99: 523
  prime 100: 541

I din main funktion skal du - ganske enkelt - gennemløbe så mange positive heltal, som det er nødvendigt, for at finde de første n primtal.

For at få alt dette til at virke skal du lave følgende primes.h fil:

/* Return if i is a prime number */
int is_prime(int i);

Endvidere skal du placere følgende programlinier i filen primes.c, og oversætte denne c fil separat.

#include "primes.h"
#include <math.h>
#include <assert.h>

/* Return if i is a prime number. 
   It is assumed as a precondition that the parameter i is non-negative */
int is_prime(int i){
   assert(i >= 0);

   if (i == 1) 
     return 0;
   else if (i == 2) 
     return 1;
   else if (i % 2 == 0)
     return 0;
   else{
     int k, limit;
     limit = (int)(ceil(sqrt(i)));
     for (k = 3; k <= limit; k += 2)
        if (i % k == 0)
           return 0;
     return 1;
   }
}

Compilering af programmet: Følg mønstret fra vores gennemgang af oversættelse af tændstikpige programmet.

Læs og forstå også funktionen is_prime.

Inspirationen til denne opgave er fra bogen C by Dissection - anvendt med tilladelse fra forlaget.

Her er en løsning på problemet:

#include <stdio.h>
#include "primes.h"

int main(void) {
  int i = 1, j = 1, n;

  printf("How many primes do you want to see: ");
  scanf("%d", &n);

  while (j <= n){
    if (is_prime(i)){
      printf("prime %d: %d\n", j, i);
      j++; i++;
    }
    else {
      i++;
    }
  }

  return 0;
}

For at oversætte og køre programmet kan følgende bruges (med Windows og MinGW):

  gcc -c primes.c
  gcc primes.o test-primes.c -lm
  a.exe

Overvej meget gerne at bruge flere options, så du lettere opdager fejl tidligt:

  gcc -c -pedantic -ansi -Wall -g primes.c
  gcc -pedantic -ansi -Wall -g primes.o test-primes.c -lm
  a.exe

Brug af -lm kun nødvendig på nogle platforme.

Goldbachs formodning udtrykker en påstand om at alle lige heltal større end to er summen af to primtal. Denne formodning er hverken bevist eller modbevist. I denne opgave vil vi beskæftige os med følgende variation af påstanden:

• Ethvert lige heltal større end 6 kan udtrykkes som summen af to ulige primtal.

Skriv et program der beviser denne formodning for alle lige heltal mellem to givne grænser. Eksempelvis for alle lige heltal mellem 7 og 2.000.000. Hvis du er i stand til at finde et modeksempel, er berømmelsen måske lige om hjørnet...

Det foreslås at funktionen is_prime fra en tidligere opgave bruges ved løsningen af denne opgave.

Det er for stor en mundfuld at løse dette problem uden opdeling i mindre delproblemer. Det foreslås derfor at I skriver en funktion, som undersøger påstanden for et bestemt lige heltal, n. Denne funktion kan så kaldes for alle lige heltal n mellem f.eks. 7 og 2.000.000.

Hint: Når I skal bevise påstanden for et tal, n, anbefales det at gennemløbe alle mulige summer (n-i) + i, og dermed undersøge om I kan finde et i så både n-i og i er ulige primtal.

Hvis I bliver hurtigt færdige med denne opgave bedes I se på den variant, der på Wikipedia beskrives som Goldbach's weak conjecture.

Som en anden udfordring, kan det være interessant at se alle mulige summer- ikke kun den første. Eller denne variant: Hvilket af de testede tal har det største antal opløsninger?

Denne opgave stammer fra bogen C by Dissection - anvendt med tilladelse fra forlaget.

Der findes en video der viser hvordan jeg udvikler programmet.

Løsningen herunder svarer til løsningen, som udvikles i den nævnte video.

#include <stdio.h>
#include <assert.h>
#include "primes.h"

void goldbach(int lower_limit, int upper_limit);
void test_goldbach_for_number(int i);
int odd(int i);
int even(int i);

int main(void) {
  int lower_limit, upper_limit;
  printf("Goldbachs Conjecture: Enter lower and upper limits:\n");
  scanf("%d %d", &lower_limit, &upper_limit);

  goldbach(lower_limit, upper_limit);

  return 0;
}

void goldbach(int lower_limit, int upper_limit){
  int lower_limit_even, i;

  lower_limit_even = odd(lower_limit) ? 
                       lower_limit + 1 : lower_limit;

  for(i = lower_limit_even; i <= upper_limit; i += 2)
    test_goldbach_for_number(i);
}

/* Test goldbach conjecture for i. Either print the sum of primes,
   or a counter example of the conjecture.
   Assume as a precondition that i is even */
void test_goldbach_for_number(int i){
  int n, m, counter = 0;
  assert(even(i));

  for(n = 1; n <= i/2; n += 2){
    m = i - n;
    /* n + m == n + (i - n) == i */
    if (odd(m) && odd(n) && is_prime(n) && is_prime(m) && 
        n > 2 && m > 2){
      printf("%d + %d = %i\n", m, n, i);
      counter++;
    }
  }
  if (counter == 0)
    printf("%d is not composable!!!\n", i);  /* Error in video: missing parameter i */
  printf("\n");
}

int odd(int i){
  return i % 2 == 1;
}

int even(int i){
  return i % 2 == 0;
}

I en tidligere opgave har vi arbejdet med PPM grafik, hvor vi med tre kald af fputc skrev én pixel bestående af tre bytes (rød, grøn, blå) på en fil. Denne opgave forbereder vores fremtidige programmering af PPM grafik med en eksplict og relativ kompakt repræsentation af farverne i én pixel.

I denne opgave vil vi repræsentere en pixel i en unsigned int, som antages at fylde 4 bytes, på følgende måde:

• Den mest betydende byte er i realiteten ubrugt - reserveret til fremtidige behov (til f.eks. at skelne mellem forskellige måder at repræsentere farver på). Vi vælger dog at skrive bitmønstret 00000001 i dette felt.
• De efterfølgende tre bytes er hhv. den røde, grønne, og blå komponent (hver positive heltal mellem 0 og 255). Den blå komponent bliver således den mindst-betydende byte.

Skriv en funktion

  unsigned int make_pixel(int red, int green, int blue);

som indsætter tre heltal (som hver forudsættes at være mellem 0 og 255) i en unsigned int, og returnerer den resulterende pixels (som en unsigned int).

Skriv endvidere tre funktioner, som udtrækker hhv. den røde grønne og blå komponent af en pixel:

  int get_red(unsigned int p);
  int get_green(unsigned int p);
  int get_blue(unsigned int p);

Det skal naturligvis være således at

• get_red(make_pixel(r, g, b)) = r
• get_green(make_pixel(r, g, b)) = g
• get_blue(make_pixel(r, g, b)) = b

Check at dette er tilfældet gennem en række eksempler (såkaldte test - eller 'unit tests').

Organiser de fire funktioner ovenfor i filen pixels.c, og lav en tilsvarende header fil pixels.h. Vær sikker på at du kan oversætte (compilere) filen pixels.c separat.

Det er attraktivt - men ikke strengt nødvendigt - at anvende de bitvise operatorer (eksempelvis <<, >> og &). Disse er beskrevet i appendix C, side C-3 i lærebogen (7. udgave). Du kan også overveje at se videoen De Bitvise Operatorer.

Her er der en løsning på opgaven, som baserer sig på brug af de bit-manipulerende operatorer i C:

#include "pixel.h"

pixel make_pixel(unsigned int red, unsigned int green, unsigned int blue){
  return (1 << 24) | (red << 16) | (green << 8) | blue; 
}

unsigned int get_red(pixel p){
  return (p >> 16) & 0xff;
}

unsigned int get_green(pixel p){
  return (p >> 8) & 0xff;
}
unsigned int get_blue(pixel p){
  return p & 0xff;
}

Det er også muligt at bruge aritmetiske operator for at løse problemet:

#include "pixel.h"

pixel make_pixel(unsigned int red, unsigned int green, unsigned int blue){
  return 1 * 256 * 256 * 256 + 
             red * 256 * 256 +
                 green * 256 +
                        blue;
}

unsigned int get_red(pixel p){
  return (p / (256 * 256)) % 256;
}

unsigned int get_green(pixel p){
  return (p / 256) % 256;
}
unsigned int get_blue(pixel p){
  return p % 256;
}

Her er header filen pixel.h:

/* PIXELS - A pixel represents a RGB color. */

/** A new type that represents a single RGB pixel */
typedef unsigned int pixel;

/** The constructor of a pixel in terms of red, green and blue (between 0 and 255) */
pixel make_pixel(unsigned int red, unsigned int green, unsigned int blue);

/** Access and return the red component of the pixel p */
unsigned int get_red(pixel p);

/** Access and return the green component of the pixel p */
unsigned int get_green(pixel p);

/** Access and return the blue component of the pixel p */
unsigned int get_blue(pixel p);

Vi har tidligere i denne lektion mødt skudårsfunktionen

int isLeapYear(int year){
  int res;
  if (year % 400 == 0)
    res = 1;
  else if (year % 100 == 0)
    res = 0;
  else if (year % 4 == 0)
    res = 1;
  else res = 0;
  return res;
}

Programmer en ny skudårsfunktion med brug af && og ||, og uden brug af if-else og uden brug af betingede udtryk.

Kald begge skudårsfunktioner for alle årstal mellem år 1900 og år 2100. Giver de to funktioner samme resultat på alle årstal?

Her er funktionen der ønskes programmeret sammen med den oprindelige funktion og main funktionen

#include <stdio.h>
#include <stdlib.h>

int isLeapYear1(int year);
int isLeapYear2(int year);

int main(void) {
  int y;

  for(y = 1900; y < 2100; y++)
    printf("Year: %d:  %d %d\n", y, isLeapYear1(y), isLeapYear2(y)); 

  return 0;
}

int isLeapYear1(int year){
  int res;
  if (year % 400 == 0)
    res = 1;
  else if (year % 100 == 0)
    res = 0;
  else if (year % 4 == 0)
    res = 1;
  else res = 0;
  return res;
}

int isLeapYear2(int year){
  return (year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0));
}

Bibliotektet math.h indholder som bekendt funktionen sqrt, som beregner kvadratroden af et tal i typen double.

Programmer din egen kvadratrodsfunktion my_sqrt med brug af Newtons metode. Newtons metode gør det muligt for os at finde denne rod. Se f.eks. denne video (lavet Oscar Veliz) om hvordan dette virker. (Se formlen for rækkeudviklingen ved tid 2:23). Bemærk venligst at forfatteren af videoen laver en fejl i den nederste formel ved tid 2:26. Den korrekte formel er x_n+1 = 1/2(x_n + a/x_n). Regn selv efter.

Vær sikker på at du programmerer en funktion, som tager en double som parameter, og som returnerer en double som resultat.

Hvordan vil du håndtere en situation, hvor der overføres et negativt input?

Udskriv en table over a, my_sqrt(a) og sqrt(a) for alle heltal a mellem 0.0 og 25.0, og check dermed om din nye funktion leverer gode resultater.

Her er en mulig løsning:

#include <stdio.h>
#include <math.h>
#define EPSILON 0.00001

double my_sqrt(double x);

int main(void) {
  double d;

  for(d = 1.0; d <= 25; d++)
    printf("my_sqrt(%4f) = %8f   sqrt(%4f) = %f\n", d, my_sqrt(d), d, sqrt(d));

  return 0;
}

double my_sqrt(double a){
 double guess = a / 3 , next_guess = 0;
 int done = 0;
 int c = 0;

 while (!done){
   next_guess = 0.5 * (guess + a / guess); 
   done = fabs(next_guess - guess) <= EPSILON;
   guess = next_guess;
 }

 return guess;
}

I lektionen om iterative kontrolstrukturer arbejdede vi med to opgaver, som vi nu vil tage op igen med det formål at indføre abstraktion med funktioner.

I opgave programmeringsopgave 1 side 267 (i Problem Solving and Program Design in C, eighth edition) summerede vi alle heltal fra 1 til n, og vi sammenlignede værdien af denne sum med (n + 1)* n / 2. Skriv nu følgende to funktioner:

• En funktion sum_iter med én int parameter n. Funktionen skal addere alle heltal fra 1 til n. Funktionen skal returnere denne sum.
• En funktion sum_formula med én int parameter n som indkapsler beregningen af (n + 1)* n / 2, og som returnerer værdien af dette udtryk.

I skal kalde disse to funktioner på passende input og sammenligne deres resultater (ligesom i den oprindelige opgave).

I lektionen om iterative kontrolstrukturer arbejdede vi også med opgave 1 side 181 i bogen. Vi har en befolkning på 9870 personer som vokser med 10% per år. Spørgsmålet var hvor mange år der går inden befolkningstallet er mere end 30000.

Skriv nu en funktion som generaliserer denne opgave. Mere specifikt:

• En funktion population_projection med tre double parametre: start-befolkningstallet, vækstprocent pr år, og den øvre grænse af befolkningstallet. Funktionen skal returnere det antal år (af typen int) det tager for befolkningen at vokse fra start-befolkningstlalet til mere end slut-befolkningstallet.

Kald derefter funktionen så den løser opgaven fra side 181 i bogen (med de tre givne tal 9870, 10% og 30000).