Umeå Universitet
Institutionen för datavetenskap
Programmeringsteknik för tekniska fysiker

Niklas Frykholm, 24 februari 1999

Gruppövning 1 - Lösningsförslag

a) Finn sex fel

g1_1.c

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

/* Detta  program beräknar sinus eller cosinus av ett
   tal. */
int main(void)
{
  int val;
  double tal;

  printf("Vad vill du göra?\n");
  printf("(1 = beräkna sinus, 2 = beräkna cosinus): ");
  scanf("%d", &val);

  printf("Ange talet: ");
  scanf("%lf", &tal);

  if (val==1)
    printf("sin(%lf) = %lf\n", tal, sin(tal));
  else
    printf("cos(%lf) = %lf\n", tal, cos(tal));

  return 0;
}

b) Operatorer och uttryck

 i <=j  --->  3 <= 7  --->  1
 i = j  --->  i = 7   --->  7
 2 + j % i  --->  2 + 7 % 3 --->  2 + 1  ---> 3
 j / i * 2  --->  7 / 3 * 2 --->  2 * 2  ---> 4
 j == i  --->  7 == 3  --->  0
 i && i - 3  --->  3 && 3 - 3  --->  3 && 0  --->  0

c) Problemlösning och programmering

1. Måla krocketklot

g2_c1.c

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

int main(void)
{
  double d, m2_per_l;
  double pi = atan(1)*4;

  printf("Ange klotets diameter (i cm): ");
  scanf("%lf", &d);

  printf("Ange hur många m^2 1 liter färg räcker till: ");
  scanf("%lf", &m2_per_l);

  printf("Det går åt %.3lf liter färg.\n",
     (4*pi*(d/200)*(d/200))/m2_per_l);
}

2. Födelsedatum

g2_c2.c

#include <stdio.h>

/* Inte år 2000-säkert. */
int main(void)
{
  int idag, fodd;

  printf("Skriv in dagens datum (på formen 990203): ");
  scanf("%d", &idag);

  printf("När är du född (på samma form): ");
  scanf("%d", &fodd);

  printf("Du är %d år gammal.\n", (idag-fodd)/10000);
}

d) Problemlösning

Lösningarna i denna avdelning består endast av algoritmer, inte av C-kod. Om man vill skriva programmet måste algoritmen "översättas" till C-kod.

1. Avgör om n är ett primtal

for i = 2...sqrt(n)
   om n är jämnt delbart med i så är n inte ett primtal
om n inte är jämnt delbart med något av talen så är n ett primtal

2. Beräkna summan av alla tal mellan 1 och n

sum = 0
for i = 1...n
   sum = sum + i

Eller - mer effektivt

sum = n*(n+1)/2

3. Hitta det största primtalet mellan a och b

for i = b...a  (i räknar nedåt)
   if primtal(i)
     i är det största primtalet mellan a och b
om vi kommer hit utan att hitta något primtal finns det inget

För funktionen primtal(i) kan algoritmen från problem 1 användas.

4. Avgör om ett tal är perfekt

Vi delar upp problemet på flera funktioner.

perfekt(n):
   return summa_delare(n) == n

summa_delare(n):
   sum = 0
   for i = 1...n-1
      if i delar n
         sum = sum + i
   return sum

5. Översätta svenska->engelska med engelskt-svenskt lexikon

oversatt(svenskt_ord):
   for (engelskt_uppslagsord, svenskt_uppslagsord) = alla ordpar i lexikonet
      if svenskt_ord == svenskt_uppslagsord
         return engelskt_uppslagsord
   om vi kommer hit utan att ha hittat något finns inte det svenska ordet
     i lexikonet

6. Översätta med svenskt-engelskt lexikon

oversatt(svenskt_ord, lexikon)
   (svenskt_uppslagsord, engelskt_uppslagsord) == ordparet i mitten av lexikonet
   if svenskt_ord > svenskt_uppslagsord
      return oversatt(svenskt_ord, andra halvan av lexikonet)
   else if svenskt_ord < svenskt_uppslagsord
      return oversatt(svenskt_ord, första halvan av lexikonet)
   else if svenskt_ord == svenskt_uppslagsord
      return engelskt_uppslagsord

Denna algoritm är snabbare eftersom ordlistan halveras i varje steg. Vi behöver inte titta på alla ord i listan. Om listan innehåller N ord behöver vi bara titta på log(N)/log(2) ord.

7. Översätta hel text

for ord = varje ord i texten
   ord = oversatt(ord, lexikon)

8. Hitta det största talet i en lista av tal

storsta = första talet i listan
for i = varje tal i listan utom det första
   if i > storsta
      storsta = i

9. Sortera en lista av tal i storleksordning

Det finns många algoritmer för detta --- några klurigare än andra. En av de enklare ges nedan.

Idén är att gå igenom listan position för position och sätta talet på varje position till det minsta av talen som finns kvar i listan.

säg att listan innehåller n stycken tal
for position = 1...n
    minsta_position = position
    for position2 = (position+1)..n
       if talet på position2 < talet på minsta_position
          minsta_position = position2
    byt plats på talen på position och minsta_position

10. Hitta ut ur en labyrint

En idé till en algoritm är

Sätt högra handen på väggen
Håll kvar den där
Gå tills du kommer ut ur labyrinten