Oppgave 1

  public static int a(int n)           // n et ikke-negativt tall
  {
    if (n < 0) throw new IllegalArgumentException("n er negativ!");

    int x = 0, y = 1, z = 1;

    for (int i = 0; i < n; i++)
    {
      z = 2*y + 3*x; x = y; y = z;
    }
    return z;
  }

Oppgave 2

Oppgave 3

  public static int tverrsum(int n)
  {
    int sum = 0;

    while (n > 0)
    {
      sum += n % 10;
      n /= 10;
    }

    return sum;
  } 

Oppgave 4

  public static int sifferrot(int n)
  {
    while (n >= 10) n = tverrsum(n);
    return n;
  }

Vi har for alle ikke-negative heltall n at 9 går opp i n hvis og bare hvis 9 går opp i tverrsummen til n. Se oppgave 5a) nedenfor. Det betyr at sifferroten til et heltall n der 9 går opp, er lik 9. Hvis n ikke går opp, er sifferroten lik resten når n deles med 9.

  public static int sifferrot(int n)
  {
    n %= 9;
    return n == 0 ? 9 : n;
  }

Oppgave 5 a)

Vi tar som eksempel et vilkårlig firesifret tall med a, b, c og d som de fire sifrene. Dvs. tallet 1000a + 100b + 10c + d. Tverrsummen blir lik a + b + c + d. Tar vi differensen får vi 1000a + 100b + 10c + d − (a + b + c + d) = 999a + 99b + 9c = 9(111a + 11b + c). Dermed ser vi at 9 går opp i tallet hvis og bare hvis 9 går opp i tallets tverrsum. Samme type argument kan brukes for tall hvor antall siffer både er større og mindre enn fire.

Oppgave 5 b)

Påstanden kan skrives slik: sifferrot(sifferrot(a)*sifferrot(b)) = sifferrot(a*b)

Eksempel på hvordan dette kan bruke:

  int a = 1234;
  int b = 5839;

  int x = sifferrot(sifferrot(a)*sifferrot(b));
  int y = sifferrot(a*b);

  System.out.println(x + " " + y);

Oppgave 6

a) Største felles divisor for 1529 og 14036 er 11.

b)  public static int euklid(int a, int b)
    {
      while (b > 0)
      {
        int c = a % b; a = b; b = c;
      }
      return a;
    }

c) Lamés setning sier at hvis b er mindre enn eller lik a, vil antallet divisjoner som utføres i Euklids algoritme alltid være mindre enn eller lik fem ganger antallet desimale siffer i b. Dvs. algoritmen er av orden log₁₀(b). Det største antallet divisjoner får vi hvis a og b er to tall som er naboer i rekkefølgen av Fibonacci-tall.

Oppgave 7

  public static int kvadratsum(int n)
  {
    if (n == 1) return 1;
    else return kvadratsum(n-1) + n*n;
  }

  // Formel:  n*(n + 1)*(2*n + 1)/6  

Oppgave 8

  public static int sum(int n, int k)
  {
    if (n == k) return n;
    int m = (n + k)/2;
    return sum(n,m) + sum(m+1,k);
  }

Oppgave 9

  public static int maks(int[] a, int v, int h)
  {
    if (v == h) return v;
    int m = (v + h)/2;  // midten
    int mv = maks(a,v,m);
    int mh = maks(a,m+1,h);

    return a[mv] >= a[mh] ? mv : mh;
  }

  public static int maks(int[] a)
  {
    return maks(a,0,a.length-1);
  }

Oppgave 10

  public static int fakultet(int n)
  {
    return n < 2 ? 1 : fakultet(n-1)*n;
  }

Oppgave 11

fib(20) = 6765, fib(30) = 832040, fib(40) = 102334155 og fib(50) = 12586269025.

Den siste verdien, dvs. fib(50), vil du ikke få. For det første vil programmet ta svært lang tid. Kanskje så lang tid at du mister tålmodigheten. Men hvis du til slutt får ut et svar, vil det være et negativt tall. Det kommer av at fib(50) er for stort for datatypen int. Se Oppgave 12.

Oppgave 12

  public static long fibonacci(int n)
  {
    long a = 0, b = 1, c = 0;

    for (int i = 0; i < n; i++)
    {
      a = b; b = c; c = a + b;
    }
    return c;
  }

Oppgave 13

Fasit mangler!

Oppgave 14 a)

  public static int B(int n, int k)
  {
    if (k == 0 || k == n) return 1;
    return B(n-1,k-1) + B(n-1,k);
  }

Oppgave 14 b)

  public static int binomial(int n, int k)
  {
    if (k < 0 || k > n)
      throw new IllegalArgumentException("Ulovlig parameterverdi!");

    if (k > n/2) k = n - k;

    return B(n,k);
  }

Oppgave 14 c)

  public static int binomial(int n, int k)
  {
    if (k < 0 || k > n)
      throw new IllegalArgumentException("Ulovlig parameterverdi!");

    if (k > n/2) k = n - k;

    int verdi = 1;
    for (int i = 1, j = n; i <= k; i++,j--)
      verdi = (verdi*j)/i;

    return verdi;
  }