Eksempeloppgaver

Tips: Prøv å løse oppgavene selv før du ser på løsningsforslaget!

Eksempeloppgaver til 1. runde

Oppgavene fra 1. runde tidligere år:

Oppgavene i årets 1. runde vil være av samme type. Omfanget av prøven er 90 minutter, og alle oppgavene er flervalgsoppgaver med ett riktig svar. Vi har også et dokument med flere eksempeloppgaver:
Eksempeloppgaver 1. runde

Introduksjonsoppgave – “Kalkulatoren”

Dette er en enkel oppgave som, innebygd i oppgaveteksten, inneholder mye nyttig informasjon til de som ikke har deltatt i programmeringskonkurranser før (også de som ikke kan programmere). Lærere kan også ha interesse av dette.

Oppgave 1 – “Stereoanlegget”

Denne eksempeloppgaven er lagt opp på samme måte som inntaksoppgavene og finaleoppgavene.


Oppgave 2

Skilpadden Linda dro hjemmefra for å se seg om i den vide verden. Mens hun reiste, kom hun til en ørken, og lærte fort at hun etterlater seg avtrykk i sanden. Snart begynte hun å tegne forskjellige bilder. Etter en stund ville Linda tegne trær som hun hadde sett i en av de botaniske hagene hun besøkte på veien. Trærne hun hadde sett hadde de følgende egenskapene:

 

  • de hadde ingen blader
  • jo eldre treet var, jo flere greiner hadde det, og hvert tre hadde en spesifik vinkel til utgreining alfa (se under).
  • et ett år gammelt tre besto kun av en loddrett stamme med lengde d.
  • hvis treet var N år gammelt, startet to greiner på toppen av stammen: en på venstre side under vinkelen alfa/2, og en på høyre side under vinkelen alfa/2. Begge disse greinene kunne ha flere nye greiner. De så ut som et tre med alderen N-1 med en stamme halvparten så lang, og med samme vinkel med nye utgreininger.

Imidlertid ble Linda fort veldig forvirret av å tegne disse trærne. Hun spør deg om du kunne skrive et program som kan skrive ut sekvenser med instruksjoner til henne, som hun kan bruke til å tegne trærne. Programmet vil lese et heltall N, og to desimaltall D, og alfa, og vil deretter skrive ut en sekvens av instruksjoner. Skilpadden Linda forstår følgende instruksjoner:

Forward a  - flytter a skritt fram i den retningen hun står
Left a     - snur a grader til venstre
Right a    - snur a grader til høyre

Skilpadden kan tegne over de samme linjene mer enn en gang.

 


Figur 1. Eksempeltre
Løsning

Det første vi legger merke til er at et tre med alder N består av en stamme med lengde d, og to nye trær med alder N-1 som starter vedenden av stammen; det ene står på skrått mot høyre med vinkel alpha/2, mens det andre står på skrått mot venstre med samme vinkel.

Denne typen problem kalles gjentakende, eller rekursive, og dette – å kalle en funksjon innenfra samme funksjon – tilbys i de fleste programmeringsspråk. Etter at utførelsen av den indre funksjonen er ferdig fortsetter den ytre som normalt.

La oss ta en titt på algoritmen før vi skriver noe faktisk kode:

For å tegne et tre med alder N > 1, med stamme av lengde d og forgreningsvinkel alpha må vi:

 

  • gå d steg fremover (for å tegne stammen)
  • snu oss alpha/2 mot høyre
  • tegne et tre med alder N-1, med stammelengde d/2 og vinkel alpha
  • snu oss alpha mot venstre
  • tegne et tre med alder N-1, med stammelengde d/2 og vinkel alpha
  • snu oss 180 – alpha/2 mot venstre
  • gå d skritt fremover (tilbake til startposisjonen)
  • snu oss 180 mot venstre (tilbake til startretningen)

Legg merke til at skilpadden må returnere til sin orginale posisjon og retning, dette fordi vi ønsker å kunne kalle samme funksjon for å tegne trær med lavere alder. Algoritmen er imidlertid ikke komplett (og fungerende) før vi spesifiserer hvordan vi tegner et tre med alder 1:

 

  • gå d skritt fremover (for å tegne stammen)
  • snu oss 180 mot venstre
  • gå d skritt fremover (tilbake til startposisjonen)
  • snu oss 180 mot venstre

Nå kan vi implementere algoritmen, for eksempel i programmeringsspråket C:

 

#include <stdio.h>

int alpha;

void tree(int n, float d)
{
	if (n > 1)
	{
		printf("Forward %f\n", d);
		printf("Right %f\n", (float)alpha / (float)2.0);
		tree(n - 1, d / 2);
		printf("Left %d\n", alpha);
		tree(n - 1, d / 2);
		printf("Left %f\n", 180 - alpha / (float)2.0);
		printf("Forward %f\n", d);
		printf("Left 180\n");
	}
	else
	{
		printf("Forward %f\n", d);
		printf("Left 180\n");
		printf("Forward %f\n", d);
		printf("Left 180\n");
	}
}

int main()
{
	int n;
	float d;

	printf("Tree age:");
	scanf("%d", &n);
	printf("Trunk length:");
	scanf("%f", &d);
	printf("Branching angle:");
	scanf("%d", &alpha);

	tree(n, d);

	return 0;
}

Det kan være interessant å bergne hvor mange stammer skilpadden vil tegne for et tre med alder N (la oss kalle dette tallet L(N)). Fra algoritmen over: L(1) = 1 og L(N) = 1 + 2*L(N-1). Hvis vi løser ut alle parantesene får vi: L(N) = 1 + 2 + 4 + … + 2N-1, og det kanvises matematisk at dette er det samme som: L(n) = 2^N. Tidskompleksisteten til denne algoritmen er altså eksponensiell (det vil si at for hvert ekstra år vil algoritmen bruke dobbelt så lang tid).

Leave a Reply

Your email address will not be published. Required fields are marked *