Torkelndes Rentier?

Hier ist die Aufgabe:

Bild zum Beitrag

Das habe ich soweit:

public static long waysHome(int length, int x, int y) {

if (x == length && y == 0) { // Base case: reached the end

return 1;

} else if (x > length || y < 0 || y > (length - x)) { // Edge case: exceeded the boundary

return 0;

} else {

// Recursive case: count the number of ways to reach the end by going right and swaying left or right

return waysHome(length, x + 1, y) + waysHome(length, x + 1, y + 1) + waysHome(length, x + 1, y - 1);

}

Leider funktioniert es nicht. Wäre cool, wenn ihr mir hilft .

1 Antwort

petermaier11

16.01.2023, 16:08

Ich vermute, der Fehler liegt in dieser Zeile:

return waysHome(length, x + 1, y) + waysHome(length, x + 1, y + 1) + waysHome(length, x + 1, y - 1);

Genauer gesagt ist der erste Funktionsaufruf zu viel. Er schwankt ja immer nach rechts oder links; aber der Fall, nicht zu schwanken, sondern nur vorwärts zu gehen, kommt nicht vor. Ohne diesen Term terminiert es bei mir jedenfalls.

Woher ich das weiß:Studium / Ausbildung – B.Sc., M.A., M.Sc. & Doktorand

PWolff

16.01.2023, 17:19

Terminieren müsste es auch mit diesem Fall - x erhöht sich ja in jedem Fall um 1.

petermaier11

16.01.2023, 17:34

@PWolff

Würde ich theoretisch auch sagen. Praktisch tut es das aber bei mir nicht, was ich mir nicht erklären kann.

petermaier11

16.01.2023, 17:38

@petermaier11

Wahrscheinlich wird der Rekursionsbaum zu groß.

PWolff

16.01.2023, 18:59

@petermaier11

Bei mir terminiert der Code des Fragestellers, braucht allerdings in der Größenordnung eine Minute.

(Falls es interessiert: er ruft die Funktion 2677380022-mal auf.)

PWolff

16.01.2023, 19:02

@PWolff

Wenn man hier nicht rekursiv vorgeht, sondern iterativ (Abwandlung des Pascalschen Dreiecks) kommt man mit 144 Additionen aus.

KevinSpiegel12

Beitragsersteller

16.01.2023, 19:02

@PWolff

Also sollte ich es lassen oder wie soll ich machen?

PWolff

16.01.2023, 22:08

@KevinSpiegel12

Nimm den Summanden

waysHome(length, x + 1, y)

raus. Dann funktioniert der Code.

KevinSpiegel12

Beitragsersteller

16.01.2023, 16:11

Also sollte das waysHome(length, x + 1, y) weg aus der return

petermaier11

16.01.2023, 16:23

@KevinSpiegel12

Genau.

Ähnliche Beiträge

Wie kann ich dieses switch-case in if umwandeln?

Hallo,

meine Aufgabe lautet, dass ich dieses switch-case in if-Verzweigungen umwandeln soll:

int choice = 2;

switch (choice) {
  case 1:
  case 2:
    System.out.print("Feuer");
    break;
  case 3:
    System.out.print("Luft");
    break;
  default:
    System.out.print("ungültig");
}

Und meine if-Verzweigung sieht so aus:

public class choice {
  public static void main(String[] args) {
    int choice = 2;

    if (choice >= 1) {
      System.out.println("Feuer");
      return;
    }

    if (choice == 2) {
      System.out.println("Feuer");
      return;
    }

    if (choice <= 3) {
      System.out.println("Luft");
      return;
    }
    else {
      System.out.println("ungueltig");
    }
  }
}

Aber beim Ausführen gibt er mir trotz Luft und else (ungültig) bei allen Zahlen Feuer aus. Weiß jemand warum?

...zum Beitrag

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);
  }
}

...zum Beitrag

Formatierung in Euro (0,00€) wiedergeben?

Hallo,

ich habe ein Problem beim wiedergeben der Preise, Ich möchte preise in Euro Angezeigt bekommen also 0,00 und nicht anders. Meine preise werden von z.B 19 Euro im eingegebenen format 19,00 Euro zu 1900 geändert. Kann mir jemand die Lösung zeigen?

Die Methoden:

  public static void currencyTXT(TextView text, String nomninal, Context context) {
    SettingPreference sp = new SettingPreference(context);
    if (nomninal.length() == 1) {
        text.setText(nomninal + " " + sp.getSetting()[0]);
    } else if (nomninal.length() == 2) {
        text.setText(nomninal + " " + sp.getSetting()[0]);
    } else {
        Double getprice = Double.valueOf(nomninal);
        DecimalFormat formatter = new DecimalFormat("#,###,##");
        String formattedString = formatter.format(getprice);
        text.setText(sp.getSetting()[0] + formattedString.replace(".",","));
    }
}

...zum Beitrag

Java Strings mischen?

Hallo, Ich habe hier zwei Strings:

String a = "QWERTZU";
String b = "abc";
boolean append = false;

Wenn append true ist soll es einmal gemischt werden: "QaWbEcRTZU";
Wenn es false ist dann = "QaWbEcRaTbZcUa";

Mein Versuch:

private static String zippStrings(String text1, String text2, boolean append) {
    String result = "";
    int len = text1.length();
    if (text2.length() > text1.length()) {
        len = text2.length();
    }
for (int i = 0; i <= len; i++) {
    if (text1.length() > text2.length()) {
        text2 += " ";
    } else if (text2.length() > text1.length()) {
        text1 += " ";
    }
    result += text1.charAt(i);
    result += text2.charAt(i);
}
return result;

}

...zum Beitrag

Quicksort "Code" erklären?

Hi Leute, ich habe ein Problem mit Quicksort code und zwar ich verstehe wie das irl gemacht wird aber für mich ist der Code schwer zu verstehen. Kann mir bitte jemand diesen Code erklären?

public class QuicksortSimple {

  public void sort(int[] elements) {
    quicksort(elements, 0, elements.length - 1);
  }

  private void quicksort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left >= right) return;

    int pivotPos = partition(elements, left, right);
    quicksort(elements, left, pivotPos - 1);
    quicksort(elements, pivotPos + 1, right);
  }

  public int partition(int[] elements, int left, int right) {
    int pivot = elements[right];

    int i = left;
    int j = right - 1;
    while (i < j) {
      // Find the first element >= pivot
      while (elements[i] < pivot) {
        i++;
      }

      // Find the last element < pivot
      while (j > left && elements[j] >= pivot) {
        j--;
      }

      // If the greater element is left of the lesser element, switch them
      if (i < j) {
        ArrayUtils.swap(elements, i, j);
        i++;
        j--;
      }
    }

    // i == j means we haven't checked this index yet.
    // Move i right if necessary so that i marks the start of the right array.
    if (i == j && elements[i] < pivot) {
      i++;
    }

    // Move pivot element to its final position
    if (elements[i] != pivot) {
      ArrayUtils.swap(elements, i, right);
    }
    return i;
  }

}

...zum Beitrag

In Java bestimmte Werte aus einem Array in Indexvariable eines neuen Arrays speichern?

Hallo,

ich habe gerade das Problem, dass ich an einer Aufgabe sitze, bei welcher man ein Neues Feld erzeugen soll in welchem die Werte aus einem vorgegebenen Feld so eingefügt werden, dass alle negativen Zahlen im linken Bereich und alle postiven Zahlen sowie 0 im rechten Bereich liegen. Gegeben ist folgender Code:

public static int randomInt(int a, int e) {
    return (int) (Math.random() * ((e - a) + 1)) + a;
}

public static void fuellen(int[] feld, int a, int e) {
    for (int i=0;i<feld.length;i++){
        feld[i] = randomInt(a,e);
    }
}

public static void ausgeben(int[] feld){
    for (int i=0;i<feld.length;i++){
        System.out.printf("%3d ", feld[i]);
        if ((i+1) % 10 == 0) {
            System.out.println();
        }
    }
    System.out.println();
}

bis Jetzt war mein Ansatz dieser hier:

public static int[] verteilen(int[] feld){
    int[] feld2 = new int[feld.length];
    int first = feld2[0];
    int last = feld2[feld2.length - 1];
    int count = 0;
    int right = feld2.length - 1;
    for(int i=0;i<feld.length;i++) {
        if(feld[i] < 0) {
            first = feld[i];
            count++;
        }
        else {
            last = feld[i];
            right--;
        }
    }
    return feld2;
}

und als Ergebnis soll das rauskommen aber irgendwie klappt es nicht:

39-34 76-84-79-61-59-50 96 55 -71-51-89 77 64 93-20-86 43 33

-34 -84 -79 -61 -59 -50 -71 -51 -89 -20
-86  33  43  93  64  77  55  96  76  39

...zum Beitrag

Python Code unsauber?


bool_again1 = True
bool_again2 = True

while bool_again1:

    bool_again2 = True

    while bool_again2:
        int_operator = int(input("Do you want to add(1), subtract(2), multiply(3) or divide(4) two numbers: "))

        if int_operator < 1 or int_operator > 4:
            print("Invalid Input")
        else:
            bool_again2 = False

    bool_again2 = True

    int_number1 = int(input("First number: "))
    int_number2 = int(input("Second number: "))

    match int_operator:
        case 1:
            print("The solution is: ", int_number1 + int_number2)
        case 2:
            print("The solution is: ", int_number1 - int_number2)
        case 3:
            print("The solution is: ", int_number1 * int_number2)
        case 4:
            print("The solution is: ", int_number1 / int_number2)

    while bool_again2:
        int_again = int(input("Do you want to use the calculator again ( Yes(1), No(2) ): "))

        if int_again == 1:
            bool_again2 = False
        elif int_again == 2:
            bool_again1 = False
            bool_again2 = False
        elif int_again != 1 or int_again != 2:
            print("Invalid Input")

Ich bin ziemlich neu bei der Programmierung und habe dieses einfache Rechenprogramm geschrieben. Allerdings möchte ich erfahrenen Programmierer fragen, wie ich diesen Code besser schreiben könnte oder ob er ok ist, da er meiner Meinung nach sehr unsauber aus sieht (durch die vielen verschiedenen "again" Variabelen, etc)

Danke

...zum Beitrag

wie kann ich durch einen baum iterieren Java?

package ListenInJava.Baume;


public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;


    TreeNode(int data){
        this.data = data;
        this.left = null;
        this.left = null;
    }
}





package ListenInJava.Baume;


public class Tree {
    TreeNode root;


    Tree (){
        root = null;
    }


    public void add(int data){
        TreeNode t1 = new TreeNode(data);
        if(root == null){
            root = t1; 
            return;
        }
        TreeNode help = root;
        while(help != null){
            if(help.data > t1.data){
                
                if(help.left == null){
                    help.left = t1;
                    return;
                }
                help = help.left;
            } else{
                if(help.right == null){
                    help.right = t1;
                    return;
                }
              help = help.right;   
            }
        }
        return;
    }


 
}

ich möchte dann den baum in form von:

root

left right

usw. haben, aber wie genau könnte ich denn durch den baum iterieren mit einer schleife?

...zum Beitrag

Java - Benutzereingabe auf Zahlen überprüfen?

public boolean onlyNumbers(String eingabe) {
    String regex = "[a-zA-Z]+";                             
    if (Pattern.matches(regex, eingabe)) {
        return true;
    } else {
        return false;
    }
}

Gibt eine simple Methode wie man die Eingabe überprüfen kann ob ausschließlich Zahlen darin vorkommen (vergleichbar mit dem Beispielcode oben mit String)?

...zum Beitrag

Java void-Methode: If return, oder If else. Was ist professioneller?

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?

...zum Beitrag

Findet ihr den Taschenrechner gut?

Hey ich habe gerade einfach spontan nach paar Videos Java lernen zum ersten mal mein eigenes Programm erstellen wollen und hab mal versucht einen Taschenrechner der + - / * ausführen kann zu machen, findet ihr den Code ok?

import java.util.Scanner;
public class Calc {
    public static void main (String[] args){
        Scanner scan = new Scanner(System.in);
        int zahl;
        int operation;
        int zahl2;
        int ergebnis = 0;
        int wiederholung = 1;

        while (wiederholung == 1) {

            System.out.println("Tippen sie eine Zahl ein");
            zahl = scan.nextInt();
            System.out.println("Welche Operation möchten sie durchführen? - (0) + (1) / (2) * (3)");
            operation = scan.nextInt();
            if (operation == 0) {
                System.out.println("Mit welcher Zahl möchten sie subtrahieren?");
            } else if (operation == 1) {
                System.out.println("Mit welcher Zahl möchten sie addieren?");
            } else if (operation == 2) {
                System.out.println("Mit welcher Zahl möchten sie dividieren?");
            } else if (operation == 3) {
                System.out.println("Mit welcher Zahl möchten sie multiplizieren?");
            }
            zahl2 = scan.nextInt();
            if (operation == 0) {
                ergebnis = zahl - zahl2;
            } else if (operation == 1) {
                ergebnis = zahl + zahl2;
            } else if (operation == 2) {
                ergebnis = zahl / zahl2;
            } else if (operation == 3) {
                ergebnis = zahl * zahl2;
            }
            System.out.println("Hier ist ihr Ergebnis: " + ergebnis + " ...möchten sie weitere Berechnungen durchführen? ja (1) nein (2)");
            wiederholung = scan.nextInt();
            if (wiederholung == 2) {
                System.out.println("Programm wird beendet");
                break;
            } else if (wiederholung == 1) {
                System.out.println("Super!");
            }
        }

...zum Beitrag

Wieso gibt die Methode eine falsche Ausgabe?

Hallo,

Das ist die Method, die überprüft ob das Jahr ein Schaltjahr ist. Ich habe sie getestet und sie funktioniert richtig aber innehalb eine switch case statement doch nicht (Es wird immer true züruck gegeben) und deshalb wird die else Statement nie ausgeführt.

Ich verstehe es nicht wieso?

public static boolean schaltJahr(int year) {

if(year%400==0)

return true;

else if(year%100==0)

return false;

else if(year%4==0)

return true;

return false;

}

LG :)

...zum Beitrag

C++: Wie kann ich eine Abfrage für die Wiederholung meines Programms einbauen?

Ich habe einen C++-Programmcode geschrieben, welcher zwei Zahlen addiert oder subtrahiert.

Nach der Ausgabe habe ich eine Abfrage eingebaut, welche abfragt, ob man noch eine weitere Addition/Subtraktion durchführen oder das Programm beenden möchte.

Leider funktioniert das nicht, obwohl es dies eigentlich tun sollte.

Ich komme nicht mehr weiter. Vielleicht kann jemand von euch mir helfen.

Hier der C++-Code:

#include <iostream>

using namespace std;

int entscheidung() {
  cout << "Hallo" << endl;
  cout << "1 zum addieren zweier Zahlen" << endl;
  cout << "2 zum subtrahieren zweier Zahlen" << endl;
  cout << "" << endl;

  int a;
  cin >> a;
  cout << "" << endl;
  cout << "" << endl;

  return a;
}

int rechner(int a) {
  if (a == 1) {
    cout << "Eingabe zweier Zahlen" << endl;
    cout << "Diese werden addiert" << endl;
    cout << "" << endl;

    int zahl1, zahl2;
    cin >> zahl1;
    cin >> zahl2;

    int zwischenergebnis = zahl1 + zahl2;
    cout << "" << endl;
    cout << zahl1 << " + " << zahl2 << " = ";

    return zwischenergebnis;
  }
  else if (a == 2) {
    cout << "Eingabe zweier Zahlen" << endl;
    cout << "Diese werden addiert" << endl;
    cout << "" << endl;

    int zahl1, zahl2;
    cin >> zahl1;
    cin >> zahl2;

    int zwischenergebnis2 = zahl1 - zahl2;
    cout << "" << endl;
    cout << zahl1 << " - " << zahl2 << " = ";

    return zwischenergebnis2;
  }
  else {
    cout << "---FEHLER---" << endl;
  }
}

int main() {
  int zahl = entscheidung();
  int a = rechner(zahl);
  cout << a << endl;
  cout << "" << endl;
  cout << "Moechten Sie weiter machen?" << endl;
  cout << "Geben Sie die Zahl 1 ein zum --FORTSETZEN-- !" << endl;
  cout << "Gebens Sie die Zahl 0 ein zum --STOPPEN--  !" << endl;

  int b;
  cin >> b;

  if (b == 1) {
    cout << "" << endl;
    return entscheidung();
  }
  else {
    cout << "ENDE" << endl;
    return 0;
  }
}

...zum Beitrag

Hilfe bei Python-Programm (Wochentag eines Datum bestimmen)?

Ich weiß nicht was ich falsch gemacht habe, kann mir jemand den Fehler in meinem Programm nennen?:

def main():
  day = int(input("Day: "))
  month = int(input("Month: "))
  year = int(input("Year: "))
  print(day_name(day, month, year))

def day_name(day, month, year):
  months = {1 : 0,
            2 : 31,
            3 : 59,
            4 : 90,     
            5 : 120,
            6 : 151,
            7 : 181,
            8 : 212,
            9 : 243,
            10 : 273,
            11 : 304,
            12 : 334}
  days_m = 0
  if month in months:
    days_m = int(months[month])
  days_y = 0
  for y in range(year ):
  if (y % 4 == 0 and y % 100 != 0) or y % 400 == 0:
    days_y += 366
  else:
    days_y += 365

  complete_days = int(day) + int(days_m) + int(days_y)

  if int(complete_days) % 7 == 0:
    return "Sunday"
  elif int(complete_days) % 7 == 1:
    return "Monday"
  elif int(complete_days) % 7 == 2:
    return "Tuesday"
  elif int(complete_days) % 7 == 3:
    return "Wednesday"
  elif int(complete_days) % 7 == 4:
    return "Thursday"
  elif int(complete_days) % 7 == 5:
    return "Friday"
  elif int(complete_days) % 7 == 6:
    return "Saturday"
main()

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen