Kapitel 3
Funktioner

Kurt Nørmark ©
Institut for Datalogi, Aalborg Universitet

Sammendrag
Forrige lektion Næste lektion
Stikord Referencer Indhold		I denne lektion gennemgår vi funktions- og procedure begrebet, herunder lokale variable og parametre. Vi ser naturligvis også på detaljer omkring funktioner i C.

Funktioner - Lasagne
Lasagne al forno
Slide Indhold Stikord
Referencer Lærebog 

  • Bland og ælt 500 g durum hvedemel, 5 æg, lidt salt og 2 spsk olie.

  • Kør pastaen gemmen en pastamaskine i tynde baner.

  • Smelt 3 spsk smør, og rør det sammen med 3 spsk mel.

  • Spæd med med 5 dl mælk og kog sovsen under svag varme.

  • Svits 2 hakkede løg med 500 g hakket oksekød, samt salt og pebber.

  • Tilsæt 3 spsk tomatpuré, en ds. flåede tomater og 3 fed knust hvidløg.

  • Kog kødsovsen 10 minutter.

  • Bland nu lagvis pastabaner, kødsovs og hvid sovs. Drys med paramesanost.

  • Gratiner retten i ovnen 15 minutter ved 225 grader.

En god lasagne - en ustruktureret opskrift

Struktureret lasagne
Slide Indhold Stikord
Referencer Lærebog 

I en mere struktureret opskrift indgår delopskrifter på lasagneplader, hvid sovs og kødsovs

Program: Lasagne. 
Lav en dobbelt portion lasagneplader.

Lav en portion hvid sovs.

Lav en portion kødsovs.

Bland nu lagvis pastabaner, kødsovs og hvid sovs. Drys med paramesanost.

Gratiner retten i ovnen 15 minutter ved 225 grader.

Program: Lav en dobbelt portion lasagneplader. 
Bland og ælt 500 g durum hvedemel, 5 æg, lidt salt og 2 spsk olie;

Kør pastaen gemmen en pastamaskine i tynde baner;

Program: Lav en portion hvid sovs. 
Smelt 3 spsk smør, og rør det sammen med 3 spsk mel;

Spæd med med 5 mælk og kog sovsen under svag varme;

Program: Lav en portion kødsovs. 
Svits 2 hakkede løg med 500 g hakket oksekød, 
samt salt og pebber;

Tilsæt 3 spsk tomatpuré, en ds. flåede tomater
og 3 fed knust hvidløg;

Kog kødsovsen 10 minutter;

Anvendelser af delopskrifter højner abstraktionsniveauet og muliggør genbrug af basale opskrifter.

Delopskrifter svarer til procedurer i programmeringssprog. Brug af parametre generaliserer en opskrift så den bliver mere alsidig.

Lasagne ala C
Slide Indhold Stikord
Referencer Lærebog 

Program: Et pseudo C program som laver lasagne. 
#include <stdio.h>

void make_lasagne_plates(void);
void make_white_sauce(void);
void make_meat_sauce(void)

int main(void) {
  make_lasagne_plates();
  make_white_sauce();
  make_meat_sauce();
  
  mix plates, meat sauce, and white sauce;
  sprinkle with paramesan cheese;
  bake 15 minutes at 225 degrees;  
  
  return 0;
}

void make_lasagne_plates(void) {
  mix flour, egs, salt and oil;
  process the pasta in the pasta machine;
}

void make_white_sauce(void) {
  melt butter and stir in some flour;
  add milk and boil the sauce;
}

void make_meat_sauce(void){
  chop the onion, and add meat, salt and pebber;
  add tomatos and garlic;
  boil the sauce 10 minutes;
}

Tændstikgrafik abstraktioner
Eksempel: En tændstikpige (1)
Slide Indhold Stikord
Referencer Lærebog 

Vi ønsker at tegne en 'tændstikpige' ved brug af simpel tegngrafik

Program: Udskrivning af tændstikpige i termer af udskrivning af hoved, arme, krop og ben. 
int main(void){
  prn_match_girl();
  return 0;
}

void prn_match_girl(void){
  prn_head();
  prn_arms();
  prn_body();
  prn_legs();
}

Program: Det ønskede program output. 
      *          
    *   *        
  *       *      
  *       *      
    *   *        
      *          
-------------    
     /\         
    /  \        
   /    \       
  /      \      
 /        \     
/          \    
-------------    
     /\         
    /  \        
   /    \       
  /      \      
 /        \     
/          \

Tegneprocessen udføres top-down.

Det udtrykkes at en tændstikpige tegnes som et hoved, arme, krop og ben.

I næste trin må vi definere, hvordan disse kropsdele tegnes.

Eksempel: En tændstikpige (2)
Slide Indhold Stikord
Referencer Lærebog 

Pigens hoved, arme, krop og ben tegnes ved kald af generelle geometriske tegne procedurer

Program: Udskrivning af hoved, arme, krop og ben i termer af generelle geometriske figurer. 
void prn_head(void){
  prn_circle();
}

void prn_arms(void){
  prn_horizontal_line();
}

void prn_body(void){
  prn_reverse_v();
  prn_horizontal_line();
}

void prn_legs(void){
  prn_reverse_v();
}

I næste trin må vi definere hvordan vi tegner cirkler, linier og andre geometriske former

Eksempel: En tændstikpige (3)
Slide Indhold Stikord
Referencer Lærebog 

Cirkler, linier og andre former tegnes ved brug af primitiv tegngrafik

Program: Udskrivning af cirkler, linier og andre geometriske figurer. 
#include <stdio.h>

void prn_circle(void){
  printf("      *          \n");
  printf("    *   *        \n");
  printf("  *       *      \n");
  printf("  *       *      \n");
  printf("    *   *        \n");
  printf("      *          \n");
}

void prn_horizontal_line(void){
  printf("-------------    \n");
}

void prn_reverse_v(void){
  printf("     /\\         \n");
  printf("    /  \\        \n");
  printf("   /    \\       \n");
  printf("  /      \\      \n");
  printf(" /        \\     \n");
  printf("/          \\    \n");
}

Eksempel: En tændstikpige (4)
Slide Indhold Stikord
Referencer Lærebog 

Programmet er lavet top-down.

Programmering ved trinvis forfinelse.

Programmet designes og implementeres i et antal niveauer med postulering og efterfølgende realisering af et antal procedurer

Figur. En illustration of problemer og delproblemer i forbindelse med tegning af en tændstikpige

Eksempel: En tændstikpige (5)
Slide Indhold Stikord
Referencer Lærebog 

Den samlede organisering af C programmet som tegner tændstikpigen

Program: Tændstikpige programmet. 
#include "char-graphics.h"

void prn_match_girl(void);
void prn_head(void);
void prn_arms(void);
void prn_body(void);
void prn_legs(void);

int main(void){
  prn_match_girl();
  return 0;
}

void prn_match_girl(void){
  prn_head();
  prn_arms();
  prn_body();
  prn_legs();
}

void prn_head(void){
  prn_circle();
}

void prn_arms(void){
  prn_horizontal_line();
}

void prn_body(void){
  prn_reverse_v();
  prn_horizontal_line();
}

void prn_legs(void){
  prn_reverse_v();
}

Program: Filen char-graphics.h - header fil med prototyper af de grafiske funktioner. 
/* Very simple graphical character-based library  */


/* Print a circle */
void prn_circle(void);

/* Print a horizontal line */
void prn_horizontal_line(void);

/* Print a reverse v shape */
void prn_reverse_v(void);

Program: Filen char-graphics.c - implementationen af de grafiske funktioner. 
#include <stdio.h>

void prn_circle(void){
  printf("      *          \n");
  printf("    *   *        \n");
  printf("  *       *      \n");
  printf("  *       *      \n");
  printf("    *   *        \n");
  printf("      *          \n");
}

void prn_horizontal_line(void){
  printf("-------------    \n");
}

void prn_reverse_v(void){
  printf("     /\\         \n");
  printf("    /  \\        \n");
  printf("   /    \\       \n");
  printf("  /      \\      \n");
  printf(" /        \\     \n");
  printf("/          \\    \n");
}

Program: Oversættelse af programmerne. 
* Compilation of the char-graphics.c library:

   gcc -c char-graphics.c

* Compilation of the match-girl.c program:

   gcc match-girl.c char-graphics.o

Program: Oversættelse af programmerne - med mange warnings. 
* Compilation of the char-graphics.c library:

   gcc -ansi -pedantic -Wall -O -c char-graphics.c

* Compilation of the match-girl.c program:

   gcc -ansi -pedantic -Wall -O match-girl.c char-graphics.o

Henvisning

Funktioner skal erklæres før brug.

Genbrugelige funktioner organiseres i separat oversatte filer.

Prototyper af sådanne funktioner skrives i såkaldte header filer.

Del og hersk
Slide Indhold Stikord
Referencer Lærebog 

Komplekse problemer kan ofte opdeles i et antal simplere delproblemer.

Delproblemernes løsninger kan ofte sammensættes til en løsning på det oprindelige problem.

Figur. Opdelning af et kompleks problem i delproblemer

  • Del og hersk som top down programmering ved trinvis forfinelse:

    • Hvert delproblem P løses i en procedure

    • Procedurer, som er løsninger på delproblemer af P, placeres efter proceduren som løser P

      • Kræver erklæring af funktionsprototyper i starten af programmet

    • I kroppen af proceduren, som løser problemet P, programmeres en sammensætning af delproblemernes løsning

Procedurer og funktioner
Procedurer og funktioner
Slide Indhold Stikord
Referencer Lærebog 

Begrebet procedure: En procedure er en abstraktion over en sekvens af kommandoer
Begrebet funktion: En funktion er en abstraktion over et udtryk

  • Procedure

    • En proceduredefinition indkapsler et antal kommandoer

    • Kaldet af en procedure er selv en kommando

  • Funktion

    • En funktionsdefinition indkapsler netop ét udtryk

    • Kaldet af en funktion er selv et udtryk

Både procedurer og funktioner kan generaliseres ved brug af parametre

Funktionsdefinitioner i C
Slide Indhold Stikord
Referencer Lærebog 

C skelner ikke skarpt mellem procedurer og funktioner

I C kaldes begge abstraktionsformer funktioner

Syntax: En funktionsdefinition i C

type function_name (formal_parameter_list) {
  declarations
  commands
}

  • Karakteristika:

    • Procedurer angiver type som void

    • Funktioner angiver type som en kendt datatype, f.eks. int, char, eller double

    • I procedurer og funktioner uden parametre angives formal_parameter_list som void

I mange tilfælde er en C funktion en blanding af en procedure og en funktion

Man kan tænke på mange C funktioner som værdi-returnerende procedurer

Funktionskald i C
Slide Indhold Stikord
Referencer Lærebog 

Syntax: Et funktionskald i C

function_name (actual_parameter_list)

  • Karakteristika:

    • En funktion kan ikke kaldes før den er erklæret

    • Antallet af aktuelle parametre i kaldet skal modsvare antallet af formelle parametre i definitionen

    • En aktuel parameter er et udtryk, som beregnes inden den overføres og bindes til den tilsvarende formelle parameter

Der er flere karakteristika, som knytter sig til parametrene.

Vi vender tilbage til disse lidt senere.

Eksempel: Temperaturomregninger
Slide Indhold Stikord
Referencer Lærebog 

Eksempler på ægte matematisk funktioner, som udelukkende karakteriseres af deres input og output

Program: Et program som omregner frysepunkt og kogepunkt til Fahrenheit grader. 
#include <stdio.h>

double fahrenheit_temperature(double celcius_temp){
  return (9.0 / 5.0) * celcius_temp + 32.0;
}

int main(void){

  printf("Freezing point: %6.2lf F.\n", 
         fahrenheit_temperature(0.0));

  printf("Boiling point: %6.2lf F.\n",
         fahrenheit_temperature(100.0));
  
  return 0;
}

Figur. To kald af fahrenheit_temperature funktionen

Program: Et program som udskriver en nyttig temperaturkonverteringstabel. 
#include <stdio.h>

double celcius_temperature(double fahrenheit_temp){
  return (5.0 / 9.0) * (fahrenheit_temp - 32.0);
}

int main(void){
  double f;  

  printf("%-20s %-20s\n", "Fahrenheit degrees", "Celcius degrees");

  for (f = 1.0; f <= 100.0; f++)
    printf("%-20.2lf %-20.2lf\n", f, celcius_temperature(f));
  
  return 0;
}

Program: Output fra ovenstående program. 
Fahrenheit degrees   Celcius degrees     
1.00                 -17.22              
2.00                 -16.67              
3.00                 -16.11              
4.00                 -15.56              
5.00                 -15.00              
6.00                 -14.44              
7.00                 -13.89              
8.00                 -13.33              
9.00                 -12.78              
10.00                -12.22              
11.00                -11.67              
12.00                -11.11              
13.00                -10.56              
14.00                -10.00              
15.00                -9.44               
16.00                -8.89               
17.00                -8.33               
18.00                -7.78               
19.00                -7.22               
20.00                -6.67               
21.00                -6.11               
22.00                -5.56               
23.00                -5.00               
24.00                -4.44               
25.00                -3.89               
26.00                -3.33               
27.00                -2.78               
28.00                -2.22               
29.00                -1.67               
30.00                -1.11               
31.00                -0.56               
32.00                0.00                
33.00                0.56                
34.00                1.11                
35.00                1.67                
36.00                2.22                
37.00                2.78                
38.00                3.33                
39.00                3.89                
40.00                4.44                
41.00                5.00                
42.00                5.56                
43.00                6.11                
44.00                6.67                
45.00                7.22                
46.00                7.78                
47.00                8.33                
48.00                8.89                
49.00                9.44                
50.00                10.00               
51.00                10.56               
52.00                11.11               
53.00                11.67               
54.00                12.22               
55.00                12.78               
56.00                13.33               
57.00                13.89               
58.00                14.44               
59.00                15.00               
60.00                15.56               
61.00                16.11               
62.00                16.67               
63.00                17.22               
64.00                17.78               
65.00                18.33               
66.00                18.89               
67.00                19.44               
68.00                20.00               
69.00                20.56               
70.00                21.11               
71.00                21.67               
72.00                22.22               
73.00                22.78               
74.00                23.33               
75.00                23.89               
76.00                24.44               
77.00                25.00               
78.00                25.56               
79.00                26.11               
80.00                26.67               
81.00                27.22               
82.00                27.78               
83.00                28.33               
84.00                28.89               
85.00                29.44               
86.00                30.00               
87.00                30.56               
88.00                31.11               
89.00                31.67               
90.00                32.22               
91.00                32.78               
92.00                33.33               
93.00                33.89               
94.00                34.44               
95.00                35.00               
96.00                35.56               
97.00                36.11               
98.00                36.67               
99.00                37.22               
100.00               37.78

Eksempel: Antal dage i en måned
Slide Indhold Stikord
Referencer Lærebog 

Vi introducerer en funktion i programmet der beregner antal dage i en måned

Vi bruger eksemplet til at diskutere overførsel af parametre til funktioner

Program: Et program der beregner antal dage i en måned med en funktion. 
#include <stdio.h>
#include <stdlib.h>

int daysInMonth(int mth, int yr);
int isLeapYear(int yr);

int main(void) {

  int mth, yr;

  do{
    printf("Enter a month - a number between 1 and 12: ");
    scanf("%d", &mth);
    printf("Enter a year: ");
    scanf("%d", &yr);

    printf("There are %d days in month %d in year %d\n",
              daysInMonth(mth, yr), mth, yr);
  } while (yr != 0);

  return 0;
}

int daysInMonth(int month, int year){
  int numberOfDays;
  switch(month){
    case 1: case 3: case 5: case 7: case 8: case 10: case 12: 
      numberOfDays = 31; break;
    case 4: case 6: case 9: case 11: 
      numberOfDays = 30; break;
    case 2:
      if (isLeapYear(year)) numberOfDays = 29; 
      else numberOfDays = 28; break;
    default: exit(-1);  break;
  }
  return numberOfDays;
}   

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;
}

Henvisning

Vi har øget genbrugeligheden - og dermed værdien af vort program

Vi ønsker som regel at undgå brug af scanf og printf i genbrugelige procedurer og funktioner

Eksempel: GCD
Slide Indhold Stikord
Referencer Lærebog 

Vi introducerer ligeledes en funktion i programmet der beregner den største fælles divisor

Vi vil igen diskutere overførsel af parametre

Program: Et program der beregner største fælles divisor med en funktion. 
#include <stdio.h>

int gcd(int, int);

int main(void) {
  int i, j, small, large;
 
  printf("Enter two positive integers: ");
  scanf("%d %d", &i, &j);

  small = i <= j ? i : j;
  large = i <= j ? j : i;
  
  printf("GCD of %d and %d is %d\n\n", i, j, gcd(large, small));
  
  return 0;
}

int gcd(int large, int small){
  int remainder; 
  while (small > 0){
    remainder = large % small;
    large = small;
    small = remainder;
  }
  return large;
}

Henvisning

Parametre til C funktioner
Slide Indhold Stikord
Referencer Lærebog 

Parametre til en funktion bruges til at gøre funktionen mere generelt anvendelig

Begrebet formel parameter: En parameter, som optræder i en funktionsdefinition, kaldes en formel parameter. En formel parameter er et navn.
Begrebet aktuel parameter: En parameter, som optræder i et kald af en funktion, kaldes en aktuel parameter. En aktuel parameter er et udtryk, som beregnes inden det overføres.

  • Regler for parameteroverførsel:

    • Antallet af aktuelle parametre i kaldet skal modsvare antallet af formelle parametre i definitionen

    • Typen af en aktuel parameter skal modsvare den angivne type af hver formel parameter

      • Dog muligheder for visse implicitte typekonverteringer

    • Parametre til funktioner i C overføres som værdiparametre

      • Der overføres en kopi af den aktuelle parameters værdi

      • Kopien bindes til (assignes til) det formelle parameternavn

      • Når funktionen returnerer ophører eksistensen af de formelle parametre, på samme måde som lokale variable i funktionen.

Eksempel: Rodsøgning
Rodsøgning (1)
Slide Indhold Stikord
Referencer Lærebog 

Enhver kontinuert funktion f, som har en negativ værdi i l og en positiv værdi i u (eller omvendt) vil have mindst én rod r mellem l og u.

Figur. En kontinuert funktion f med en rod mellem l og u

Ved at indsnævre intervallet [l, u], og ved hele tiden at holde roden mellem l og u, kan vi hurtigt finde frem til en værdi r for hvilken f(r) = 0.

Rodsøgning (2)
Slide Indhold Stikord
Referencer Lærebog 

Program: Rodsøgningsfunktionen. 
double findRootBetween(double l, double u){
 while (!isSmallNumber(f(middleOf(l,u)))){ 
   if(sameSign(f(middleOf(l,u)), f(u)))
     u = middleOf(l,u);
   else 
     l = middleOf(l,u);
 }
 return middleOf(l,u);
}

Program: Funktionerne sameSign, middleOf og isSmallNumber. 
int sameSign(double x, double y){
  return x * y >= 0.0;
}

double middleOf(double x, double y){
  return x + (y - x)/2;
}

int isSmallNumber(double x){
  return (fabs(x) < 0.0000001);
}

Program: Hele rodsøgningsprogrammet. 
#include <stdio.h>
#include <math.h>
 
double f (double x){
  /* (x - 5.0) * (x - 3.0) * (x + 7.0) */
  return (x*x*x - x*x - 41.0 * x + 105.0);
}

int sameSign(double x, double y){
  return x * y >= 0.0;
}

double middleOf(double x, double y){
  return x + (y - x)/2;
}

int isSmallNumber(double x){
  return (fabs(x) < 0.0000001);
}   

double findRootBetween(double l, double u){
 while (!isSmallNumber(f(middleOf(l,u)))){ 
   if(sameSign(f(middleOf(l,u)), f(u)))
     u = middleOf(l,u);
   else 
     l = middleOf(l,u);
 }
 return middleOf(l,u);
}  

int main (void){
    double x, y;
    int numbers; 

    do{
      printf("%s","Find a ROOT between which numbers: ");
      numbers = scanf("%lf%lf", &x, &y);

      if (numbers == 2 && !sameSign(f(x),f(y))){
          double solution = findRootBetween(x,y);
          printf("\nThere is a root in %lf\n", solution);
        }
      else if (numbers == 2 && sameSign(f(x),f(y)))
          printf("\nf must have different signs in %lf and %lf\n",
                  x, y);
      else if (numbers != 2)
          printf("\nBye\n\n");
    }
    while (numbers == 2);
}

Rekursive funktioner
Rekursive funktioner
Slide Indhold Stikord
Referencer Lærebog 

En rekursiv funktion kalder sig selv

Rekursive funktioner er nyttige når et problem kan opdeles i delproblemer, hvoraf nogle har samme natur som problemet selv

Henvisning

Program: Et program med en rekursivt defineret fakultetsfunktion. 
#include <stdio.h>

unsigned long factorial(unsigned long n){
  if (n == 0)
    return 1;
  else return n * factorial(n - 1);
}

int main(void) {
  unsigned long k;

  for (k = 1; k <= 12; k++)
    printf("%-20lu %20lu\n", k, factorial(k));
  
  return 0;
}

Program: Output fra ovenstående program. 
1                                       1
2                                       2
3                                       6
4                                      24
5                                     120
6                                     720
7                                    5040
8                                   40320
9                                  362880
10                                3628800
11                               39916800
12                              479001600

Henvisning

Program: En rekursiv version af funktionen findRootBetween. 
double findRootBetween(double l, double u){
  if (isSmallNumber(f(middleOf(l,u))))
     return middleOf(l,u);
  else if (sameSign(f(middleOf(l,u)), f(u)))
     return findRootBetween(l, middleOf(l,u));
  else if (!sameSign(f(middleOf(l,u)), f(u)))
     return findRootBetween(middleOf(l,u),u);
  else exit (-1);
}

Program: Hele rodsøgningsprogrammet. 
#include <stdio.h>
#include <math.h>
 
double f (double x){
  /* (x - 5.0) * (x - 3.0) * (x + 7.0) */
  return (x*x*x - x*x - 41.0 * x + 105.0);
}

int sameSign(double x, double y){
  return x * y >= 0.0;
}

double middleOf(double x, double y){
  return x + (y - x)/2;
}

int isSmallNumber(double x){
  return (fabs(x) < 0.0000001);
}   

double findRootBetween(double l, double u){
  if (isSmallNumber(f(middleOf(l,u))))
     return middleOf(l,u);
  else if (sameSign(f(middleOf(l,u)), f(u)))
     return findRootBetween(l, middleOf(l,u));
  else if (!sameSign(f(middleOf(l,u)), f(u)))
     return findRootBetween(middleOf(l,u),u);
  else exit (-1);
}  

int main (void){
    double x, y;
    int numbers; 

    printf("RECURSIVE ROOT FINDING\n\n");

    do{
      printf("%s","Find a ROOT between which numbers: ");
      numbers = scanf("%lf%lf", &x, &y);

      if (numbers == 2 && !sameSign(f(x),f(y))){
          double solution = findRootBetween(x,y);
          printf("\nThere is a root in %lf\n", solution);
        }
      else if (numbers == 2 && sameSign(f(x),f(y)))
          printf("\nf must have different signs in %lf and %lf\n",
                  x, y);
      else if (numbers != 2)
          printf("\nBye\n\n");
    }
    while (numbers == 2);
}

Korrekthed af programmer
Assertions
Slide Indhold Stikord
Referencer Lærebog 

Det er muligt at 'dekorere' et program med logiske udtryk (assertions), som fortæller os om programmet opfører sig som vi forventer

  • To specielt interessante assertions:

    • Præbetingelse af en funktion: Fortæller om det giver mening at kalde funktionen

    • Postbetingelse af en funktion: Fortæller om funktionen returnerer et korrekt resultat

Program: En forkert implementation af my_sqrt. 
#include <stdio.h>
#include <math.h>
/* #define NDEBUG 1 */
#include <assert.h>

int isSmallNumber(double x){
  return (fabs(x) < 0.0000001);
}   

double my_sqrt(double x){
  double res;
  assert(x >= 0);
  res = 7.3;
  assert(isSmallNumber(res*res - x));
  return res;
}

int main(void) {

  printf("my_sqrt(15.0): %lf\n", my_sqrt(15.0));
  printf("my_sqrt(20.0): %lf\n", my_sqrt(20.0));
  printf("my_sqrt(2.0): %lf\n", my_sqrt(2.0));
  printf("my_sqrt(16.0): %lf\n", my_sqrt(16.0));
  printf("my_sqrt(-3.0): %lf\n", my_sqrt(-3.0));
  
  return 0;
}

Program: En brugbar implementation af my_sqrt implementeret via rodsøgningsfunktionen. 
#include <stdio.h>
#include <math.h>
/* #define NDEBUG 1 */
#include <assert.h>

int isSmallNumber(double x){
  return (fabs(x) < 0.0000001);
}   

double displacement; 

double f (double x){
  return (x * x - displacement);
}

int sameSign(double x, double y){
  return x * y > 0.0;
}

double middleOf(double x, double y){
  return x + (y - x)/2;
}

double findRootBetween(double l, double u){
 while (!isSmallNumber(f(middleOf(l,u)))){ 
   if(sameSign(f(middleOf(l,u)), f(u)))
     u = middleOf(l,u);
   else 
     l = middleOf(l,u);
 }
 return middleOf(l,u);
}  


double my_sqrt(double x){
  double res;
  assert(x >= 0);
  displacement = x; 
  res = findRootBetween(0,x);
  assert(isSmallNumber(res*res - x));
  return res;
}

int main(void) {

  printf("my_sqrt(15.0): %lf\n", my_sqrt(15.0));
  printf("my_sqrt(20.0): %lf\n", my_sqrt(20.0));
  printf("my_sqrt(2.0): %lf\n", my_sqrt(2.0));
  printf("my_sqrt(16.0): %lf\n", my_sqrt(16.0));
  
  return 0;
}

Program: En udgave af findRootBetween med præbetingelse og postbetingelse. 
double findRootBetween(double l, double u){
 double res;
 assert(l <= u); assert(!sameSign(f(l), f(u))); 
 while (!isSmallNumber(f(middleOf(l,u)))){ 
   if(sameSign(f(middleOf(l,u)), f(u)))
     u = middleOf(l,u);
   else 
     l = middleOf(l,u);
 }
 res = middleOf(l,u);
 assert(isSmallNumber(f(res)));
 return res;
}

Samlede referencer
Indhold Stikord
Notes about GCC
Programmet der beregner antal dage i en måned
Programmet der beregner største fælles divisor
Rekursive delproblemer
Den iterative funktion findRootBetween

 

Kapitel 3: Funktioner
Kursets hjemmeside     Forfatteren's hjemmeside     Om frembringelsen af disse sider     Forrige lektion (top)     Næste lektion (top)     Forrige lektion (bund)     Næste lektion (bund)     
Genereret: 7. Juli 2010, 15:10:30