PROBLEM

Et nyt rumforsøg involverer N objekter, nummereret fra 1 til N, hvor N er ulige. Hvert af objekterne har en entydig, men ukendt styrke givet ved et naturligt tal Y, hvor 1 £ Y £ N. Objektet med median-styrken, er det objekt X, hvor der er lige så mange objekter med mindre styrke end X, som der er objekter med større styrke end X.

Skriv et program der finder objektet med median-styrken.

Uheldigvis kan objekternes styrke kun sammenlignes ved hjælp af et apparat som – givet tre forskellige objekter – fortæller hvilket der besidder median-styrken blandt disse tre objekter.

Bibliotek til interaktion

Der er givet et bibliotek med navnet device, som indeholder tre operationer:

• GetN, som skal kaldes én gang I begyndelsen uden argumenter, og som returnerer værdien af N.
• Med3, som kaldes med numrene på tre forskellige objekter som argumenter, og som returnerer nummeret på objektet med median-styrken blandt disse tre.
• Answer, som kaldes én gang til slut. Argumentet skal være nummeret på det objekt som programmet anser for at være objekt med median-styrken. Answer sørger selv for at afslutte programmet på rette måde.

MEDIAN.OUT og MEDIAN.LOG.

MEDIAN.OUT består af to linjer:

• I første linje argumentet fra kaldet af Answer.
• I den anden linje antallet af kald af Med3, som programmet har foretaget.

INSTRUKTION TIL PASCAL-PROGRAMMØRER

Medtag følgende i din kildetekst:

uses device;
 
 

INSTRUKTION TIL C/C++ PROGRAMMØRER

Medtag følgende i din kildetekst:

#include "device.h"

Opret projektet MEDIAN.PRJ og tilføj filerne MEDIAN.C (MEDIAN.CPP) og DEVICE.OBJ til projektet.

HVORDAN DU KAN TESTE DIT PROGRAM

Du kan eksperimentere med biblioteket device ved at oprette en tekstfil DEVICE.IN, der skal bestå af to linjer. Den første indeholder heltallet N, der angiver antallet af objekter. Den anden linje skal indeholde heltallene fra 1 til N i en eller anden rækkefølge til beskrivelse af objekternes styrke, så det i’te heltal er styrken på det i’te objekt.

EKSEMPEL

DEVICE.IN:

5

2 5 4 3 1

Filen DEVICE.IN ovenfor beskriver inddata med 5 objekter, hvis styrke er som følger:
 

Objekt	1	2	3	4	5
Styrke	2	5	4	3	1

Nedenstående er en mulig reaktiv sekvens af kald til biblioteket:

1. GetN (i Pascal) eller GetN() (i C/C++), som returnerer 5.
2. Med3(1,2,3), som returnerer 3.
3. Med3(3,4,1), som returnerer 4.
4. Med3(4,2,5), som returnerer 4.
5. Answer(4)

• Antallet af objekter N opfylder 5 £ N £ 1499 og N er ulige.
• Objekternes numre er heltal fra 1 til og med N.
• Objekternes styrke Y opfylder at 1 £ Y £ N og at alle styrker er forskellige.
• Pascalbibliotekets navn: device.tpu
• Pascalbibliotekets funktioner og procedurer:

• C/C++bibliotekets filnavne:

• C/C++ bibliotekets funktioner:

• Der må højst foretages 7777 kald til funktionen Med3 i hver programkørsel.
• Programmet må ikke læse fra eller skrive til nogen fil.