# Streichholrätsel



## aykuzo412 (5. Nov 2020)

Definiere ein geeignetes Format zur Darstellung solcher Streichholzanordnungen im Rechner. Schreibe ein Programm, das zwei in deinem Format vorliegenden Streichholzanordnungen und eine Anzahl umzulegender Streichhölzer als Eingabe nimmt und berechnet, ob das Rätsel lösbar ist. Falls das Rätsel lösbar ist, soll ausgegeben werden, welche Streichhölzer wie umgelegt werden müssen. Wende dein Programm auf die Streichholzrätsel an, die du auf den BWINF-Webseiten findest, und dokumentiere die Ergebnisse.

Könnte jemand vielleicht dazu ein Programm schreiben oder mir helfen ich komme nicht weiter, weiß nicht wie ich anfangen soll.


----------



## AndiE (5. Nov 2020)

Bundeswettbewerb Informatik

Einsendeschluss ist der 23. November. 

Du solltest vielleicht mal konkreter werden, wo du nicht weiterkommst.


----------



## aykuzo412 (5. Nov 2020)

AndiE hat gesagt.:


> Bundeswettbewerb Informatik
> 
> Einsendeschluss ist der 23. November.
> 
> Du solltest vielleicht mal konkreter werden, wo du nicht weiterkommst.


allgemein komm ich nicht klar mit der aufgabe würde helfen wenn jemand mir ein programm schreiben könnte


----------



## thecain (5. Nov 2020)

Und dann gewinnst du? Nicht gerade fair...


----------



## MoxxiManagarm (5. Nov 2020)

aykuzo412 hat gesagt.:


> mit der aufgabe würde helfen wenn jemand mir ein programm schreiben könnte



Das ist keine Hilfe und für einen Wettbewerb schon garnicht. Für einen Wettbewerb gelten die gleichen Regeln wie für Hausaufgaben.


----------



## aykuzo412 (5. Nov 2020)

thecain hat gesagt.:


> Und dann gewinnst du? Nicht gerade fair...


es geht nicht ums gewinnen das wird benotet von der lehrerin und die kann nichts erklären


----------



## White_Fox (5. Nov 2020)

Dann setz dich hin und such dir ein paar Tutorials. Ihr habt doch sicherlich ein Lehrbuch, in dem alles steht was du brauchst.


----------



## aykuzo412 (5. Nov 2020)

White_Fox hat gesagt.:


> Dann setz dich hin und such dir ein paar Tutorials. Ihr habt doch sicherlich ein Lehrbuch, in dem alles steht was du brauchst.


wir haben kein buch das ist doch das problem tutorials gibts auch nicht direkt zu der aufgabe hab ich schon versucht, sonst würde ich nicht hier auf der seite fragen.


----------



## kneitzel (5. Nov 2020)

aykuzo412 hat gesagt.:


> wir haben kein buch das ist doch das problem tutorials gibts auch nicht direkt zu der aufgabe hab ich schon versucht, sonst würde ich nicht hier auf der seite fragen.


Also ich bin gerne bereit, dir das so zu glauben, aber ich habe da massive Probleme:
a) Wie lange habt Ihr schon Unterricht bei der Lehrerin? Was für Stoff hat sie durchgenommen den Du (oder ihr) nicht verstanden hast (habt)?
==> Meine Erwartungshaltung ist da, dass man zeitnah reagiert. Sei es durch Aufarbeiten (Schwer - in der Schule ist eigenständiges Aufarbeiten nicht Standard. So andere es verstanden haben, dann ist evtl. Nachhilfe angesagt ... Oder Eltern helfen  ... oder oder oder .... Wenn die Klasse generell etwas nicht verstanden hat, dann ist die Situation ggf. über die Eltern zu eskalieren...)
b) Mittel gibt es genug! Bücher oder Tutorials kann man finden. Man kann zeitig nachfragen. Dann wird z.B. auch hier im Forum etwas erläutert.

Jetzt von anderen die Aufgabe erledigen zu lassen löst nicht das Problem. Das machen wir hier in der Regel auch nicht. Aber ggf, gegen Bezahlung macht es doch noch einer - wobei das aus meiner Sicht Betrug ist, denn Du gibst fremde Leistung als Deine aus.

Ich würde Dir gerne helfen und das eine oder andere Erläutern. Aber da wäre dann wichtig zu verstehen, wo es hakt. Da sehe ich aber jetzt keinen Punkt, an dem ich ansetzen könnte.


----------



## MoxxiManagarm (5. Nov 2020)

kneitzel hat gesagt.:


> a) Wie lange habt Ihr schon Unterricht bei der Lehrerin? Was für Stoff hat sie durchgenommen den Du (oder ihr) nicht verstanden hast (habt)?



Ich glaube nicht, dass das damit was zu tun hat. Es ist ein Bundeswettbewerb, da geht es nicht unbedingt darum was man in der Schule hatte, sondern auch darüber hinaus. Ich habe früher in der Schule oft an Mathewettbewerben teilgenommen. Da ging es nur bedingt darum die richtige Lösung zu finden, sondern vorallem auch um den Weg. Ein Weg bei dieser Aufgabe hier ist vorallem schon das Format (und möglichst eine Begründung zu der Wahl). Im ein Format vorzuschlagen wäre also eigentlich schon zu viel.


----------



## kneitzel (5. Nov 2020)

MoxxiManagarm hat gesagt.:


> Ich glaube nicht, dass das damit was zu tun hat. Es ist ein Bundeswettbewerb, da geht es nicht unbedingt darum was man in der Schule hatte, sondern auch darüber hinaus. Ich habe früher in der Schule oft an Mathewettbewerben teilgenommen. Da ging es nur bedingt darum die richtige Lösung zu finden, sondern vorallem auch um den Weg. Ein Weg bei dieser Aufgabe hier ist vorallem schon das Format (und möglichst eine Begründung zu der Wahl). Im ein Format vorzuschlagen wäre also eigentlich schon zu viel.


Aber die Aussage war ja, dass es eine bewertete Aufgabe sein soll ("das wird benotet von der lehrerin"). Somit ist es wohl etwas, das die Lehrerin gesehen hat und es als gute Aufgabe zur Bewertung des Lehrstoffes gesehen hat.

Das Format ist ggf. schon halb vorgegeben, denn es ist ja gesagt, dass man da etwas herunter laden soll. ("Wende dein Programm auf die Streichholzrätsel an, die du auf den BWINF-Webseiten findest"). Wenn man sich das Dateiformat anschaut, dann wird man daraus ggf. ein Format für das Programm ableiten können.

Also was ich als Hilfe geben kann an der Stelle wäre:
- Die angegebenen Rätsel herunter laden und das Format anschauen.
- Diese Vorgaben erst einmal laden -> Die erste Datenstruktur ergibt sich dann aus den Dateien

Dann hat man erst einmal einen ersten Schritt. Dann würde ich Schritt für Schritt vorgehen:
- Man hat ja zwei Abbildungen: Wie kann man entscheiden, ob durch umlegen von Streichhölzern aus einem Abbild das andere Abbild erzeugt werden kann? Was muss da erfüllt sein?
- Dann müsste man sich allgemein überlegen, was man denn machen könnte, um heraus zu finden, wie viele Streichhölzer mindestens umgelegt werden müssten. Wenn man sich die Abbilder auf einer Folie aufmalt - dann könnte man beim manuellen Prüfungen ja die Folien aufeinander legen um dann eine Position zu finden, bei der es möglichst viele Übereinstimmungen gibt.... 

Damit wäre ein Vorgehen kurz erläutert ...


----------



## MoxxiManagarm (5. Nov 2020)

kneitzel hat gesagt.:


> Aber die Aussage war ja, dass es eine bewertete Aufgabe sein soll ("das wird benotet von der lehrerin"). Somit ist es wohl etwas, das die Lehrerin gesehen hat und es als gute Aufgabe zur Bewertung des Lehrstoffes gesehen hat.



Du hast recht, das hatte ich überlesen


----------



## kneitzel (5. Nov 2020)

MoxxiManagarm hat gesagt.:


> Du hast recht, das hatte ich überlesen


Wobei ich das irgendwie für unwahrscheinlich halte ... Das ist halt nicht wirklich eine Aufgabe für alle Schüler. Das sind halt Wettbewerbe, wo sich die guten Schüler messen sollen ... Mittelmäßige und schlechte Schüler wird es aber auch in einer Klasse geben, daher ist das eher keine Hausaufgabe, die sich benoten lässt. Aber darüber nachzudenken oder gar zu spekulieren führt ja zu nichts. Ich will nur sagen, dass ich durchaus auch Deine Position teile oder zumindest nicht für falsch erachte - trotz der Textstelle 

Edit: "Wobei ich das irgendwie für unwahrscheinlich halte" -> das "das" bezieht sich nicht auf Dein Zitat sondern auf den vermutlichen Wahrheitsgehalt der überlesenen Textstelle. (Was Du gelesen hast oder nicht kann ich ja nicht wissen und da werde ich deine Aussage natürlich nicht anzweifeln!)


----------



## aykuzo412 (5. Nov 2020)

kneitzel hat gesagt.:


> Wobei ich das irgendwie für unwahrscheinlich halte ... Das ist halt nicht wirklich eine Aufgabe für alle Schüler. Das sind halt Wettbewerbe, wo sich die guten Schüler messen sollen ... Mittelmäßige und schlechte Schüler wird es aber auch in einer Klasse geben, daher ist das eher keine Hausaufgabe, die sich benoten lässt. Aber darüber nachzudenken oder gar zu spekulieren führt ja zu nichts. Ich will nur sagen, dass ich durchaus auch Deine Position teile oder zumindest nicht für falsch erachte - trotz der Textstelle
> 
> Edit: "Wobei ich das irgendwie für unwahrscheinlich halte" -> das "das" bezieht sich nicht auf Dein Zitat sondern auf den vermutlichen Wahrheitsgehalt der überlesenen Textstelle. (Was Du gelesen hast oder nicht kann ich ja nicht wissen und da werde ich deine Aussage natürlich nicht anzweifeln!)


Ja das ist ein wettbewerb aber unsere schule nimmt an der nicht teil. Es gibt unegfähr 10 aufgaben wo alle schüler sich raussuchen sollen welche sie bearbeiten müssen. Aber das problem ist das wir das schon seit 4-5 schulstunden durchnehmen und keiner aus der klasse kriegt es hin ein programm zu schreiben. Wenn meine eltern mir helfen könnten würde ich ja auch nicht hier fragen und informatik ist bei mir nur ein nebenfach, das heißt das ich irgendwie versuchen will eine 04 zu bekommen oder noch besser. Klar ist das dann nicht mein programm und meine leistung, aber habe keine zeit für eine nachhilfe weil ich nebenbei nach der schule ein minijob habe und schon nachhilfe in anderen fächern habe. Mir gehts nicht drum irgendwie oder irgendwo zu gewinnen sondern nur um meine note. Das thema wird auch niewieder dran kommen weil ich informatik nach dem jahr abwähle einfach nur aus dem grund weil ichs nicht kann und leider auch keine zeit habe nach der schule mich damit zu befassen. Da bleibt mir nur die zeit in der schule, wo ich diese aufgaben bearbeiten kann, doch ich weiß nicht wie ich das programmieren soll. Bin ja nicht der einzige aus der klasse. Manche machen das dann zu hause mit ihren eltern und manche interessiert die note einfach nicht weils ein nebenfach ist. Die machen dann im Unterricht nichts außer am handy zu sitzen und im internet zu surfen. Mir ist die note nicht egal weil ich dieses jahr einen guten schnitt brauche für eine Ausbildung. Deshalb wäre es sehr hilfreich wenn ich jemanden finde der mir das schreibt und ich das abgebe und die sache niemals wieder mehr brauche.
Lg


----------



## aykuzo412 (5. Nov 2020)

kneitzel hat gesagt.:


> Also ich bin gerne bereit, dir das so zu glauben, aber ich habe da massive Probleme:
> a) Wie lange habt Ihr schon Unterricht bei der Lehrerin? Was für Stoff hat sie durchgenommen den Du (oder ihr) nicht verstanden hast (habt)?
> ==> Meine Erwartungshaltung ist da, dass man zeitnah reagiert. Sei es durch Aufarbeiten (Schwer - in der Schule ist eigenständiges Aufarbeiten nicht Standard. So andere es verstanden haben, dann ist evtl. Nachhilfe angesagt ... Oder Eltern helfen  ... oder oder oder .... Wenn die Klasse generell etwas nicht verstanden hat, dann ist die Situation ggf. über die Eltern zu eskalieren...)
> b) Mittel gibt es genug! Bücher oder Tutorials kann man finden. Man kann zeitig nachfragen. Dann wird z.B. auch hier im Forum etwas erläutert.
> ...


Ich bin mir sicher das es hier auch welche gibt die das kostenlos machen nur um zu helfen. Ich bin nicht bereit für ein nebenfach was ich sowieso abwählen werde zu bezahlen.
Dafür bezahlen schon meine eltern mathe und französisch.


----------



## aykuzo412 (5. Nov 2020)

aykuzo412 hat gesagt.:


> Ich bin mir sicher das es hier auch welche gibt die das kostenlos machen nur um zu helfen. Ich bin nicht bereit für ein nebenfach was ich sowieso abwählen werde zu bezahlen.
> Dafür bezahlen schon meine eltern mathe und französisch.


Trotzdem danke für die rückmeldung.<3


----------



## MoxxiManagarm (5. Nov 2020)

aykuzo412 hat gesagt.:


> Es gibt unegfähr 10 aufgaben wo alle schüler sich raussuchen sollen welche sie bearbeiten müssen.


Das verstehe ich jetzt aber so, dass du dir eine Aufgabe von den 10 raussuchen kannst. Warum dann ausgerechnet diese? Mein persönlicher Favorit wäre ja Tobis Tunier, wenn ich mir etwas aussuchen dürfte


----------



## White_Fox (5. Nov 2020)

Wie jetzt...ich dachte daß ist eine benotete Aufgabe? Jetzt ein schulinterner Wettbewerb (an den ich ehrlich gesagt noch viel weniger glaube)?

Edit:
Und jetzt doch nur ein Nebenfach, daß du abwählen willst?

So langsam verstehe ich, wie 100k-Programmierer arbeiten...


----------



## aykuzo412 (5. Nov 2020)

kneitzel hat gesagt.:


> Also ich bin gerne bereit, dir das so zu glauben, aber ich habe da massive Probleme:
> a) Wie lange habt Ihr schon Unterricht bei der Lehrerin? Was für Stoff hat sie durchgenommen den Du (oder ihr) nicht verstanden hast (habt)?
> ==> Meine Erwartungshaltung ist da, dass man zeitnah reagiert. Sei es durch Aufarbeiten (Schwer - in der Schule ist eigenständiges Aufarbeiten nicht Standard. So andere es verstanden haben, dann ist evtl. Nachhilfe angesagt ... Oder Eltern helfen  ... oder oder oder .... Wenn die Klasse generell etwas nicht verstanden hat, dann ist die Situation ggf. über die Eltern zu eskalieren...)
> b) Mittel gibt es genug! Bücher oder Tutorials kann man finden. Man kann zeitig nachfragen. Dann wird z.B. auch hier im Forum etwas erläutert.
> ...


Ich habe die lehrerin seit der 5 klassen, das heißt ich verstehe in informatik vieles nicht wie zb java-programmierung. Bin jetzt in der 10ten klasse. Man hat halt informatik immer vernachlässigt weils irgendwie immer für eine 4 gereicht hat auf dem zeugniss. Es war aber schon damals klar das ich informatik aufjedenfall abwählen werde.


----------



## kneitzel (5. Nov 2020)

Ich kann die Situation durchaus verstehen, aber ich fürchte, dass Deine Hoffnung auf "Das schreibt mir jemand" hier aufgehen werden.

Der Ansatz der Meisten hier ist nun einmal, dass wir gerne helfen, wenn jemand etwas lernen / verstehen will. Aber nur Hausaufgaben für jemanden anderes erledigen - das schließe ich für mich aus und so sehen es wohl die Meisten....



White_Fox hat gesagt.:


> Wie jetzt...ich dachte daß ist eine benotete Aufgabe? Jetzt ein schulinterner Wettbewerb (an den ich ehrlich gesagt noch viel weniger glaube)?


Nein, die Schule nimmt nicht teil (wobei das doch eigentlich etwas ist, wo generell Schüler teilnehmen können ... Also unabhängig davon, ob die Lehrer da mitmachen oder nicht... Aber egal ...) und die Lehrerin nimmt das wohl als Vorlage, damit die Schüler beschäftigt sind.... So verstehe ich das jetzt.



aykuzo412 hat gesagt.:


> Ich habe die lehrerin seit der 5 klassen, das heißt ich verstehe in informatik vieles nicht wie zb java-programmierung. Bin jetzt in der 10ten klasse. Man hat halt informatik immer vernachlässigt weils irgendwie immer für eine 4 gereicht hat auf dem zeugniss. Es war aber schon damals klar das ich informatik aufjedenfall abwählen werde.


Dann ist klar, dass die Grundlagen massiv fehlen. Eine 4 lässt sich so auf Dauer nicht halten, da ja vieles aufeinander aufbaut. Und wenn die Grundlagen schon fehlen, dann ist das nachfolgende nicht zu schaffen. Daher ist Dein Ansatz auch der einzig machbare aus meiner Sicht: Eine ganze Lösung müsste geliefert werden - die ganzen fehlenden Grundlagen wird man hier nicht im Forum aufarbeiten können .... Nur eben fürchte ich, dass Du diese Hilfe hier auch nicht bekommen wirst...


----------



## aykuzo412 (5. Nov 2020)

kneitzel hat gesagt.:


> Ich kann die Situation durchaus verstehen, aber ich fürchte, dass Deine Hoffnung auf "Das schreibt mir jemand" hier aufgehen werden.
> 
> Der Ansatz der Meisten hier ist nun einmal, dass wir gerne helfen, wenn jemand etwas lernen / verstehen will. Aber nur Hausaufgaben für jemanden anderes erledigen - das schließe ich für mich aus und so sehen es wohl die Meisten....
> 
> ...


Trotzdem danke


----------



## White_Fox (5. Nov 2020)

kneitzel hat gesagt.:


> Nein, die Schule nimmt nicht teil (wobei das doch eigentlich etwas ist, wo generell Schüler teilnehmen können ... Also unabhängig davon, ob die Lehrer da mitmachen oder nicht... Aber egal ...) und die Lehrerin nimmt das wohl als Vorlage, damit die Schüler beschäftigt sind.... So verstehe ich das jetzt.


So habe ich das anfangs auch verstanden, allerdings hat mich #14 etwas verwirrt...ok, vielleicht hab ich seine Äußerungen auch mißverstanden, dann entschuldige ich mich dafür.

Aber trotzdem: Ich habe mir die ersten Aufgaben gerade mal genauer angesehen, daß ist definitiv kein Schulstoff, da muß man schon etwas überlegen und ich bin mir relativ sicher, daß die meisten Erst- und Zweitsemester in Informatik mit vielen Aufgaben darin durchaus auch zu kämpfen hätten. Und das in der 10. Klasse? Entweder die Lehrerin hat so wirklich gar keine Ahnung von dem was sie da lehren soll, oder wir werden hier von einem Troll gnadenlos verarscht.
Schau dir doch mal die Aufgabe "Baulwürfe" oder das Dreieckspuzzle an.


----------



## kneitzel (5. Nov 2020)

Vollkommen klar. Das Ziel dieses Bundeswettbewerbs ist ja auch, dass die besten Schüler sich da messen sollen. Das ist also etwas, das von Grund auf für die total unterforderten Einser-Schüler gedacht, damit die sich - nach eigener Vertiefung - mit so Themen beschäftigen können...

Also dass da Schüler in der 20ten Klasse keine wirkliche Chance haben, ist klar und gewollt ...


----------



## aykuzo412 (5. Nov 2020)

Ja aber hab mich ja schon für die streichholz aufgabe entschieden kann das jetzt nichtmehr umändern. Würde das sonst machen


----------



## aykuzo412 (5. Nov 2020)

White_Fox hat gesagt.:


> So habe ich das anfangs auch verstanden, allerdings hat mich #14 etwas verwirrt...ok, vielleicht hab ich seine Äußerungen auch mißverstanden, dann entschuldige ich mich dafür.
> 
> Aber trotzdem: Ich habe mir die ersten Aufgaben gerade mal genauer angesehen, daß ist definitiv kein Schulstoff, da muß man schon etwas überlegen und ich bin mir relativ sicher, daß die meisten Erst- und Zweitsemester in Informatik mit vielen Aufgaben darin durchaus auch zu kämpfen hätten. Und das in der 10. Klasse? Entweder die Lehrerin hat so wirklich gar keine Ahnung von dem was sie da lehren soll, oder wir werden hier von einem Troll gnadenlos verarscht.
> Schau dir doch mal die Aufgabe "Baulwürfe" oder das Dreieckspuzzle an.


Nein ist keine verarsche bin in der 10ten klasse und die lehrerin hat wirklich keine ahnung davon was sie unterrichtet


----------



## White_Fox (5. Nov 2020)

Ok...dann anders: Wenn ich dich richtig verstanden habe, hast du seit 5 Jahren Informatik in der Schule.

Wie würdest du ein Streichholz überhaupt darstellen? Schreib doch mal ein paar Gedanken dazu auf, so ein bisschen was muß doch hängen geblieben sein. Vielleicht kriegen wir dich ja in die richtige Richtung geschubst...


----------



## aykuzo412 (5. Nov 2020)

White_Fox hat gesagt.:


> Ok...dann anders: Wenn ich dich richtig verstanden habe, hast du seit 5 Jahren Informatik in der Schule.
> 
> Wie würdest du ein Streichholz überhaupt darstellen? Schreib doch mal ein paar Gedanken dazu auf, so ein bisschen was muß doch hängen geblieben sein. Vielleicht kriegen wir dich ja in die richtige Richtung geschubst...


Hab bisher im unterricht nur aufgeschrieben wie die streichhölzer liegen könnten. Also wie viel grad usw... und das die gradanzahlen als zahl angegeben werden also 30grad=1 60grad=2 90grad=3 usw bis 330grad mehr hab ich nicht hinbekommen....


----------



## aykuzo412 (5. Nov 2020)

aykuzo412 hat gesagt.:


> Hab bisher im unterricht nur aufgeschrieben wie die streichhölzer liegen könnten. Also wie viel grad usw... und das die gradanzahlen als zahl angegeben werden also 30grad=1 60grad=2 90grad=3 usw bis 330grad mehr hab ich nicht hinbekommen....


Ja hab jtz seit 5 jahren informatik am Gymnasium und das was die lehrerin mir in den 5 jahren beigebracht hat ist wie ich die ersten 3 zeilen von einem programm anzufangen hab.


----------



## White_Fox (5. Nov 2020)

aykuzo412 hat gesagt.:


> Hab bisher im unterricht nur aufgeschrieben wie die streichhölzer liegen könnten. Also wie viel grad usw... und das die gradanzahlen als zahl angegeben werden also 30grad=1 60grad=2 90grad=3 usw bis 330grad mehr hab ich nicht hinbekommen....


Naja...immerhin. Dazu erstmal der erste Schubser:
Du könntest jetzt 30°, 60° und 90° darstellen. Kriegst du auch beliebige Winkel hin?

Und wie siehts mit 30,3° aus? Wie könntest du so etwas noch in deine Lösung einbauen?


----------



## kneitzel (5. Nov 2020)

Die Winkel sind ja vorgegeben. Dadurch kann man das tatsächlich einfach als eine Verkettung angeben. Dann hat man ein Streichholz, welches einen Winkel hat und verbundene Streichhölzer.

Das geht prinzipiell. Damit hat man dann eine Representation.

Aber um gleich liegende Streichhölzer zu finden, muss man erkennen, welche Streichhölzer gleich liegen, Da könnte es also helfen, Positionen zumindest ermitteln zu können. Beispiel:

Streichholz gerade, dann geht es schräg hoch, dann wieder schräg runter und wieder ein gerades Streichholz.
Das Ziel ist gleich, nur eben geht es nicht hoch sondern runter. Die beiden geraden Streichhölzer sind also auf der gleichen Position. Das muss auch erkannt werden.

Da muss man sich also überlegen, wie man das macht.... Durch die Begrenzung auf jeweils 30° hat man das etwas vereinfacht. Dadurch hat man Bewegungen in x bzw y Richtung von 0, 0,5, 0,866 oder 1, also (0/1), (0,5/0,866), (0,866/0,5), (1/0) wenn man nur einen Sektor betrachtet. Das natürlich beliebig gespiegelt also auch alles mit - oder eben nicht dabei. Und Angabe in Streichholzlängen. Also wenn ich ein Streichholz in 30° hinlege, dann geht es in eine Richtung um 0,86 Streichholzlängen und in die andere Richtung um 0,5 Streichholzlängen.

Oder anders ausgedrückt: Dreieck mit Seitenlänge 1, 0,5 und 0,86 ist ein rechtwinklinges Dreieck mit den beiden anderen Winkeln: 30° und 60°.
Die 0,866 ist natürlich nur ein Näherungswert. sin(60°) ist 0,86602540378443864676372317075294....

Ich würde Koordinaten angeben als Menge an 0,5er und 0,866er Schritte. Damit hat man dann Punkte, deren x und y Koordinate immer als zwei int Werte dargestellt werden. Dadurch vermeidet man Ungenauigkeiten bei Double Werten und man kann diese Punkte gut erfassen.

Dann hat man also zwei Darstellungen.
Eine Darstellung ist eine Menge von Punkten, deren Koordinaten (und Winkel) ich wie oben beschrieben speichere.
Eine Darstellung kann ich verschieben. Ich kann also die Position jedes Streichholz einer Darstellung so verändern, dass ein gewähltes Streichholz einen bestimmten Anfangspunkt hat.
Dann kann ich also einfach hin gehen und für jedes Streichholz der ersten Darstellung hin gehen und:
- Jedes Streichholz der zweiten Darstellung prüfen, ob es die gleiche Lage hat. Ist dies der Fall, dann verschiebe ich die zweite Darstellung, so dass das verglichene Streichholz die gleiche Position hat.
--> Dann prüfe ich für jedes Streichholz der ersten Darstellung, ob es ein Streichholz mit der gleichen Position und Lage in der zweiten Darstellung gibt. (Achtung - die Richtung ist egal! Also entweder beim Vergleich beide Fälle betrachten oder einfach alle Lagen standardisieren, d.h. es wird beim einlesen direkt verändert. Also wenn nur der Winkel 0° erlaubt ist, dann wird beim Winkel 180° das Streichholz sozusagen direkt gedreht.)
--> So habe ich nun eine Summe an übereinstimmenden Streichhölzern.

Und ich merke mir in der äußeren Schleife das Maximum der übereinstimmenden Streichhölzer.

Das Ergebnis ist dann: n - maximum der übereinstimmenden Streichhölzer, d.h. es können das gefundene Maximum an Streichhölzern beibehalten werden und die übrigen (n-maximum) Streichhölzer müssen bewegt werden.

Damit haben wir natürlich auch ein Kriterium: Die Anzahl der Streichhölzer muss gleich sein. Falls wegnehmen erlaubt ist, dann muss die Anzahl der Streichhölzer im ersten größer gleich sein und n oben bezieht sich dann auf das erste (original) Bild.

Aber damit sind wir bei einer Betrachtung, die der TE so als solche nicht erfassen kann fürchte ich... Aber das ist evtl. ein Text, den er der Lehrerin um die Ohren hauen kann


----------



## MoxxiManagarm (5. Nov 2020)

kneitzel hat gesagt.:


> Dann prüfe ich für jedes Streichholz der ersten Darstellung, ob es ein Streichholz mit der gleichen Position und Lage in der zweiten Darstellung gibt.


Woran machst du den Ursprung des Koordinatensystems fest, damit du die Position vergleichen kannst? Alleine im unteren Beispiel wird das äußerst schwierig. Eventuell würde es für das Beispiel Sinn machen eine Knotengewichtung (die Mitte hat die meisten Streichholzenden) als Ursprung zu nehmen, allerdings gibt es auch genügend andere Beispiele wo das wiederum ungünstig ist.



kneitzel hat gesagt.:


> Die 0,866 ist natürlich nur ein Näherungswert. sin(60°) ist 0,86602540378443864676372317075294....



Würde persönlich eher mit einer Streichholzläge 2 rechnen. Dann hat man ein Vielfaches von 1 und √3. Dein Wert ist √0.75. Könnte man auch machen, siehe aber unschöner aus ;-)


----------



## kneitzel (5. Nov 2020)

MoxxiManagarm hat gesagt.:


> Woran machst du den Ursprung des Koordinatensystems fest, damit du die Position vergleichen kannst?


Du nimmst einfach ein beliebiges Streichholz, dass bei 0,0 startet. Da Du ja generell ständig transformierst ist es egal.



MoxxiManagarm hat gesagt.:


> Würde persönlich eher mit einer Streichholzläge 2 rechnen.



Nunja - das ist naheliegend, damit man die 0,5er Schritte los wird und den Wert in ein int packen kann. Ansonsten wird es sehr schwer, das in zwei int Zahlen zu merken. Spätestens an der Stelle würde man bei der Implementierung das entsprechend anpassen.


----------



## MoxxiManagarm (5. Nov 2020)

Weiß nicht, finde das nachwievor sehr umständlich, obwohl umständlich vermutlich auf ziemlich alle Ansätze zutrifft. Ich hatte ganz am Anfang noch eine Baumstruktur im Sinn, bei dem man in beiden Bildern sinnvoll einen Root definiert und dann Kinder umhängt und so. Was wirklich am besten ist - ka, denn ich muss zugeben, dass ich die Aufgabe von allen aus dem Wettbewerb am herausfordernsten finde. Die Wahl auf die Aufgabe war echt sehr unglücklich


----------



## kneitzel (5. Nov 2020)

Mir gefällt das eigentlich ganz gut. Was blöd ist, ist die Komplexität O(n^2).
Baumstruktur wird schwierig, denn Du musst zum einen auf Kreise aufpassen und du musst natürlich erkennen, wenn zwei Streichhölzer gleich liegen relativ zueinander. Das wäre ja das Beispiel mit den zwei Wegen die zu einem Streichholz führen würden, also z.B. einmal als "Dach" und einmal nach unten....

Aber wir haben noch eine Komplexität vergessen: Was ist mit gedrehten Figuren? Also ich lege ein Quadrat mit erstem Streichholz 0°: ist es die Gleiche Figur wie ein Quadrat, welches um 30° gedreht wurde? Das ist ja sozusagen die gleiche Figur nur eben aus einem anderen Blickwinkel!
Sprich: Was ist da die Lösung? 0 Streichhölzer müssen bewegt werden oder 4 Streichhölzer müssen bewegt werden?

Das ist aber bei mir auch abdeckbar - dann hat man nur eben eine weitere Schleife und die zweite Figur wird 6 mal um 30° gedreht und ggf. die Winkel angepasst, so man nur 6 Winkel erlaubt hat ... also wenn beim Drehen ein Winkel auf 180° gesetzt wurde, dann muss er auf 0° gesetzt werden ...


----------



## AndiE (5. Nov 2020)

Ich würde das anders machen:

Ein Streichholz hat die Ausrichtung:  0 bis 5 ( 0 bis 180 grad), gemessen an der vorderen Tischkante

Ein stehendes Dreiecke besteht also aus drei Streichhölzern mit den Richtungen a=0, b=2,c=4

Nun würde ich die Punkte an denen sich zwei Streichhölzer Treffen als Knoten bezeichnen und damit a=S(A,B), B=S(A,C), c=S(C,B)

was bedeutet, dass die Strecke a in Richtung 0 zwischen den Punkten A und B verläuft.

Macht man es sich einfach, benutzt man für beide Darstellungen, die gleichen Bezeichnungen für die Knoten also würde im Beispiel der Sternknozen einmal 8 Mal in den Beschreibungen der Streichhölzer auftauchen und einmal 12 Mal. Das scheint nicht verboten zu sein.


----------



## White_Fox (5. Nov 2020)

Wie wäre es, wenn man stattdessen ein kartesisches Koordinatensystem nimmt und nur die Koordinaten des Anfangs- und des Endpunkts eines Streichholz berücksichtigt? Dann würde sich die Lage von selbst ergeben.
Als Normal wird die Achse aus Westen in Richtung Osten bzw. die Abszissenachse aus dem negativen in Richtung des positiven Bereichs definiert, Drehung im mathematischen Drehsinn, d.h. alle Winkel sind relativ dazu. Beispiele: 0° -> Das Streichholz liegt genau horizintal mit Köpfchen rechts, 90° -> das Streichholz liegt vertikal mit Köpfchen oben, ...

Das hätte einerseits den Vorteil, daß sich direkt aus den Lagekoordinaten heraus ergibt, ob zwei Hölzchen zusammenliegen und wenn ja, wo.

Oder, noch eine Mögilchkeit: Streichhölzer werden als Vektorgleichungen behandelt, also Stützvektor und Richtungsvektor. Das hatte ich allerdings erst im Abitur, und noch nicht in der 10. Klasse.

Aber wie auch immer, ich denke der Thread reicht aus daß @aykuzo412 den ausdrucken und seiner Lehrerin auf den Tisch knallen kann.


----------



## kneitzel (5. Nov 2020)

Vor allem all diese Ideen vom Prinzip her zu verstehen und dann vor zu tragen sollte auch ohne Umsetzung hoffentlich seine gewünschte 4 ergeben .... jetzt muss er vom Prinzip her nur verstanden haben, was wir so alles gesagt haben ...


----------



## White_Fox (5. Nov 2020)

Wenn er das hinkriegt hat er aber deutlich mehr als nur eine vier verdient - immerhin muß er dazu nicht gerade wenig Stoff aus dem Matheunterricht vorrausgreifen.



kneitzel hat gesagt.:


> jetzt muss er vom Prinzip her nur verstanden haben, was wir so alles gesagt haben ...


Und gerade das wird einem in der Schule am allerwenigsten beigebracht. Eigentlich ist es geradezu verpönt...

Hier hat doch vor einiger Zeit mal eine Lehrerin ein paar Sachen über Informatik angefragt...ich will nicht behaupten daß es in Deutschland keinen einzigen Informatiklehrer gibt, der diese Aufgaben nicht beurteilen und einschätzen könnte. Aber die Wahrscheinlichkeit, daß die Lehrerin von @aykuzo412 das kann dürfte nahe bei null sein. Sehr nahe. (Ohne damit einem Lehrer zu nahe treten zu wollen, diese Aufgaben sind wirklich kein Schulstoff mehr und insofern außerhalb seiner Aufgabe. Sind ja auch nur Menschen...)


----------



## mihe7 (6. Nov 2020)

"Ein Streichholzrätsel besteht darin, dass man ausgehend von einer zusammenhängenden Anordnung von Streichhölzern auf einem Tisch durch das Umlegen einer bestimmten Anzahl von Streichhölzern zu einer anderen zusammenhängenden Anordnung gelangen soll."

Da Streichhölzer umgelegt werden sollen, verändern die anderen ihre Position nicht. Damit wird die Aufgabe trivial: Hölzchen, die in beiden Figuren die gleichen Endpunkte haben, weden aus beiden Figuren entfernt. Dann bleiben in den Figuren k und m Hölzchen übrig. Ist k != m, ist das Rätsel nicht lösbar ansonsten müssen k Hölzchen umgelegt werden, die Zuordnung ist egal. Laufzeit O(n)


----------



## kneitzel (6. Nov 2020)

Das setzt aber voraus, dass die Vorgaben feste Orte haben. Es sind aber nach meiner Auffassung nur Muster, die nicht ortsfest sind.
Aber ja: wenn man es so vereinfacht, dann wird es trivial.


----------



## mihe7 (6. Nov 2020)

kneitzel hat gesagt.:


> Das setzt aber voraus, dass die Vorgaben feste Orte haben. Es sind aber nach meiner Auffassung nur Muster, die nicht ortsfest sind.
> Aber ja: wenn man es so vereinfacht, dann wird es trivial.


----------



## White_Fox (6. Nov 2020)

kneitzel hat gesagt.:


> Das setzt aber voraus, dass die Vorgaben feste Orte haben. Es sind aber nach meiner Auffassung nur Muster, die nicht ortsfest sind.
> Aber ja: wenn man es so vereinfacht, dann wird es trivial.


Richtig. Ich hab erstmal überlegt wie das Rätsel überhaupt zu lösen sei und hab ein paar Minuten gegrübelt, weil daß ja so nicht gehen kann...weil ich genau das gemacht habe, was mihe7 vorgeschlagen hat - allerdings den Bezugspunkt falsch gewählt habe.


----------



## mihe7 (6. Nov 2020)

White_Fox hat gesagt.:


> Richtig. Ich hab erstmal überlegt wie das Rätsel überhaupt zu lösen sei und hab ein paar Minuten gegrübelt, weil daß ja so nicht gehen kann...weil ich genau das gemacht habe, was mihe7 vorgeschlagen hat - allerdings den Bezugspunkt falsch gewählt habe.


ROFL. Was gehen würde - dann natürlich in quadratischer Lauzeit: das Verfahren für jeden Endpunkt des Zielgraphen wiederholen, wobei der Ausgangsgraph vorher in den betreffenden Endpunkt verschoben wird.


----------



## kneitzel (6. Nov 2020)

mihe7 hat gesagt.:


> ROFL. Was gehen würde - dann natürlich in quadratischer Lauzeit: das Verfahren für jeden Endpunkt des Zielgraphen wiederholen, wobei der Ausgangsgraph vorher in den betreffenden Endpunkt verschoben wird.


Genau, das war auch mein Ansatz. Wobei die Frage ist: Wenn das nur ein Muster ist, dann kann man das ja nicht nur verschieben sondern auch drehen. Das ändert dann aber nur einen Faktor und es bleibt somit bei O(n^2)...


----------



## mihe7 (6. Nov 2020)

kneitzel hat gesagt.:


> Genau, das war auch mein Ansatz. Wobei die Frage ist: Wenn das nur ein Muster ist, dann kann man das ja nicht nur verschieben sondern auch drehen. Das ändert dann aber nur einen Faktor und es bleibt somit bei O(n^2)...


Wobei hier als Bezugslinie die Tischkante angegeben ist.


----------

