INSTITUT FÜR MATHEMATIK UND
WISSENSCHAFTLICHES RECHNEN
Text Karl-Franzens-Universitaet logo uni graz
     Präsentation     Mitarbeiterinnen    Forschung    Lehre    Allgemeines    Bibliothek    Fakultät    Uni Graz    Home
 

Humor in der Mathematik - Löwenjagd

<Prev | Index | Next>


Wie fängt man einen Löwen in der Sahara?

Methoden aus der Informatik

Zunächst einige grundsätzliche Bemerkungen:
Wenn wir annehmen, daß der Löwe von unserm Standpunkt aus wahrscheinlich in südlicher Richtung zu finden ist, ist die ganze Aufgabe ein Problem der Geschwindigkeit, so daß wir mit einem gewoehnlichen PC leider aufgeschmissen sind. Durch Parallelverarbeitung können wir die Suche in südlicher Richtung aber deutlich beschleunigen. Wenden Sie sich mit diesbezüglichen Fragen bitte an den "Arbeitskreis paralleles Rechnen".

Die Lineare Suche:

Stelle Dich in die linke obere Ecke der Sahara. Gehe einen Schritt nach Osten. Wiederhole, bis Du den Löwen gefunden hast, oder bis Du an den rechten Rand der Sahara gekommen bist. Wenn Du an den rechten Rand gekommen bist, gehe einen Schritt nach Süden und gehe nach Westen, bis Du den Löwen hast, oder am linken Rand angekommen bist. Fahre so fort, bis Du den Löwen gefunden hast. Hast Du ihn gefunden, so stülpe einen Käfig über ihn. Sollte der Löwe Dich fressen, bevor Du das schaffst, drücke den RESET-Knopf und versuche es erneut.

Die Monte-Carlo-Methode

Wir nehmen eine Zufallszahl, die den Raum, in dem wir suchen, indiziert. Nimmt man benachbarte Punkte aus der Suche heraus, kann man die zu untersuchende Punktzahl drastisch reduzieren. Nach den Gesetzen der Wahrscheinlichkeit wird der Löwe somit früher oder später auftauchen.

Die Methode der künstlichen Intelligenz:

suche(Löwe,Wüste,_) :- var(Wüste),!,fail.
        % In einer nicht instantiierten W"uste
        % lassen sich keine L"owen fangen.
suche(Löwe,Wüste,Wüste) :- atomic(Wüste), gefunden(Löwe,Wüste).
        % Wenn die W"uste atomar ist,
        % mu"s dort der L"owe sein.
suche(Löwe,[],_):- !, fail.
        % Wenn die W"uste leer ist, ist auch
        % kein L"owe drin.
suche(Löwe,[HEAD],HEAD) :- gefunden(Löwe,HEAD).
        % Wenn der L"owe im ersten Element
        % der W"uste ist, dann fertig.
suche(Löwe,[_|T],X) :- suche(Löwe,T,X).
        % Sonst weiter schauen.
fange(Was,Wo,Womit) :-
        fange(Was,Wo,WoGenau),
        bewege(Womit,WoGenau).
gefunden(Was,Worin) :- member(Was, Worin).
bewege(Was,  _  ) :- retract(position(Was,_)), fail.
bewege(Was,Wohin) :- asserta(position(Was,Wohin)).
test_Wüste([Wüste_1, Wüste_2, Wüste_3, Wüste_4, Wüste_5,
            Wüste_6, Wüste_7, [Wüste_8, Löwe],  Wüste_9,
            Wüste_A, [Wüste_B, wagen],  Wüste_C, Wüste_D]).
fange_Löwe_test :-
        bewege(Käfig,wagen),
        test_Wüste(Wüste),
        fange(Löwe,Wüste,Käfig).,

Hier noch einige iterative Methoden aus der Angewandten Informatik.
Geeignete Datenstrukturen werden vorrausgesetzt!

Standardlösung:

MODULE Fang; 
FROM Problem IMPORT Loesung; 
BEGIN; 
   Loesung; 
END Fang. 

ASM (MS-DOS)

- nur möglich ab MASM 9.0 oder TASM 4.5:

dosseg 
.DATA 
MAX equ 65535 
Wüsten_Feld db MAX dup (0) 
Käfig db 
extern Löwe_Fkt_Nummer:Word ; DOS-Int. Nummer 
.CODE 
  lds si, W_Feld        ; ES:DI zeigt auf Anfang des Feldes 
  cld 
  mov CX,MAX            ; CX als max. Index 
M1: 
  lodsb 
  cmp al,Löwe 
  je  Gefangen 
  loop M1 
  jmp Error 

Gefangen: 
  mov BX,SI 
  mov AX,Löwe_Fkt_Nummer 
  lds di, Käfig 
  int 21h               ; Dos-Interrupt, da alle aufwendigen Proc. in 
                        ; ASM ausgelagert werden sollen. 
Error: 
  int 20h 
END 

C++:

int fang(string str) 
{
    object ob1,ob2,ob3; 
    if (!str || str!="Löwe mit Käfig") 
    {
        write("WEN willst du mit WAS fangen ?\n"); 
        return 1; 
    } 
ob1=clone_object("/obj/Wüste"); /* Wüste enthält Löwe s.Aufgabe */ ob2=clone_object("/obj/Käfig"); if (ob3 = present("Löwe",ob1)) == NULL) { write("Es ist kein Löwe in der Wüste !\n"); /* Falls weggerannt */ return 1; } ob3->move(ob2); write("Der Löwe befinde sich jetzt im Käfig.\n"); return 0; }

Diese Funktion muß noch an ein Ereignis angehängt werden, die Objekte Käfig.c und Wüste.c sind geeignet zu implementieren.

Turbo Pascal:

     program Test_Loesung; 
     type Wüster_Typ= Array[1..Max_X,1..Max_Y] of Index; 
          Inhalt     = { weiß nicht } 
          Käfig_Typ = record 
                voll   : Boolean; 
                Inhalt : Tier; 
              end; 
          Löwen_Typ = Tier; 
     var Wüste : Wüster_Typ; 
         Käfig : Käfig_Typ; 
         Tiere  : Array[1..Max_Tiere] of Tier; { Falls noch Kamele in der Wüste } 
                                               { sind .                         } 
     procedure Löwen_Fang; 
     var i,j:Word; 
     begin; 
       Käfig.voll:=false; 
       for i:=1 to Max_X do                        { Wüste nach Löwe absuchen  } 
         for j:=1 to Max_Y do 
            if Wüste[i,j]=LöweN_INDEX then begin; 
                                               Käfig.Inhalt:=Tiere[Wüste[i,j]]; 
                                               Käfig.voll:=true; 
                                               Wüste[i,j]:=KEINER_INDEX; 
                                               exit;  { Da der Käfig schon voll } 
                                             end;    { ist.Man könnte aber auch } 
                                   { mit dieser Procedure alle Löwen einfangen. } 
       WriteLn('Achtung ! Kein Löwe gefunden, wie wärs mit einem Kamel ?'); 
     end; 
  
     begin; 
       Init;   { Wüste, Tiere  werden eingestellt. } 
       Löwen_Fang; 
       if (Käfig.voll) then WriteLn(' Ok,der Löwe ist im Käfig.') 
                        else WriteLn('Achtung ! Kein Löwe gefunden, durch "+ 
                                     'Abänderung in KAMEL_INDEX wäre vielleicht"+ 
                                     #10#13'ein Kamel möglich ?'); 
     end. 

Shellscript:

#!/bin/sh 
for $tier in $Wüste 
do 
    if [ $tier = $Löwe ] 
    then mv $tier $Käfig; exit 0 
    fi 
done 

 


<Prev | Index | Next>

footer bild
  AKTUELL    SITEMAP   SUCHE   ENGLISCH   UNI GRAZ         Betreuer: Bernd Thaller / 13.11.04