Oppgave 3-1 i "Accelerated c++"

[Manuel]

Oppgaven går som følger:

Suppose we wish to find the median of a collection of values. Assume that we have read some of the values so far, and that we have no idea how many values remain to be read. Prove that we cannot afford to discard any of the values we have read. Hint: One proof strategy is to assume that we can discard a value, and then find values for the unread - and therefore unknown - part of our collection that would cause the median to be the value that we discarded

Enten er det jeg som ikke forstår oppgaven, eller så er den like elendig formulert som enkelte andre oppgaver i boken: Hva er det oppgaven egentlig vil at jeg skal gjøre?

 

Pro definisjon er median den enkeltverdien som skiller halvdelene av en sortert tallrekke. Med mindre jeg har oversett et finurlig triks, så er det aldri mulig å vite om medianen blir annerledes hvis man fjerner et tall. Se på tallrekken:

 

5, 6, 92, 14, 92, 92, 110, 1153, 92

Sortert: 5, 6, 14, 92, 92, 92, 92, 110, 1153

Medianen er 92

 

Vi fjerner så to tall, f.eks 1153 og 110 for å være "snille" med resultatet: 5, 6, 14, 92, 92, 92, 92

Medianen er fortsatt 92, selv om vi har fjernet et tall. Så heldige er vi ikke hvis vi fjerner et annet tall, eller sørger for at vi er nødt til å regne ut gjennomsnittet av to tall for å finne medianen. Ærlig talt så skjønner jeg ikke hva den såkalte "bevisstrategien" prøver å bevise.

 

Er det noen som har et annet forslag for å løse problemet?

[einaros]

Oppgaven vil at du skal bevise at du ikke kan droppe allerede leste verdier, dersom du skal finne median i en tallrekke av ubestemt lengde. Sier seg selv, det.

[Manuel]

Oppgaven vil at du skal bevise at du ikke kan droppe allerede leste verdier, dersom du skal finne median i en tallrekke av ubestemt lengde. Sier seg selv, det.

7595237[/snapback]

Problemet mitt er at dette virker som en altfor simpel løsning på oppgaven. Hvorfor lage en oppgave av det? Det er et mattematikkspørsmål, og har lite eller ingenting å gjøre med programmering!

[einaros]

Oppgaven vil at du skal bevise at du ikke kan droppe allerede leste verdier, dersom du skal finne median i en tallrekke av ubestemt lengde. Sier seg selv, det.

7595237[/snapback]

Problemet mitt er at dette virker som en altfor simpel løsning på oppgaven. Hvorfor lage en oppgave av det? Det er et mattematikkspørsmål, og har lite eller ingenting å gjøre med programmering!

7595281[/snapback]

 

Hvorfor leser du så en programmeringsbok? Hvis du ikke er villig til å implementere løsninger på "real world"-problematikk, eller tilsvarende fra andre tekniske fagfelt; har du vel bommet med hobbyvalget

[Zethyr]

Man vil regne med at i en bok som skal lære bort programmering vil ma være innom emnet programmering uansett hva slags oppgaver det er. Å kreve matte-beviser kan man unnlate i slike bøker, så lenge de ikke er relatert til noe man senere skal jobbe med i oppgavene.

 

 

De foreslåtte bevisstrategien er bevis med moteksempel, formulert litt rart.

Gitt tallrekken: 1,2,3,4,...

Vi ser bort fra nr 4 (erstatter den med en x for syns skyld), og får servert resten av rekken:

1,2,3,x,5,6,7

 

Medianen er så den verdien vi forkastet, og dette vil ikke fungere.

[einaros]

[...] Å kreve matte-beviser kan man unnlate i slike bøker, [...]

7625369[/snapback]

 

Mange vil vel argumentere med at de fleste algoritmiske handlinger man foretar seg i programmeringen har sitt utspring i matematikken.

 

[...] så lenge de ikke er relatert til noe man senere skal jobbe med i oppgavene. [...]

7625369[/snapback]

 

Og det er tilfellet her. Forfatteren har til hensikt å fortelle at man ikke kan optimalisere bort lagring av midlertidige data, da disse data er nødvendige for at algoritmen skal finne det ønskede resultat.

 

Accelerated C++ er forøvrig en innføring i C++, så det vil typisk være trukket inn en hel del emner som ikke direkte relateres til programmering. Disse nevnes først og fremst for at den aspirerende utvikleren skal kunne assosiere (de noen ganger abstrakte) konseptene, til kunnskap han / hun besitter fra før. En "myk start", med andre ord.

[DarkSlayer]

Syns oppgaven var knotete skrevet ja. Men husk at dataforfattere ofte er nerder som strøk i språk (muntlig og skriftlig), og liker å skrive innfløkt for å imponere andre, gjerne med andre ord enn de faktiske ord som gjelder for ting.

 

Men matte får du bare svelge.

 

Skal jo bare lage ei linka liste, og sortere den, og det er jo enkelt.

[einaros]

Syns oppgaven var knotete skrevet ja. Men husk at dataforfattere ofte er nerder som strøk i språk (muntlig og skriftlig), og liker å skrive innfløkt for å imponere andre, gjerne med andre ord enn de faktiske ord som gjelder for ting.

7680675[/snapback]

 

That made no sense at all, men stå på.

 

Dersom du synes oppgaven er dårlig formulert, så er det vel heller din engelskforståelse det skorter på, enn forfatterens evne til å uttrykke seg