Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

np

Junior Schreiberling

  • "np" started this thread

Posts: 155

Date of registration: Oct 23rd 2002

1

Thursday, September 18th 2003, 10:02am

Sortieren oder Enttäuschen

Zuweilen bin ich doch etwas enttäuscht vom typischen Informatik-Studierenden, denn viele scheinen die Auffassung zu vertreten, Informatik (und insbesondere Programmieren) sei so etwas wie Essen kochen: Ich habe ein klar definiertes Ziel (Pfannkuchen) und suche mir aus einem Kochbuch einfach das Rezept das ich brauche. Ich hoffe, dass nicht alle so denken (von wenigen weiß ich das bereits).

Daher aus aktuellem Anlass eine kleine Aufgabe, die so ähnlich auch in der D&A-Klausur gestellt wurde:

Eine Datenquelle liefert eine Folge von mehreren Millionen 8-Bit-Zahlen. Nach Übertragung der gesamten Sequenz soll diese sortiert ausgegeben werden.
* Beschreiben Sie ein Verfahren, das diese Aufgabe in O(n) löst (mit n als Anzahl der Zahlen).
* Bedenken Sie, dass Sie dazu weniger als 1MB Speicher zur Verfügung haben (in-situ Verfahren zählen also nicht). [Keine Panik, in der Klausur zählen sie schon, man kommt aber ohne aus.]
  • Send private message

Shadow

... mit bunten Sternchen und so

  • "Shadow" is male

Posts: 838

Date of registration: Dec 21st 2001

Location: Hamburg

2

Thursday, September 18th 2003, 10:51am

Damit jeder noch ein bisschen knobeln kann, meine Lösung als Rot13:

Qvr Yöfhat vfg tnam rvasnpu:
Rf xöaara ahe 256 (2^8) qvfxergr Jregr nhsgergra. Rf ervpug nyfb nhf, wrqrf Nhsgergraqr Mrvpura mh mäuyra. Zvg 32ovg Inevnoyra xnaa zna ovf üore 4 Zvyyvneqra mäuyra. Vaftrfnzg oeähpugr zna nyfb - 32ovg Mäuyreinevnoyra ibenhftrfrgmg ahe 8192ovg = 1xO Fcrvpure.

Mhe Nhftnor zhff zna oybß wrqrf 8-ovg-Mrvpura ragfcerpuraqr qrz Mäuyrefgnaq qre mhtrbeqargra Inevnoyra a Zny nhftrora.

Gruß
Shadow
"Man hält die Erzeugung von Information für ein Zeichen von Intelligenz, während in Wirklichkeit das Gegenteil richtig ist: Die Reduktion, die Auswahl der Information ist die viel höhere Leistung."
-- Heinz Zemanek

This post has been edited 1 times, last edit by "Shadow" (Sep 18th 2003, 10:51am)

  • Send private message

Shadow

... mit bunten Sternchen und so

  • "Shadow" is male

Posts: 838

Date of registration: Dec 21st 2001

Location: Hamburg

3

Thursday, September 18th 2003, 10:53am

BTW für die nicht-Unixer gibts Rot13 als Javascript hier:

http://pflock.de/rot13.htm
"Man hält die Erzeugung von Information für ein Zeichen von Intelligenz, während in Wirklichkeit das Gegenteil richtig ist: Die Reduktion, die Auswahl der Information ist die viel höhere Leistung."
-- Heinz Zemanek
  • Send private message

denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

4

Thursday, September 18th 2003, 11:47am

begin 644 loesung
M36ET>N1H;&5N('=I979I96QE(&YU;&QE;BP@96EN<V5N+"!Z=V5I96XL("XN
M+B!Z=V5I:'5N9&5R=&;\;F9U;F1F_&YF>FEG96X@_&)E<G1R86=E;B!W=7)D
M96X@=6YD(&1A;FXL(&%N9V5F86YG96X@;6ET(&1E;B!N=6QL96XL(&5N='-P
8<F5C:&5N9"!V:65L92!A=7-G96)E;BX*
`
end
  • Send private message

np

Junior Schreiberling

  • "np" started this thread

Posts: 155

Date of registration: Oct 23rd 2002

5

Thursday, September 18th 2003, 12:13pm

Quoted

Original von Shadow
Qvr Yöfhat vfg tnam rvasnpu:
Rf xöaara ahe 256 (2^8) qvfxergr Jregr nhsgergra. Rf ervpug nyfb nhf, wrqrf Nhsgergraqr Mrvpura mh mäuyra. Zvg 32ovg Inevnoyra xnaa zna ovf üore 4 Zvyyvneqra mäuyra. Vaftrfnzg oeähpugr zna nyfb - 32ovg Mäuyreinevnoyra ibenhftrfrgmg ahe 8192ovg = 1xO Fcrvpure.

Mhe Nhftnor zhff zna oybß wrqrf 8-ovg-Mrvpura ragfcerpuraqr qrz Mäuyrefgnaq qre mhtrbeqargra Inevnoyra a Zny nhftrora.

Na, das lässt mich doch wieder hoffen ;) Kennst Du "Programming Pearls" von Jon Bentley? Da wird ein ähnliches Problem beschrieben (und gut lesbar ist das Buch auch).

Quoted

Original von denial
...
M+B!Z=V5I:'5N9&5R=&;\;F9U;F1F_&YF>FEG96X@_&)E<G1R86=E;B!W=7)D
M96X@=6YD(&1A;FXL(&%N9V5F86YG96X@;6ET(&1E;B!N=6QL96XL(&5N='-P
8<F5C:&5N9"!V:65L92!A=7-G96)E;BX*
...

Was ist das? Brainf*? Befunge? Binary?
  • Send private message

denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

6

Thursday, September 18th 2003, 12:21pm

uuencoded
  • Send private message

Shadow

... mit bunten Sternchen und so

  • "Shadow" is male

Posts: 838

Date of registration: Dec 21st 2001

Location: Hamburg

7

Thursday, September 18th 2003, 12:31pm

Quoted

Original von denial
uuencoded

Ist zwar ungewöhnlich Sachen in Foren zu uuencoden, damit sie nicht auf anhieb lesbar sind, aber die Lösung ist soweit korrekt. :)

In Rot13 siehts so aus:

Quoted

Zvgmäuyra jvrivryr ahyyra, rvafra, mjrvra, ... mjrvuhaqregsüashaqsüasmvtra üoregentra jheqra haq qnaa, natrsnatra zvg qra ahyyra, ragfcerpuraq ivryr nhftrora.
"Man hält die Erzeugung von Information für ein Zeichen von Intelligenz, während in Wirklichkeit das Gegenteil richtig ist: Die Reduktion, die Auswahl der Information ist die viel höhere Leistung."
-- Heinz Zemanek
  • Send private message

denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

8

Thursday, September 18th 2003, 12:36pm

Im Vergleich zu meiner ersten Idee, ASCII85, ist uuencode geläufiger.
  • Send private message

Shadow

... mit bunten Sternchen und so

  • "Shadow" is male

Posts: 838

Date of registration: Dec 21st 2001

Location: Hamburg

9

Thursday, September 18th 2003, 1:27pm

Außer in PostScript wird das doch in der Praxis nicht wirkich verwendet, oder?

Naja, so langsam wird das hier Off Topic. ;)

BTW: ERSTER! :]

Shadow
"Man hält die Erzeugung von Information für ein Zeichen von Intelligenz, während in Wirklichkeit das Gegenteil richtig ist: Die Reduktion, die Auswahl der Information ist die viel höhere Leistung."
-- Heinz Zemanek
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

10

Thursday, September 18th 2003, 1:34pm

ZGEga2FubiBtYW4gZG9jaCBlY2h0IG51ciBNVUggc2FnZW4gOik=
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

11

Thursday, September 18th 2003, 2:26pm

Quoted

Original von Shadow
Außer in PostScript wird das doch in der Praxis nicht wirkich verwendet, oder?


Ist eigentlich schade, da ASCII85 mindestens 6,25% kleinere Dateien als Base64, uuencode und BinHex erzeugt (wenn man die CRLFs und header/trailer vernachlässigt).

This post has been edited 1 times, last edit by "denial" (Sep 18th 2003, 2:27pm)

  • Send private message