Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Schnurlängen (Rekursion)

Eine Schnur mit einer Gesamtlänge von 450 m soll in Teilstücke der Länge 17 m, 19 m und 21 m geteilt werden. Ist das ohne Rest möglich? Die Frage reduziert sich darauf, ob eine der drei Differenzen

  • 450 - 17 = 433,
  • 450 - 19 = 431 und
  • 450 - 21 = 429

ohne Rest aufgeschnitten werden kann. Denn wenn dies für eine der genannten drei Differenzen möglich ist, so ist es sicher auch für 450 m möglich. Schreiben Sie eine Methode zerlegbar(gesamt, laenge1, laenge2, laenge3), die im Wesentlichen prüft, ob eine der drei Bedingungen

  • zerlegbar(gesamt-laenge1, laenge1, laenge2, laenge3),
  • zerlegbar(gesamt-laenge2, laenge1, laenge2, laenge3) oder
  • zerlegbar(gesamt-laenge3, laenge1, laenge2, laenge3)

zutrifft.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

3 Lösung(en)

/**
 * Das folgende Programm zeigt, ob ein Rohr der
 * Länge "gesamt" einteilbar ist in Stücke der
 * Länge l1, l2 und l3. 
 * Dabei dürfen beliebig viele Stücke jeder Sorte
 * (l1, l2, und l3) geschnitten werden.
 * 
 * Das Programm liefert TRUE, wenn es keinen Rest
 * gibt.
 * @author Philipp Gressly (phi AT gressly DOT ch)
 */
public class Schnurlaengen {
    public static void main(String[] args) {
        new Schnurlaengen() . top();
    }
    
    void top() {
        if(teilbar(450, 17, 19, 21)) {
            System.out.println("Teilbar");
        } else {
            System.out.println("Unteilbar");
        }
    }
    
    boolean teilbar(int gesamt, int l1, int l2, int l3) {
        
        if(gesamt == l1 || gesamt == l2 || 
           gesamt == l3 || gesamt == 0) {
          return true;
        }
        if(gesamt < l1 || gesamt < l2 || 
           gesamt < l3 ) {
          return false;
        }
        return
          teilbar( gesamt - l1, l1, l2, l3) ||
          teilbar( gesamt - l2, l1, l2, l3) ||
          teilbar( gesamt - l3, l1, l2, l3);
    }
}
                
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
Schnurlängen
https://www.programmieraufgaben.ch/aufgabe/schnurlaengen/acgo5ap7
"""

# Programmieraufgabe:
#     Eine Schnur mit einer Gesamtlänge von 450 m soll in Teilstücke der Länge
#     17 m, 19m und 21 m geteilt werden. Ist das ohne Rest möglich? Die Frage
#     reduziert sich darauf, ob eine der drei Differenzen
#         450 - 17 = 433,
#         450 - 19 = 431 und
#         450 - 21 = 429
#     ohne Rest aufgeschnitten werden kann. Denn wenn dies für eine der genannten
#     drei Differenzen möglich ist, so ist es sicher auch für 450 m möglich.
#     Schreiben Sie eine Methode zerlegbar(gesamt, laenge1, laenge2, laenge3),
#     die im Wesentlichen prüft, ob eine der drei Bedingungen
#         zerlegbar(gesamt-laenge1, laenge1, laenge2, laenge3),
#         zerlegbar(gesamt-laenge2, laenge1, laenge2, laenge3) oder
#         zerlegbar(gesamt-laenge3, laenge1, laenge2, laenge3)
#     zutrifft.
#
# Autor, Erstellung:
#     Ulrich Berntien, 2018-08-24
#
# Sprache:
#     Python 3.6.6


from typing import *


def zerlegbar(gesamt_laenge: int, teil_laengen: Iterable[int]) -> bool:
    """
    Kontrolliert ob Gesamtlänge in einzelne Längen zerlebar ist.
    :param gesamt_laenge:  Die zu zerlegende Gesamtlänge.
    :param teil_laengen:  In diese Längen kann zerlegt werden.
    :return: True, genau dann wenn die Gesamtlänge ohne Rest in die Teillängen zerlegbar ist.
    """
    assert gesamt_laenge > 0
    assert all(l > 0 for l in teil_laengen)
    for laenge in teil_laengen:
        if gesamt_laenge == laenge:
            # passt genau
            return True
        elif gesamt_laenge > laenge:
            if zerlegbar(gesamt_laenge - laenge, teil_laengen):
                return True
    # Keine Möglichkeit gefunden
    return False


tests = ((450, (17, 19, 21)),
         (100, (17, 19, 21)),
         (101, (17, 19, 21)))
for (test_gesamt, test_laengen) in tests:
    test_zerlegbar = zerlegbar(test_gesamt, test_laengen)
    print("Gesamtlänge {0} zerlegbar in {1}: {2}".format(test_gesamt, test_laengen, test_zerlegbar))
                

Lösung von: Ulrich Berntien ()

/**
 *  Programmieraufgabe: Schnurlängen
 *  https://www.programmieraufgaben.ch/aufgabe/schnurlaengen/acgo5ap7
 */


/**
 *  Kontrolliert ob Gesamtlänge in einzelne Längen zerlebar ist.
 *  @param gesamtLaenge Die zu zerlegende Gesamtlänge.
 *  @param teilLaengen In diese Längen kann zerlegt werden.
 *  @return true, genau dann wenn die Gesamtlänge ohne Rest in die Teillängen zerlegbar ist.
 */
fun zerlegbar(gesamtLaenge: Int, teilLaengen: IntArray): Boolean {
    assert(gesamtLaenge > 0)
    assert(teilLaengen.all { it > 0 })
    for (laenge in teilLaengen) {
        if (gesamtLaenge == laenge) {
            // Diese Teillänge passt genau
            return true
        } else if (gesamtLaenge > laenge) {
            // Bei dieser Teillänge würde ein Rest entstehen.
            if (zerlegbar(gesamtLaenge - laenge, teilLaengen)) {
                // Der Rest ist zerlegbar, also eine Möglichkeit gefunden.
                return true
            }
        }
    }
    // Mit keiner Teillänge wurde eine Zerlegung gefunden,
    // also gibt es keine Möglichkeit.
    return false
}

/**
 * Testfälle automatisch ausführen.
 * @param argv wird ignoriert.
 */
fun main(argv: Array<String>) {
    val tests = arrayOf(
            Pair(450, intArrayOf(17, 19, 21)),
            Pair(100, intArrayOf(17, 19, 21)),
            Pair(101, intArrayOf(17, 19, 21)))
    for ((gesamt, teile) in tests) {
        val result = zerlegbar(gesamt, teile)
        print("Gesamtlänge $gesamt zerlegbar in ${teile.contentToString()}: $result\n")
    }
}

                

Lösung von: Ulrich Berntien ()

Verifikation/Checksumme:

450 (17, 19, 21) -> Teilbar

100 (17, 19, 21) -> Unteilbar

101 (17, 19, 21) -> Teilbar

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 1
Schwierigkeit: k.A.
Webcode: acgo-5ap7
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen