Arithmetische Summe in C++

21.05.2019, 21:43

Arigatoo

Auf diesen Beitrag antworten »

Arithmetische Summe in C++

Meine Frage:
Hallo zusammen,

ich versuche die Summe $\begin{eqnarray*} \sum\limits_{i=0}^{n} i \end{eqnarray*}$ zu programmieren. Der Nutzer soll eine natürliche Zahl $\begin{eqnarray*} n\in \mathbb N_0 \end{eqnarray*}$ eingeben und das Programm soll die Summe ausgeben.

Meine Ideen:
Meine Idee ist, die Summe über die Partialsumme zu berechnen: $\begin{eqnarray*} \sum\limits_{i=0}^{n} i = P(n) = P(n-1) + n \end{eqnarray*}$

Mein bisheriger Ansatz:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

#include <iostream>

int summe( int n )
{
    if ( n == 0 ) {
        return 0;
    }
    else {
        int i = 1, P_i, P_i_minus_1 = 0;
        while( i <= n ) {
            P_i_minus_1 = P_i;
            P_i = P_i_minus_1 + i;
            i++;
        }
    return P_i;
    }
}

int main()
{
    int n, S;
    
    std::cout << "Gib eine natürliche Zahl ein: ";
    std::cin >> n;
    
    S = summe( n );
    std::cout << "Die Summe der ersten " << n << " natürlichen Zahlen ist " << S << std::endl;
    }
    return 0;
}

Leider erhalte ich eine Endlosschleife... Bin dankbar für jede Hilfe! Wink

Wink

21.05.2019, 21:48

HAL 9000

Auf diesen Beitrag antworten »

Nicht P_i_minus_1, sondern P_i musst du mit 0 initialisieren!!! Schau dir die kritischen Zeilen da nämlich nochmal genau an...

Der Zweig n==0 ist verzichtbar, das wird im unteren Teil auch im Fall n=0 richtig verarbeitet, d.h., wenn du deinen gerade erwähnten Initialisierungsfehler passend korrigierst. Augenzwinkern

Augenzwinkern

P.S.: Endlosschleifen sehe ich aber keine. verwirrt

verwirrt

21.05.2019, 21:59

Arigatoo

Auf diesen Beitrag antworten »

Danke dir HAL 9000,

ich habe es verbessert:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

#include <iostream>

int summe( int n )
{
    int i = 1, P_i = 0, P_i_minus_1;
    while( i <= n ) {
         P_i_minus_1 = P_i;
         P_i = P_i_minus_1 + i;
         i++;
    }
    return P_i;
}

int main()
{
    int n, S;
    
    std::cout << "Gib eine natürliche Zahl ein: ";
    std::cin >> n;
    
    S = summe( n );
    std::cout << "Die Summe der ersten " << n << " natürlichen Zahlen ist " << S << std::endl;
    return 0;
}

Vielleicht nutze ich auch das falsche Programm (ich nutze die Site cpp.sh), denn dieses steckt auch nach der Verbesserung nach der Zahleingabe in "Program running" fest verwirrt

verwirrt

21.05.2019, 22:10

HAL 9000

Auf diesen Beitrag antworten »

Ich hab es mal 1:1 wie oben übersetzt - funktioniert tadellos. Scheint mit deiner Toolchain irgendwas im argen zu liegen.

21.05.2019, 22:14

Arigatoo

Auf diesen Beitrag antworten »

Okay, das klingt doch super, danke! smile

smile

Dann frage ich das den Tutor in der nächsten Übung Wink

Wink

21.05.2019, 22:18

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Arigatoo
(ich nutze die Site cpp.sh)

Hab ich jetzt auch probiert - funktioniert auch (abgesehen von der verkorksten Umlautdarstellung). Vielleicht stimmt was mit deinem Browser nicht (Skriptblocker o.ä.) ?

Anzeige

21.05.2019, 22:23

Arigatoo

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Arigatoo
(ich nutze die Site cpp.sh)

Hab ich jetzt auch probiert - funktioniert auch (abgesehen von der verkorksten Umlautdarstellung). Vielleicht stimmt was mit deinem Browser nicht (Skriptblocker o.ä.) ?

In einem anderen Browser (der keinerlei Add-ons hat) gelangt es nicht einmal zur Zahleingabe verwirrt

verwirrt

Ich muss das mal in der Übung an einem Linux-Rechner probieren.

22.05.2019, 09:01

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Arithmetische Summe in C++
Willkommen im Matheboard!

Zitat:

Original von Arigatoo
Meine Idee ist, die Summe über die Partialsumme zu berechnen

Deine Idee in allen Ehren, aber statt

code:
1: 2:	P_i_minus_1 = P_i; P_i = P_i_minus_1 + i;

kann man doch gleich

code:
1:	P_i = P_i + i;

schreiben und die Hilfsvariable P_i_minus_1, die nirgends sonst gebraucht wird, weglassen, oder? Denk an Occam!

Viele Grüße
Steffen

22.05.2019, 12:06

HAL 9000

Auf diesen Beitrag antworten »

Na wenn es um Effizienz geht, dann hätte ich es so geschrieben

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:	int summe( int n ) { int P_i = 0; while ( n > 0 ) { P_i += n; n--; } return P_i; }

oder noch besser

code:
1: 2: 3: 4:	int summe( int n ) { return (n*(n+1))>>1; }

Big Laugh

22.05.2019, 15:42

Finn_

Auf diesen Beitrag antworten »

Zitat:

oder noch besser

code:
1: 2: 3: 4:	int summe( int n ) { return (n*(n+1))>>1; }

Es geht auch:

code:
1: 2: 3: 4:	unsigned long summe(unsigned long n) { return n*(n+1)/2; }

Das produziert fast den gleichen Maschinencode. Lediglich ist SAR (arithmetischer Rechtsshift) gegen SHR (logischer Rechtsshift) ersetzt:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

# int summe(int n){return (n*(n+1))>>1;}
_Z5summei:
# main.cpp:6: {
	mov	edx, DWORD PTR 4[esp]	# n, n
# main.cpp:7:     return (n*(n+1))>>1;
	lea	eax, 1[edx]	# tmp93,
	imul	eax, edx	# tmp94, n
	sar	eax	# tmp92

# unsigned long summe(unsigned long n){return n*(n+1)/2;}
_Z5summem:
# main.cpp:6: {
	mov	edx, DWORD PTR 4[esp]	# n, n
# main.cpp:7:     return n*(n+1)/2;
	lea	eax, 1[edx]	# tmp93,
	imul	eax, edx	# tmp94, n
	shr	eax	# tmp92

# int summe(int n){return n*(n+1)/2;}
_Z5summei:
# main.cpp:6: {
	mov	edx, DWORD PTR 4[esp]	# n, n
# main.cpp:7:     return n*(n+1)/2;
	lea	eax, 1[edx]	# tmp93,
	imul	edx, eax	# tmp94, tmp93
	mov	eax, edx	# tmp95, tmp94
	shr	eax, 31	# tmp95,
	add	eax, edx	# tmp96, tmp94
	sar	eax	# tmp97

22.05.2019, 15:49

Steffen Bühler

Auf diesen Beitrag antworten »

Ja, die Compiler sind heute doch etwas fortgeschrittener als in den 90ern. Was haben wir da geshiftet, um ein Programm schneller zu bekommen. Und jetzt kann man einfach mal durch 16 teilen, das wird dann halt erkannt und durch einen 4bit-Shift optimiert.

PS: obwohl gerade da laut dieser Seite nicht immer alles sauber läuft...

22.05.2019, 15:55

HAL 9000

Auf diesen Beitrag antworten »

Wobei ich bei n*(n+1)/2 aufpassen würde: Die meisten Compiler mögen das hier von links nach rechts abarbeiten, aber schreibt das der C/C++-Standard auch wirklich vor? Bin mir da nicht so sicher und würde deshalb sicherheitshalber (n*(n+1))/2 schreiben, denn eine Ausführung n*((n+1)/2) in Integeroperationen wäre im Fall "n gerade" fatal. smile

smile

--------------------------------------------------------------------------------------

Interessant ist auch der umständlich erscheinende Maschinencode für (n*(n+1))/2 im Falle von vorzeichenbehafteten n:

Da der Compiler weder erkennt (wäre auch ein bisschen viel verlangt), dass das Produkt p=n*(n+1) immer nichtnegativ noch dass es immer gerade ist, erzeugt er für die Integerdivision /2 auch noch Zusatzcode, der das letzte Bit "korrigiert" für den Fall eines negativen ungeraden $\begin{eqnarray*} p \end{eqnarray*}$ - damit der Quotient verlässlich in Richtung 0 gerundet wird.

Während p>>1 in jedem Fall $\begin{eqnarray*} \left\lfloor \frac{p}{2} \right\rfloor \end{eqnarray*}$ umsetzt, also z.B (-3)>>1 = -2 statt (-3)/2 = -1

22.05.2019, 17:55

Finn_

Auf diesen Beitrag antworten »

Zitat:

Die meisten Compiler mögen das hier von links nach rechts abarbeiten, aber schreibt das der C/C++-Standard auch wirklich vor?

Ja, die arithmetischen Operationen sind linksassoziativ, da darf der Compiler nichts dran ändern.

Die Auswertung der Operanden kann aber asynchron geschehen, da muss man aufpassen, sofern keine referentiell transparenten Ausdrücke vorliegen.

22.05.2019, 19:12

Finn_

Auf diesen Beitrag antworten »

In Anbetracht des XY-Problems sehe ich mich genötigt, zusätzlich eine ästhetische Musterlösung zu posten:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:

#![warn(clippy::pedantic)]
#![allow(clippy::needless_return)]
#![allow(clippy::non_ascii_literal)]
#![allow(clippy::single_match_else)]

fn print_prompt(prompt: &str) {
    use std::io::Write;
    print!("{}",prompt);
    let _ = std::io::stdout().flush();
}

fn get_i32(prompt: &str) -> Result<i32,std::num::ParseIntError> {
    print_prompt(prompt);
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)
        .expect("failed to read from stdin");
    return input.trim().parse::<i32>();
}

trait AdditiveMonoid: Sized+std::ops::Add<Output=Self> {
    fn zero() -> Self;
    fn checked_add(self, y: Self) -> Option<Self>;
}

impl AdditiveMonoid for i32 {
    fn zero() -> Self {0}
    fn checked_add(self, y: Self) -> Option<Self> {
        self.checked_add(y)
    }
}

fn sum<M>(a: i32, b: i32, f: impl Fn(i32)->M) -> Option<M>
where M: AdditiveMonoid
{
    let mut s = M::zero();
    for i in a..=b {
        s = s.checked_add(f(i))?; 
    }
    return Some(s);
}

fn main() {
    loop {
        let n = match get_i32("\nGib eine natürliche Zahl ein: ") {
            Ok(value) => value,
            Err(_) => {
                println!("Konnte die Zahl nicht lesen.");
                continue;
            }
        };
        if n<0 {
            println!("Eine nichtnegative Zahl bitte!");
            continue;
        }
        if let Some(s) = sum(0,n,|i| i) {
            println!("Die Summe der ersten {} natürlichen Zahlen ist {}.",n,s);
        }else{
            println!("Die Zahl ist zu groß für eine Berechnung.");        
        }
    }
}

22.05.2019, 19:32

HAL 9000

Auf diesen Beitrag antworten »

Die Eingabewertkontrolle schön und gut, aber der Rest wirkt für das hier anstehende Problem arg aufgeblasen. Big Laugh

Big Laugh

22.05.2019, 19:49

Finn_

Auf diesen Beitrag antworten »

Dann so:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

fn print_prompt(prompt: &str) {
    // ...
}

fn get_i32(prompt: &str) -> Result<i32,std::num::ParseIntError> {
    // ...
}

fn main() {
    loop {
        let n = match get_i32("\nGib eine natürliche Zahl ein: ") {
            Ok(value) => value,
            Err(_) => {
                println!("Konnte die Zahl nicht lesen.");
                continue;
            }
        };
        if n<0 {
            println!("Eine nichtnegative Zahl bitte!");
            continue;
        }
        if let Some(s) = (0..=n).try_fold(0i32,|x,y| x.checked_add(y)) {
            println!("Die Summe der ersten {} natürlichen Zahlen ist {}.",n,s);
        }else{
            println!("Die Zahl ist zu groß für eine Berechnung.");        
        }
    }
}

22.05.2019, 22:15

Finn_

Auf diesen Beitrag antworten »

Die folgende Variante bietet sich auch an. Langzahlarithmetik ermöglicht hier beliebig große Zahlen und die Parallelisierung mittels into_par_iter nutzt alle Prozessorkerne voll aus (zumindest sagt das die Systemüberwachung bei meinem 2-Kern-Prozessor).

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:

use num_bigint::BigInt;
use rayon::prelude::*;

fn print_prompt(prompt: &str) {
    use std::io::Write;
    print!("{}",prompt);
    let _ = std::io::stdout().flush();
}

fn get_i64(prompt: &str) -> Result<i64,std::num::ParseIntError> {
    print_prompt(prompt);
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)
        .expect("failed to read from stdin");
    return input.trim().parse::<i64>();
}

fn sum(a: i64, b: i64, f: impl Fn(i64)->BigInt+Sync+Send) -> BigInt {
    let binc = b.checked_add(1).unwrap();
    return (a..binc)
        .into_par_iter()
        .map(f)
        .reduce(|| BigInt::from(0),|x,y| x+y);
}

fn main() {
    loop {
        let n = match get_i64("\nGib eine natürliche Zahl ein: ") {
            Ok(value) => value,
            Err(_) => {
                println!("Konnte die Zahl nicht lesen.");
                continue;
            }
        };
        if n<0 {
            println!("Eine nichtnegative Zahl bitte!");
            continue;
        }
        let s: BigInt = sum(0,n,|i| BigInt::from(i));
        println!("Die Summe der ersten {} natürlichen Zahlen ist {}.",n,s);
    }
}

23.05.2019, 19:03

Arigatoo

Auf diesen Beitrag antworten »

Da habe ich ja eine lebhafte Diskussion losgetreten. smile

smile

Keine Ahnung, was Occam ist, Augenzwinkern

Augenzwinkern

aber

code:
1:	P_i = P_i + i;

war ein guter Tipp! Also Funktioniert C++ so, dass man eine Variable V mit einem Ausdruck A(V) belegen kann, in dem die Variable selbst vorkommt?

23.05.2019, 19:19

HAL 9000

Auf diesen Beitrag antworten »

Ja, es wird es rechts komplett alles ausgerechnet mit dem "alten" Wert von p_i, bevor der dann durch die Zuweisung = durch den neuen Wert überschrieben wird.

C/C++ lässt da viele Konstrukte zu, die allerdings im Sinne eines gut lesbaren Quelltextes nicht zu empfehlen sind - Beispiel

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	int summe( int n ) { int P_i = 0; while ( n > 0 ) { P_i += (n--); } return P_i; }

Klappt auch, während das Pendant

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	int falschesumme( int n ) { int P_i = 0; while ( n > 0 ) { P_i += (--n); } return P_i; }

nicht (im beabsichtigten Sinne) funktioniert.

P.S.: https://de.wikipedia.org/wiki/Ockhams_Rasiermesser

24.05.2019, 11:07

Arigatoo

Auf diesen Beitrag antworten »

Danke!

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »