Thema indholdsfortegnelse -- Tastaturgenvej: 'u'  Forrige tema i denne lektion -- Tastaturgenvej: 'p'  Næste slide i denne lektion -- Tastaturgenvej: 'n'Kontrolstrukturer
9.  Gentagelse af kommandoer

En af styrkerne ved en computer er dens evne til at gennemføre mange gentagelser på kort tid. Når vi programmerer bruger vi forskellige løkker til at kontrollere gentagelser af kommandoer. Undertiden bruget vi også betegnelsen iterationer i stedet for gentagelser.

I C er der tre forskellige løkker, som vi alle vil se på i dette afsnit. Vi starter med whileløkker.

9.1 Gentagelse med while (1)9.5 Gentagelse med for (1)
9.2 Gentagelse med while (2)9.6 Gentagelse med for (2)
9.3 Gentagelse med do (1)9.7 Break, continue og return
9.4 Gentagelse med do (2)9.8 Konvertering af do og for løkker til while
 

9.1.  Gentagelse med while (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Hvis man kun vil lære én løkke konstruktion er det while løkken man bør kaste sig over. Som vi vil indse i afsnit 9.8 kan alle løkker i C relativt let omformes til whileløkker.

I en løkke er det muligt at gentage en kommando nul, én eller flere gange.

I en while løkke er det ubestemt hvormange gange kommandoen udføres.

Syntaksen af whileløkker minder om syntaksen af if, jf. syntaks 8.2 . Betydningen af en while kontrolstruktur er derimod helt forskellig fra en if kontrolstruktur.


while (logicalExpression)
  command
Syntaks 9.1    Syntaksen af en while løkke i C.

Vi viser en flowgraf for whileløkken herunder. Bemærk for det første muligheden for at køre rundt i løkken, altså det at kommandoen kan udføres et antal gange, under kontrol af det logiske udtryk. Bemærk også, at vi kan udføre whileløkken helt uden af udføre kommandoen (nemlig i det tilfælde at det logiske udtryk er falsk når vi møder det første gang).

Figur 9.1    Flow graf for en while løkke

 

9.2.  Gentagelse med while (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi beskriver her på punktform betydningen af en whileløkke.

  • Betydningen af while:

    • Det logiske udtryk beregnes

    • Hvis værdien er true udføres kommandoen, og while løkken startes forfra

    • Hvis værdien er false afsluttes while løkken

Vores første eksempel er et klassisk program, nemlig Euclids algoritme til at finde den største fælles divisor af to positive heltal. Givet to heltal small og large ønsker vi altså at finde det største tal, som både går op i small og large.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

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

  small = i <= j ? i : j;
  large = i <= j ? j : i;
  
  while (small > 0){
    remainder = large % small;
    large = small;
    small = remainder;
  }

  printf("GCD of %d and %d is %d\n\n", i, j, large);
  
  return 0;
}
Program 9.1    Euclids algoritme - største fælles divisor - programmeret med en while løkke.

Ved første øjesyn er det ikke umiddelbart klart, hvorfor algoritmen virker. Man mener, at netop ovenstående algoritme er det første eksempel i historien på en ikke-triviel beregningsmæssig opskrift (algoritme).

Lad os kort forklare programmet ud fra et eksempel. Lad os antage at vi skal finde den største fælles divisor af tallene 30 og 106. Dette tal betegnes som gcd(30,106), og det viser sig at være 2. gcd betyder "greatest common divisor". Variablen small starter altså med at være 30 og large er 106. I det første gennemløb af whileløkken beregnes resten af division af 106 med 30. Dette er 16, og dette tal vil generelt altid være mindre end divisoren 30. Hermed bliver large sat til 30 og small til 16.

Set over et antal gennemløb producerer programmet talrækken

Den essentielle indsigt er nu at gcd(106,30) = gcd(30,16) = gcd(16,14) = gcd(14,2) = gcd(2,0) = 2. Dette indses ved et induktionsargument. Den sidste lighed følger af, at det største tal der både går op i 2 og 0 naturligvis er 2.

Med dette vil programmet finde, at det største tal der både går op i 106 og 30 er 2. Ydermere viser det sig, at programmet finder resultatet i et bemærkelsesværdigt lille antal skridt.

Herunder er vist en simpel variant af program 9.1 som udskriver information om mellemresultaterne.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

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

  small = i <= j ? i : j;
  large = i <= j ? j : i;

  printf("%d %d ", large, small);
  
  while (small > 0){
    remainder = large % small;
    large = small;
    small = remainder;
    printf("%d ", small);
  }

  printf("\n\nGCD of %d and %d is %d\n\n", i, j, large);
  
  return 0;
}
Program 9.2    En udgave af Euclids algoritme som udskriver den beregnede talrække.

 

9.3.  Gentagelse med do (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I nogle situationer er vi interesserede i at arbejde med løkker, som sikrer mindst én gentagelse. I C er do-løkken af en sådan beskaffenhed. I andre sprog, ala Pascal, hedder sådanne løkker ofte repeat until.

En do-løkke sikrer altid mindst ét gennemløb af løkken


do
  command
while (logicalExpression)
Syntaks 9.2    Syntaksen af en do-løkke i C

Figur 9.2    Flow graf for en do løkke

 

9.4.  Gentagelse med do (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Ligesom for de andre kontrolstrukturer vi har set vil vi beskrive betydningen på punktform, og vi vil se på et eksempel.

  • Betydningen af do:

    • Kommandoen udføres

    • Det logiske udtryk beregnes

    • Hvis værdien er true overføres kontrollen til starten af do

    • Hvis værdien er false afsluttes do løkken

I nedenstående program viser vi en programstump, som vi kunne kalde "ask user". Programmet insisterer på et ja/nej svar, i termer af bogstavet 'y' eller 'n'. Vi antager her, for at simplificere opgaven, at brugeren kun indtaster ét tegn.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

int main(void) {

  char answer, forget;

  do {
    printf("Answer yes or no (y/n): ");
    scanf("%c%c", &answer, &forget);
  } while (answer != 'y' && answer != 'n');

  printf("The answer is %s\n\n", 
          answer == 'y'? "yes" : "no");
  
  return 0;
}
Program 9.3    Et program som ønsker et 'yes/no' svar.

Kroppen af løkken skal udføres mindst én gang. Hvis ikke svaret er tilfredsstillende skal vi udføre kroppen endnu en gang.

Bemærk at vi læser to tegn, answer og forget. forget introduceres for læse lineskiftet (RETURN), som er nødvendig for at få scanf til at reagere. Dette er ikke en perfekt løsning på problemet, men dog bedre end hvis kun ét tegn læses. Leg gerne selv med mulighederne.

 

9.5.  Gentagelse med for (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Ideen med den næste løkke, for-løkken, er i bund og grund at kunne kontrollere et fast og på forhånd kendt antal gentagelser. Det er imidlertid sådan, at for-løkker i C er mere generelle end som så.

I mange sprog benyttes for kontrolstrukturen hvis man på forhånd kender antallet af gentagelser.

for kontrolstrukturen i C kan benyttes således, men den bruges også ofte til mere generel gentagelse.

Her følger syntaksen og dernæst den punktvise betydning af for-løkken.


for(initExpression; continueExpression; updateExpression)
  command
Syntaks 9.3    Opbygningen af en for-løkke i C.

  • Betydning af en for-løkke:

    • Trin 1: initExpression evalueres af hensyn til sideeffekter

    • Trin 2: continueExpression evalueres, og hvis den er false (0) er for løkken færdig

    • Trin 3: for løkkens command udføres

    • Trin 4: updateExpression evalueres, og der fortsættes med trin 2

I nedenstående eksempel udskriver vi alle tal fra og med lower til og med upper. Dette eksempel egner sig godt til en for-løkke, idet vi inden løkken starter ved at der skal bruges upper - lower + 1 gentagelser.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int main(void) {

  int upper, lower, k;

  printf("Enter two integers, lower and upper: ");
  scanf("%d %d", &lower, &upper);

  for (k = lower; k <= upper; k++)
    printf("k = %d\n", k);
  
  return 0;
}
Program 9.4    En typisk for-løkke med et forudbestemt antal gentagelser.

 

9.6.  Gentagelse med for (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Lad os illustrere den udvidede styrke af for-løkker i C. Altså styrken ud over at kunne kontrollere et på forhånd bestemt antal gentagelser.

Det er muligt at styre en kompleks gentagelse som anvender flere kontrolvariable ved brug af en for løkke

Vi genprogrammerer Euclids Algoritme fra program 9.1, nu med brug af en for-løkke. Vi vil referere til de tre bestanddele af en for-løkke, jf. syntaks 9.3.

I den røde initExpression sørger vi for at variablene sml og lg initielt indeholder det største hhv. det mindste af de tal, som er indlæst. I den lilla updateExpression laver næste skridt i rækkeudviklingen, som vi beskrev i afsnit 9.2. I den blå continueExpression kontrollerer vi termineringen (afslutningen) af gentagelsen. Bemærk at alle tilstandsændringer og check foregår i init, continue og update delene. For løkken i program 9.5 er uden krop!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

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

  for(sml = i<=j?i:j , lg = i<=j?j:i;
      sml > 0;
      rem = lg % sml , lg = sml, sml = rem);

  printf("GCD of %d and %d is %d\n\n", i, j, lg);
  
  return 0;
}
Program 9.5    Euclids algoritme - største fælles divisor - programmeret med en for-løkke 'uden krop'.

Bemærk brugen af komma i de røde og blå dele. Komma er her en operator, som beregner udtryk i sekvens, og som returnerer værdien af det sidst evaluerede udtryk. Kommaoperatoren minder om semikolon, som skal placeres mellem (eller rettere efter) kommandoer i C. Læs om kommaoperatoren i afsnit 3.13 side 98 af C by Dissection. Kommaoperatoren har lavest mulig prioritering, jf. tabel 2.3 hvilket betyder at udtryk med alle andre operatorer end komma beregnes først.

Alle udtryk kan udelades, hvilket afstedkommer en uendelig løkke

Vi skitserer herunder situationen hvor initExpression og continueExpression begge er tomme. Dette afstedkommer en uendelig løkke - altså en løkke som ikke terminerer med mindre vi udfører et eksplicit hop ud af for-løkkens krop.

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>

int main(void) {

  long i = 0;

  for( ; ; ++i)
    printf("%ld: Hi there...\n", i);
  
  return 0;
}
Program 9.6    En for løkke, der optæller en variabel uendeligt.

 

9.7.  Break, continue og return
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi vil her se på mulighederne for at påvirke kontrolforløbet af løkker og visse udvælgende kontrolstrukturer.

I C kan man bruge goto og labels, som antydet i afsnit 5.2. Vi foretrækker dog mere specifikke og specialiserede hop kommandoer, som ikke kræver at vi introducerer labels. Vi ser nu på break, continue og return.

Anvendelse af generelle hop - goto - anses for meget dårlig programmeringsstil.

Brug af 'mere specialiserede hop' bruges oftere.

  • break

    • anvendes til at springe ud af (den inderste) switch, while, do, eller for

  • continue

    • anvendes til at afslutte kommandoen i en while, do eller for løkke

  • return

    • anvendes til at afbryde, og returnere et resultat fra en funktion

Vi viser her et program, som illustrerer continue og break. Programmet indeholder en 'uendelig for-løkke'. Den røde del sørger for at gentagelser med lige i værdier overspringes, i det mindste således at i ikke skrives ud i printf kommandoen. Den blå del sørger for at afbryde løkken når værdien af i bliver større end 1000.

Samlet set vil program 9.7 udskrive alle ulige tal mellem 1 og 1000.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int main(void) {

  long i = 1;

  for( ; ; ++i){
    if (i % 2 == 0) continue;
    if (i > 1000) break;
    printf("%ld: Hi there...\n", i);
  }
  
  return 0;
}
Program 9.7    Illustration af break og continue i en for-løkke.

Vi møder return kommandoen i kapitel 10, hvor emnet er funktioner.

 

9.8.  Konvertering af do og for løkker til while
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I dette afsnit overbeviser vi os om, at både do- og for-løkker kan omskrives til whileløkker. Skabelonen for omskrivningerne ses i tabel 9.1.

Ethvert program med do og for løkker kan let omskrives til kun at bruge while løkker

Original Transformation
for (expr1; expr2; expr3)
  command


expr1;
while (expr2) {
  command;
  expr3;
}
do
  command
while (expr)
command;
while (expr)
  command;
Tabel 9.1    

Læg mærke til, at der for alle gentagende kontrolstrukturer gælder, at kontrol udtrykket er en fortsættelsesbetingelse.

Med andre ord afbrydes alle former slags løkker i C når kontroludtrykkets værdi bliver false.

Genereret: Onsdag 7. Juli 2010, 15:10:25
Thema indholdsfortegnelse -- Tastaturgenvej: 'u'  Forrige tema i denne lektion -- Tastaturgenvej: 'p'  Næste slide i denne lektion -- Tastaturgenvej: 'n'