Kleinere Zahlen hinzuzählen

[GericasS]

Hallo DP,

ich wollte mal fragen wie folgendes in Delphi zu realisieren ist...

ich hab zum Beispiel die Zahl 7 und möchte nun alle Zahlen die kleiner sind als 7 also von 1 (einschließlich 1 :D ) hinzuzählen daraus ergibt sich :

1+2+3+4+5+6+7

LG


GericasS :?:

[inherited]

Zwei ansätze: Iterativ:

Delphi-Quellcode:

function Summ(a: integer): Integer;
var i: integer;
begin
  result:=0;
  for i := 1 to a do
    result:=result+i;
end;

Rekursiv:

Delphi-Quellcode:

function Summ(a: Integer): Integer;
begin
  if a <=1 then
  begin
    result:=a;
    exit;
  end;
  result:=Summ(a-1)+a;
end;

Ungetestet

[sirius]

Habt ihr in der Schule grad Einführung in Rekursionen?

[GericasS]

Zitat:

Zitat von sirius

Habt ihr in der Schule grad Einführung in Rekursionen?

Nein ich will in Delphi ein Beispiel für digitale Abschreibung erstellen :D

Zitat:

Zitat von inherited

Zwei ansätze: Iterativ:

Delphi-Quellcode:

function Summ(a: integer): Integer;
var i: integer;
begin
  result:=0;
  for i := 1 to a do
    result:=result+i;
end;

Rekursiv:

Delphi-Quellcode:

function Summ(a: Integer): Integer;
begin
  if a <=1 then
  begin
    result:=a;
    exit;
  end;
  result:=Summ(a-1)+a;
end;

Ungetestet

danke werds gleich mal versuchen :D

[Nikolas]

Und wo bleibt der Resourcenschonende Ansatz? (Green IT und so...)

Delphi-Quellcode:

function Summ(n: integer): Integer;
begin
result = n*(n+1)/2.0;
end;

[himitsu]

so ist das Rechenergebnis eine Fließkommazahl und kein Integer:
also müßte man es noch umwandeln
[add]ohhh und Vergleich statt Zuweisung ... kein ":" :shock: [/add]

Delphi-Quellcode:

function Summ(n: integer): Integer;
begin
  result := Round(n * (n + 1) / 2.0);
end;

oder besser glich bei Integer bleiben:

Delphi-Quellcode:

function Summ(n: integer): Integer;
begin
  result = n * (n + 1) div 2;
end;

aber ich hab noch'n paar Löungen mit Schleifchen :angel:

Delphi-Quellcode:

// Result=0 wenn n negativ
function Summ(n: integer): Integer;
begin
  Result := 0;
  while n >= 1 do
  begin
    Inc(Result, n);  //Result := Result + n;
    Dec(n);
  end;
end;

Delphi-Quellcode:

// Result=n wenn n negativ
function Summ(n: integer): Integer;
begin
  Result := 0;
  repeat
    Inc(Result, n);  //Result := Result + n;
    Dec(n);
  until n < 1;
end;

[sirius]

Zitat:

Zitat von Nikolas

Und wo bleibt der Resourcenschonende Ansatz? (Green IT und so...)

Womit bewiesen wäre, dass Gauss ein Grüner war.

[Nikolas]

Zitat:

[add]ohhh und Vergleich statt Zuweisung ... kein ":"[/add]

Seit dem ich an meinem schönen weißen iBook arbeite, sind meine Syntaxkenntnisse etwas eingeschlafen...
Python ist so eine schöne Sprache und da sinds eben die ==-Vergleiche.

[DP-Maintenance]

Dieses Thema wurde von "Matze" von "Programmieren allgemein" nach "Sonstige Fragen zu Delphi" verschoben.
Delphi-Frage

[GericasS]

Zitat:

Zitat von Nikolas

Und wo bleibt der Resourcenschonende Ansatz? (Green IT und so...)

Delphi-Quellcode:

function Summ(n: integer): Integer;
begin
result = n*(n+1)/2.0;
end;

bist du selbst auf diese Formel gekommen oder ist die schon iwo festgelegt ? :zwinker:

[Nikolas]

Das ist doch offensichtlich :roll:

Nein. Das ist so ziemlich die Standardaufgabe, um die Beweistechnik der Vollständigen Induktion einzuführen. 'Festlegen' kann man da nichts :lol: Entweder es ist so, oder nicht.

Die Idee ist eigentlich recht einfach: Zahlen von 1 bis 10:

Code:

1+2+3+...+10=
1 + 2 +3 +4 +5+
10+ 9 +8 +7 +6 =
_________________
11+11+11+11+11 = (10+1)*(5)=(n+1)(n/2)

[sirius]

Zitat:

Zitat von GericasS

Zitat:

Zitat von Nikolas

Und wo bleibt der Resourcenschonende Ansatz? (Green IT und so...)

Delphi-Quellcode:

function Summ(n: integer): Integer;
begin
result = n*(n+1)/2.0;
end;

bist du selbst auf diese Formel gekommen oder ist die schon iwo festgelegt ? :zwinker:

Das sind in der Mathematik "endliche Reihen" :zwinker: Such einfach mal danach

[inherited]

Und ein wunderbares Beispiel für Vollständige Induktion ;)
(Hab jetzt keine Zeit, können wir heut abend mal beweisen)

[taaktaak]

quod erat demonstrandum - huhuhu, verdammt lange her :mrgreen:

[sirius]

Zitat:

Zitat von taaktaak

quod erat demonstrandum - huhuhu, verdammt lange her :mrgreen:

Heute schreibt man doch "nur" noch
w.z.b.w.
darunter

[GericasS]

@sirius : danke für den Link habs verstanden ! :thumb: :stupid:

[inherited]

Zu beweisen: 1+2+3+...+n = n(n+1)/2
Induktionsanfang für n=1:
1 = 1(1+1)/2 = 1 (r.)
n=2:
1+2 = 2(2+1)/2 = 3 (r.)

Induktionsannahme:
Unter der Vorraussetzung dass für alle n >= 1 gilt
1+2+3+...+n = n(n+1)/2

Induktionsschluss
1+2+3+..+n+ (n+1) = (n(n+1)/2) +(n+1)
= (n(n+1)/2) +2(n+1)/2 = (n(n+1)+2(n+1))/2 = ((n+1)(n+2))/2 qed
(Im letzten Schritt n+1 ausgeklammert)


(Daniel will uns ja keine LaTeX-tags geben :( )

[Nikolas]

Ich glaube, du hast die Beweisidee noch nicht ganz verstanden.

Zitat:

Induktionsannahme:
Unter der Vorraussetzung dass für alle n >= 1 gilt
1+2+3+...+n = n(n+1)/2

Diese Vorraussetzung muss nicht erfüllt sein, da du sie noch nicht gezeigt hast, d.h. du darfst daraus nichts folgern.
Dein Satz lautet: Unter der Vorraussetzung, dass der Satz richtig ist, folgt, dass der Satz richtig ist.



Du müsstest so argumentieren:

Zitat:

Sei n eine natürliche Zahl, für die die Aussage gilt. (dass es mindestens so eine Zahl gibt, habe ich gerade gezeigt, in dem ich es für n=1 explizit gezeigt habe.)
Jetzt zeige ich, dass die Aussage auch für (n+1) gilt: (...)

Dann setzt man gedanklich n=1 und weiss, dass die Aussage gilt (hat man ja explizit berechnet) und weiss, dass sie auch für n+1=2 gilt. Dann setzt man n=2 ein und erfährt, dass es auch für n=3 gilt. Und das kann man sich beliebig fortgesetzt denken und hat es so für alle natürlichen Zahlen gezeigt.

[inherited]

Dann ist dieser Schritt in dem Buch aus dem ich das habe falsch.
(Mathematik für Informatiker, von wem das war hab ich vergessen)
Worum es bei dem beweis geht habe ich verstanden, fand den Schritt bisher aber immer unnötig ._.

[Nikolas]

Das steht so in einem Buch? Also mit 'für alle' und nicht 'für ein'?
Welchen Schritt fandest du unnötig?

[3_of_8]

Korrekt lautet der Beweis so:

Behauptung:
n
Sigma i = n(n+1)/2
i=1

Induktionsanfang:
1
Sigma i = 1 = 1(1+1)/2
i=1

Induktionsvoraussetzung:

Die Behauptung gilt für alle n in N mit n<=k:

Induktionsschluss:

n+1
Sigma i =
i=1

n
=Sigma + n+1 = n(n+1)/2 + n+1 = (n(n+1)+2n+2)/2 = (n²+3n+2)/2 =
i=1

=(n+1)(n+2)/2

Es folgt: Gilt die Behauptung für alle n in N mit n<=k, dann gilt die Behauptung auch für alle n in N mit n<=k+1.

Es folgt die Gültigkeit der Behauptung für N.

q.e.d.

[Nikolas]

Du hast in so ziemlich allen Summen deine Laufvariable vergessen...

n
sigma = 0
i=1

Warum forderst du denn, dass die Aussage für alle k <=n gilt und was ist eigentlich dieses n? Später benutzt du nur, dass die Aussage für n gilt.

Es reicht zu fordern, dass es für ein (einziges) n in N gilt, wenn man zeigt, dass man daraus auch die Gültigkeit für n+1 zeigen kann und zusätzlich noch explizit zeigt, dass die Aussage für die 1 gilt. (oder die Null, die Formel gilt immer)

[3_of_8]

Ich hab das ganze jetzt nochmal leicht korrigiert.

Also, was ich mache ist das:
Ich beweise erst einmal, dass meine Behauptung für n=1 gilt. (Also für alle n in N mit n<=1).

Anschließend beweise ich (unter der Vorraussetzung, dass die Behauptung für alle n in N mit n<=k gilt), dass die Behauptung auch für alle n in N mit n<=k+1 gilt.

[inherited]

3_of_8: Toll, wie schön dass du das auch kannst. zufrieden?
Nikolas: Ja, und ich fand/finde die Induktionsannahme unwichtig, wobei man das so und so sehen kann.

[Nikolas]

Zitat:

Anschließend beweise ich (unter der Vorraussetzung, dass die Behauptung für alle n in N mit n<=k gilt), dass die Behauptung auch für alle n in N mit n<=k+1 gilt.

a) Warum forderst du, dass die Behauptung für alle n<=k gilt? Diese Vorraussetzung wird nicht benutzt.
b) Wer ist eigentlich dieses k?

BTW: Du zeigst nicht, dass die Behauptung für alle n<=k+1 gilt. Du zeigst ausschließlich, dass sie für n+1 (k+1?) gilt.

@ GrünFisch: Ohne diese Annahme kommst du aber nicht ans Ziel. Und wenn du etwas unter einer unbewiesenen Annahme berechnen willst, musst du die schon angeben.

[3_of_8]

@Nikolas:

Da kommt ja die Induktion ins Spiel.
k ist sozusagen die obere Schranke, für die das ganze gilt.
Beim Induktionsanfang ist k=1. Dann beweise ich, dass es, wenn es für k gilt, auch für k+1 gilt. Also wenn für k=1, dann auch für k=2, dann auch für k=3 usw. Wenn man das bis unendlich fortdenkt, ist es für {1; 2; 3;...}, also ganz N, bewiesen.

@Inherited:

Dann hast du das Verfahren wohl noch nicht so ganz verstanden. Ohne Induktionsannahme funktioniert da nämlich gar nix. Und darum hab ich es auch nochmal korrekt formuliert. ;)

[inherited]

3_of_8: Der Beweis mag ohne nicht komplett sein, aber die Aussage "ohne funktioniert da garnicht" ist schlichtweg falsch.

[Nikolas]

Zitat:

3_of_8: Der Beweis mag ohne nicht komplett sein, aber die Aussage "ohne funktioniert da garnicht" ist schlichtweg falsch.

Da hast du Unrecht. Wenn du nicht explizit vermerkst, dass du diese Annahme triffst, sondern die unbewiesene Aussage einfach benutzt, hast du im Endeffekt gar nichts gezeigt, da du einen logischen Bruch hast. Nur weil die Aussage für n=1 gilt, darfst du sie nicht allgemein einsetzen.

Zitat:

Da kommt ja die Induktion ins Spiel.
k ist sozusagen die obere Schranke, für die das ganze gilt.
Beim Induktionsanfang ist k=1. Dann beweise ich, dass es, wenn es für k gilt, auch für k+1 gilt. Also wenn für k=1, dann auch für k=2, dann auch für k=3 usw. Wenn man das bis unendlich fortdenkt, ist es für {1; 2; 3;...}, also ganz N, bewiesen.

Wie ein Induktion funktioniert, ist mir schon klar, ich habe in den ersten Semestern auch 3-4 MatheVorlesungen (also richtige, nicht die für Informatiker) gehört.

Was du hier schreibst, ist aber nicht das, was du in deinem Beweis geschrieben hast. Der Satz 'Dann beweise ich, dass es, wenn es für k gilt, auch für k+1 gilt.' ist die Kernaussage. Du betrachtest keine Menge von Zahlen, für die die Aussage gilt, sondern nur eine einzige und zeigt, dass es auch für die nächste Zahl gilt.
Deine Vorraussetzung ist zu stark und kann dir bei anderen Beweisen Ärger bringen. Bei einem Satz (ich glaube etwas über Bäume), kann man die Aussage erst für alle zweierPotenzen zeigen und dann die Induktion von n nach n-1 machen und so rückwärts induzieren.
Bei sowas hättest du dann Probleme mit deiner Vorraussetzung.