+ Antworten
Ergebnis 1 bis 8 von 8

analytische Formel

Eine Diskussion über analytische Formel im Forum Hausaufgaben. Teil des Reallife-Bereichs; Hi, ich bin ja nun am Studieren. In Informatik sollen wir eine "analytische" Formel für die rekursive Funktion T(1) = ...

  1. #1
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201

    analytische Formel

    Hi,

    ich bin ja nun am Studieren. In Informatik sollen wir eine "analytische" Formel für die rekursive Funktion T(1) = 1, T(2n hoch n) = 2 T(2 hoch n-1) + 1 herleiten. Das ist weiter nicht das Problem:

    T(2^n) = 2 * (2^n + 2^(n-1) + 2^(n-2)… + 1) + 1

    = 2 * Summenzeichen von i=0 bis n von 2^(n-i) ) + 1

    Meine Frage: Ist dies eine analytische Formel oder muss ich das Summenzeichen noch in einen Ausdruck, der nur von n abhängt zerlegen?

    Thx schon jetzt für eure Antworten.
    ]

  2. #2
    Space Cowboy
    Avatar von Macross
    Registriert seit
    10.02.2005
    Ort
    Tokyo, Kasai
    Alter
    33
    Beiträge
    7.340
    Name
    Kurisu
    Nick
    Macross/Paladin
    Clans
    3 2 1 Hasselhoff
    gibt es nicht Mathe Foren? Da wird einem mit sicherheit besser geholfen als in nem game Forum

  3. #3
    Hier gibt es doch ebenso Studenten, welche ein Mathestudium belegt haben, oder in ihrem Studium regelmäßig von der Mathematik begleitet werden (z.B. Physiker).

    Wie habt ihr denn analytische Formeln definiert ?
    Als analytische Funktion oder als eine Funktion welche das Ergebnis von F ohne Rekursion bestimmt ?

    Ist n ein Element der natürlichen Zahlen ?
    Ist T nur für 1 und 2*n^n (mit n Element der natürlichen Zahlen) definiert ?

  4. #4
    Administrator
    Avatar von Mooff
    Registriert seit
    02.08.2002
    Ort
    Mooff VI
    Beiträge
    25.425
    Nick
    Mooffs
    Ich denke du musst das Summenzeichen noch wegbekommen.

  5. #5
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201
    Denke, ich hab´s nun. Siehe Anhang. Meint ihr, das passt so?



    Warum ist .doc als Format für den Anhang erlaubt und docx nicht? grrr^^
    Angehängte Dateien Angehängte Dateien
    • Dateityp: zip 18.zip (9,6 KB, 11x aufgerufen)
    ]

  6. #6
    Nur ist die Formel falsch.

    Rekursion:
    T(1) = T(2^0) = 1
    T(2^1) = 2 * T(1) + 1 = 3

    Deine Formel:
    T(2^1) = 4 * ( 1 * ( 1 + 1) / 2) + 1 = 4 * 1 + 1 = 5 =!= 3
    Es könnte auch sein, das du dort 2 ^ x rechnest, das kann ich nicht erkennen, jedoch kommt dann immernoch 5 raus.
    T'(2^1) = 4 ^ ( 1 * ( 1 + 1) / 2) + 1 = 4^1 + 1 = 5 =!= 3

    Dein Induktionsbeweis funktoniert daher auch nur, weil schon die Summe falsch ist und deine Induktionsannahme falsch ist (der kleine Gauß beginnt bei k = 1 und nicht k = 0).
    Außerdem fehlt mir da ein wenig das + 1 in deiner Auflistung und daher ist auch die 2 nicht gut ausgeklammert, denn

    T(2^n) ist nicht
    2 * (2^n + 2^n-1 + … + 1) + 1
    sondern
    2 * (2 * ( 2 * ( 2 * ( 2 * ... (2 * 0 + 1) ... ) + 1) +1) +1) + 1) + 1

    T(2^1) ist dann also
    2 * ( 2 * 0 + 1 ) + 1 = 4 * 0 + 2 + 1 = 4 * 0 + 3 = 3
    Und T(2^2) ist dann
    2 * (2 * ( 2 * 0 + 1 ) + 1) + 1 = 4 * ( 2 * 0 + 1 ) + 3 = 8 * 0 + 4 + 3 = 7
    Und T(3^2) ist dann
    2 * (2 * (2 * ( 2 * 0 + 1 ) + 1) + 1) + 1 = 4 * (2 * ( 2 * 0 + 1 ) + 1) + 3 = 8 * ( 2 * 0 + 1 ) + 1) + 7 = 16 * 0 + 8 + 4 + 2 + 1 = 15

    Und nochmal deutlicher aufgelistet:
    T(2^0) = 2^0
    T(2^1) = 2^0 + 2^1
    T(2^2) = 2^0 + 2^1 + 2^2
    T(2^3) = 2^0 + 2^1 + 2^2 + 2^3
    T(2^4) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4
    T(2^5) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5
    T(2^6) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6
    T(2^7) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7
    T(2^8) = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8

    Man könnte es jetzt mit den Binärzahlen vergleichen, da immer alle addiert werden und wir wissen, dass
    2^3 + 2^2 + 2^1 + 2^0 = 2^4 - 1
    ist
    also ist deine gesuchte Formel

    2^(n+1) - 1

  7. #7
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201
    Danke dir, Osbes. Hatte einen Denkfehler drin, weil ich 2^0 nicht richtig in die Summe mit einberechnet habe. Deines ist auf jeden Fall richtig. Werd das noch schnell formal aufschreiben und die Herleitung aufstellen und das passt´s. Danke
    ]

  8. #8
    Zitat Zitat von Derksowitch Beitrag anzeigen
    Denke, ich hab´s nun. Siehe Anhang. Meint ihr, das passt so?

    Warum ist .doc als Format für den Anhang erlaubt und docx nicht? grrr^^
    Nur um das aufzugreifen...weil Office 2007 ist

    Ne im Ernst...es hat einfach vor dir noch nie jemand gebraucht ^^

+ Antworten

Ähnliche Themen

  1. Formel 1-Thread
    Von asunflash im Forum Sport Forum
    Antworten: 20
    Letzter Beitrag: 08.03.2004, 16:41
  2. der neue formel 1 weltmeister
    Von HaLfLiFe im Forum Sport Forum
    Antworten: 51
    Letzter Beitrag: 01.10.2003, 00:31
  3. Neue Formel-1 Regeln ==> mehr Spannung?
    Von FiX im Forum OFF-Topic
    Antworten: 30
    Letzter Beitrag: 03.11.2002, 16:09
  4. Interesse An Formel 1 Forum???
    Von Jörg im Forum OFF-Topic
    Antworten: 44
    Letzter Beitrag: 16.10.2002, 16:28
  5. Wer wird Formel 1 Weltmeista
    Von fert im Forum OFF-Topic
    Antworten: 22
    Letzter Beitrag: 19.07.2002, 09:28

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •