1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

[Ruby] Ich sitze auf dem Baum fest und komme nicht runter

Dieses Thema im Forum "Algorithmen und Datenstrukturen" wurde erstellt von Mat, 10. Juli 2017.

  1. Mat

    Mat Active Member c-b Experte

    Sprache ist Ruby, aber die Frage betrifft algorithmische Sportgymnastik im Allgemeinen (hab die Ruby-Kurzschreibweise nach Möglichkeit in leichter lesbaren Code umgewandelt, für Nicht-Ruby-Leute.. sonst einfach fragen, wenn etwas noch zu exotisch aussieht):

    Ich bin ein bisschen am Ruby üben für eine Klausur und bin dabei auf eine Hirnblockade gestoßen. Habe als Datenstruktur einen Möchtegern-Baum (ist so vorgegeben), man könnte ihn eigentlich sogar eher als gerichteten Graphen abarbeiten. Der Baum besteht aus Knoten mit einem Wert (dient in diesem Fall nur als ID) und einem optionalen Array von Subknoten.

    Bild:
    Baum.png

    Problem:
    Ich möchte die maximale Tiefe bzw. den längsten Pfad beginnend ab dem ausgewählten Knoten finden. Ich sitze oben in der Baumspitze fest und will wissen, wie weit ich gleich runter fallen werde. Eigentlich ein Selbstläufer..aber ich hab eine Denkblockade.

    Knoten.rb (Methode get_max_tiefe() macht Probleme)
    Code:
    class Knoten
      def initialize(wert, unterknoten = [])
        @wert = wert
        @unterknoten = unterknoten
      end
    
      def get_anz_unterknoten()
        return @unterknoten.size()
      end
    
      def add_unterknoten(knoten)
        @unterknoten << knoten
      end
    
     def get_max_tiefe()
        return 1 if get_anz_unterknoten() < 1
    
        max = 0
        tmp = 0
        for knoten in @unterknoten
          tmp += knoten.get_max_tiefe()
          max = [tmp,max].max()
        end
    
        return max + 1
      end
    
      def to_s
        return "n#{@wert}"
      end
    
    end

    KnotenTest.rb (Test schlägt fehl)
    Code:
    require_relative 'Knoten'
    require 'test/unit'
    
    class KnotenTest < Test::Unit::TestCase
      def setup()
        # n1(n11(n111),n12(n121,n122,n123,n123(n1241)),n13)
        @n1 =  Knoten.new(1)
    
        @n11 =  Knoten.new(11)
        @n12 =  Knoten.new(12)
        @n13 = Knoten.new(13)
    
        @n111 =  Knoten.new(111)
        @n121 =  Knoten.new(121)
        @n122 =  Knoten.new(122)
        @n123 =  Knoten.new(123)
        @n124 =  Knoten.new(124)
    
        @n1241 = Knoten.new(1241)
    
        @n1.add_unterknoten(@n11)
        @n1.add_unterknoten(@n12)
        @n1.add_unterknoten(@n13)
    
        @n11.add_unterknoten(@n111)
    
        @n12.add_unterknoten(@n121)
        @n12.add_unterknoten(@n122)
        @n12.add_unterknoten(@n123)
        @n12.add_unterknoten(@n124)
    
        @n124.add_unterknoten(@n1241)
      end
    
      def test_get_anz_unterknoten()
        assert_equal(@n1.get_anz_unterknoten(), 3, "Falsche Anzahl Subknoten bei #{@n1}")
        assert_equal(@n11.get_anz_unterknoten(), 1, "Falsche Anzahl Subknoten bei #{@n11}")
        assert_equal(@n12.get_anz_unterknoten(), 4, "Falsche Anzahl Subknoten bei #{@n12}")
        assert_equal(@n13.get_anz_unterknoten(), 0, "Falsche Anzahl Subknoten bei #{@n13}")
    
        nTemp = Knoten.new(0)
        assert_equal(nTemp.get_anz_unterknoten(), 0, "Falsche Anzahl Subknoten bei #{nTemp}")
      end
    
      def test_add_unterknoten()
        numUnterknotenVorher = @n1.get_anz_unterknoten()
        @n1.add_unterknoten(Knoten.new(0))
    
        assert_equal(@n1.get_anz_unterknoten(), numUnterknotenVorher + 1, "Falsche Anzahl Subknoten nach Add")
      end
    
      # Hier schlägt's fehl: 
      # => Falsche maximale Tiefe bei n12 festgestellt. 
      # <3> expected but was <6> in `test_get_max_tiefe'
      def test_get_max_tiefe()
        assert_equal(1, @n1241.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n1241} festgestellt")
        assert_equal(2, @n11.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n11} festgestellt")
        assert_equal(3, @n12.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n12} festgestellt")
        assert_equal(4, @n1.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n1} festgestellt")
      end
    end

    Knoten als Objekt (sieht richtig aus):

    Code:
    #<Knoten:0x00000002b68530 @wert=1,
        @unterknoten=[
            #<Knoten:0x00000002b684b8 @wert=11,
                @unterknoten=[#<Knoten:0x00000002b68300 @wert=111,
                    @unterknoten=[]>
                ]>,
            #<Knoten:0x00000002b68418 @wert=12,
                @unterknoten=[#<Knoten:0x00000002b682b0 @wert=121,
                    @unterknoten=[]>,
                #<Knoten:0x00000002b68238 @wert=122,
                    @unterknoten=[]>,
                #<Knoten:0x00000002b68198 @wert=123,
                    @unterknoten=[]>,
                #<Knoten:0x00000002b68058 @wert=124,
                    @unterknoten=[
                        #<Knoten:0x00000002b68008 @wert=1241,
                            @unterknoten=[]>
                    ]>
                ]>,
            #<Knoten:0x00000002b683a0 @wert=13,
                @unterknoten=[]>
        ]>
  2. Mat

    Mat Active Member c-b Experte

    Ja toll.. grad abgeschickt.. Beitrag überflogen.. Fehler gefunden....

    Zeile 20 in Knoten.rb.. richtig wäre:
    Code:
    for knoten in @unterknoten
          tmp = knoten.get_max_tiefe()
          max = [tmp,max].max()
    end
    Anstelle von:
    Code:
    for knoten in @unterknoten
          tmp += knoten.get_max_tiefe()
          max = [tmp,max].max()
    end
    Das nochmal in längerer Schreibweise zu lesen hat geholfen :mauer:

    Hat sich erledigt.. kann weg oder als Mahnmal so stehen bleiben :D