Entwickler-Ecke :: Thema anzeigen - Längste steigende Teilfolge finden

Mike_C - So 31.10.04 17:03
Titel: Längste steigende Teilfolge finden

Hi

ich stehe gerade komplett auf dem Schlauch. Ich will eine Funktion schreiben, die mir aus einem Array die längste monoton steigende Teilfolge rausfiltert und mir sowohl die Teilfolge nennt, als auch ihre Länge mitteilt.

ich stelle mir das so vor:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

const N = 10;
var teilfolge: array[0..N] of integer = (1,2,3,4,1,5,7,8,2,3,5);
    i: integer;

...
getTeilfolge(startpos, len);  //beide variablen sollen von der Funktion verändert werden!
for i := 0 to len-1 do
  s := s + IntToStr(teilfolge[startpos+i])+', ';
Memo1.Lines.Add('Die längste Teilsumme ist: '+s+' mit der Länge '+intToStr(len));

leider hab ich keine Ahnung, wie ich die Funktion getTeilfolge programmieren soll. ich glaube aber dass es relativ einfach sien sollte. wie gesagt ich stehe im moment komplett auf dem schlauch. Hat jemand eine Idee?

Gruß MikeC

.Chef - So 31.10.04 17:10

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

var
  a, b, c : Integer;
begin
  a:=0;
  c:=0;
  for b:=1 to Length(Teilfolge)-1 do
    if Teilfolge[b-1] <= TeilFolge[b] then c:=b else a:=b;
  if c < a then c:=1 else c:=c-a;

a enthält die Startposition, c die Länge. Ungetestet!!

Gruß,
Jörg

Mike_C - So 31.10.04 17:19

hmm das funktioniert nicht so ganz: bei der teilfolge

Delphi-Quelltext

1:
2:
3:

const
  N = 10;
  teilfolge: array[0..N-1] of integer = (1,2,3,4,1,5,8,2,3,5);

gibt die Prozedur getTeilfolge das Ergebnis

getTeilfolge hat folgendes geschrieben:

Die längste Teilsumme ist: 2, 3, mit der Länge 2

aus. das ergebnis müsste aber sein: "Die längste Teilfolge ist 1,2,3,4, mit der Länge 4". mal sehen, ob ich das hinbekomme.
danke schonmal für den ansatz

gruß
MikeC

.Chef - So 31.10.04 17:43

War ein Denkfehler drin. :oops:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

var
  a, b : Integer;
  start, laenge : Integer;
begin
  a:=0;
  start:=0;
  laenge:=0;
  for b:=1 to Length(Teilfolge)-1 do
    if Teilfolge[b-1] > Teilfolge[b] then
      if b-a > laenge then
      begin
        start:=a;
        laenge:=b-a;
        a:=b;
      end;

Du musst nur noch etwas einbauen für den Fall, dass die längste steigende Folge ganz hinten im Array steht. Aber sonst gehts.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!