{"id":2465,"date":"2019-09-12T01:53:51","date_gmt":"2019-09-11T23:53:51","guid":{"rendered":"https:\/\/vielhuber.de\/?p=2465"},"modified":"2020-09-08T01:42:06","modified_gmt":"2020-09-07T23:42:06","slug":"project-euler-lattice-paths","status":"publish","type":"post","link":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/","title":{"rendered":"Project Euler: Lattice paths"},"content":{"rendered":"\n<p><a rel=\"noreferrer noopener\" aria-label=\" (opens in a new tab)\" href=\"https:\/\/projecteuler.net\" target=\"_blank\">Project Euler<\/a> ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, das man raffinierte Algorithmen entwickeln muss, um in einer vern\u00fcnftigen Laufzeit zum Ziel zu kommen. Heute l\u00f6sen wir <a rel=\"noreferrer noopener\" aria-label=\"Problem 15: Lattice paths (opens in a new tab)\" href=\"https:\/\/projecteuler.net\/problem=15\" target=\"_blank\">Problem 15: Lattice paths<\/a>, bei dem man mit einfachen kombinatorischen Mitteln an die L\u00f6sung kommt.<\/p>\n\n\n\n<!--more-->\n\n\n\n<p>Die Frage lautet wie folgt:<\/p>\n\n\n\n<p class=\"notranslate\"><strong>\u201eStarting in the top left corner of a 2\u00d72 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.  How many such routes are there through a 20\u00d720 grid?\u201c<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"221\" height=\"162\" src=\"https:\/\/vielhuber.de\/wp-content\/uploads\/image-2.png\" alt=\"\" class=\"wp-image-2466\"\/><\/figure><\/div>\n\n\n\n<p>Die Problemstellung l\u00e4sst sich auch anders formulieren: Gesucht ist die M\u00e4chtigkeit der Teilmenge aller Wege<\/p>\n\n\n\n<p>$$W = {w_1, \u2026, w_{2^n}}, \\, w_k = p_1 \\cdots p_{2\\cdot n}, \\, p_k \\in \\{ R, D \\}.$$<\/p>\n\n\n\n<p>Es handelt sich hier um ein einfaches kombinatorisches Problem, bei dem wir das Urnenmodell heranziehen (ohne Zur\u00fccklegen und ohne Beachtung der Reihenfolge). Wir sind nun genau an denjenigen Wegen interessiert, f\u00fcr die gilt, dass \\(R\\) und \\(D\\) genau gleich oft vorkommen. Demnach ergibt sich f\u00fcr alle m\u00f6glichen Kombinationen:<\/p>\n\n\n\n<p>$$\\binom{2\\cdot n}{n} = \\frac{(2\\cdot n)!}{n!\\cdot n!}$$<\/p>\n\n\n\n<p>F\u00fcr \\(n=20\\) ergibt sich damit:<\/p>\n\n\n\n<p>$$ \\frac{(40)!}{20!\\cdot 20!} = 137846528820.$$<\/p>\n\n\n\n<p>Wir k\u00f6nnen das Problem auf nicht-quadratische Grids erweitern. Nachfolgende L\u00f6sung realisiert in PHP mit Hilfe von <a rel=\"noreferrer noopener\" aria-label=\"bcmath (opens in a new tab)\" href=\"https:\/\/www.php.net\/manual\/de\/book.bc.php\" target=\"_blank\">bcmath<\/a> mit einer Laufzeit von \\( O(n) \\) eine Berechnung mit dem Eingabeformat \"Anzahl der Testf\u00e4lle, \\(n_1\\) \\(m_1\\), ...\":<\/p>\n\n\n\n<p class=\"githubgist\" data-gist-file=\"script.php\">47bb78215ee0531a787bb5034652eaf4<\/p>\n\n\n\n<p>Alle Probleme des Euler Projects lassen sich auf der empfehlenswerten Seite <a href=\"https:\/\/www.hackerrank.com\" target=\"_blank\" rel=\"noreferrer noopener\" aria-label=\"HackerRank (opens in a new tab)\">HackerRank<\/a> \u00fcbrigens auch online l\u00f6sen.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, das man raffinierte Algorithmen entwickeln muss, um in einer vern\u00fcnftigen Laufzeit zum Ziel zu kommen. Heute l\u00f6sen wir Problem 15: Lattice paths, bei dem man mit einfachen kombinatorischen Mitteln an die L\u00f6sung kommt.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"gtbabel_prevent_lngs":"","gtbabel_alt_lng":"","footnotes":""},"categories":[1],"tags":[],"class_list":{"0":"post-2465","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-blog"},"acf":[],"yoast_head":"<title>Project Euler: Lattice paths &#060; Vielhuber David<\/title>\n<meta name=\"description\" content=\"Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, da...\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/\" \/>\n<meta property=\"og:locale\" content=\"de_DE\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Project Euler: Lattice paths &#060; Vielhuber David\" \/>\n<meta property=\"og:description\" content=\"Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, das\" \/>\n<meta property=\"og:url\" content=\"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/\" \/>\n<meta property=\"og:site_name\" content=\"Vielhuber David\" \/>\n<meta property=\"article:published_time\" content=\"2019-09-11T23:53:51+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-09-07T23:42:06+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/vielhuber.de\/wp-content\/uploads\/image-2.png\" \/>\n<meta name=\"author\" content=\"David\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vielhuber\" \/>\n<meta name=\"twitter:site\" content=\"@vielhuber\" \/>\n<meta name=\"twitter:label1\" content=\"Verfasst von\" \/>\n\t<meta name=\"twitter:data1\" content=\"David\" \/>\n\t<meta name=\"twitter:label2\" content=\"Gesch\u00e4tzte Lesezeit\" \/>\n\t<meta name=\"twitter:data2\" content=\"1\u00a0Minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/\"},\"author\":{\"name\":\"David\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\"},\"headline\":\"Project Euler: Lattice paths\",\"datePublished\":\"2019-09-11T23:53:51+00:00\",\"dateModified\":\"2020-09-07T23:42:06+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/\"},\"wordCount\":263,\"publisher\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\"},\"image\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/image-2.png\",\"articleSection\":[\"Blog\"],\"inLanguage\":\"de\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/\",\"url\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/\",\"name\":\"Project Euler: Lattice paths &#060; Vielhuber David\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/image-2.png\",\"datePublished\":\"2019-09-11T23:53:51+00:00\",\"dateModified\":\"2020-09-07T23:42:06+00:00\",\"description\":\"Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, das\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/#breadcrumb\"},\"inLanguage\":\"de\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"de\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/#primaryimage\",\"url\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/image-2.png\",\"contentUrl\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/image-2.png\",\"width\":221,\"height\":162,\"caption\":\"Starting in the top left corner of a 2\u00d72 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/project-euler-lattice-paths\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/vielhuber.de\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Project Euler: Lattice paths\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#website\",\"url\":\"https:\\\/\\\/vielhuber.de\\\/\",\"name\":\"Vielhuber David\",\"description\":\"Full-Stack Developer\",\"publisher\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/vielhuber.de\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"de\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\",\"name\":\"David\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"de\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\",\"url\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\",\"contentUrl\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\",\"width\":700,\"height\":552,\"caption\":\"David\"},\"logo\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\"},\"sameAs\":[\"https:\\\/\\\/x.com\\\/vielhuber\"]}]}<\/script>","yoast_head_json":{"title":"Project Euler: Lattice paths &#060; Vielhuber David","description":"Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, da...","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/","og_locale":"de_DE","og_type":"article","og_title":"Project Euler: Lattice paths &#060; Vielhuber David","og_description":"Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, das","og_url":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/","og_site_name":"Vielhuber David","article_published_time":"2019-09-11T23:53:51+00:00","article_modified_time":"2020-09-07T23:42:06+00:00","og_image":[{"url":"https:\/\/vielhuber.de\/wp-content\/uploads\/image-2.png","type":"","width":"","height":""}],"author":"David","twitter_card":"summary_large_image","twitter_creator":"@vielhuber","twitter_site":"@vielhuber","twitter_misc":{"Verfasst von":"David","Gesch\u00e4tzte Lesezeit":"1\u00a0Minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/#article","isPartOf":{"@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/"},"author":{"name":"David","@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef"},"headline":"Project Euler: Lattice paths","datePublished":"2019-09-11T23:53:51+00:00","dateModified":"2020-09-07T23:42:06+00:00","mainEntityOfPage":{"@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/"},"wordCount":263,"publisher":{"@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef"},"image":{"@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/#primaryimage"},"thumbnailUrl":"https:\/\/vielhuber.de\/wp-content\/uploads\/image-2.png","articleSection":["Blog"],"inLanguage":"de"},{"@type":"WebPage","@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/","url":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/","name":"Project Euler: Lattice paths &#060; Vielhuber David","isPartOf":{"@id":"https:\/\/vielhuber.de\/#website"},"primaryImageOfPage":{"@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/#primaryimage"},"image":{"@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/#primaryimage"},"thumbnailUrl":"https:\/\/vielhuber.de\/wp-content\/uploads\/image-2.png","datePublished":"2019-09-11T23:53:51+00:00","dateModified":"2020-09-07T23:42:06+00:00","description":"Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, das","breadcrumb":{"@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/#breadcrumb"},"inLanguage":"de","potentialAction":[{"@type":"ReadAction","target":["https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/"]}]},{"@type":"ImageObject","inLanguage":"de","@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/#primaryimage","url":"https:\/\/vielhuber.de\/wp-content\/uploads\/image-2.png","contentUrl":"https:\/\/vielhuber.de\/wp-content\/uploads\/image-2.png","width":221,"height":162,"caption":"Starting in the top left corner of a 2\u00d72 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner."},{"@type":"BreadcrumbList","@id":"https:\/\/vielhuber.de\/blog\/project-euler-lattice-paths\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/vielhuber.de\/"},{"@type":"ListItem","position":2,"name":"Project Euler: Lattice paths"}]},{"@type":"WebSite","@id":"https:\/\/vielhuber.de\/#website","url":"https:\/\/vielhuber.de\/","name":"Vielhuber David","description":"Full-Stack Developer","publisher":{"@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/vielhuber.de\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"de"},{"@type":["Person","Organization"],"@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef","name":"David","image":{"@type":"ImageObject","inLanguage":"de","@id":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg","url":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg","contentUrl":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg","width":700,"height":552,"caption":"David"},"logo":{"@id":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg"},"sameAs":["https:\/\/x.com\/vielhuber"]}]}},"_links":{"self":[{"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/posts\/2465","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/comments?post=2465"}],"version-history":[{"count":19,"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/posts\/2465\/revisions"}],"predecessor-version":[{"id":2745,"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/posts\/2465\/revisions\/2745"}],"wp:attachment":[{"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/media?parent=2465"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/categories?post=2465"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vielhuber.de\/id\/wp-json\/wp\/v2\/tags?post=2465"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}