Zahlenfolgen generieren, für die bestimmte Kriterien zutreffen

Don06

Hallo,

Ich möchte gerne einen Algorithmus entwerfen, um Zahlenfolgen zu generieren, für die bestimmte Bedingungen zutreffen. Die Zahlenfolgen sollen eine Länge N haben. Die Zahlen selbst kommen aus dem Intervall [-1, 1] allerdings sind es nur natürlichen Zahlen (also -1, 0 und 1).
Desweiteren soll für die Folgen gelten (x_i ist die i-te Zahl in der Folge):

(Sigma_i[1, n] x_i) >= 0 für alle natürlichen n in [1, N]
und für den Sonderfall n = N
(Sigma_i[1, N] x_i) = 0

Also die Summe der Zahlen bleibt immer nicht-negativ. Addiert man alle Zahlen so ist die Summe null.

Für N = 2 würden sich also folgende Folgen ergeben:

[0, 0], [1, -1]

Für N = 3 entsprechend:

[0, 0, 0], [0, 1, -1], [1, -1, 0], [1, 0, -1]

Ich könnte natürlich alle möglichen Folgen generieren lassen und dann überprüfen, ob die gegebenen Bedingungen erfüllt sind. Allerdings, weiss ich nicht, wie hoch der "Überschuss" für sehr große N ist.

Ich bin für jeden Denkanstoß dankbar, da ich im Moment etwas ratlos bin. Kann ich das Problem vielleicht über Permutationen lösen? Ich habe festgestellt, dass nicht alle gültig sind. Gibt es eventuell ein leichtes Verfahren, die ungültigen auszuschließen? Oder ist das doch ein vollkommen falscher Ansatz?

Gruß
Don06

Jester

Hinweise zur Lösung entfernt, da die Aufgabe dem laufenden Bundeswettbewerb für Informatik entstammt.

SeppJ

Ich würde da was rekursives machen. Die Details will ich jetzt nicht alle
ausarbeiten (das sollst du ja machen), aber die groben Schritte:

1. Ist die Länge der Folge = N? Wenn ja -> Abbruch und Ausgabe der Folge
2. Ist die Quersumme > 0? Wenn ja, knnen -1,0,1 angehängt werden und mit
allen drei Fällen bei 1. weitergemacht werden. Wenn nein, können nur 0,1
angehängt werden und bei 1. weitermachen.

Der Zweite Schritt ist aber noch nicht komplett. Du musst zusätzlich noch
(N-Länge(Folge)) mit der Quersumme vergleichen. Die Quersumme darf nämlich
im nächsten Durchgang nicht größer sein als die Anzahl der Restglieder. In
dem Fall darf dann keine 1 angehängt werden. Ist die Quersumme genau gleich
der Anzahl der Restglieder kann man auch gleich abbrechen und den Rest der Folge mit -1 auffüllen.

Das sollte sich recht einfach in der Programmiersprache deiner Wahl umsetzen
lassen. Da keine unnötigen Schritte gemacht werden, sollte der Algorithmus
auch recht effizient sein. Einziges mögliches Problem ist evtl. der
Speicherverbrauch, weil sämtliche Zahlenfolgen in den Speicher passen müssen
und bei großem N können das bestimmt sehr viele sein.

Jester

Hinweise zur Lösung entfernt, da die Aufgabe dem laufenden Bundeswettbewerb für Informatik entstammt.

SeppJ

Jester schrieb:

Danke für die genauere Ausführung. Rekursiv würde ich es allerdings eher nicht implementieren.

Klar geht das auch anders, aber im Prinzip kann man sich das ganze doch als einen Baum mit 3er Astgabeln vorstellen. Nun will man alle Äste durchgehen. Wenn irgendeine Aufgabe nach Rekursion schreit, dann doch diese!

Jester

Hinweise zur Lösung entfernt, da die Aufgabe dem laufenden Bundeswettbewerb für Informatik entstammt.

Ben04

Wieso nicht einfach immer eine konstante 0 Folge ausgeben?

Oder willst du nicht nur eine sondern alle generieren?

Jester

Hinweise zur Lösung entfernt, da die Aufgabe dem laufenden Bundeswettbewerb für Informatik entstammt.

Ben04

Jester schrieb:

Ben04 schrieb:

Wieso nicht einfach immer eine konstante 0 Folge ausgeben?

Oder willst du nicht nur eine sondern alle generieren?

Vielleicht liegt die Wahrheit irgendwo dazwischen?

Das kann nur der OP mit Sicherheit sagen. Am Ende will er eventuell zählen wie viele es gibt und damit wäre es ein ganz anderes Problem.

Don06

Ah, erst mal Danke für die vielen und ausführlichen Antworten.

@Jester: Folgen zufällig generieren habe ich benutzt, um mir ein paar Beispiele für diese Folgen zu holen, allerdings brauche ich immer alle gültigen Folgen. Solange zufällige Folgen generieren, bis alle Folgen gefunden worden sind, kann für sehr große N wohl sehr lange daueren bzw. gar nicht funktionieren.

@ SeppJ: An einen Baum, hatte ich auch schon gedacht. Ich werde mich wohl mal an eine Implementierung dieses Algorithmus machen, mal schauen wie es wird.

Nur zum Allgemeinen Verständnis, falls noch jemand eine Idee dazu hat: Ich versuche Alle Folgen zu finden, da sie im weiteren Verlauf noch benötigt werden. Jede Folge ist Input für einen weiteren Arbeitsschritt. Dabei müssen die Daten nur in sequentieller Form vorliegen, sprich zuerst Zahl 1, dann Zahl 2, ... Es wird immer nur ein Wert benötigt. Deshalb dachte ich, dass man dies auch speicherschonend implementieren kann. In etwa so (Pseudo-Code C++-like):

Folge = Array mit Anzahl_der_Folgen Folgen
for (i = 0; i < Anzahl_der_Folgen; ++i)
  WerteAus(Folgen[i])

N = Länge_der_Folge;
WerteAus(Folge folge)
  for (i = 0; i <= N; ++i)
    BenutzeWert(folge.Wert)
    folge.Weiter

Der nächste Wert einer Folge würde dann durch die Nummer der Folge (Alle Folgen für ein N sind durchnummeriert, nach irgendeinem Schema), die aktuelle Werte-Position und die aktuelle Quersumme den nächsten Wert ermitteln. Nicht objektorientiert wäre die eine Funktion, die ungefähr so aussähe:

int wert(int N, int Nummer_der_Folge, int Werte_Position, int Quersumme)

Für so eine Implementierung bräuchte man wohl auch die Anzahl aller Folgen in Abhängigkeit von N. Da beisse ich aber im Moment auf Granit. 2^(N-1) passt nur für N in [1, 3];

Naja, ich bin für alle Ideen offen. Und nochmal Danke für die bisherigen Gedankenanstöße

Gruß
Don06

Das ist Aufgabe 3 des momentan laufenden Bundeswettbewerbs Informatik:
http://www.bwinf.de/uploads/media/bwinf271-aufgabenblatt-einfach.pdf

Jester

danke!

@Don06: das hättest Du vielleicht dazu sagen sollen, so geht's schließlich nicht.

ich hoffe hier hilft keiner mehr.