Tut mir leid, dass ich die ursprüngliche Frage gelöscht habe, hier ist es: Wir haben eine Tasche oder ein Array von n ganzen Zahlen, wir müssen das Produkt von jedem der (n-1) Teilmengen finden. z.B.:
S = {1, 0, 3, 6}
ps [1] = 0 * 3 * 6 = 0;
ps [2] = 1 * 3 * 6 = 18; usw.
Nach Diskussionen müssen wir uns um die drei Fälle kümmern und sie werden im Folgenden illustriert:
%Vor%Danke.
Wenn das Set sehr groß ist, kann es bequem sein:
Wenn die Menge Null enthält (d. h. P = 0, x = 0), müssen Sie sie als Sonderfall behandeln.
BEARBEITEN . Hier ist eine Lösung in Scheme, die die Antwort von andand berücksichtigt. Ich bin ein kompletter Anfänger - kann jemand mir helfen, den folgenden Code zu verbessern (macht es effizienter, lesbarer, lisp-ish)? (Fühlen Sie sich frei, meine Antwort zu bearbeiten.)
%Vor%
Sie müssen die drei Fälle explizit berücksichtigen:
1) Keine Nullen: Berechnen Sie das Produkt aller Elemente und teilen Sie das gewünschte Mengenelement aus diesem Produkt auf.
2) Eine Nullstelle: Berechne das Produkt der Nicht-Null-Elemente vorberechnen. Die Antwort ist immer 0, außer wenn Sie das einzelne Nullelement entfernen. In diesem Fall ist es das vorberechnete Produkt.
3) Mehr als eine Null: Die Antwort ist immer 0.
Dies setzt voraus, dass Sie einen Datentyp haben, der die Produkte enthalten kann ... das heißt, Sie müssen darauf achten, dass Ihr Produkt den Maximalwert des Typs, den Sie zum Speichern verwenden, nicht überschreitet.
Berechnen Sie für die tatsächliche Implementierung immer das Produkt der Nicht-Null-Elemente und verfolgen Sie, wie viele Nullen es gibt. Wenn das "Set" dynamisch ist (seine Werte ändern sich), müssen Sie das Produkt und die Nullzählung aktualisieren. Wenn Sie nach einem bestimmten Teilprodukt gefragt werden, betrachten Sie die verschiedenen Fälle und handeln Sie entsprechend.
Wenn ich Ihre Frage verstehe, ist das die triviale Lösung. Es sollte in jeder Programmiersprache einfach zu implementieren sein.
Sie können dies in O(N) lösen, indem Sie O(1) zusätzlichen Speicherplatz verwenden (das O(N) -Ausgabefeld nicht mitgerechnet), ohne die Division zu verwenden. Hier ist der Algorithmus in Java.
Angenommen, Sie können Python verwenden:
Sie können die Methode combinations aus dem Modul itertools verwenden, um träge zu generieren die verschiedenen Teilmengen des betreffenden Satzes. Sobald Sie das haben, können Sie reduce und operator.mul , um das Produkt eines jeden zu erzeugen.