Google Treasur Hunt

Tutorials.at
Verfügbare Informationen zu "Google Treasur Hunt"

  • Qualität des Beitrags: 0 Sterne
  • Beteiligte Poster: jan040793 - Moritz - wirthi
  • Forum: Tutorials.at
  • Forenbeschreibung: Programmierforum
  • aus dem Unterforum: Pascal
  • Antworten: 6
  • Forum gestartet am: Mittwoch 19.04.2006
  • Sprache: deutsch
  • Link zum Originaltopic: Google Treasur Hunt
  • Letzte Antwort: vor 14 Jahren, 10 Monaten, 9 Tagen, 7 Stunden, 10 Minuten
  • Alle Beiträge und Antworten zu "Google Treasur Hunt"

    Re: Google Treasur Hunt

    jan040793 - 18.05.2008, 20:36

    Google Treasur Hunt
    Also mal vorne weg:

    Die Google Treasur Hunt ist eine von Google initiierte "Schnitzeljagd", bei der die Teilnehmer mathematische Probleme lösen müssen, um Runde für Runde weiter zu kommen und am Ende einen Preis zu gewinnen (Ich weiß bis heute nicht was >.<*).

    Ich habe mir gedacht *Macht bestimmt Spaß* und hab dann nur mal so mitgemacht. Habe dann auch bald bemerkt, dass das nicht allzu einfach wird... Die erste "Aufgabe" war die folgende:

    Zitat: A robot is located at the top-left corner of a 62 x 50 grid (marked 'Start' in the diagram below)*.

    The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below)*.

    How many possible unique paths are there?
    (Note: Answer must be an exact, decimal representation of the number.)

    Habe das Problem dann in den nächsten Tagen im Kopf gewälzt und habe dann vor 3 Tagen mal nen Code aufgesetzt. Wie gewöhnt kam erstmal ein fehler und so weiter und so fort... Habe den Fehler jetzt vor ner knappen Stunde gefunden - Ich habe in der Funktion die Variable "x" mit einem "var" markiert, was sie global machte und damit das gesammte Programm zerriss ^^ - und jetzt klappt alles ganz wunderbar (Ich poste den Code am Ende...)

    Ich habe das Programm dann gestartet und wie erwartet passierte erstmal gar nichts (Ich habe im Vorwege schonmal einfach die Zahl 2^102 gesetzt [der Roboter braucht immer 102 Schritte bis zum Ziel. Jeder dieser Schritte ergibt 2 neue Möglichkeiten. Ergebnis: 31stellige Zahl. Die ganz schlauen unter euch haben es bestimmt schon bemerkt - Sobald der Roboter am unteren oder rechten Rand angekommen ist resultieren keine 2 Möglichkeiten mehr. Deshalb ist das ganze doch ein wenig komplexer XD] und bin zu dem Schluss gekommen, dass die Variablen in Pascal vermutlich nicht groß genug für die resultierende Zahl ist. Wollte es trotzdem einfach mal versuchen.).

    Da nach einer halben Stunde immernoch nichts passiert war, habe ich einfach mal ein
    Code: writeln(counter);
    eingesetzt und kann jetzt den Verlauf verfolgen.

    Habe das ganze nochmal gestartet und bin jetzt nach 20 Minuten bei 100 000 000 möglichen Wegen angekommen. Das finde ich verdammt wenig, zumal ich in Foren, in denen die Antwort schon gepostet wurde, gelesen habe, dass die Rechendauer maximal 30 Minuten betragen hat (Die Werte für das Feld, in dem sich der Roboter bewegt, variieren bei jedem Teilnehmer).

    Deshalb frage ich jetzt einfach mal, ob irgendjemand den Fehler im Quellcode findet oder mir erzählt, dass Pascal Müll ist und ich damit niemals zum Ziel komme (was nichts neues für mich wäre - orientiere mich bereits um. Aber in Pascal bin ich momentan halt am fittesten und deshalb habe ich damit angefangen das Problem zu lösen.).

    Ich glaube nicht, dass es an meinem PC liegt, da er nicht unbedingt der schlechteste ist (wobei das natürlich relativ ist XP).

    Naja hier halt mal der Code - vielleicht hat ja jemand eine Idee...

    Code: program roboter;
    uses crt;
    var  zaehler : double;
         y,x : integer;

    procedure paths (var y : integer; x : integer; var counter : double); //y und x sind momentane Position
    var i : integer;
    begin
    for i := y to 50 do        //von oben bis unten...
      begin
        if (x < 62)  //solange noch nicht rechts angekommen
          then
          begin
            x := x+1;            //einen weiter nach rechts
            paths (i,x,counter);  //rekursiv nochmal ausfhren
          end
        else counter:= (counter + 1);    //counter wird um ein erhäht, wenn noch nicht am Rand angekommen
      end;
      writeln(counter); //gibt Zwischenstand aus...
    end;

    begin
    zaehler := 0;   //zaehler initialisieren
    y := 0;         //y initialisiert
    x := 0;         //x initialisiert
    paths (y,x,zaehler);  //prozedur wird ausgefhrt
    write (zaehler);
    readkey;      //hält an bis tastendruck
    end.


    PS: Bitte keine Kritik an meinen Comments - ich hab die so geschrieben, dass ich weiß, was ich getan hab und habe dabei nicht auf "korrekte Formulierung" geachtet...

    Na gut.. Bei Fragen bitte Fragen. Ich kann das immer schlecht beurteilen, wie gut/schlecht ich ein Problem formuliert habe...



    Re: Google Treasur Hunt

    Moritz - 19.05.2008, 10:33


    versuchs mal so:


    Code:
    program roboter;
    uses crt;
    var  zaehler : double;
         y,x : integer;

    procedure paths (const y : integer; x : integer; counter : double); //y und x sind momentane Position
    var i : integer;
    begin
    for i := y to 50 do        //von oben bis unten...
      begin
        if (x < 62)  //solange noch nicht rechts angekommen
          then
          begin
            x := x+1;            //einen weiter nach rechts
            paths (i,x,counter);  //rekursiv nochmal ausfhren
          end
        else counter:= (counter + 1);    //counter wird um ein erhäht, wenn noch nicht am Rand angekommen
      end;
      writeln(counter); //gibt Zwischenstand aus...
    end;

    begin
    zaehler := 0;   //zaehler initialisieren
    y := 0;         //y initialisiert
    x := 0;         //x initialisiert
    paths (y,x,zaehler);  //prozedur wird ausgefhrt
    write (zaehler);
    readkey;      //hält an bis tastendruck
    end.



    Re: Google Treasur Hunt

    wirthi - 19.05.2008, 12:00


    51440844805891595420929002811800



    Re: Google Treasur Hunt

    jan040793 - 19.05.2008, 17:11


    wirthi hat folgendes geschrieben: 51440844805891595420929002811800

    Na danke - und was soll mir das bringen? Was bringt mir das Ergebnis, wenn ich den Weg nicht verstanden habe? Ne kleine Erklärung, wie du das gemacht hast wäre schon ganz nett gewesen - und wenn du nicht Zeit/Lust dazu hast, dann lass es am besten einfach, anstatt einfach eine Zahl in den Raum zu werfen...

    @moritz:

    Danke, dass du dir die Zeit genommen hast mal drüber zu gucken ^^
    Habe mithilfe des Programmes WinMerge deine Veränderungen gefunden - hätte ich sonst wahrscheinlich nie gesehen...

    Wie auch immer - ich habs mal ausgeführt und jetzt klappts noch weniger als vorher. Der Counter geht nicht höher als 50. Keine Ahnung wieso, aber ich sehe nicht, was deine Änderungen bewirken sollen...

    Einigermaßen nachvollziehbar für mich ist ja grade noch, dass du in der Prozedur das Code: var durch ein Code: const ersetzt hast - der direkte Nutzen offenbart sich mir nicht, aber vom Stil her könnte es besser sein. Was mir aber garnicht in den Kopf geht, ist warum du das var vor dem counter entfernt hast. Dadurch wird die Variable ja lokal und kann keinen Wert zurückgeben... Ich kriegs jetzt momentan nicht konstruiert, aber anscheinend bekommt Counter einfach 50ig mal + 1 und wird dann "resetted".

    Aus irgend einem Grund wird die Bedingung für die Unterbrechung der rekursive Ausführung auch nie erfüllt. -> Endlosschleife.

    Ich habe gestern Abend auch noch einen Fehler gefunden - zumindest denke ich, dass es ein Fehler ist. Ich habe die Variable x nicht mehr selbst inkrementiert, sondern nur eine Kopie davon.

    Wie auch immer - Ich bedanke mich für die Zeit, die ihr geopfert habt.



    Re: Google Treasur Hunt

    wirthi - 19.05.2008, 17:26


    Das ergebnis soll dir deutlich machen, dass es nicht funktionieren wird, wenn du alle wege durchrechnest - das dauert einfach viel zu lange.

    Ich habs übrigens in einer Excel-Tabelle errechnet; natürlich kannst du das gleiche auch in einem Programm in einem Array machen.

    Wie? Ganz einfach: du startest links oben ([0,0]) und willst rechts unten (einfacheres Beispiel: [9,9]) hin. Rechnen wir einfach mal rückwärts!

    Du stehst in der Zelle ganz rechts unten ([9,9]) - wieviel Wege hast du dort noch ins Ziel? Genau, 0 (bist ja schon dort).

    In [8,9] hast du noch genau einen Weg: einmal nach rechts. Gleiches in [9,8]: ein Weg, nach unten.

    In [8,8] hast du zwei möglichkeiten: du könntest nach rechts oder nach unten gehen. Gehst du nach rechts, hättest du 1 Weg (steht so in [9,8]). Gehst du nach unten, hättest du 1 Weg (steht so in [8,9]). In Summe hast du also, wenn du in [8,8] bist, noch 2 verschiedene Wege.

    Dies kannst du nun beliebig fortsetzen. Du füllst die Matrix also beispielsweise von unten nach oben und von rechts nach links, solange, bis du auf den Startknoten kommst. Der Wert in array[x,y] errechnet sich mit array[x+1,y]+array[x,y+1]; außer natürlich am rand des arrays, so x+1 oder y+1 möglicherweise nicht mehr geht.

    Code:
         .     .     .    .
         .     .     .    .
    ...10    6    3    1

    ...  4    3    2    1

    ...  1    1    1    1 


    Achtung allerdings: die Werte werden schnell sehr groß. In einen normalen int geht das nicht mehr hinein. Ich weiß nicht, ob es in Pascal überhaupt einen passenden Datentyp gibt, der den korrekten Wert noch abspeichern kann.

    Nachtrag: mit Excel ließ es sich nur ungefähr errechnen - auch diesem fehlte der Datentyp, offenbar hat es in Gleitkomma gerechnet und stieß bald an die Grenzen dieses Datentypes. Die genaue Lösung lässt sich etwa unter Java mit BigInteger errechnen - ähnliche Datentypen gibt es vermutlich auch für andere Programmiersprachen.



    Re: Google Treasur Hunt

    jan040793 - 19.05.2008, 17:30


    @ wirthi: Danke ^^*

    Damit ist das ganze wohl geklärt. Von mir aus könnt ihr das Thema closen...



    Mit folgendem Code, können Sie den Beitrag ganz bequem auf ihrer Homepage verlinken



    Weitere Beiträge aus dem Forum Tutorials.at

    Allgemeine strukturen - gepostet von DrPhil_Guth am Dienstag 27.06.2006
    Problem - gepostet von Bratwurst am Sonntag 27.01.2008
    Volumenrechner [Erledigt] - gepostet von AQE89 am Sonntag 28.05.2006
    hab ein problem mit turbo C - gepostet von AMÖ27 am Sonntag 13.05.2007
    Kapitel 5 und 6 von C - gepostet von tamdy am Freitag 22.02.2008
    C++ Tutorial (by progger) - gepostet von progger am Freitag 25.08.2006
    Schriftfarbe in C - gepostet von mitti am Sonntag 29.04.2007
    Blitz3D-Welten - gepostet von Dragorad am Dienstag 14.11.2006
    Umstieg von DevCpp zu Visual C++ 6.0 - gepostet von DrPhil_Guth am Mittwoch 28.03.2007



    Ähnliche Beiträge wie "Google Treasur Hunt"

    Geld fuer HomerSports - David (Dienstag 18.03.2008)
    Deine Mudda-Witze - bigdaddy1990 (Dienstag 13.02.2007)
    Sprüche/Witze - krissi (Donnerstag 10.08.2006)
    Witze - baerchenmama (Donnerstag 19.10.2006)
    Witze - Lexy (Mittwoch 01.03.2006)
    Polic witze :D - jacksen (Donnerstag 02.03.2006)
    Witze - Bulldog28 (Donnerstag 24.01.2008)
    anti Witze - Rai (Samstag 24.06.2006)
    Beamten Witze falls ihr noch gute habt bitte eintrage - nici2711 (Sonntag 19.11.2006)
    Witze - copykakashi (Freitag 15.06.2007)