Laden...

Gegebene natürliche Zahl in möglichst viele Summanden i+(i+1)+(i+2)+(i+3)+... aufteilen

Erstellt von SilverX vor 9 Jahren Letzter Beitrag vor 9 Jahren 7.482 Views
S
SilverX Themenstarter:in
5 Beiträge seit 2014
vor 9 Jahren
Gegebene natürliche Zahl in möglichst viele Summanden i+(i+1)+(i+2)+(i+3)+... aufteilen

Hallo Devs,

ich habe eine Frage bezüglich eine Aufgabe, die sich in meinem Informatikstudium ergeben hat. Da ich erst im 1. Semester bin und noch sehr wenig über das Programmieren weiß und mir nach Stunden des Kopfzerbrechens immer noch kein Lösungsansatz einfällt, wollte ich hier Tipps einholen - Keine Lösung.

In meiner Aufgabe stehe ich vor folgendem Szenario, dass ich in einen Quellcode übersetzen soll:

Der Nutzer gibt eine beliebige natürliche Zahl ein. Das Programm soll nun die Zahl als Summanden sehen und eine möglichst lange Zahlenfolge ausgeben, die erstens, zusammenaddiert wieder den Summanden ergibt und zweitens, aufeinanderfolgend (n+1) sein muss.

Beispiel:

9

Einerseits: 4+5
Andererseits: 2+3+4

Das Programm soll mir nun die größte Anzahl Summanden, also "2,3,4" ausgeben.

-> Mir stellt sich mir die Frage: Kann man den Algorithmus mittels Schleifen und if-Bedingungen lösen oder benötige ich andere Tools, die ich noch nicht beherrsche?

Mein Problem ist, dass ich Variablen deklarieren muss, die ihren Wert ändern. Ich kann ja nicht n-viele Werte von 1 bis Unendlich deklarieren und jede Zahlenreihe mir ausmalen. Bedeutet, ich benötige ein Schema, das folgendermaßen aussieht:

1+2+3+4+5
Userinput: 9

Wenn 1+2 != 9 || 1+2+3 != 9 || 1+2+3+4 != 9, dann lösche die 1

(Weil keine der drei Rechnungen 9 ergibt und alle weiteren Rechnungen sowieso >9 wären)

Darauf würde folgen:

Wenn 2+3 != 9 || 2+3+4 != 9 -> Lösung gefunden.

Habt Ihr Ideen?
Grüße

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo SilverX,

sei die gegebene Zahl n.

Die Zahl lässt sich in zwei Summanden der beschrieben Art aufteilen, wenn sie ungerade und größer gleich der Summe der ersten zwei natürlichen Zahlen ist. bzw. - was das gleich ist - wenn n-1 durch zwei teilbar ist. Die Summanden ((n-1)/2) und ((n+1)/2). Oder anders formuliert ((n-1)/2) und ((n-1)/2)+1.

Die Zahl lässt sich in drei Summanden aufteilen, wenn sie durch drei teilbar und größer gleich der Summe der ersten drei natürlichen Zahlen ist. Die Summanden sind (n/3-1), (n/3) und (n/3+1). Oder anders formuliert (n/3-1), (n/3-1)+1 und (n/3-1)+2.

Die Zahl lässt sich in vier Summanden aufteilen, wenn n+2 die durch vier teilbar und größer gleich der Summe der ersten fünf natürlichen Zahlen ist. Die Summanden sind ((n-3)/2), ((n-1)/2), ((n+1)/2) und ((n+3)/2). Oder anders formuliert ((n-3)/2), ((n-3)/2)+1, ((n-3)/2)+2 und ((n-3)/2)+3.

Die Zahl lässt sich in fünf Summanden aufteilen, wenn sie durch fünf teilbar und größer gleich der Summe der ersten fünf natürlichen Zahlen ist. Die Summanden sind (n/5-2), (n/5-1), (n/5), (n/5+1) und (n/5+2). Oder anders formuliert (n/5-2), (n/5-2)+1, (n/5-2)+2, (n/5-2)+3 und (n/5-2)+4.

Keine Garantie für die Abwesenheit von Flüchtigkeitsfehlern, aber ich denke, das Muster ist auf jeden Fall klar geworden. Und wenn nicht, dann ist die Richtung aufgezeigt, wie man sich das Muster selbst überlegen kann.

Ob eine Zahl durch eine bestimmte Zahl teilbar ist, kann man mit dem Modulo-Operator testen.

Du musst also eigentlich nur den größten Teiler der von n, n+1, n+2 usw. (bis zu einer gewissen Grenze, die man sich überlegen kann) ermitteln. Dann kannst nach dem Muster den ersten Summanden berechnen. Alle weiteren ergeben sich automatisch durch Addition von jeweils 1 mehr.

Bitte beachte bei etwaigen Rückfragen vorsorglich [Hinweis] Wie poste ich richtig? Punkt 1.1.1

herbivore

2.078 Beiträge seit 2012
vor 9 Jahren

Ich war zu langsam 😄
Gut, dann nur noch eine kleine Ergänzung:

Ich kann ja nicht n-viele Werte von 1 bis Unendlich deklarieren

Doch kannst du, Stichwort Array. Es gibt auch noch andere wichtige Auflistungstypen, wie z.B. List<T>
In den meisten Fällen nutze ich List<T>, weil sie am einfachsten zu nutzen ist.

PS:
Okay, nicht bis unendlich, irgendwann ist der RAM voll, aber ich glaube, so viele Werte wirst du nicht zusammen bekommen. ^^

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo Palladin007,

grundsätzlich richtig, allerdings: Arrays werden für die Aufgabe überhaupt nicht benötigt.

herbivore

C
2.121 Beiträge seit 2010
vor 9 Jahren

Man könnte evtl. was mit der Summenformel anfangen. Die lässt sich auch verallgemeinern, für Zahlen von m bis n.

P
1.090 Beiträge seit 2011
vor 9 Jahren

Wenn ich es noch richtig im Kopf habe kann man die 2er Potenten nicht zerlegen.

Sollte man mal gelesen haben:

Clean Code Developer
Entwurfsmuster
Anti-Pattern

S
SilverX Themenstarter:in
5 Beiträge seit 2014
vor 9 Jahren

Wow. Mit so viel Resonanz habe ich nicht gerechnet. Kenne das von anderen Foren, dass man teilweise Tage auf Antwort warten muss und hier gleich Scharen an Ideen - Genial!

@herbivore: Das hört sich schon sehr logisch an. Werde das morgen gleich mal umsetzen und berichten. Was mich interessiert an deinem Ansatz - Wie hast du ihn hergeleitet? Ist das "logisch" oder sind das Erfahrungswerte / historische Beweise?

@Palladin007: Auch dir schon mal: Danke! Noch versuche ich den unbekannten Arrays aus dem Weg zu gehen, aber das wird sich hoffentlich bald ändern.

@chilic: Bin bei meinen Recherchen auch auf das Gaußsche Verfahren gestoßen, kam da aber nicht direkt zu meinem Problem.

@Palin: Beziehst du dich auf herbivores Ansatz?

189 Beiträge seit 2014
vor 9 Jahren

Hallo SilverX,

quick & dirty würde das mit zwei verschachtelten Schleifen funktionieren. Genauer 3 - eine für die Ausgabe.
Wenn du die gefundene Folge nur ausgeben und nicht irgendwie noch weiterverarbeiten willst, dann kommst du auch mit den ganz einfachen Elementen (und ohne Arrays, Listen, ...) die du beherrschen solltest hin.

Ezio

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo Ezio,

leider ganz und gar keine gute Idee. Und auch vollkommen unnötig.

Hallo SilverX,

bei einer ungeraden Anzahl von Summanden ist es doch recht offensichtlich(). Angefangen bei drei Summanden. Ich finde, da sieht man auf es den ersten Blick. Nennen wir den mittleren Summanden mal j. Dann ergeben sich die Summanden (j-1) , j und (j+1). Jetzt kann man plus eins vom letzten Summanden mit der minus eins vom ersten Summanden verrechnen und bekommt j, j und j. Mit anderen Worten 3j. Da wir jetzt aber von der Summe n (die wie erkannt die Form 3*j haben muss, also durch drei teilbar sein muss) auf die Summanden schließen wollen, sind diese eben j = n/3.

Solange die Anzahl der Summanden ungerade ist, gibt es immer einen mittleren und die rechts und links addierten Konstanten heben sich gegenseitig auf. Wenn wir die Anzahl der Summanden a nennen, kommt man so immer auf einen Durchschnittswert der Summanden von a*j. Die Summe muss sich also durch a teilen lassen, damit die Zerlegung in a Summanden möglich ist.

Wenn man es für ungerade Anzahl von Summanden erstmal verstanden hat, dann sieht man, dass es für gerade Anzahlen von Summanden zwar nicht ganz so schön aufgeht, weil es keinen exakt mittleren Summanden gibt, dass sich aber ein ähnliches Muster finden lässt.

herbivore

(*) Zumindest wenn man weiß, wie Grauß die Formel für die Summe der ersten n natürlichen Zahlen hergeleitet hat. Da hat er aus je zwei Werten auch Paare gebildet, deren Summe mit der Summen aller anderen gebildeten Paare übereinstimmt, so dass das Aufsummieren auf eine einfache Multiplikation des Paarwerts mit der Anzahl der Paare hinauslief. Nicht viel anderes hier im konkreten Fall.

189 Beiträge seit 2014
vor 9 Jahren

Hallo herbivore,
mir ist klar, dass das weder eine schöne noch eine performante Lösung ist. Ich dachte nur, für die Lösung eines kleinen mathematischen Rätsels würde Q&D ausreichend sein, v.a. da es IMHO recht schnell umzusetzen geht.

leider ganz und gar keine gute Idee. Und auch vollkommen unnötig.

Mich würde interessieren, weshalb du das dann aber für eine SO schlechte Idee hältst?! 😃

Ezio

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo Ezio,

darüber, was mit der Übungsaufgabe beabsichtigt ist bzw. beim Lernenden bewirkt werden soll, kann man natürlich geteilter Meinung sein, aber üblicherweise geht es gerade nicht darum, irgendwas quick&dirty zu machen, sondern die Strukturen zu erkennen und damit eine möglichst gute Lösung zu finden. Das ist schon der erste Grund, warum ich deinen Vorschlag ungünstig finde.

Per Schleife einen Wert zu suchen (hier konkret j, wenn a gegeben ist), den man auch direkt ermitteln kann, also so wohl schneller als auch mit weniger Code, ist mein zweiter Kritikpunkt.

Und dann sollte man bei zwei und erst recht mehr geschachtelten Schleifen immer sehr auf der Hut sein, weil das performance-mäßig ganz schnell katastrophal werden kann (gemeint sind Laufzeiten von Minuten, Stunden, Tagen, Monaten, Jahren und mehr, statt Sekundenbuchteilen oder wenigen Sekunden), siehe dazu auch Warum haben WinForms, DataGridView & LINQ eine gute Performance? [==> lineare Aufwandsklasse] und Mergesort langsamer als Bubblesort? [==> Nein, Messfehler / Aufwandsklasse vs. Mikrooptimierungen].

herbivore

1.361 Beiträge seit 2007
vor 9 Jahren

Hey SilverX,

dein eingangs erdachtes Schema scheint mir hier am zielführendsten:

Betrachte ein Intervall von Zahlen (n, n+1, n+2, ..., m) und "verschiebe" es:*Wenn die Summe dieses Intervalls kleiner ist als dein Ziel "Z", dann füge hinten (m+1) an. *Wenn die Summe dieses Intervalls größer ist als dein Ziel "Z", dann entferne vorn (n). *Wenn die Summe dieses Intervalls exakt gleich deinem Ziel "Z" ist, dann merke dir (m-n) als Länge des Intervalls und füge hinten (m+1) an.

Anfangen tust du mit dem leeren Intervall und n=m=0.
Sobald du bei m=Z angelangt bist, kannst du aufhören.
Und immer wenn die Summe gerade Z entspricht, guckst du, ob dies die bisher längste Abfolge ist und speicherst diese Länge.

Glücklicherweise brauchst du das Intervall selbst überhaupt nicht zu speichern.
Denn erstens ist es implizit durch deine momentanen Zahlen n und m gegeben und es genügt darüber hinaus, wenn du lediglich die Summe des Intervalls mitführst.
Die Summe kannst du direkt updaten, indem du m+1 addierst oder n abziehst.

Das ganze kannst du in einer einzigen Schleife implementieren, benötigst nur Addition, Subtraktion und 4 Variablen:
n (Intervallbeginn), m (Intervallende), s (Summe des Intervalls von n bis m) und x (das bisherige Maximum der Längen derjenigen Intervalle, deren Summe s gerade gleich Z ist)

beste Grüße
zommi

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo zommi,

wenn man das längste Intervall am Ende der Schleife noch kennen will (und nicht nur seine Länge), dann muss man sich ein fünfte Variable merken, nämlich z.B. den Wert von n zu dem Zeitpunkt wo man x (das letzte mal) gesetzt hat.

Ansonsten sehe ich bei deinem Vorschlag viele unnötige Iterationen. Wenn man in einem (bzw. zwei aufeinander folgenden) Iterationsschritt(en) n weglässt und m+1 hinzufügt, dann erhöht sich die Summe des Intervalls schlicht um a, nämlich der momentan Länge des Intervalls (denn alle Werte sind nun um eins größer). Statt nun immer m+1 hinzuzufügen und n zu entfernen kann man, wenn man weiß, dass die Summe von n bis m unter aber die Summe von n bis m+1 über Z liegt, in einem Schritt bestimmen, ob man mit mit einem Intervall der momentanen Länge von n bis m die Zahl Z exakt erreichen kann. Dazu muss man nur prüfen, ob Z minus der Summe von n bis m sich durch die momentane Länge des Intervalls a teilen lässt. Wenn die Teilbarkeit besteht und wir den Quotienten q nennen, dann ist das Intervall n+q bis m+q eine Lösung. Wenn die Teilbarkeit nicht besteht, dann gibt es keine Lösung der Länge a.

Es reicht also für jede Länge a die Summe der erst a natürlichen Zahlen zu berechnen. Dann schaut man, um die Differenz von Z und der Summe der ersten a natürlichen Zahlen durch a teilbar ist. Wenn ja, gibt es eine Lösung der Länge a, die man sofort ausrechnen kann.

Die größte Länge von a, die man betrachten muss, ist die, bei der die Summe der erste a natürlichen Zahlen kleiner gleich Z ist und gleichzeitig die Summe der ersten a+1 natürlichen Zahlen größer als Z ist. Von dort aus reicht eine einfach Schleife über a absteigend, die man abbrechen kann, sobald man eine Lösung gefunden hat. Dies ist nämlich automatisch die längste.

herbivore

S
SilverX Themenstarter:in
5 Beiträge seit 2014
vor 9 Jahren

Hallo herbivore,

nach genauerem Betrachten habe ich die Regeln verstanden. Habe sie auch direkt in mein Programm umgesetzt -> Funktionalität absolut gegeben.

Bei Zahlen, wie 8 oder 16 gilt keine der Regeln, zumindest nicht in dem angegebenen Rahmen von maximal fünf Summanden. Soll mir aber recht sein, ich hoffe der Prof sieht das genauso, andernfalls füge ich weitere if-Bedingungen für weitere Summanden nach dem selben Schema hinzu.

Negative Zahlen gelten genauso - Super. Ich danke!

C
2.121 Beiträge seit 2010
vor 9 Jahren

@chilic: Bin bei meinen Recherchen auch auf das Gaußsche Verfahren gestoßen, kam da aber nicht direkt zu meinem Problem.

Zumindest bei der einfachen Variante die bei 1 beginnt hast du eine simple Formel.
Summe aus 1 bis n = 1/2 * n * (n+1)
Das kannst du als quadratische Gleichung nach n auflösen und hättest sofort das Ergebnis.

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo SilverX,

für 8 und 16 gibt es tatsächlich keine Lösung; nicht mit maximal fünf Summanden und mit mehr erst recht nicht.

Ich bin bei allen meinen Überlegungen von echt positiven, also echt natürlichen Zahlen ausgegangen. In wieweit die Überlegungen auch für Null und für negative Zahlen gelten habe ich mir nicht überlegt.

herbivore

P
1.090 Beiträge seit 2011
vor 9 Jahren

Bei Zahlen, wie 8 oder 16 gilt keine der Regeln, zumindest nicht in dem angegebenen Rahmen von maximal fünf Summanden.

8 und 16 sind 2er Potenzen, genau wie 32 und 64. Bei 2er Potenzen gilt das sie nicht in der Form zerlegt werden können. Also sie selber die Lösung sind. Prüfe also ob es eine 2er Potenz ist und wenn ja, gib die Zahl selber zurück.

MFG
Björn

Sollte man mal gelesen haben:

Clean Code Developer
Entwurfsmuster
Anti-Pattern

S
SilverX Themenstarter:in
5 Beiträge seit 2014
vor 9 Jahren

8 und 16 sind 2er Potenzen, genau wie 32 und 64. Bei 2er Potenzen gilt das sie nicht in der Form zerlegt werden können. Also sie selber die Lösung sind. Prüfe also ob es eine 2er Potenz ist und wenn ja, gib die Zahl selber zurück.

Kann die Summe gleich dem Summand sein? Wage ich zu bezweifeln, aber darauf kommt es ja gar nicht an. Wichtig ist, dass dem Nutzer der Hinweis gegeben wird, warum die erwünschte Summe nicht zerlegt werden kann.

@herbivore: Negative Zahlen werden wohl nur eingeschränkt funktionieren. Schließlich addiere ich für die Zerlegung in Summanden positive Werte, was bei einer negativen Eingabe falsch wäre. Den Stress mache ich mir aber nicht, dass ich da Eingaben <0 in den definierten Zahlenbereich erlauben würde.

1.346 Beiträge seit 2008
vor 9 Jahren

Man kann 16 auch als Summe aus einen Summanden "darstellen" und hätte damit auch in diesem Fall eine Lösung.

P
1.090 Beiträge seit 2011
vor 9 Jahren

Kann die Summe gleich dem Summand sein?

Ich denke aus mathematischer Sicht schon (Studium ist schon ein bisschen her). Du suchst die maximale Menge aufeinander folgender Zahlen, die zusammen addiert eine Zahl ergeben. Die Menge 1 (die Zahl selber) ist großer als die Leere Menge.

Deine Lösung ist aber auch OK, frag einfach nach welche der beiden Lösunge was erwartet wird.
Wie mein Physik Professor zu sagen pflegte: "Mathematisch ist es zwar nicht korrekt, aber es funktioniert, das reicht mir."
Wie mein Tutor zu sagen pflegte: "Ja es funktioniert, es ist aber mathematisch nicht korrekt, das reicht mir nicht." 😉

MFG
Björn

Sollte man mal gelesen haben:

Clean Code Developer
Entwurfsmuster
Anti-Pattern

1.361 Beiträge seit 2007
vor 9 Jahren

Nach OESIS:

a(n) is the largest k such that n can be written as sum of k consecutive positive integers.

lässt sich auch jede Zweierpotenz als Summe von einer Abfolge von Zahlen (genau einer Zahl) darstellen. Ist also kein Problem.
Prinzipiell hängt diese Darstellbarkeit von den ungeraden Teilern von N ab, die es natürlich bei Zweierpotenzen (neben der 1) nicht gibt.

Die Beschreibung zu A109814 gibt auch gleich noch eine Berechnungsvorschrift, die ich mal nach Python übersetzt habe:

max(min(d, 2*N/d) for d in xrange(1, N+1, 2) if (N%d == 0))

Man braucht natürlich nur bis zur Wurzel zu testen, da ein Teiler ja nicht größer sein kann.

beste Grüße
zommi