Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Struktogramm Matrix
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Struktogramm Matrix
wolperacer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 07.07.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-07


Hallo zusammen,

ich grüble gerade vor einer Aufgabe, bei welcher ich leider überhaupt nicht durchsteige....
Leider muss ich bis heute eine Antwort haben... doch keiner auch in anderen Foren hat eine Idee.... Vielleicht habe ich hier Glück....

Gegeben sei eine Matrix, deren Felder entweder mit 0 oder 1 belegt sind.
Wir definieren nun einen Einschuss als ein Quadrat aus 1’en. Die obige Matrix enthält zwei Einschüsse. Sie dürfen im Folgenden annehmen, dass Einschüsse sich nicht überlagern und nicht aneinandergrenzen. Schreiben Sie eine Methode als Struktogramm, welche die Anzahl der Einschüsse zählt.

Ich gehe mal davon aus, dass die Felder sich an den Ecken dann auch nicht berühren dürfen. Zumindest nehme ich das jetzt einfach mal an.

Ich würde jetzt erstmal eine Matrix eingeben lassen. Danach suche ich in der ersten Zeile eine 1 und ob danach noch eine kommt. Horizontal müssen genauso viele Einsen wie vertikal sein. Um das ganze herum dürfen nur Nullen sein, oder der Matrixrand. Wenn das so ist, wird der Zähler auf eins gesetzt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 692
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-07


Hallo wolperacer, und herzlich willkommen auf dem Matheplaneten!

Für dieses Problem ein Struktogramm aus dem Stegreif zu schreiben halte ich auch nicht für einfach.

Schreibe zuerst Pseudocode auf Papier und überzeuge dich von seiner Korrektheit. Wenn du dich hier auf die drei Grundstrukturen prozeduraler Programmierung (Sequenz, Selektion, Iteration) beschränkst, dann kannst du das Struktogramm danach erstellen.

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wolperacer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 07.07.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-07


Hallo, das habe ich schon versucht, allerdings komme ich da noch weniger weiter. Ich muss zugeben, dass ich nicht wirklich das Informatikass bin. Das ist bei mir nur n kleines Nebengebiet was ich nie wieder als Maschinenbauer benötige....

muss ich das irgendwie formell hinschreiben oder kann ich als Auswahl auch allgemein schreiben: Überprüfe ob umliegende Felder NULL sind?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 692
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-07-07


2020-07-07 10:25 - wolperacer in Beitrag No. 2 schreibt:
kann ich als Auswahl auch allgemein schreiben: Überprüfe ob umliegende Felder NULL sind?

Das kann ich nicht sagen, weil ich nicht weiß, an welche Programmiersprache sich das Struktogramm anlehnen soll. In C beispielsweise kann man das nicht so einfach.

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27412
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-07-07


Hi wolperacer

Den Anfang hast du doch schon: suche zeilenweise nach der ersten 1.
Die ist dann auf jeden Fall die linke obere Ecke eines Einschusses. Denn so etwas kann laut Vorgabe nicht vorkommen:
1 1 1
0 1 1
Denn das wäre ein Aneinandergrenzen von 2 Einschüssen (1×1 und 2×2).
Es kann auch keine Rechtecke geben, denn das wäre eine Überlagerung von zwei Quadraten, oder im Extremfall zwei benachbarte Quadrate (z.B. 2×4 sind zwei benachbarte 2×2 Quadrate).
Wenn du also eine solche 1 gefunden hast ist sie a) als Einschuß zu zählen und b) der ganze zusammenhängende Block zu löschen (auf 0 setzen; oder auf 2, falls du die Matrix danach wieder in den Ursprungszustand versetzen willst).
Gehe wieder zu Schritt 1 und suche die nächste 1, bis du durch die Matrix durch bist.

Prüfungen auf Rand oder Umgebung sind nicht nötig, da die Vorgaben ungültige Bereiche von 1en ausschließen.
Diagonal berührende Einschüsse sind kein Problem, sie werden auf jeden Fall als 2 Einschüsse gezählt:
1 0 0
0 1 1
0 1 1
Die 1 links oben hängt nicht mit dem anderen Block zusammen. Ein zusammenhängender Block sind alle 1en, die horizontal oder vertikal erreichbar sind. Und das muß immer ein Quadrat (also ein Einschuß) sein, sonst wären die Vorgaben verletzt.

Und dieses Verfahren ist einfach umzusetzen. Entscheidend sind die Vorüberlegungen, was eigentlich nur auftreten kann.

Gruß vom ¼

[Die Antwort wurde nach Beitrag No.2 begonnen.]


-----------------
Bild



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27412
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-07-07


2020-07-07 10:25 - wolperacer in Beitrag No. 2 schreibt:
muss ich das irgendwie formell hinschreiben oder kann ich als Auswahl auch allgemein schreiben: Überprüfe ob umliegende Felder NULL sind?
Ist ja auch nicht nötig, siehe meine Überlegungen im vorigen Post.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wolperacer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 07.07.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-07-07


... siehe Beitrag 7



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wolperacer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 07.07.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-07-07


Das Prinzip ist, dass ich die Matrix Linie um Linie und Spalte um Spalte iteriere
Finde ich eine 1 so gehe ich von dieser Position (posX,posY) nach  rechts bis ich auf eine 0 oder am rechten Rand ankomme. Dies bestimmt die Breite des Quadrats
Dann gehe von der Initialposition (posX,posY) nach unten bis ich auf eine 0 oder am unteren Rand ankomme. Dies bestimmt die Höhe des Quadrats
Nur wenn Breite = Hoehe ist habe ich ein Quadrat (ansonsten ein Rechteck)
Ist dies der Fall, so iteriere ich das Quandrat und zähle die 1 (bei einem 2x2 Quadrat brauche ich 4 Einsen)
Ist die Anzahl Einsen  = Breite * Hoehe so habe ich ein perfekt gefülltes Quadrat



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27412
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-07-07


Anscheinend hast du dich Null die Bohne mit Beitrag #4 beschäftigt.
Oder ihn nicht verstanden.

Mit deinem „Struktogramm“ kann ich nix anfangen. Es enthält ja nicht einmal eine Schleife, um alle Einschußlöcher zu finden.
Hast du es einmal an dem Beispiel aus deinem Eingangspost ausprobiert?

[Die Antwort wurde nach Beitrag No.6 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wolperacer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 07.07.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-07-07


Hat sich wohl überschnitten... siehe Beitrag 7... sorry



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wolperacer
Junior Letzter Besuch: im letzten Monat
Dabei seit: 07.07.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-07-07


Bin mir aber so nicht sicher... Verbesserungsvorschläge?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 692
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-07-08 12:00


2020-07-07 16:17 - wolperacer in Beitrag No. 10 schreibt:
Bin mir aber so nicht sicher... Verbesserungsvorschläge?

Erkläre jedes Element des Struktogramms: warum ist es da, welche Bedeutung haben die verwendeten Variablen, ...

prüfe schrittweise, ob das Struktogramm das tut, was es soll.

Zum Beispiel:
Warum änderst du Einträge in der Matrix?
Du benutzt bspw. die Anweisung "M[x,y]=0".

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27412
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-07-08 12:47


Jetzt sind zwar Schleifen drin.
Aber auch deine if-Bedingungen stellst du mit dem Schleifenkonstrukt dar. Das hattest du in deinem ersten (inzwischen verschwundenen) Struktogramm besser.

Und wie thureduehrsen ebenfalls vorschlägt: spiel das Ding mal durch (nennt sich Schreibtischtest).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
wolperacer wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]