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

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.

Imidlertidig, Linda ble 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 en heltall N, og to reeltall 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

Figur 1. Eksempeltre

Løsning

Det første vi legger merke til er at et tre med alder N består av enstamme 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).