Index over opgaver i denne lektion   Alfabetisk indeks   Kursets hjemmeside   

Opgaver og løsninger
Flere Kontrolstrukturer


4.1   Forklaring af et program med while løkke og udtryk med assignments  

Forklar hvad der udskrives af følgende program. Hvor mange gange udføres kroppen af while-løkken? Og hvilken række af tal udskriver programmet (helt præcist)? Forudsig først resultatet, og kør dernæst programmet.

#include <stdio.h>
int main(void){
   int i = 0, power = 1;

   while (++i <= 10)
      printf("%5d", power *= 2);
   printf("\n");

   return 0;
}

++i tæller i en op og power *= 2 fordobler power. Men vær sikker på at du forstår værdierne af de to udtryk ++i og power *= 2.

Hvad sker der hvis ++i erstattes af i++?

Det viste program er skrevet i typisk, koncis C-stil, og er på denne måde en typisk repræsentant for den programmeringsstil, som dyrkes af mange C programmører.

Omskriv programmet (stadig med brug af en while-løkke) således at assignments (ala *=) og increments (++) kun har en effekt på variable, men uden direkte at anvende værdierne af disse udtryk, som det er gjort i ovenstående program.

Det er også interessant at omskrive programmet, så det bruger en for-løkke i stedet for en while-løkke. Prøv dette!

Vurder selv hvilken udgave af programmet du foretrækker.

Løsning

Programmet giver følgende output:

    2    4    8   16   32   64  128  256  512 1024

Kroppen af while-løkken udføres altså 10 gange.

Hvis ++i ertattes af i++ udskrives en ekstra potens af 2:

    2    4    8   16   32   64  128  256  512 1024 2048

Hvorfor? Fordi ++i starter med at tælle i op inden der sammenlignes med 10. i++ returnerer værdien af i til sammenligning med 10, inden optælling.

Programmet i opgaven:

#include <stdio.h>
int main(void){
   int i = 0, power = 1;

   while (++i <= 10)
      printf("%5d", power *= 2);
   printf("\n");

   return 0;
}

er svært at forstå, primært på grund af incrementet af variablen i i det logiske udtryk i while-løkken.

Her er det omskrevne program, som adskiller assignments fra udtryk:

#include <stdio.h>
int main(void){
   int i = 1, power = 1;

   while (i <= 10){
      power = power * 2;
      printf("%5d", power);
      i++;
   }
   printf("\n");

   return 0;
}

Dette program er - efter min bedste overbevisning - et bedre program end det fra opgaveteksten.

Programmet kan også skrives med brug af en for-løkke, hvor for-løkken både kontrollerer variablene i og power:

#include <stdio.h>
int main(void){
   int i, power;

   for(i = 1, power = 2; i <= 10; i++, power *= 2)
      printf("%5d", power);
   printf("\n");

   return 0;
}

Bemærk brugen af kommaet i udtrykket, som indgår i initialiserings-delen af for-løkken. I C er , en operator, med lavest mulig prioritet. x,y er et udtryk på lige fod med x+y. Værdien af udtrykket x,y er y.   x er altså kun nyttig i forhold den sideeffekt den har (typisk på variable).


4.2   Sum af tal i interval som er dividerbare med samme tal  

I denne opgave gives tre positive heltal m, n og k, hvor k er større end 1. Skriv et program der adderer alle heltal mellem m og n (begge inklusive) hvor i k går op.

Eksempler:

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

Løsning

Her er en mulig løsning:

#include <stdio.h>

int main(void){

  int k, m, n, i, sum = 0;

  printf("Enter two integers m an n.\n");
  scanf("%d %d", &m, &n);

  printf("Enter an integer k greater than 1.\n");
  scanf("%d", &k);

  for(i=m; i<=n; i++){
    if (i % k == 0){
      sum += i;
    }
  }

  printf("Sum of numbers between %d and %d that are divisible by %d: %d \n", m, n, k, sum);
 
  return 0;
}


4.3   Endnu en sum af tal i et interval  

Skriv et program som læser et heltal n. Programmet skal addere alle tal i intervallet fra n til 2 * n hvis n er ikke negativ. Hvis n er negativ, skal programmet addere tallene fra 2 * n til n.

Skriv først en version med for-løkker. Dernæst en version med while løkker.

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

Løsning

Her er en mulig løsning, som anvender en for-løkke:

#include <stdio.h>

int main(void){

  int n, sum = 0, i;

  printf("Enter a positive or negative integer:\n");
  scanf("%d", &n);

  if (n < 0)
    for(i = 2 * n; i <= n; i++) sum += i;
  else 
    for(i = n; i <= 2 * n; i++) sum += i; 

  printf("%d \n", sum);

  return 0;
}

Og her er programmet lavet med en while-løkke:

#include <stdio.h>

int main(void){

  int n, sum = 0;

  printf("Enter a positive or negative integer:\n");
  scanf("%d", &n);

  if (n < 0){
    int i = 2 * n;
    while (i <= n) sum += i++;
  }
  else {
    int i = n; 
    while (i <= 2 * n) sum += i++;
  }

  printf("%d \n", sum);

  return 0;
}


4.4   Generering af grafik-filer  

I denne opgave vil vi generere grafik filer med flotte mønstre. Vi vil benytte et meget simpelt fil-format, Portable Pixmap (PPM). Du kan se på Wikipedia artiklen Netpbm format, som giver et godt overblik over formatet. Der findes også en video der diskuterer formatet, og videoen lægger kort op til denne opgave.

Her følger et velkommenteret C program, som genererer et 500 x 500 rødt rektangel:

#include <stdio.h>

int main(void) {

  FILE *image_file;                               /* The file on which to write the image */
  int i, j;

  image_file = fopen("image-file-1.pnm", "wb");   /* Open a file for writing.             */

  fputs("P6\n", image_file);                      /* Write the header, including the      */
                                                  /* so-called magic number P6            */
  fputs("500 500\n", image_file);                 /* Width: 500, Height: 500              */
  fputs("255\n", image_file);                     /* 255 colors per byte.                 */

  for(i = 0; i < 500; i++)              
    for (j = 0; j < 500; j++){
      fputc(255, image_file);                     /* Writing the red byte                 */
      fputc(0, image_file);                       /* Write the green byte                 */ 
      fputc(0, image_file);                       /* Write the blue byte                  */
    }

  fclose(image_file);                             /* Close the file.                      */
  return 0;
}

Her er en variation af programmet, som genererer et lidt mere spændende resultat:

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

int main(void) {

  FILE *image_file;
  int i, j;
  int r, g, b;

  image_file = fopen("image-file-4.pnm", "wb"); 

  fputs("P6\n", image_file); 
  fputs("500 500\n", image_file);
  fputs("255\n", image_file);

  for(i = 0; i < 500; i++)
    for (j = 0; j < 500; j++){
      r = i % 256; g = j % 256; b = (i+j) % 256;
      fputc(r, image_file);  fputc(g, image_file); fputc(b, image_file);
    }

  fclose(image_file);
  return 0;
}

Begge programmer udskriver, via den ydre for-løkke, RGB bytes (red, green, blue) række for række.

Den kreative udfordringen består i at lave flotte mønstre ved at variere programmerne ovenfor. I denne opgave er det dog en betingelse at de to for-løkker, som kontrollerer hhv. række og søjler i bitmønstret, bibeholdes. Du skal ikke forsøge at lave et stort array af RGB værdier, og ændre i dette. Senere i kurset vil vi udvikle varianter af programmet, som gør det meget mere fleksibelt at tegne forskellige geometriske figurer i en stor tabel (array) af pixels.

Det er naturligvis vigtigt, at du kan se den grafik som genereres af dit program. Her er et antal muligheder, som jeg ved virker:


4.5   En simplificeret udgave af Euclids algoritme  

Denne opgaver tager udgangspunkt i følgende udgave af Euclids algoritme, som vi har studeret nøje i denne lektion:

/* General condition loop - Euclid again*/

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

Hvad sker der hvis vi dropper ombytningen af i og j, og således risikerer at small bliver større end large i while-løkken? Her er en sådan version af programmet:

#include <stdio.h>

int main(void) {
  int a, b, i, j, remainder;
 
  printf("Enter two non-negative integers: ");
  scanf("%d %d", &a, &b);

  i = a; j = b;  /* We don't know if i > j */  
  while (j > 0){
    remainder = i % j;
    i = j;
    j = remainder;
  }

  printf("GCD of %d and %d is %d\n\n", a, b, i);
  
  return 0;
}   

Virker dette - hvorfor, eller hvorfor ikke?

Løsning

Den nye udgave virker. Her er programmet vi taler om:

#include <stdio.h>

int main(void) {
  int a, b, i, j, remainder;
 
  printf("Enter two non-negative integers: ");
  scanf("%d %d", &a, &b);

  i = a; j = b;  /* We don't know if i > j */  
  while (j > 0){
    remainder = i % j;
    i = j;
    j = remainder;
  }

  printf("GCD of %d and %d is %d\n\n", a, b, i);
  
  return 0;
}   

Hvis j > i lige før while-løkken, vil de tre sætninger i kroppen af løkken:

     remainder = i % j;
     i = j;
     j = remainder;

være ækvivalete med:

     remainder = i;
     i = j;
     j = remainder;

altså en ombytning af i og j. Undervejs i løkken vil i være større end (eller lig med) j.


4.6   Ligefrem programmering af 'største fælles divisor'  

I denne lektion har vi set at der findes fine, smarte, og effektive algoritmer til at finde den største fælles divisor af to positive heltal. Se her.

Målet med denne opgave er at træne dig i programmering med løkker, herunder at vælge gode iterative kontrolstrukturer til opgaven. Som altid er det også målet at lave et velopstillet program med god indrykning, og med brug af gode variabelnavne.

I denne opgave skal du skrive et ligefrem program, der på en simpel og intuitiv måde finder den største fælles divisor af to ikke-negative heltal a og b. Programmet skal på en systematisk måde - med brug af en løkke - afprøve om forskellig, nøje udvalgte tal er divisorer i både a og b. Overvej omhyggeligt hvordan løkken starter, og hvordan den slutter. Programmet skal finde den største sådanne divisor: altså største fælles divisor. Overvej også om der er nogle specialtilfælde vi skal tage os af, inden vi starter løkken?

Programmet skal indlæse de to heltal a og b af hvilke vi ønsker at finde den største fælles divisor. Men for ikke at starte programmet forfra hver gang vi ønsker at finde den største fælles divisor af to tal (a og b) bedes du lave programmet således at den gentager beregningen af den største fælles divisor af to indlæste tal indtil et af tallene er negativ.

Løsning

Her er en naiv løsning på GCD problemet:

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

int main(void) {
  int i, j, small, large, n;

  do {
    printf("Enter two non-negative integers: ");
    scanf("%d %d", &i, &j);
  
    small = i <= j ? i : j;
    large = i <= j ? j : i;
  
    if (small < 0 || large < 0)
      printf("Bye");
    else if (small == 0 && large == 0)
      printf("We cannot find gcd in case both inputs are zero\n");
    else if (small == 0)
      printf("GCD of 0 and %d is %d\n", large, large);
    else {                       
      /* small > 0 && large > 0 */ 
  
      n = small;
      while((small % n != 0 || large % n != 0) && (n >= 2)){
        --n;
      }
  
      /* (small % n == 0 && large % n == 0)  || (n == 1) */
  
      printf("GCD of %d and %d is %d\n", large, small, n);
    }
  } while (i >= 0 && j >= 0);

  return EXIT_SUCCESS;
}   


Genereret: Tirsdag 12. oktober 2021, 14:04:02