Not logged in. · Lost password · Register

Ezekiel15
Ezekiel15
Member since Oct 2015
182 posts
Subject: Vorschlag für Aufgabe 6 (Dynamische Programmierung) Altklausur SS15
  1. public class DynProg {
  2.  
  3.     private static int[] a;
  4.  
  5.     public DynProg(int max) {
  6.         this.a = new int[max];
  7.     }
  8.  
  9.     static int f(int n) {
  10.         return n < 3 ? 1 : f(n - 2 * f(n - f(n - 1))) + 1;
  11.     }
  12.  
  13.     static int fDP(int n) { // Dynamische Programmierung
  14.         int fn = 1; // Basisfall n < 3 trivial
  15.         // fn schon einmal berechnet?
  16.         if (n > 3 && n < a.length && a[n] != 0) {
  17.             return a[n];
  18.         } else if (n >= 3) {
  19.             int temp = fDP(n - 2 * fDP(n - fDP(n - 1))) + 1; // fn muss noch
  20.                                                                 // berechnet
  21.                                                                 // werden
  22.             if (n < a.length) {
  23.                 a[n] = temp;
  24.                 return a[n];
  25.             }
  26.             return temp;
  27.         }
  28.         return fn;
  29.     }
  30.  
  31.     static int fIter(int n) { // Iterativ
  32.         int k = 1; // Zaehler
  33.         int fk = 1;
  34.         for (k = 1; k <= n; k++) { //one may write instead: for(; k<=n; k++) {
  35.             for (int i = 1; i <= (1 + k) * k; i++) {
  36.                 if (i == n) {
  37.                     return fk;
  38.                 }
  39.             }
  40.             fk++;
  41.         }
  42.  
  43.         return fk;
  44.  
  45.     }
  46.  
  47.     public static void main(String[] args) {
  48.  
  49.         for (int i = 1; i <= 20; i++) { // Test f
  50.             System.out.print(f(i) + " ");
  51.         }
  52.         System.out.println();
  53.  
  54.         int max = 10;
  55.         int n = 20;
  56.         int result = new DynProg(max).fDP(n); // Test fDP
  57.         for (int i = 0; i < max; i++) { // a[0], a[1] are the trivial cases,
  58.                                         // that fDP handles itself (read
  59.                                         // exercise description)
  60.             System.out.print(a[i] + " ");
  61.         }
  62.         System.out.println();
  63.         System.out.println(result);
  64.  
  65.         for (int i = 1; i <= 20; i++) { // Test fIter
  66.             System.out.print(fIter(i) + " ");
  67.         }
  68.     }
  69. }
This post was edited on 2016-03-12, 17:18 by Ezekiel15.
Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
622 posts
Wie kommst du auf (1+k)*k in for (int i = 1; i <= (1 + k) * k; i++)?

Ich habe das so gelöst:
  1. public static int fIter(int n) {
  2.     int k = 1;
  3.     int fk = 1;
  4.        
  5.     int offset = 0;
  6.     while (k < n) {
  7.         k++;
  8.         if (k > offset + 2*fk) {
  9.             offset += 2 * fk;
  10.             fk++;
  11.         }
  12.     }
  13.    
  14.     return fk;
  15. }
Ezekiel15
Ezekiel15
Member since Oct 2015
182 posts
Ich zähle hier einfach stupide die Zahl der Terme, Gauß'sche Summenformel. Viel Magie ist da nicht dabei, das war auch das erste was mir hierzu eingefallen ist. Ich finde deine Lsg. daher auch schöner, da du (denke ich) die ganzen Terme weglässt, die ich bei mir mehrmals zähle.
This post was edited on 2016-03-14, 13:41 by Ezekiel15.
ic97usop
ehemals Chayyam
Member since Sep 2015
369 posts
Ich hätte das so gelöst:
  1. public static int fIter(int n){
  2.     int k = 1;
  3.     int fk = 1; // Den Codebereich darf man in der Klausur leider nicht löschen.
  4.     fk = 0;
  5.     while(fk < n){
  6.         fk += 2 * k;
  7.         k++;
  8.     }
  9.     return k - 1;
  10. }
Eine ruhige, sachliche und freundliche Arbeitsweise ist der Schlüssel zum Erfolg.
snoopjav
Member since Oct 2014
11 posts
In reply to post #1
Wieso brauche ich bei der Abfrage "if (n > 3 && n < a.length && a[n] != 0)" den Teil mit n < a.length?  :'(
gaku
Member since Oct 2011
693 posts
+1 snoopjav
Sollte das Array a nicht n-viele Stellen haben, dann kannst du auch nicht prüfen, ob ein größerer Wert berechnet wurde oder nicht. Beispiel:
  1. int [] a = new int[5];
  2. int n = 6;
  3. if( a[n] != 0 ){
  4.   ...
  5. }

Das wird definitiv einen ArrayIndexOutOfBounds-Fehler verursachen, weil es die gefragte Position (also das n) gar nicht im Array a gibt.
snoopjav
Member since Oct 2014
11 posts
Danke
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen