Hilfe en algorithmus zu entwickeln...

[Thunderbolt]

Aaaaaaaalso. Die Aufgabe hab ich in der Schule bekommen. Es ging eigentlich darum die Summen von allen Zahlen miteinander in einer Menge (also jeweils nur 2 Zahlen).

Das ganze hab ich so gelöst:

Delphi-Quellcode:

[code:1:06509b420c]program algorithmus;
{$APPTYPE CONSOLE}
uses SysUtils;

type
  menge = set of byte;

var
  neu, alt, zwischen :menge;
  eingabe,i,obergrenze :integer;
  eingaben: array [1..10] of integer;

procedure dazutun(wert :integer);
begin
  for i:=1 to obergrenze do
    begin
      if i in alt then zwischen:=zwischen+[i+wert];
    end;
  alt:=alt+[wert];
  zwischen:=zwischen+[wert];
end;

procedure ausgabe(ausgeben :menge);
var limit,erstes :integer;
begin
  erstes:=0; limit:=0;
  neu:=ausgeben;
  repeat
    if erstes in ausgeben then
      begin
        limit:=limit + erstes;
        neu:=neu-[erstes];
      end;
    inc(erstes);
  until neu=[];

  write('Mögliche Ergebnisse sind: ');
  for i:=0 to limit do if i in ausgeben then write(i:3,',');

end;

begin
  write('Blubb bla bla blub bla blubb blubb.');
  neu:=[]; alt:=[]; zwischen:=[]; eingabe:=0;
  write('Obergrenze: ');
  readln(obergrenze);
  repeat
    write('Wert: ');
    readln(eingabe);
    if not ((eingabe=0) or (eingabe in alt) or (eingabe>obergrenze)) then
      begin
        dazutun(eingabe);
      end
      else if eingabe>obergrenze then writeln('Obergrenze überschritten!');
  until eingabe=0;
  ausgabe(zwischen);
  readln;
end.[/code:1:06509b420c]

ich weiss... man könnte ein paar sachen weglassen...

Jetzt würde mich mal interessieren wie man dasselbe mit ALLEN Kombinationen untereinander macht. Ich hab schon rumüberlegt, weiss aber nit wie man das anstellen soll.
Wenn ich da also die Zahlenmenge [1,2,4,8,16,32] habe, müsste mir das Ding jetzt alle Zahlen von 1 bis 69 auflisten.

mfg,
ThunderbolT

[OregonGhost]

Zitat:

Wenn ich da also die Zahlenmenge [1,2,4,8,16,32] habe, müsste mir das Ding jetzt alle Zahlen von 1 bis 69 auflisten.

Entweder verstehe ich die Problemstellung nicht oder das Programm müsste alle Zahlen von 1 (bzw. 0) bis 63 auflisten?

[Thunderbolt]

ja. sorry. 63 müssts sein

[Kedariodakon]

Versteh nix

Bitte genauer erklären

Bye

[Thunderbolt]

sry das hört sich jetzt etwas hart an, aber wenn du aus dem quelltext heraus nicht verstehst was das programm macht, wirst du mir kaum helfen können.

das programm soll zahlen einlesen. aus diesen zahlen soll es nun alle möglichen kombinationen generieren um zu sehen welche werte man daraus kombinieren kann. das könnte man vergleichen mit einer alten wage, wo man sich immer ein gegengewicht zusammenstellen musste aus mehreren unterschiedlichen gewichten...

[OregonGhost]

So ein ähnliches Programm musste ich vor einiger Zeit für KI in Prolog schreiben, da ist das gar nicht so kompliziert ;c)

So könnte man es machen:

Delphi-Quellcode:

program DPZusammenRechnen;

uses
  Windows, SysUtils;

{$R *.RES}

type ISet = set of Byte;

var
  numbers: Array Of Byte;
  results: ISet;
  i: Integer;

procedure AddArray(current: Array Of Byte; var result: ISet);
var i, j: Integer; next: Array Of Byte; sum: Byte;
begin
sum := 0; // Aktuelle Summe initialisieren (für current)
SetLength(next, High(current));
// Summieren
for i := 0 to High(current) do begin
   sum := sum + current[i];
  // Alle Zahlen in current außer current[i] in next kopieren
  for j := 0 to High(current) do begin
     if j < i then begin
       next[j] := current[j];
    end else if (j > i) then begin
       next[j - 1] := current[j];
    end;
  end;
  // Wenn next ein oder mehrere Werte enthält, das ganze von neuem
  if (Length(next) > 0) then
     AddArray(next, result);
end;
// Aktuelle Summe der Ergebnismenge hinzufügen
result := result + [sum];
end;

begin
// Array füllen
SetLength(numbers, 6);
for i := 0 to High(numbers) do begin
   numbers[i] := 1 shl i;
  WriteLn(numbers[i]);
end;

WriteLn;
AddArray(numbers, results);

// Ergebnismenge ausgeben
for i := 0 to 255 do begin
   if i in results then begin
     WriteLn(IntToStr(i));
  end;
end;

ReadLn;

end.

Ich hab' allerdings außer für das Ergebnis jetzt nur Arrays verwendet, aber vom Prinzip her geht's mit Mengen ja so ähnlich.

[negaH]

Kombinationen ohne Duplikate.

Delphi-Quellcode:

function Kombinationen(const Values: array of Integer): Integer;

  function DoCombi(Index, Start: Integer): Integer;
  begin
    if Index <= High(Values) then
    begin
  // Ausgabe der gebildeten Summe
      WriteLn( Start + Values[Index]:5 );

  // kombinatorische Rekusionen und Berechnung der Anzahl der Summen
      Result := 1 + DoCombi(Index +1, Start + Values[Index]) +
                    DoCombi(Index +1, Start );
    end else Result := 0;
  end;

begin
  Result := DoCombi(Low(Values), 0);
end;

Mehrfach bildbare Summen werden nicht ausgefiltert.

Gruß Hagen

[OregonGhost]

@negaH:
Dein Code gibt bei mir Dinge wie die folgenden aus:

Code:

134480385
134488593
134488615
134488615
134488620
268969005
268969000
134488620
268969005
268969000
134488593
134488598

Getestet mit dem numbers-Array aus meinem Quellcode oben.

[negaH]

mit

Delphi-Quellcode:

procedure Test;
var
  Numbers: array of Integer;
  I: Integer;
begin

  SetLength(Numbers, 6);
  for I := Low(Numbers) to High(Numbers) do
    Numbers[I] := 1 shl I;

  WriteLn( Kombinationen(Numbers):5 );
end;

wird bei mir

Code:

    1
    3
    7
   15
   31
   63
   47
   23
   55
   39
   11
   27
   59
   43
   19
   51
   35
    5
   13
   29
   61
   45
   21
   53
   37
    9
   25
   57
   41
   17
   49
   33
    2
    6
   14
   30
   62
   46
   22
   54
   38
   10
   26
   58
   42
   18
   50
   34
    4
   12
   28
   60
   44
   20
   52
   36
    8
   24
   56
   40
   16
   48
   32
   63

ausgegeben. Delphi 5.

Gruß hagen

[OregonGhost]

Bei mir ist es, damit das mit den Mengen funktioniert, ein Array of Byte. Daher der Fehler bei mir. Mit einem Array Of Integer geht's natürlich.