Algorithmus - Wie kann ich aus einen beliebig langen Array alle erdenklichen Summen bilden?

Hallo Zusammen :)

Ich habe vor kurzem eine interessante Aufgabe bekommen, bei der weder ich, noch der Aufgabensteller wissen ob und wie es möglich ist.

Problem ist Folgendes: Ich soll ein Programm schreiben, welches eine beliebige Anzahl von Doublewerten entgegennimmt und daraus alle nur möglichen summen bildet. Und mit allen Summen meine ich auch Summen aus beispielsweise 3,4,5 oder mehr Summanden.

Ich stehe momentan ziemlich auf den schlauch und ich habe auch noch keinen Algorithmus gefunden der mit der variablen Arraygröße mit skaliert.

Hoffe ich konnte mich verständlich ausdrücken. Ich bin echt für jede Hilfe dankbar! (Vorschläge wären mir am Liebsten in c# oder Java)

2 Antworten

Vom Beitragsersteller als hilfreich ausgezeichnet

FaronWeissAlles

05.02.2016, 20:08

Eine Lösung wäre wenn du einen Algorithmus implementierst der dir aus einem double-Array dessen Potenzmenge berechnet. Du hast dann sozusagen ein Array aus Arrays die alle möglichen Kombinationen von Summanden enthalten. Dann musst du dir nur noch die Arrays mit der Länge x raussuchen (für alle x-summandigen Summen) und jeweils aufaddieren.

Wenn du keine Lust hast dich mit der Arraygröße herumzuschlagen (um bei der Eingabe der Werte zu wissen wie groß du dein Array machen musst), nimm einfach statt einem double-Array die Klasse List<double> bzw. ArrayList<double> (in Java).

Code dazu findest du im Internet, falls du es nicht schaffst.

Natürlich benötigt diese Art von Aufgabe viel Speicher, vor allem diese Lösung wenn du erstmal die ganze Potenzmenge berechnest

Kloebner

05.02.2016, 14:09

Das ginge z.B. über einen dynamic programming Ansatz: https://en.wikipedia.org/wiki/Dynamic_programming. Dabei entsteht eine 2D-Tabelle mit allen möglichen Untersummen (die sicher einige Dopplungen enthält die man im Anschluss herausfiltern muss).

Woher ich das weiß:Berufserfahrung – Seit 20+ Jahren

Ähnliche Beiträge

Ist es in Java möglich mit Unbekannten(keine Variablen) zu Rechnen?

Ist es in Java möglich mit Unbekannten(keine Variablen) zu Rechnen?
Also das ich z. B. eingebe (a+b)^2 und zurückbekomme a^2+2ab+b^2, ohne das selber einzuprogrammieren?

Komplexe Zahlen nicht mit eingeschlossen :)

LG
TheProgrammer99

...zum Beitrag

Plus und Minus rechnen in Excel?

Hallo

Ich habe mir eine Excel Tabelle gebastelt wo ich den Abtrag eines Kredites brerechnen möchte .

Dazu habe ich unter G1 die noch offenen Kreditsumme ( 6000,00 €)

In der Spalte B habe ich die Monatlichen Raten (200,00 €) von B5 bis B52 in der Spalte B54 mit der Formel ( =SUMME(B5:B52) )zusammen gerechnet.

Das selbe habe ich mit den Zinsen in der Spalte in der Spalte E gemacht ( =SUMME(E5:E52) ). Ergebnis steht unter E54

Jetzt möchte ich unter B56 die Offene Kreditsumme aus Spalte G1 ( 6000€ + die Gesamtsumme der Zinsen aus Spalte E54 zusammenrechnen und den Abtrag aus Spalte B54 davon abziehen. Diese Formel dachte ich ( =SUMME(G1:G54-B54) )mir.

Das klappt aber nicht . Wo ist dort mein Fehler ?

Kann mir das einer Beantworten und mir mal die Formel aufschreiben

Danke

Rainer

...zum Beitrag

Versteh ich explizite Deklarationen in C++ richtig?

Hallo Leute,

ich habe hier einen C++ Code einer expliziten Deklaration. Meine Frage ist, ob ich das richtig verstanden habe.

In Zeile 3 wird erstmal nur bekanntgegeben, dass eine Funktion des Namens Summe existiert.
In Z. 10 wird die Funktion des Namens Summe dann aufgerufen. Das (a,b) bedeutet, dass es 2 Variablen (bzw. 2 Parameter) mit dem Namen a und b gibt.
In Z. 12 wird dann die Definition der Funktion vorgenommen. Das int lhs, int rhs bedeutet, dass es 2 Parameter mit dem Namen lhs und rhs des Typs integer gibt.
In Z. 15 findet die eigentliche Berechnung statt und wird als ein int zurück an Z. 12 gegeben, welche ihrerseits den Wert an Z.10 ausgibt.

Ist das bis hierhin alles korrekt was ich erzählt habe?

Was ich nun nicht verstehe ist, an welcher Stelle und woher der Code weiß, dass er den Wert von a und b auf lhs und rhs legen soll? Ergibt sich das evtl. einfach aus der Reihenfolge und (richtigen) Anzahl der Parameter?

viele Grüße und danke für die Antworten!

...zum Beitrag

Welches ist der beste Sortieralgorithmus?

Ich denke das diese Frage objektiv beantwortbar ist. Ich sage der gesuchte Algorithmus hat eine möglich kurze Laufzeit (selbst bei Datenmengen, wie sie in Enterprise-Systemen verarbeitet werden müssen) und ist stabil. Wie lässt sich der Umsetzen (Pseudocode reicht vollkommen)? Und Themenverwandt weiß man welcher Sortieralgorithmus eigentlich von Datenbanken wie SQL im Hintergrund angewendet wird oder sind das Firmengeheimnisse?

...zum Beitrag

Suche Tool zu decodieren von Email Quelltext.

Kennt ihr ein Tool, oder Email Programm, wo man den original Email Quellcode einsetzen kann, und er daraus ursprüngliche Mail mit allen Formatierungen anzeigt bekommt?

Ich habe nur den Quellcode möchte aber die Email schön angezeigt bekommen. Möglichst natürlich Freeware.

Danke!

...zum Beitrag

Creative Pebble Störgeräusche, wie kriege ich sie weg?

Hallo Zusammen,

seit kurzem summen meine PC Boxen. Vorher ist mir das nie aufgefallen, also gehe ich davon aus dass es noch nicht so lange her ist. Allerdings benutzte ich die Boxen auch sehr selten, da ich 95% der Zeit mit Headset zocke. Der PC wird ausschließlich zum zocken benutzt.

Kurzer Fakten-Check:

Die Boxen summen bereits beim Hochfahren von Windows
Wenn ich die Boxen lauter oder leiser stelle macht die Höhe keinen unterschied. Das Summen ist immer gleich laut.
Alternativ habe ich zbs. die Nintendo Switch von meinem Sohn angeschlossen, perfekter Klang... Also liegt es am PC
Headset und Boxen hängen an einem Y-Kabel. D.h. es kann von beiden Geräten gleichzeitig der Ton abgespielt werden. Wenn ich es aber ausstecke, ausschalte, direkt am PC stecke oder ähnliches bringt es nichts. Es summt immer noch.
Auch vorne am PC sind (noch stärkere) Störgeräusche

Ich hoffe Ihr könnt mir weiter helfen. :)

...zum Beitrag

Java: Wie kann ich in switch-Statements Benutzereingaben verarbeiten?

Hallo!

Also, ich muss eine Ampel in Java basteln. Die Ampel soll wechseln:

rot => rot-gelb => gelb => grün => rot => rot-gelb => gelb...

Ich habe jetzt ein Switch Statement (switch case) verwendet:

 public class TrafficLight {
public static void main(String[] args) {

    int tl = 2;
    String tlString;
    switch (tl) {
        case 1:  tlString = "red";
                 break;
        case 2:  tlString = "red-yellow";
                 break;
        case 3:  tlString = "green";
                 break;
        case 4:  tlString = "yellow";
                 break;
        default: tlString = "Invalid tl";
                 break;
    }
    System.out.println(tlString);

}
 }

Das funktioniert schonmal, aber ich bekomme nur „red-yellow” als Ausgabe. Damit ist die 1. Hälfte getan. Nun müsste der Benutzer nur noch eine Aktion machen (z.B. „c” eingeben). und dann sollte die Ampel umschalten (also auf grün wechseln). Ich habe also mit

  import java.util.Scanner;

den Scanner importiert (1. Zeile) und dann zwischen die letzten beiden geschweiften Klammern (s.o.)

public static void input(String[] args) {

    Scanner scan = new Scanner(System.in);
    int y = scan.nextInt();

    System.out.println("Please enter a the letter c:");
    int year = scan.nextInt();

}

eingefügt. Aber Java gibt noch nichtmal die Ausgabe aus, dass eine Eingabe erwartet wird und Eingaben sind auch nicht möglich! Was mache ich falsch? Oder ist die Idee generell falsch?

Hier die Aufgabe im Original:

Implementieren Sie die Steuerung einer Verkehrsampel. Die Verkehrsampel kann sich dabei ausschlielich in einem der folgenden vier Zustände benden: rot, rot-gelb, grün und gelb. Die Ampel darf dabei nur von rot auf rot-gelb, von rot-gelb auf grün, von grün auf gelb und von gelb auf rot umschalten. Schreiben Sie eine Klasse TrafficLight, die diesen Anforderungen genügt. Die Klasse soll jeweils eine Methode zum Weiterschalten der Ampel zwischen den erlaubten Zuständen anbieten. Ferner sollte es möglich sein, denaktuellen Zustand der Ampel auf den Bildschirm auszugeben. Schreiben Sie eine Main-Methode, in der Sie ihre Implementierung gründlich testen.

Danke im Voraus!

...zum Beitrag

Musikordner verwalten/sortieren?

Habe eine riesige Musiksammlung, aber leider total unordentlich. Wenn ich das jetzt alles von Hand in eine beliebige Ordnung bringen müsste täte das ewig dauern =)
Habt ihr Ideen wie das einfacher oder gar komplett automatisiert realisiert werden könnte?

...zum Beitrag

Wie kann ich in Excel in Echtzeit einen bestimmten Wert von einer Webseite darstellen lassen?

Ich möchte gerne eine Zahl, in diesem Fall die Anzahl von Followern, von einer anderen Seite in einer Exceltabelle in Echtzeit sehen. Ist das irgendwie möglich?

...zum Beitrag

xcopy-Batchdatei - Warum ist zyklisches Kopieren nicht möglich?

Ich versuche gerade über die Aufgabenplanung (unter Win 8.1) eine automatische Sicherung aller Daten von C:\ in einen Dropboxordner zu erstellen. Ich verwende folgende Batch (Nummern am Anfang zur Verdeutlichung der Zeilenzahl) :

@echo off
echo Kopieren von neuen oder geänderten Daten aus C:\ in den Dropbox-Ordner "Backup(Ronald)"
xcopy "c:\" "c:\Users\Assembly\Dropbox\Backup(Ronald)" /D /E /Y /I

Dabei befindet sich die Batch nicht auf C:\ sondern auf einer externen Platte, versucht sich also nicht selbst mitzukopieren. Bei jedem Versuch die Sicherung zu starten bekomme ich die Fehlermeldung: "Zyklische Kopie nicht möglich"

Würde mich über etwaige Lösungsvorschläge freuen, vielen Dank.

...zum Beitrag

Mehrere CSV-Dateien zu einer Datei zusammenfassen - ist das möglich?

Ich habe mehrere CSV-Dateien, die jeweils eine Zeile enthalten. Nun möchte ich daraus eine Datei mit mehreren Zeilen machen. Wie kann ich die Dateien zusammenfügen? Gibts dafür Software?

...zum Beitrag

Ist es möglich in einer Zelle (Excel) mehrere Rechnungen ausführen zu lassen?

Ich möchte in einer Zelle zwei Ergebnisse präsentier haben, in etwa so: "30 / 40". Dabei soll der Wert 30 die Summe aus zwei oder mehreren Zellen sein und der Wert 40 das Produkt zweier andere Zellen. Beide Ergebnisse sollen durch einen Schrägstrich abgegerenzt werden. Geht so was? Und wenn ja wie?
Danek schonmal

Office 2007, Excel 2007

...zum Beitrag

Wie füge ich in eine Exceltabelle eine variable Anzahl neuer Zeilen ein?

Mein Problem: Ich möchte mit Hilfe eines Button-Click (also per Makro) in eine bestehende Excel-Tabelle (Bereich: (C9:H27)) an der Stelle (Zeile 11) eine variable Anzahl neuer Zeilen einfügen. Die Anzahl soll bestimmt werden durch den Wert, der in Zelle (J3) vorgegeben ist. Ich bin auf den Gebiet der Makros noch ein Neuling, habe auch schon einiges versucht, jedoch ohne Erfolg. Wer kann mir helfen? Ich danke euch jetzt schon für die zahlreichen Tips. :-)

...zum Beitrag

Gibt es eine Art erweiterter Taskmanager?

hallo :),

ich suche ein Programm das mir (die echten) Werte anzeigt und was genau die CPU belastet...Weil der normale Taskmanager zeigt bei mir 100% Auslastung an wenn ich spiele seit etwa 2 Wochen... Ich habe schon alles mögliche versucht und kann den Grund nicht finden...

Ich möchte also herausfinden was der Task macht der soviel Leistung zieht und warum was genau im Task soviel Leistung zieht. Gibts sowas wo einem quasi jeder Befehl an den CPU und jede Antwort vom Prozessor und Ram usw. angezeigt wird (das dürften ja paar Tausend die Minute oder mehr sein?)

Oder vllt gibts da sonst noch Möglichleiten.

Ich hatte mal mit Cinebench r15 einen Bench gemacht und der zeigte 293cb an...wobei mir der Wert nix sagt...

Hat jmd da eine Idee?

Oder hat vllt noch jmd das Problem das Minecraft bei euch die CPU fast abraucht?

Gab es da ein Windows 10 Update vor einigen Wochen das die Leistung erheblich verschlechtert hat?

Microsoft Windows 10 Home 10.0.18363 Build 18363

Vielen Danke im Voraus :)

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen