Array Aufgabe lösen, benötige Hilfe

[asadob1]

kann jemanden mir hilfe die Aufgabe hier zu lösen:
entweder mit einer For oder While Schleife und was ist besser. ich bin Anfänger in Programmierung Python

Gegeben ist eine Matrix (zweidimensionales Array), welches nur die Zahlenwerte 0 und 1 enthält
Matrix


Jede 0 in der Matrix steht hierbei für Land und jede 1 für einen Teil eines Flusses. Ein Fluss besteht aus einer beliebigen Anzahl von 1-en, die entweder horizontal oder vertikal benachbart sind. Eine diagonale Nachbarschaft ist ausgeschlossen. Die Anzahl der benachbarten 1-en, die einen Fluss bilden, bestimmt die Länge/ Größe des Flusses.

Beachtet außerdem, dass sich ein Fluss verdrehen und somit um Kurven bewegen kann. Mit anderen Worten, es muss keine gerade vertikale Linie oder eine gerade horizontale Linie sein - es kann zum Beispiel ein L-förmiger Fluss sein
Matrix[ A(0,0)...........A(0,4)
A(1,0) ..
.. ..
.. ..
A(4,0) ...........A(4,4)]

Matrix = [
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]

so soll die Lösung sein:
Array mit den Längen/ Größen der Flüsse = [1,2,2,2,5]
Erklärung:
A(0,3)=1
A(0,0) = 1& A(1,0)=1 --> 2
A(3,0)=1 & A(4,0) = 1 --> 2
A(2,4)=1 & A(3,4)=1-->2
dann haben wir ein L Form --> A(1,2) & A(2,2)& A(3,2)& A(4,2)-->5

Schreibe eine Funktion Python Programmiersprache, die ein Array der Größen aller Flüsse zurückgibt, die in der Eingabematrix dargestellt sind. Die Größen müssen in einer bestimmten Reihenfolge sein

[__deets__]

Wir loesen - nachzulesen gerne in viewtopic.php?f=1&t=23839 - hier nicht Hausaufgaben auf Bestellung. Sondern helfen dir, dein Verstaendnis von Python und der Aufgabe aufzubauen, so das du sie selbst loest.

Was also hast du schon in Python behandelt? Hast du schon mit einem Programm angefangen? Wie wuerdest du das Problem loesen, wenn du mit Bleistift & Papier daran arbeitest?

[asadob1]

ich habe in Python so angefangen, aber nicht weiter gekommen:

a = [
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]
for i in a:
print(a)
if a==1:

aber in andere Sprache
habe ich 2 For schleifen i, j
und wurde so vorgehen:
b[]
for (i =0 , i<5, i++)
for (j=0, j<5, j++)
if a(i,j)==1;
b =b+a(i,j)
if a((i+1),j)==1
b =b+a((i+1),j)
if a(i,(j+1))==1
b=b+a((i,(j+1))

return b[]

so habe ich gedacht soll es gehen von Algorithmus, aber da hört bei auf bei der L Form.

[__deets__]

Wieso denkst du es gaebe keine for-schleifen in Python? Das geht doch genauso.

Code: Alles auswählen

for i in range(5):
     for j in range(5):
            print(i, j)

Algorithmisch greift das aber natuerlich zu kurz. Mit einer festen Anzahl von Tests kann es auch nur eine feste Laenge und Form geben.

Hat euer Lehrer/Dozent euch keinerlei Hinweise zur Loesung gegeben?

[asadob1]

nein die Lösung haben wir es nicht, aber wie kann mit range die Matrix wie oben beschrieben bekommen--> a = [
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]

[__deets__]

Die Frage verstehe ich nicht. Willst du wissen, wie du mit einer Liste (es gibt arrays in Python, aber das ist keines) arbeitest? Das geht mit dem []-Operator, und das steht auch so in jedem Grundlagentutorial. Und habt ihr auch garantiert schon gemacht.

Code: Alles auswählen

a =  [
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]
print(a[0][0])

[Sirius3]

Entweder denke ich zu kompliziert, oder die Aufgabe ist ganz schön heftig. Es gibt ja nicht nur L sondern auch U oder gar R-Flussformen.

Du hast ein zweidimensionales Problem, also brauchst Du auch zwei for-Schleifen.

Code: Alles auswählen

landschaft = [
    [1,0,0,1,0],
    [1,0,1,0,0],
    [0,0,1,0,1],
    [1,0,1,0,1],
    [1,0,1,1,0],
]

for zeile in landschaft:
    for fleck in zeile:
        if fleck == 1:
            print("Fluss")

[__blackjack__]

@Sirius3: Man kann doch durch die Matrix iterieren und Flüssen einfach ”folgen” wenn man einen Endpunkt gefunden hat. Setzt voraus, dass es keine Kreise gibt. Und man muss bereits zugeordnete Flusszellen entsprechend markieren/entfernen. Dann ist das IMHO nicht mehr ganz so schwer. Also zumindest wenn man es in Teilprobleme zerlegt und auf Funktionen aufteilt.

@asadob1: Also doch wieder über Koordinaten iterieren oder den Code von Sirius3 durch `enumerate()` ergänzen. Auf jeden Fall nicht irgendwo einfach die Zahl 5 hinschreiben, denn diese Zahl muss zur Matrix passen, und die sollte man deshalb auch von der gegebenen Matrix *abfragen*. Vermeidet Fehler und erlaubt einfach andere Landschaften mit anderen Grössen zu verwenden, ohne dass man den Code ändern muss.

[__deets__]

Also als rekursive Aufgabe mit Markierung der besuchten Felder finde ich das jetzt nicht so kompliziert.

[asadob1]

a = [
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]
#print(a)
for i in a:
for j in a:
if (a[j])==1:
laenge=(a[j])
if (a[i+1][j])==1:
laenge=(a[i+1][j])
if (a[j+1])==1:
laenge=(a[j+1])
if (a[j-1])==1:
laenge=(a[j-1])
return laenge
ich bekomme aber Fehler in Line if (a[j])==1: TypeError: list indices must be integers or slices, not list

[__deets__]

Bitte benutze die code-tags um deinen code vernuenftig zu formatieren. Das ist der </>-Knopf im vollstaendigen Editor.

Und du laeufst jetzt nicht mit range ueber die Dimension der Liste(n), sondern ueber die Listen selbst. Dann versuchst du mit einer Liste als Index auf eine Liste zuzugreifen. Das geht eben nicht.

[asadob1]

landschaft = [
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]

for zeile in landschaft:
for fleck in zeile:
if fleck == 1:
print("Fluss")

das ist gut aber es wird die länge nicht ermittelt und soriert, es soll aber raus kommen; Laenge = [1,2,2,2,5]
d.h. ein Fluss, 3x 2 Flusse und am Ende L Form 5 Flusse

[Sirius3]

@asadob1: natürlich werden in meinem Code keine Länge ermittelt, den Code poste ich hier ja nicht, weil das ja DEINE Aufgabe ist.
Es soll nur zeigen, wie man über eine zwei-Dimensionale Landschaft mit zwei for-Schleifen iteriert. Und jetzt vergleiche mal meine Schleifen mit Deinen Schleifen und finde den Unterschied.

[asadob1]

gut danke , ich lasse es. es hat mir aber viel gebracht. ich bin ganz neu in Programmierung

[asadob1]

Danke
ich bin ganz neu in der Programmierung,
ich muss noch viel lernen.
aber dein Tipp schaue noch mal und vergleiche die For Schleifen

[__blackjack__]

Als kleiner Hinweis, dass man da nicht zwingend Rekursion zu braucht, und das eine relativ einfache Lösung mit den eher primitiven Möglichkeiten eines klassischen BASICs möglich sind:

Code: Alles auswählen

   10 N=5:RL=0:DIM M(N,N),R(N*N)
   20 FOR I=1 TO N:FOR J=1 TO N:READ M(I,J):NEXT:NEXT
   30 FOR I=1 TO N:FOR J=1 TO N:IF M(I,J) THEN GOSUB 100:NEXT:NEXT
   40 IF RL=0 THEN PRINT"NO RIVERS FOUND.":END
   50 PRINT RL;"RIVERS FOUND:":GOSUB 300:FOR I=0 TO RL-1:PRINT R(I);:NEXT:END
  100 X=I:Y=J
  110 GOSUB 200:IF C>1 THEN RETURN
  120 M(X,Y)=0:R(RL)=R(RL)+1:IF C=0 THEN RL=RL+1:RETURN
  130 X=NX:Y=NY:GOTO 110
  200 C=0:NX=-1:NY=-1
  210 IF X>0 THEN IF M(X-1,Y) THEN C=C+1:NX=X-1:NY=Y
  220 IF X<N THEN IF M(X+1,Y) THEN C=C+1:NX=X+1:NY=Y
  230 IF Y>0 THEN IF M(X,Y-1) THEN C=C+1:NX=X:NY=Y-1
  240 IF Y<N THEN IF M(X,Y+1) THEN C=C+1:NX=X:NY=Y+1
  250 RETURN
  300 F=0:FOR I=0 TO RL-2:IF R(I)>R(I+1) THEN T=R(I):R(I)=R(I+1):R(I+1)=T:F=-1
  310 NEXT:IF F THEN 300
  320 RETURN
20000 DATA 1,0,0,1,0
20010 DATA 1,0,1,0,0
20020 DATA 0,0,1,0,1
20030 DATA 1,0,1,0,1
20040 DATA 1,0,1,1,0

Sogar inklusive sortieren so schnell durchlaufen, dass sich nicht wirklich gelohnt hat eine Zeitmessung einzubauen. Programmlauf:

Code: Alles auswählen

RUN
 5 RIVERS FOUND:
 1  2  2  2  5
READY.

[asadob1]

ich denke das ganze wir noch viel schneller wenn man in eine While Schleife tuet.
ich habe es bis jetzt nicht geschaft, da ich kein Programmierer bin, aber mir geht es nur um Algorithmus.
d.h. while a[j] == 1 dann erstmal den gefundnen wert zu Laenge zuweisen und dann die nachbaren auch über If Abfrage nach rechts und nach unten, aber ich habe hier Schwierigkeiten mit dem L Form.

[asadob1]

sorry ich meine a[j]

Code: Alles auswählen

a=[a[i][j].......a[i][j+1]
[a[i+1][j]..................]

[asadob1]

das habe ich einfach bis jetzt geschaft, mir fehlt noch die Ausgabe der Flüsse in einer liste:
also bei mir werden Fluss 5x mal ausgegeben, jetzt muss die laenge einzelne fluss als summe i+j ausgegeben--> bitte einfache vorgehensweise, da ich kein programmierer bin

Code: Alles auswählen

a = [
    [1,0,0,1,0],
    [1,0,1,0,0],
    [0,0,1,0,1],
    [1,0,1,0,1],
    [1,0,1,1,0],
    ]
print (a)
for i in a:
    for j in a:
        if i== j:
            print("fluss")
            

[__blackjack__]

@asadob1: Das da findet gar keine Flüsse, nicht mal Teile von Flüsse. Schau Dir mal die Ausgabe an wenn garantiert *gar kein* Fluss in `a` enthalten ist:

Code: Alles auswählen

In [98]: a = [ 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...:     [0, 0, 0, 0, 0], 
    ...: ] 
    ...: print(a) 
    ...: for i in a: 
    ...:     for j in a: 
    ...:         if i == j: 
    ...:             print("fluss") 
    ...:                                                                        
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss
fluss

``for``- oder ``while``-Schleife ist nicht primär eine Frage der Geschwindigkeit, sondern welche im gegebenen Fall sinnvoller ist. ``for``-Schleifen verwendet man, wenn man über eine Folge von Elementen von irgendwas iteriert was man entweder schon hat, oder sich leicht erstellen kann. ``while``-Schleifen wenn man eine sinnvolle Abbruchbedingung formulieren kann, oder sich erst *im* Schleifenkörper entscheidet ob man fertig ist und die Schleife abbrechen kann, oder nicht.

Die Aufgabe erfordert mehr als eine Schleife und die müssen auch nicht alle vom gleichen Typ sein, wenn man an einigen Stellen etwas hat über das man iterieren kann und an anderen Stellen etwas solange wiederholen möchte, bis eine bestimmte Bedingung eingetreten ist.

Es wurde ja schon gesagt, dass das keine ganz triviale Aufgabe ist. Aber ganz so komplex ist sie halt auch nicht. Man braucht für eine relativ unkomplizierte Lösung beispielsweise keine Rekursion, sondern kann das mit ein paar Schleifen machen. Also ohne das man sich Rekursion mit einem eigenen Stapel nachprogrammiert oder ähnlich komplex. Ich habe das mit einer Lösung in CBM BASIC ja gezeigt, dass das bei den gegebenen Vorbedingungen mit sehr primitiven Mitteln überschaubar machbar ist.

Von der Komplexität her ist das aber schon so umfangreich, dass ich, insbesondere einem Anfänger, dringend dazu rate das in kleinere Teilprobleme zu zerlegen, und nicht zu versuchen das alles in *ein* tief verschachteltes Schleifenkonstrukt zu schreiben. Die BASIC-Lösung verwendet letztlich drei Schleifenebenen um die Flusslängen zu ermitteln, und das ist auf das Hauptprogramm und zwei Unterprogramme verteilt. Wobei man in Python vielleicht den einen Zeilenblock mit den vier nahezu identischen Inhalten vielleicht auch noch mit einer Schleife ausdrücken würde. Und ich würde da auch mehr als zwei Funktionen schreiben. Also klar, die Unterprogramme in dem BASIC-Programm wären heisse Kandidaten für eigene Funktionen in Python, aber auch das was dort drin gemacht wird, lässt sich noch sinnvoll zerlegen. Der Vorteil ist, dass man damit Codestücken einen Namen geben kann, der beschreibt, was der Code im Kontext der Problemlösung macht. Gerade als Anfänger ist es IMHO gut eher zu viele Funktionen zu definieren und lesbaren und damit verständlichen Code damit zu schreiben. Wenn man fertig ist, kann man die immer noch ”inlinen”. Das ist einfach. Schwieriger ist dagegen bei zu umfangreichem/komplexen/nicht mehr überschaubaren Code anzufangen Teile in Funktionen heraus zu ziehen. Dabei muss man deutlich mehr nachdenken und dabei können deshalb auch mehr Fehler passieren.

Möglicher Grundablauf beim Programmieren ganz allgemein: Problem in Teilprobleme zerlegen. Teilprobleme in kleinere Teilprobleme zerlegen. Solange wiederholen bis man Teilprobleme hat, die sich mit einer Funktion mit wenigen Zeilen Code lösen lassen. Diese Funktion erst testen, ob sie tatsächlich das macht was sie soll bevor man zur nächsten Teillösung/Funktion weitergeht. Es nützt nichts auf ungetesteten oder gar nachweislich nicht funktionierenden Funktionen aufzubauen. Aus funktionierenden Teillösungen lassen sich dann grössere Teillösungen zusammenbauen, bis man am Ende das Gesamtproblem gelöst hat.

Das ganze Schritt für Schritt *entwickeln*. Also nicht alles runterschreiben und *dann* erst das erste mal ausführen, sondern immer mal wieder schauen wie weit das was man hat, der Lösung näher kommt.

Vor alledem musst Du aber erst einmal einen Algorithmus überlegen. In der Regel ohne Rechner, mit Stift und Papier überlegen und an Beispielen durchspielen, wie man das grundsätzlich Lösen und diese Lösung in einer vollständigen und präzisen schriftlichen Anleitung erklären kann. Jemandem der nicht sehr schlau ist, und der sich alles notieren muss, weil er es sonst vergisst. Denn mit dem Programm musst Du das letztlich noch formaler und präziser jemandem beibringen der ultimativ dumm ist und kein Stück selbst denkt: dem Rechner.