Längste aufsteigende, zusammenhängende Teilfolge?

Hallo,

ich suche eine Divide & Conquer-Methode, mit der man die Länge der längsten, aufsteigenden, zusammenhängenden Teilfolge in einem Array ermitteln kann.

Bsp.:

{ 3, -2, -1, 1, 3, 1, -2, 3 },
lazT = { -2, -1, 1, 3 },

Also wäre die Länge 4.

Meine erste Idee in Pseudo-Code:

lazT(Array A, n, q, r) //Aufruf mit n = 1, q = 0 und r = A.length
  if q = r then
    return n
  else if A[q] < A[q+1] then
    return lazT(A, n+1, q+1, r)
  else
    return max { lazT(A, 1, q+1, r), n }

Wenn ich aber D&C richtig verstanden habe, ist das ja nur eine rekursive Methode, ohne irgendein Teilen oder Herrschen.

Wie kann ich daraus D&C machen oder einfach, wie sieht die Methode aus?
Vielen Dank im Voraus!

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

regex9

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, programmieren, Informatik

05.05.2019, 21:24

Teile und herrsche bedeutet, dass du ein Problem so lange in Teilprobleme zerlegst, bis diese beherrschbar sind. Rekursion wäre daher für einen Lösungsweg nicht ungeeignet.

Ich teile an dieser Stelle nur eine iterative Lösung (Pseudocode):

getMaxSequence(arr):
  maxSequence = 1
  currentSequence = 1

  from i = 0 to sizeof(arr) - 1:
    if arr[i] >= arr[i + 1]:
      maxSequence = max(maxSequence, currentSequence)
      currentSequence = 1
    else:
      currentSequence = currentSequence + 1

  return max(maxSequence, currentSequence)

Wenn du das unbedingt rekursiv haben möchtest, überlasse ich eine Implementation dir. 😉

Einstein0815

04.05.2019, 17:43

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Woher ich das weiß:Recherche

IronMan1909

Fragesteller

04.05.2019, 17:45

dort ist es leider nicht zusammenhängend

Ein If mit Return:

public void printArray(int[] array) {
  if(array.length > 0) {
    System.out.println("Content of Array:");
    System.out.println(Arrays.toString(array));
    return;
  }
  System.out.println("Array is empty");
}

Ein If mit Else:

public void printArray(int[] array) {
  if(array.length > 0) {
    System.out.println("Content of Array:");
    System.out.println(Arrays.toString(array));
  } else {
  System.out.println("Array is empty");
  }
}

Was ist professioneller?

...zur Frage

Array nach Wert prüfen rekrusiv (java)?

Hi sagen wir mal ich habe einen COde der so aussieht:

  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
       return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:

 public static int calculateBinomialCoefficient (int n, int k)
  {
   if (k == 1)
     return n;
   else if (n >= k && k == 0)
     return 1;
   else
for (int a=0; a<array.length;a++)
{
for (int b=0; b<array.length;b++)
{
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
     
 
  }
}

(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)

Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?

...zur Frage

Wie kann ich anhand von array in bluej attribute initialisieren?

Hallo,

Ich habe in meinem BlueJ-Java Skript ein Attribut: int aktueller_gegner. Ich möchte nun in einer Methode, bei der ich auf Werte der Klasse : Monster zugreife mithilfe dieser Zahl je zwischen den Objekten monster1, monster2, monster3, ... unterscheiden können ohne eine if-Konstruktion wie diese hier bauen zu müssen:

if (aktueller_gegner == 1)

{

monster1 ... ;

}

else if (aktueller_gegner == 2)

{

monster2 ... ;

}

else if (aktueller_gegner == 3)

{

monster3 ... ;

}

Ich habe gehört, dass das mit Array möglich wäre, habe aber keine Idee wie und auch sonst nirgendwo etwas gefunden. Kann mir da vllt. jemand weiterhelfen?

...zur Frage

Binäre Suche: Iterativ vs rekursiv?

Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?

public static int binarySearchIterative(int[] a, int z) {
  int left = 0;
  int right = a.length - 1;

  while (left <= right) {
    int midpoint = (int)((left + right) / 2);

    if (z == a[midpoint]) {
      return midpoint;
    }

    if (z < a[midpoint]) {
      right = midpoint - 1;
    }
    else {
      left = midpoint + 1;
    }
  }

  return -1;
}

public static int binarySearchRecursive(int[] a, int z, int left, int right) {
  int midpoint = (int)((left + right) / 2);

  if (right < left) {
    return -1;
  }

  if (z == a[midpoint]) {
    return midpoint;
  }

  if (z < a[midpoint]) {
    return binarySearchRecursive(a, z, left, midpoint - 1);
  }
  else {
    return binarySearchRecursive(a, z, midpoint + 1, right);
  }
}

...zur Frage

Java Binary Tree Remove Methode implementieren?

Hey Leute,
Ich versuche folgende Binary Tree Methode zu implementieren:

public void remove(T data) {
    root = remove(root, data);
}

private Nodes<T> remove(Nodes<T> root, T data) {
    Nodes<T> current = root;
    if (current == null) {
        return current;
    }
    if (current.getData().compareTo(data) > 0) {
        current.getLeftChild() = remove(current.getLeftChild(), data);
    } else if (current.getData().compareTo(data) < 0) {
        current.getRightChild() = remove(current.getRightChild(), data);
    } else {
        if (current.getLeftChild() == null && current.getRightChild() == null) {
            current = null;
        } else if (current.getRightChild() == null) {
            current = current.getLeftChild();
        } else if (current.getLeftChild() == null) {
            current = current.getRightChild();
        } else {
            Nodes<T> temp = findMinFromRight(current.getRightChild());
            current.getData() = temp.getData();
            current.getRightChild() = remove(current.getRightChild(), temp.getData());
        }
    }
    return current;
}

Er zeigt mir bei folgenden Abschnitten "Variable expected" an, aber hier sollte keine Variable erwartet werden:

if (current.getData().compareTo(data) > 0) {
    current.getLeftChild() = remove(current.getLeftChild(), data);
} else if (current.getData().compareTo(data) < 0) {
    current.getRightChild() = remove(current.getRightChild(), data);

...

 else {
    Nodes<T> temp = findMinFromRight(current.getRightChild());
    current.getData() = temp.getData();
    current.getRightChild() = remove(current.getRightChild(), temp.getData());
}

Danke schonmal für eure Hilfe!

...zur Frage

Kann mir jemand einen rekursiven Pseudocode in einer rekursiven Java Methode umwandeln?

Das ist der Pseudocode , und denn will ich in einer Java Methode umwandeln , kann mir das jemand sagen , und erklären was der unterschied ist

func (n)
begin
if (n<=2)
return n;
else
return 2* func (n-1) - func (n-2);

...zur Frage

Was ist die saubere Form bei einem if-statement ohne else?

Die Frage ist recht simpel. Was ist die saubere Form eines if-statements ohne else?

Was ich normalerweise machen würde, wäre das:

if("Bedingung") { 
    "mach etwas"
}

Aber ich habe von einem Freund gehört, dass das nicht die saubere Variante davon wäre. Besser wäre, wenn man am Ende else hinschreibt ohne dass es etwas macht:

if("Bedingung") { 
    "mach etwas"
} else {
    
}

Was ich auch schon mal gesehen habe, ist die 2 Variante mit einem return im else

if("Bedingung") { 
    "mach etwas"
} else {
    return;
}

Was wäre "offiziell" die richtige Variante?

Cheers
Luke

...zur Frage

Durchschnitt mit Arrays berechnen (Java), aber wie?

Ich habe bereits an meinem Programm gearbeitet, bekomme aber immer wirre Endergebnisse raus. Warum?

Hier mein Code:

//Eingabe: 3; 3; 3; 0;

// Bei "0" soll er abbrechen;

void setup(){

int i = 1;

float[] a = new float[99];

do{

float input = Popup.readFloat("");

if(input

a[i] = input;

i = i+l;

0){break;}else{ ==

}

}while(a[i-1]!=0);

println(durchschnitt(a));

}

float durchschnitt(float[] a){

int laenge = a.length;

float durchschnitt - 0;

for (int i = 1; i <= laenge; i++){

durchschnitt = durchschnitt + a[i-1];

}

return durchschnitt / a.length;

}

Das Ergebnis:

...zur Frage

Rekursive Methode zum finden einer Zahl im Array?

Moin, ich habe die Aufgabe bekommen, eine rekursive Methode sucheZahlRek(int Suchzahl) zu schreiben, die eine übergebene Zahl finden und ausgeben soll. Dafür soll ich int[ ]arSuchfeld = {5,3,8,0,10,2,6,1} als Array verwenden. Ist die gesuchte Zahl nicht vorhanden, kommt eine entsprechende Meldung. Dabei soll es unbedingt rekursiv programmiert werden. Kann mir jemand helfen oder zumindest einen Lösungsansatz zeigen?

Ich habe damit Probleme, weil wir das Thema Arrays nur ganz am Ende des Lockdowns mithilfe von nur einem Arbeitsblatt angeschnitten haben. Jetzt bin ich im Info-Lk und da wird das beherrschen von Arrays schon vorausgesetzt D:.

...zur Frage

Wie kann man in Excel per VBA abhängig von einem Wert Spalten aus-/einblenden?

Hey. Ich weiß zu diesem Thema gibt es schon ein paar Einträge im Netz. jedoch habe ich es nie für mich umformuliert bekommen. Vielleicht kann mir hier jemand helfen?

In Zelle G6 steht ein Wert von 1-6. Abhängig davon sollen dann immer andere Spalten ausgeblendet werden. Mein Code zur Zeit:

Sub Ausblenden()
'
' Ausblenden Makro
'
' Tastenkombination: Strg+a
'
    If "G6" = "1" Then
                Columns("v:bn").EntireColumn.Hidden = False
                Columns("v:bn").EntireColumn.Hidden = True
            Else
                If "G6" = "2" Then
                    Columns("v:bn").EntireColumn.Hidden = False
                    Columns("ae:bn").EntireColumn.Hidden = True
                Else
                    If "G6" = "3" Then
                        Columns("v:bn").EntireColumn.Hidden = False
                        Columns("an:bn").EntireColumn.Hidden = True
                    Else
                        If "G6" = "4" Then
                            Columns("v:bn").EntireColumn.Hidden = False
                            Columns("aw:bn").EntireColumn.Hidden = True
                        Else
                            If "G6" = "5" Then
                                Columns("v:bn").EntireColumn.Hidden = False
                                Columns("bf:bn").EntireColumn.Hidden = True
                            Else
                                If "G6" = "6" Then
                                    Columns("v:bn").EntireColumn.Hidden = False
                                End If
                            End If
                        End If
                    End If
                End If
    End If
End Sub

Ich bin ein VBA anfänger, also bitte seit nachsichtig x). Danke schon einmal im voraus!

...zur Frage

Java Hamster Labyrinth

Ich habe ein Problem mit folgendem Java Hamster Programm:

    void main() {
 /*class*/
 {
  if(linksFrei()) {
    vor();
  } else {
    if(vornFrei()) {
      vor();
    } else {
      rechtsUm();
    }
  }   
  if(!kornDa()) { main(); }
}

void rechtsUm(); {
  linksUm();
  linksUm();
  linksUm();
}

boolean linksFrei() {
  linksUm();
  if(vornFrei()) {
    return true;
  } 
  rechtsUm();
  return false;
}

}   
}
}

Kann mir jemand sagen, was daran flasch ist? Wäre nice.

Danke schonmal, Haribo.

...zur Frage

VBA mehrere Textboxen außer XY auf Inhalt prüfen?

Hallo zusammen,

kann man für mehrere Textboxen bis auf Ausnahmen den gleichen Inhalt prüfen?

Zu Sache: Ich habe ein Userform mit einer Multiseite mit 10 Pages. Jeder Page hat 63 Textboxen, ergo 630 Textboxen im gesamten Userform.

Von diesen 630 Textboxen muss in 620 Textboxen geprüft werden, ob diese entweder leer sind oder eine Uhrzeit steht. Wenn dieses der Fall ist, dann ist alles Ok. Ansonsten soll entsprechend der Vorgang abgebrochen werden.

Die 620 Textboxen haben alle individuelle Namen wie (AN1t1a, AN1t1e, AN1t2a usw.) Dies ist nach einem bestimmten Muster.

Die restlichen Textboxen, die NICHT geprüft werden sollen haben Namen wie (AN_Name1, AN_Name2, AN_Name3 usw. bis 10).

Wie können nun alle 620 Textboxen auf folgendes Format geprüft werden:

Private Function CheckTime(ByVal txt As String) As Boolean

If txt.Length <> 5 or txt.Length <> 0 Then
Return False
End If

If txt(0) >= "3" Then
Return False
End If

If txt(0) = "2" AndAlso txt(1) >= "4" Then
Return False
End If

If txt(2) <> ":" Then
Return False
End If

If txt(3) = "0" AndAlso txt(4) <> "0" Then
Return False
End If

If txt(3) = "1" AndAlso txt(4) <> "5" Then
Return False
End If

If txt(3) = "2" Then
Return False
End If

If txt(3) = "3" AndAlso txt(4) <> "0" Then
Return False
End If

If txt(3) = "4" AndAlso txt(4) <> "5" Then
Return False
End If

If txt(3) > "4" Then
Return False
End If

Return True
End Function

Falls die Prüfung auf die korrekte Uhrzeit fehlerhaft ist oder auch einfacher geht, nehme ich die Hilfe auch gerne an :) Erlaubte Uhrzeiten sollen im Forma HH:MM sein und im Viertelstunden Takt (10:00, 10:15, 10:30, 10:45) erlaubt sein. Nur Zahlen sind nicht möglich, da es auch einen Doppelpunkt gibt ;)

Gruß

...zur Frage

Java Zahl erraten Methode?

Ich versuche gerade eine Methode zu schreiben bei der der Computer die Zahl d erraten muss es kommen jedoch immer nur Zahlen die ungefähr d entsprechen heraus und ich finde den Fehler nicht Ich hoffe jemand kann mir helfen.

a ist die untere Grenze des Ratebereichs und b die obere.

public class raten{
    int d = 11;
        public int raten(int a, int b){
        int c = (int) (Math.random()*b+a);
        if(c < d){
            return raten(c,b);
        }
        else if(c > d){
            return raten(a,c);
           }
        else{
            return a;
        }
    }
}

...zur Frage

Java: Rekursion mit String-Methoden?

Hallo,

wir haben momentan das Thema Rekursion und dazu habe ich eine Frage.

private String wasTueIch(String wort) {
  if (wort.length() <= 1)
    return wort;
  else
    return wasTueIch(wort.substring(1, wort.length())) + wort.charAt(0);
}

Meine Frage ist, warum die Methode rekursiv ist und wie man einen Palindromtester (Palindrom: ein Wort, welches gespiegelt die gleiche Bedeutung hat) einbauen kann.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen