{"id":732,"date":"2022-07-20T22:53:40","date_gmt":"2022-07-20T20:53:40","guid":{"rendered":"https:\/\/followthescore.org\/schueler-labor\/?p=732"},"modified":"2022-09-06T07:16:40","modified_gmt":"2022-09-06T05:16:40","slug":"eichen-im-kreis","status":"publish","type":"post","link":"https:\/\/followthescore.org\/schueler-labor\/eichen-im-kreis\/","title":{"rendered":"Eichen im Kreis"},"content":{"rendered":"\n<p>Stell dir einige Eichen vor, die kreisf\u00f6rmig angeordnet sind. Deine Aufgabe besteht darin, die B\u00e4ume unregelm\u00e4\u00dfig so auf der Kreislinie zu verteilen, dass keine zwei B\u00e4ume den selben Abstand voneinander haben. Der Abstand wird in ganzen Zahlen entlang des Kreisbogens gemessen. <\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img src=\"https:\/\/www.garten-europa.com\/wp-content\/uploads\/2014\/11\/baumkreis-1280x550.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<p> Schaffst du es bei einem Kreis der <strong>Gr\u00f6\u00dfe 21 mit 5 Eichen<\/strong> durch Probieren? Bedenke, dass es insgesamt <strong>20 verschiedene Abst\u00e4nde<\/strong> gibt!<\/p>\n\n\n\n<p>Wie viele L\u00f6sungen gibt es? Wir wollen als L\u00f6sungen nur Anordnungen gelten lassen, die nicht durch Drehung oder Spiegelung auseinander hervorgehen &#8212; ja, da wird das systematische Probieren schon ein wenig m\u00fchsam&#8230;<\/p>\n\n\n\n<p>F\u00fcr <strong>sechs Eichen (Kreisumfang = 31)<\/strong> wollen wir dann doch lieber den Rechner verwenden. Schreibe ein Programm in einer beliebigen Programmiersprache (python, Java, Javascript, php, C ), welches alle L\u00f6sungen findet und ausgibt.<\/p>\n\n\n\n<p>Lass das Programm mit 7, 8 und 9 Eichen laufen. Wie unterscheiden sich die Laufzeiten? Die zugeh\u00f6rigen Kreisumf\u00e4nge betragen jeweils N*(N-1) + 1. also 43, 57 und 73.<\/p>\n\n\n\n<p>Du k\u00f6nntest ganz viele beliebige Anordnungen der Eichen per Zufall erzeugen und dann jeweils pr\u00fcfen, ob alle ihre Abst\u00e4nde verschieden sind. Aber du wirst dabei nie wissen, ob du alle L\u00f6sungen gefunden hast. Au\u00dferdem werden viele Anordnungen mehrfach erzeugt, wenn du das Programm sehr lange laufen l\u00e4sst.<\/p>\n\n\n\n<p>Vermutlich probiert dein Programm daher einfach alle denkbaren Anordnungen durch. Kannst du es so verbessern, dass nur deutlich weniger Anordnungen untersucht werden m\u00fcssen?<\/p>\n\n\n\n<p>Hast du Python verwendet? Dann ist dein Programm vermutlich kurz und elegant, aber es l\u00e4uft ungef\u00e4hr 7 mal langsamer als mit Javascript. Gegen\u00fcber Java und C ist der Unterschied noch gr\u00f6\u00dfer.<\/p>\n\n\n\n<p>Dein Rechner hat vier oder acht Rechenkerne, aber dein Programm nutzt vermutlich nur einen davon. Kannst du ihm beibringen, alle Kerne zu nutzen?<\/p>\n\n\n\n<p>Hast du eine moderne Grafikkarte (Geforce ..) ? Dann besitzt die Grafikkarte vermutlich 100 mal mehr Rechenleistung als dein &#8222;Haupt&#8220;-CPU. Du kannst eine gewaltige Beschleunigung erzielen, wenn du das Programm auf der Grafikkarte ausf\u00fchrst. Wie das geht? Schau dir mal CUDA an! CUDA unterst\u00fctzt nicht nur <em>C\/C++<\/em>, sondern auch <em>Perl, Python , Ruby, Java <\/em>und <em>.NET!<\/em><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Stell dir einige Eichen vor, die kreisf\u00f6rmig angeordnet sind. Deine Aufgabe besteht darin, die B\u00e4ume unregelm\u00e4\u00dfig so auf der Kreislinie zu verteilen, dass keine zwei B\u00e4ume den selben Abstand voneinander haben. Der Abstand wird in ganzen Zahlen entlang des Kreisbogens gemessen. Schaffst du es bei einem Kreis der Gr\u00f6\u00dfe 21 mit 5 Eichen durch Probieren?&hellip; <a class=\"more-link\" href=\"https:\/\/followthescore.org\/schueler-labor\/eichen-im-kreis\/\"><span class=\"screen-reader-text\">Eichen im Kreis<\/span> weiterlesen<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts\/732"}],"collection":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/comments?post=732"}],"version-history":[{"count":4,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts\/732\/revisions"}],"predecessor-version":[{"id":750,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts\/732\/revisions\/750"}],"wp:attachment":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/media?parent=732"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/categories?post=732"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/tags?post=732"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}