C++ Aufgabe - Wer hat einen Tipp oder weiss, wie man sowas loest?

[xound]

Hi,

folgende Aufgabe:

Schreiben Sie ein Programm, dass eine Zahl "x" einliest und alle

Reihen aus zwei oder mehr aufeinander folgenden positiven Zahlen,

deren Summe "x" ergibt, ermittelt.

Wenn also "x" zB. 15 ist, dann gibt es genau 3 Loesungen und die

Ausgabe ist:

1,2,3,4,5

4,5,6

7,8

Hat jemand ne Idee, wie man sowas macht?

Gruss,

xound

[kingofbrain]

Hallo xound,

ich hab zwar keine Musterlösung, aber vielleicht ein paar Ideen. Ist nicht garantiert, dass es funktioniert, aber so hätte ich angefangen:

Du hast eine Zahl x, die Du durch Summen aufeinanderfolgender Zahlen bilden willst. D.h. die Zahlen können nur im Bereich von 1 bis x sein. Jede dieser Zahlen ist ein potentieller Anfangswert für die Kette, also bildest Du eine Schleife über alle Zahlen von 1 bis x.

In jedem Schleifendurchlauf versuchst Du, mit dem jeweiligen Startwert eine Kette zu bilden (beim ersten Mal mit 1, dann mit 2, usw.). Du brauchst also eine zweite Schleife, die mit dem Wert i (momentaner Aufenthaltsort in der ersten Schleife) beginnt, und abbricht, wenn die Summe grösser wird, als der gesuchte Wert x. In dieser zweiten Schleife wird die Summe immer aus dem Wert der Summe und der nächsthöheren Zahl der zweiten Schleife gebildet.

Pseudocodeartig müsste es so aussehen:

i = 0

solange i <= x

    sum = 0

    j = i

    solange j < x

        sum += j

        j++

        if(j == x)

            guter Anfangswert, Kette merken

    i++

[/PHP]

Kann gut sein, dass ich jetzt was vergessen habe, aber Du willst ja auch noch was tun.

Wenn es klappt, könntest Du den richtigen Code posten. Ansonsten lass ich mich auch gerne von der Dummheit meines Ansatzes überzeugen

Peter

[Der Kleine]

Originally posted by xound

Wenn also "x" zB. 15 ist, dann gibt es genau 3 Loesungen und die

Ausgabe ist:

1,2,3,4,5

4,5,6

7,8

Wie sieht es aus mit :

1,14

1,2,12

1,3,11

1,4,10

1,2,3,9

1,5,9

usw.

Wenn du die auch in deine Betrachtungen einbeziehen willst, kann man soetwas (in meinen Augen nur rekursiv) erstellen.

Falls nicht: Wie kommst du auf genau 3 Lösungen?

Edit: (kann doch lesen) Meinst du aufeinanderfolgende Zahlen? Dann wird es etwas einfacher.

[Der Kleine]

Hier in Delphi (Übersetzen in C++ bitte selbst)

procedure Tform.Button1Click(Sender: TObject);

var

    x: Integer;            [color=blue]// // Eingabewert[/color]

    start: Integer;      [color=blue]// //aktueller Startwert[/color]

    lauf: Integer;        [color=blue]// //laufender Wert, welcher zuaddiert wird[/color]

    summe: Integer;  [color=blue]// // summe aus bisher und laufenden Wert[/color]

    j: Integer;            [color=blue]// // Laufvariable zur Ausgabe[/color]

    wert: String;        [color=blue]// // String zur Ausgabe[/color]

begin

    x:=15;

    for start:=1 to x do begin

        wert:='';

        lauf:=start+1;

        summe:=start+lauf;

        while summe < x do begin

            lauf:=lauf+1;

            summe:=summe+lauf;

        end;

        if summe=x then begin

            for j:=start to lauf do begin

                wert:=wert+inttostr(j)+' ';  [color=blue]// formatierung ordentlich[/color]

            end;

            showmessage(wert);

        end;

    end;

end;

Bei Fragen bitte Fragen.

[Klotzkopp]

Neben den "Brute-Force"-Ansätzen wie bei kingofbrain und Der Kleine ist es übrigens auch möglich, das ganze auszurechnen.

Eine Zahl n lässt sich genau dann als Summe von x aufeinanderfolgenden positiven Zahlen darstellen, wenn n geteilt durch x mindestens x/2, und, falls x ungerade ist, n modulo x gleich 0 ist, und falls x gerade ist, n modulo x gleich x/2 ist.

Beispiel: 21

21 / 2 = 11,5 reicht

21 mod 2 = 1 passt

21 / 3 = 7 reicht

21 mod 3 = 0 passt

21 / 4 = 5,25 reicht

21 mod 4 = 1 passt nicht

21 / 5 = 4,2 reicht

21 mod 5 = 1 passt nicht

21 / 6 = 3,5 reicht

21 mod 6 = 3 passt

21 / 7 = 3 reicht nicht, weil 3 < 7/2,

also gehts nicht weiter.

Mit welcher Zahl die Summe dann anfängt, kann man auch ausrechnen.

Kann aber sein, dass das durch die vielen Divisionen auch nicht schneller ist.

[Guybrush Threepwood]

Hi,

ich hab mal ne rekursive Lösung:

int rek(int ein,int wert,int i, int t)

{

	wert += i;

	if (i >= ein)

		return 0;

	if (wert < ein)

	{

		printf ("%i + ",i);

		rek(ein,wert,i+1,t);

	}

	if (wert == ein)

	{

		printf ("%i = %i\n",i,ein);

		rek(ein,0,t+1,t+1);

	}

	if (wert > ein)

	{

		printf ("%i > %i\n",i,ein);

		rek(ein,0,t+1,t+1);

	}

}

[/PHP]

Beim Aufruf der Funktion sollte für ein der gewählte Wert, für wert 0 und für

i und t jeweils 1 übergeben werden.

z.b.

[PHP]
rek(15,0,1,1);

Gruß

Guybrush

[xound]

danke fuer die zahlreichen antworten jungs. ich werde mich mal gleich damit beschaeftigen und eine gesamtloesung hier veroeffentlichen.

gruss,

xound

[xound]

so hab mal ein wenig rumprobiert, aber irgendwas stimmt da noch nicht. kann jemand den folgenden code mal ueberfliegen und mir sagen, wo die fehler liegen?

#include <iostream>

#include <stdio.h>

#include <string>

using namespace std;



int main() {


int x;  // // Eingabewert

int start; // //aktueller Startwert

int lauf; // //laufender Wert, welcher zuaddiert wird

int summe; // // summe aus bisher und laufenden Wert

int j;  // // Laufvariable zur Ausgabe

string wert;  // // String zur Ausgabe


    x == 15;


    for (start = 1; start = x; start++) {

        wert = " ";

        lauf = start+1;

        summe = start+lauf;

    }   

    while (summe < x) { 

        lauf = lauf+1;

        summe = summe+lauf;

    }

    if (summe = x) {

        for (j = start; j = lauf; j++) {

                wert += inttostr(j) +" "; // Hier gibts Probleme

        }

    cout << wert;

    }

return(0);

}


[/PHP]

[Der Kleine]

Nehme mal das 'inttostr()' raus. In Java ist die spezielle Konvertierung von Integer in String nicht notwendig. Ich hoffe mal, in C++ auch nicht.

In Delphi ist es notwendig.

Ansonsten nach der richtigen Konvertierungsfunktion suchen.

[xound]

hm, hab ich gemacht - aber eigentlich .. hmm .. passiert da gar nichts dann :-)

ich muss nochmal die schleifen kontrollieren

[Der Kleine]

#include <iostream>

#include <stdio.h>

#include <string>

using namespace std;



int main() {


int x;  // // Eingabewert

int start; // //aktueller Startwert

int lauf; // //laufender Wert, welcher zuaddiert wird

int summe; // // summe aus bisher und laufenden Wert

int j;  // // Laufvariable zur Ausgabe

string wert;  // // String zur Ausgabe


    x == 15;


    for (start = 1; start = x; start++) {

        wert = " ";

        lauf = start+1;

        summe = start+lauf;


        while (summe < x) { 

        lauf = lauf+1;

        summe = summe+lauf;

        }

        if (summe = x) {

              for (j = start; j = lauf; j++) {

                   wert += inttostr(j) +" "; // Hier gibts Probleme

               }

        cout << wert;

        }

   }

   return(0);

}

Die erste schliessende geschweifte Klammer zu früh gesetzt. Sie müßte vor dem 'return(0)' kommen.

[xound]

hm, aendert sich immer noch nichts am verhalten ....

was fuer ne ausgabe gibts denn da in delphi?

[Klotzkopp]

Also...

string wert; // // String zur Ausgabe

Den brauchst du gar nicht.

x == 15;

Das muss x = 15; heißen. Du willst ja eine Zuweisung machen, keinen Vergleich, dessen Ergebnis du dann ignorierst.

for (start = 1; start = x; start++) {

Eine for-Schleife wird solange ausgeführt, wie die Bedingung wahr ist. Das müsste also start != x (oder start < x) lauten. Kein Fehler, aber trotzdem ein guter Rat: Wenn es keinen Grund für start++ gibt, nimm ++start.

if (summe = x) {

Hier muss es jetzt == heißen, denn hier willst du einen Vergleich machen, keine Zuweisung.

for (j = start; j = lauf; j++) {

Hier machst du wieder eine Zuweisung, wo ein Vergleich hingehört, und noch dazu steht der falsche Vergleich da. Das gleiche wie oben, die Schleife läuft, solange die Bedingung wahr ist. Hier muss <= hin.

wert += inttostr(j) +" "; // Hier gibts Probleme

Mach doch einfach cout << j << " ";

cout << wert;

Und hier brauchst du dann nur noch einen Zeilenumbruch: cout << endl;

[xound]

alles klar - vielen vielen dank fuer die hilfe!!

gruss,

xound

[Der Kleine]

procedure Tform1.Button1Click(Sender: TObject);


var

    x: Integer;            [color=blue]// Eingabewert[/color]

    start: Integer;      [color=blue]//aktueller Startwert[/color]

    lauf: Integer;        [color=blue]//laufender Wert, welcher zuaddiert wird[/color]

    summe: Integer;  [color=blue]// summe aus bisher und laufenden Wert[/color]

    j: Integer;            [color=blue]// Laufvariable zur Ausgabe[/color]

    wert: String;        [color=blue]// String zur Ausgabe[/color]

begin

    x:=15;                              [color=blue]//Startwert x=15[/color]

    for start:=1 to x do begin         [color=blue]// beginne start bei eins

                                             ende bei 15 und mache folgendes "For1"[/color]

        wert:='';                      [color=blue]// Setze  Ausgabevariable auf leer[/color]

        lauf:=start+1;                  [color=blue]// lauf ist die variable, 

                                             die erhöht wird, ausgehend von start[/color]

        summe:=start+lauf;              [color=blue]// Summe ist die Summe 

                                                  vom start bis lauf[/color]

        while summe < x do begin     [color=blue] // solange summe 

                                                 < als endwert x ist mache folgendes "While1"[/color]

            lauf:=lauf+1;                [color=blue]// erhoehe lauf um 1 [/color]

            summe:=summe+lauf;           [color=blue]// ermittle neue summe 

                                                   aus alter summe + lauf[/color]

        end;                              [color=blue]//ende der while1-Schleife [/color]

        if summe=x then begin            [color=blue]// Wenn die Summe

                                                  genau den endwert entspricht (also 15) 

                                                      dann Ausgabe[/color]

            for j:=start to lauf do begin  [color=blue]// Ausgabe aller zahlen

                                                          vom start bis lauf 

                                                (also aktuellen Startwert bis aktuellen Endwert)[/color]

                wert:=wert+inttostr(j)+' '; [color=blue]// formatierung des 

                                                            Ausgabestring wert[/color]

            end;                           [color=blue]// Ende der Ausgabe - For Schleife[/color]

            showmessage(wert);              [color=blue]// Ausgabe [/color]

        end;                                [color=blue]// Ende der Ausgabe 

                                                   - wenn summe genau x war [/color]

    end;                                [color=blue]// ende der for1 - Schleife   [/color]

end;                                    [color=blue]// ende der procedure  [/color]

Also erste Variable läuft von 1 bis 15 Zweite Variable läuft ausgehend von erster bis Summe >=15 Wenn Summe = 15 war, dann erfolgt Ausgabe. Ausgabe: Zum String Wert werden alle Zahlen von erster Variable (start) bis zur letzten Variable (lauf) dazugepackt und das Leerzeichen ' ' zur Formatierung. Ausgabe ist, wie oben verlangt : "1 2 3 4 5" "4 5 6" "7 8" jeweils als String in einer Messagebox (Befehl "showmessage();") Aber ich glaube, den Algorthmus hast du verstanden. Dann muß es wohl am Code liegen. Wie sieht es mit der Compelierung aus? Läuft das Programm bis zum Ende? Kannst du Schrittweise die Werte der Variablen (Einzelschrittmodus) überprüfen? Ist die Ausgabe

cout << wert

korrekt in C++ ? (Dette weiss ich nun wirklich nicht.)

Falls ja, wird irgendetwas ausgegeben?

[Der Kleine]

OK, hat sich erledigt! :D

[xound]

sehr geile loesung, wie gesagt - und so kurz