inf-schule | Wege im Gitternetz

Problemreduktion

Das Problem auf ein analoges zurückführen

Wir betrachten weiterhin ein gitterförmiges Wegenetz und entwickeln Eigenschaften der Funktion anzahlWege.

Aufgabe 1

Begründe anhand der Abbildung: Ein (kürzester) Weg zum Punkt (9,4) führt entweder über den Punkt (8,3) oder über den Punkt (8,4).

    <img alt="Reduktionsschritt" src="https://inf-schule.de/content/8_deklarativ/2_fp_elm/2_elm_programme/10_rekursion/4_galton/2_problemreduktion/reduktion1.jpg">
    </li>

    <li>
        Begr&uuml;nde: Man erh&auml;lt daher den folgenden Problemreduktionsschritt:
        <pre>anzahlWege 9 4 -&gt; anzahlwege 8 3 + anzahlWege 8 4</pre>
    </li>
</ol>

Aufgabe 2

Die in Aufgabe 1 durchgeführte Argumentation kann man auf alle inneren Punkte des Punktgitters übertragen.

<img alt="Reduktionsschritt" src="https://inf-schule.de/content/8_deklarativ/2_fp_elm/2_elm_programme/10_rekursion/4_galton/2_problemreduktion/reduktion2.jpg">

<ol>
    <li>Erg&auml;nze den Problemreduktionsschritt:

        <pre><code>anzahlWege 6 2 -&gt; anzahlwege ... ... + anzahlWege ... ...

Verallgemeinere den Problemreduktionsschritt für innere Punkte:

Falls k > 0 und k < n:
anzahlWege n k -> anzahlwege ... ... + anzahlWege ... ...

Aufgabe 3

Begründe: Für einen Punkt am linken Rand des Punktgitters kann man die Anzahl der kürzesten Wege direkt angeben.

Begründe den Reduktionsanfang:
```
anzahlWege 4 0 -> 1
```

    <li>
        <p>Begr&uuml;nde den verallgemeinerten Reduktionsanfang: </p>
        <pre><code>Falls k == 0:

anzahlWege n k -> 1

Aufgabe 4

Begründe: Für einen Punkt am rechten Rand des Punktgitters kann man die Anzahl der kürzesten Wege ebenfalls direkt angeben.

Ergänze den Reduktionsanfang:
```
    anzahlWege 3 3 -> ...
```

<li>Erg&auml;nze den verallgemeinerten Reduktionsanfang:
    <pre><code>    Falls ...:
anzahlWege n k -&gt; ...</code></pre>
</li>

Aufgabe 5

In den Reduktionsschritten haben wir ein Verfahren benutzt, das man rekursive Problemreduktion nennt. Es besagt: Reduziere das Problem auf ein entsprechendes, aber verkleinertes Problem. Erläutere das Verfahren im aktuellen Kontext. Was bedeutet hier "entsprechend" und was bedeutet "verkleinert"?