Das wichtigste natürlich wie immer zuerst: Die Kopfkoordinaten sind natürlich rein fiktiv, hier kann man keinen Cache finden.
Ganz schön anstrengend dieses Sortieren! Nachdem unser Statistik-Cacher schon ein eigenes Verfahren und das Verfahren eines Freundes kennen gelernt hat, ist er schon ganz schön am Schwitzen, während er seine PETlinge sortiert. Da kommt ein weiteres Mitglied des Organisationsteams auf den Cacher zu. Er ist mathematisch ziemlich bewandert und hat eine super Idee, wie man dieses Sortieren viel flotter machen kann. Er schreibt seine Erinnerungen an ein ihm bekanntes Verfahren auf einen Zettel:
Der Statistik-Cacher ist hier erstmal ein wenig überfordert. Das sieht doch viel komplizierter aus als die zwei Verfahren, die er bis jetzt kennen gelernt hat. Der Mathematiker erklärte noch ein paar Dinge. Die LISTE ist einfach die Liste der zu sortierenden Elemente. In diesem Fall die Nummern der PETlinge. Diese Liste gibt man der Funktion qs, die dann wiederum die eigentliche Sortierung mit sortiere startet. Doch was passiert da jetzt eigentlich?
Die Funktion sortiere bekommt als Eingabe eine Zahl LINKS und eine Zahl RECHTS. Beim ersten Aufruf ist LINKS = 0, d.h. die linke Position der Liste (Mathematiker sind manchmal komisch und beginnen bei 0 zu zählen ;-). RECHTS entspricht der Position vom rechten Ende der Liste (wenn wir bei 0 mit dem Zählen Anfangen, müssen wir natürlich mit 999 aufhören, daher „Anzahl der Elemente in der LISTE – 1“). Wenn jetzt LINKS < RECHTS ist, was natürlich immer der Fall ist, wenn die Liste mehr als ein Element enthält, dann wird mit der teile-Funktion ein TEILER ermittelt, der irgendwo innerhalb der Liste zu sein scheint. Im Anschluss wird die sortiere-Funktion in sich selbst zweimal aufgerufen (dieses Prinzip nennt man übrigens Rekursion). Einmal für alle Elemente, die links vom TEILER stehen und einmal für alle Elemente, die rechts vom TEILER zu finden sind. Das ist auch im Prinzip schon der ganze Zauber ;-)
Jetzt gibt es da noch die Funktion teile. Hier wird erstmal festgelegt, dass in einer Variable i die Zahl LINKS gespeichert wird (also die Position in der Liste ganz links), und in einer Variable j die Zahl RECHTS - 1 (also die Position des vorletzten Elements der Liste). Dann gibt es da noch ein Element Namens PIVOT. „Was soll das denn sein?“ fragt sich unser Statistik-Freund. Das Pivotelement ist einfach irgendeine Zahl aus der Liste, die mal nutzt, um daran Vergleiche mit anderen Zahlen zu machen. Hier wird einfach das Element ganz rechts benutzt. Anschließend wird i solange um 1 erhöht, bis von links nach rechts gelesen eine Zahl gefunden wird, die kleiner oder gleich dem PIVOT ist. Weiterhin wird j solange um 1 verkleinert, bis von rechts nach links gelesen eine Zahl gefunden wird, die größer oder gleich dem PIVOT ist. Wenn i < j ist, dann werden die Elemente an Position i und j in der Liste einfach vertauscht. Nachdem nun alle i und j getauscht wurden und i grade noch kleiner als j ist, wird das Element an Stelle i in der Liste mit dem PIVOT getauscht, falls das Pivotelement kleiner ist. Damit stehen alle Elemente, die kleiner als das PIVOT sind links von diesem Element und alle Elemente die größer sind als das PIVOT rechts. Die Funktion teile gibt dann letztendlich als Antwort die Position des Pivotelements zurück. Der mathematische Freund will dem Cacher das ganze nochmal an einem Beispiel zeigen.
Wem ab hier alles klar ist, der darf die Stelle überspringen, alle anderen dürfen sich hier das Beispiel des Cacherfreundes nochmal anschauen (Dropbox-Link, keine schädlichen Inhalte, ein einfaches PDF Dokument):
https://dl.dropboxusercontent.com/u/10805545/BeispielCIB3.pdf
Ein wenig schräg findet der Statistik-Cacher das ganze schon. Wer denkt sich denn bitte sowas aus? Aber sein Hobby hat ihn auch gelehrt, dass man auch den verrücktesten Dingen eine Chance geben sollte. Manchmal führen doch wirklich die seltensten Wege zum Ziel. Also zieht er es einfach durch und sortiert seine chaotische Cachesammlung mit dem Verfahren seines mathematischen Freundes. Die Dosen liegen wie immer in folgender Reihenfolge vor:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 822, 450, 624, 122, 144, 247, 976, 803, 242, 438, 340, 250, 270, 374, 383, 605, 590, 571, 367, 330, 993, 319, 585, 865, 926, 197, 673, 727, 574, 168, 572, 743, 1000, 159, 423, 790, 665, 736, 193, 816, 869, 153, 542, 689, 884, 745, 989, 813, 468, 744, 352, 889, 485, 175, 881, 979, 821, 323, 616, 389, 298, 375, 283, 556, 569, 967, 629, 713, 702, 971, 183, 842, 230, 843, 296, 759, 312, 315, 925, 880, 581, 915, 652, 687, 437, 598, 458, 635, 287, 320, 506, 617, 362, 466, 717, 439, 678, 373, 623, 784, 804, 278, 397, 207, 773, 403, 218, 414, 226, 681, 327, 645, 706, 820, 649, 396, 432, 772, 526, 333, 173, 747, 902, 540, 463, 351, 524, 753, 789, 467, 483, 261, 530, 391, 244, 907, 877, 501, 292, 399, 900, 253, 544, 553, 966, 917, 754, 174, 344, 136, 798, 356, 796, 625, 701, 631, 126, 448, 811, 162, 782, 953, 408, 275, 791, 593, 726, 560, 163, 361, 237, 484, 415, 282, 879, 555, 192, 722, 920, 297, 632, 557, 964, 895, 529, 823, 893, 308, 614, 547, 668, 746, 965, 970, 862, 139, 503, 299, 234, 943, 477, 996, 734, 418, 406, 723, 761, 871, 732, 551, 416, 479, 700, 863, 243, 562, 799, 422, 272, 213, 514, 897, 502, 219, 690, 123, 733, 851, 850, 309, 471, 712, 819, 788, 675, 143, 924, 956, 930, 441, 921, 519, 859, 888, 792, 494, 716, 954, 357, 945, 370, 766, 891, 224, 525, 724, 167, 584, 817, 548, 276, 644, 583, 646, 935, 767, 856, 922, 305, 252, 919, 401, 853, 937, 674, 639, 260, 273, 987, 185, 128, 628, 968, 335, 184, 489, 227, 595, 962, 545, 328, 258, 388, 800, 212, 400, 148, 814, 324, 145, 941, 480, 588, 985, 214, 659, 615, 929, 848, 841, 570, 204, 535, 302, 240, 641, 933, 289, 657, 321, 636, 882, 977, 683, 342, 444, 497, 537, 131, 932, 515, 233, 912, 846, 453, 999, 304, 648, 587, 719, 958, 465, 424, 684, 656, 413, 861, 288, 825, 206, 794, 838, 923, 536, 827, 527, 462, 606, 721, 369, 225, 604, 246, 121, 762, 407, 660, 739, 679, 774, 951, 249, 265, 133, 992, 867, 711, 459, 125, 508, 500, 815, 695, 513, 199, 728, 662, 786, 368, 410, 749, 232, 840, 341, 436, 151, 688, 708, 973, 834, 969, 251, 775, 285, 696, 520, 512, 359, 768, 669, 828, 293, 160, 314, 460, 511, 178, 801, 504, 564, 518, 451, 974, 883, 829, 364, 181, 322, 395, 898, 129, 855, 349, 836, 903, 211, 157, 231, 200, 758, 908, 984, 878, 189, 972, 610, 130, 472, 149, 179, 640, 948, 201, 533, 909, 180, 667, 366, 326, 676, 155, 663, 457, 269, 983, 209, 132, 402, 936, 236, 534, 336, 405, 493, 182, 378, 931, 546, 844, 872, 577, 580, 661, 946, 594, 741, 452, 347, 345, 797, 618, 868, 196, 385, 266, 509, 955, 507, 481, 210, 826, 653, 284, 150, 141, 241, 715, 579, 894, 707, 217, 582, 621, 434, 750, 990, 417, 522, 832, 934, 694, 812, 905, 313, 637, 738, 152, 316, 190, 864, 573, 835, 146, 166, 995, 194, 280, 730, 505, 664, 655, 433, 412, 372, 140, 440, 549, 597, 763, 411, 254, 329, 238, 642, 290, 461, 771, 858, 714, 963, 704, 550, 949, 705, 857, 916, 360, 268, 499, 198, 404, 420, 756, 666, 510, 215, 824, 267, 777, 496, 303, 960, 780, 470, 446, 633, 176, 612, 939, 735, 355, 517, 698, 338, 409, 435, 839, 906, 576, 205, 478, 449, 630, 346, 860, 886, 447, 672, 691, 318, 473, 558, 575, 239, 430, 778, 137, 849, 392, 229, 602, 138, 235, 899, 870, 245, 600, 729, 975, 255, 307, 259, 216, 942, 650, 911, 779, 257, 331, 262, 950, 959, 256, 135, 228, 831, 300, 998, 488, 386, 765, 795, 626, 764, 988, 306, 454, 482, 847, 429, 978, 938, 940, 802, 742, 532, 222, 982, 543, 874, 127, 991, 892, 154, 622, 334, 521, 709, 837, 281, 873, 944, 913, 455, 445, 896, 539, 147, 456, 671, 177, 393, 770, 651, 866, 961, 807, 263, 295, 172, 634, 793, 692, 876, 442, 737, 854, 371, 286, 725, 538, 223, 498, 491, 748, 431, 578, 703, 808, 187, 740, 348, 757, 311, 685, 343, 427, 783, 464, 332, 910, 927, 487, 810, 443, 195, 591, 566, 686, 186, 358, 170, 317, 191, 875, 169, 476, 528, 833, 601, 279, 567, 523, 552, 890, 776, 752, 220, 613, 980, 720, 363, 421, 425, 350, 760, 377, 541, 337, 981, 755, 294, 264, 274, 599, 379, 208, 769, 380, 398, 202, 619, 928, 643, 918, 677, 291, 277, 390, 381, 310, 428, 134, 563, 171, 718, 561, 627, 699, 164, 947, 620, 607, 994, 188, 751, 120, 731, 710, 682, 609, 475, 852, 156, 486, 559, 419, 845, 904, 901, 957, 680, 997, 339, 124, 474, 142, 531, 221, 203, 492, 670, 568, 806, 830, 394, 165, 376, 248, 365, 787, 589, 952, 426, 693, 596, 611, 469, 608, 354, 654, 158, 697, 885, 325, 554, 382, 914, 161, 516, 603, 658, 818, 301, 785, 592, 271, 781, 565, 638, 384, 495, 887, 490, 805, 353, 986, 387, 809, 586, 647
Die Frage ist nun: Wie oft wird hier eigentlich die Funktion sortiere selbst aufgerufen? Und vor allem: Wie viele Vergleiche und Vertauschungen finden hier insgesamt statt? Als Vergleich gelten alle Abfragen der Form „wenn (xyz) ist, dann…“ (3 Stück im Code). Die Vertauschungen sind durch das Schlüsselwort „vertausche“ gekennzeichnet (2 Stück im Code). Finden hier wirklich so viel weniger Vergleiche und Vertauschungen statt als bei den zwei „alten“ Verfahren? Außerdem wäre doch hier mal interessant, welchen Wert die Variable RECHTS beim 1., 2. und 3. Aufruf der Funktion sortiere hat. Helft dem Cacher diese Fragen zu beantworten!
A sei hier die Anzahl der Aufrufe der Funktion sortiere
B sei die Anzahl der Vertauschungen
C sei die Anzahl der Vergleiche
D sei die Summe der drei Werte von RECHTS im 1., 2. und 3. Aufruf der Funktion sortiere
Nun noch etwas für die Handrechner unter euch: Geht von der unsortierten Zahlenreihe [2, 6, 3, 5, 7, 1, 4] aus. Geht davon aus, dass man diese Zahlen mit dem oben gezeigten Algorithmus sortiert. E = (Summe aller Pivotelemente – Anzahl aller Pivotelemente)
Gesucht ist nun eine Lösungszahl, die ganz einfach berechnet werden kann:
Lösungszahl = ((C – A) / E) + B – D
Wenn ihr diese Zahl bei certitudes.org eingebt, erhaltet ihr die Koordinaten der Dose und könnt schon mal eins der tausend Verstecke aufsuchen :-)
Da es hier einen Bonus bei dieser Cacheserie gibt, notiert euch bitte die Bonuszahl, falls ihr auch noch diese Dose finden möchtet. Viel Spaß beim rätseln, rechnen, suchen und loggen! Es ist möglich diese Serie auch als Wanderung anzugehen - was ich übrigens auch empfehle. Die Wegstrecke beträgt etwa 5km. Benutzt dafür den angegebenen Parkplatz. Ich empfehle euch dabei die Caches in der Reihenfolge (Chaos 5, Chaos 1, Chaos 2, Chaos 4, Chaos 3 und Chaos Bonus) anzugehen.