Learntofish's Blog

A blog about math, physics and computer science

Basic algorithm 2: Sum of integers

Posted by Ed on November 11, 2011

Last time we talked about finding the greatest integer in an array. Today we deal with the following problem:

Find the sum of the integers from 1 to 100 using:
a) a for loop
b) a while loop
c) the Gauss formula
d) without using “for” and “while” (Hint: recursive function)

Here is my solution in C++:

#include <iostream>
using namespace std;

// function prototypes
int sumUpto(int x);
int sumUpto2(int x);
int gaussSum(int x);
int sumUptoRec(int x, int counter, int total);


// main function -------------------------------------------------------
int main()
{
    int n=100;
    cout << "sum from 1 to " << n << " (for loop): " << sumUpto(n) << endl;
    cout << "sum from 1 to " << n << " (while loop): " << sumUpto2(n) << endl;
    cout << "sum from 1 to " << n << " (Gauss formula): " << gaussSum(n) << endl;
    cout << "sum from 1 to " << n << " (recursive): " << sumUptoRec(n,0,0) << endl;


    return 0;
}
// ---------------------------------------------------------------------

// using for loop
int sumUpto(int x){
    int total=0;
    for(int i=0; i<=x; i++){
        total=total+i;
    }
    return total;
}

// using while loop
int sumUpto2(int x){
    int total=0;
    int counter=1;
    while(counter<=x){
        total=total+counter;
        counter++;
    }
    return total;
}

// gauss formula
int gaussSum(int n){
    return n*(n+1)/2;
}

// using recursive function
// (note: no "for" or "while" is used)
int sumUptoRec(int x, int counter, int total){
    if(counter==x){
        return total+x;
    }
    else{
        return sumUptoRec(x, counter+1, total+counter);
    }
}

a) Using the for loop is easy. Note that we used the condition “<=x" instead of the usual "<x".
b) The while loop works similar to the for loop. You just have to introduce a counter variable.
c) Here we use the famous Gauss formula for the sum of the integers from 1 to N.
d) Writing a recursive function may take some experience. The trick is to "hide" the update of the variables counter and total in the arguments. We then initialize these variables with 0 by calling the function sumUptoRec(n,0,0) with 0 in the last two parameters. If you want to get a good training on this technique have a look at the programming language Haskell. Haskell does not know for or while loops, so you are forced to write recursive functions.

Here is my solution in Java:

public class BasicAlgorithm2_sumIntegers {
	
	// using a for loop
	int sumUpto(int x){
		int total=0;
		for(int i=1; i<=x; i++){
			total=total+i;
		}
		return total;
	}
	
	// using a while loop
	int sumUpto2(int x){
		int total=0;
		int counter=0;
		while(counter<=x){
			total+=counter;
			counter++;
		}
		return total;
	}
	
	// using Gauss formula
	int gaussFormula(int n){
		return n*(n+1)/2;
	}
	
	// using recursion
	// (note: "for" or "while" is used)
	int sumUptoRec(int x, int counter, int total){
		if(counter==x){
			return total+x;
		}
		else{
			return sumUptoRec(x, counter+1, total+counter);
		}	
	}
	
	
	// main function ---------------------------------------------------------------------
	public static void main(String[] args){
		
		// creating an object
		BasicAlgorithm2_sumIntegers myObj = new BasicAlgorithm2_sumIntegers();
		
		int n=100;
		System.out.println("sum from 1 to " + n + "(for loop): " + myObj.sumUpto(n));
		System.out.println("sum from 1 to " + n + "(for loop): " + myObj.sumUpto2(n));
		System.out.println("sum from 1 to " + n + "(for loop): " + myObj.gaussFormula(n));
		System.out.println("sum from 1 to " + n + "(for loop): " + myObj.sumUptoRec(n, 0, 0));
			
	}
	//------------------------------------------------------------------------------------

}

Here is my solution in Python 3:

# using a for loop
def sumUpto(x):
    total=0
    for i in range(1,x+1):
        total=total+i
    return total

# using a while loop
def sumUpto2(x):
    total=0
    counter=0
    while(counter<=x):
        total=total+counter
        counter=counter+1
    return total

# using Gauss formula
def gaussFormula(n):
    # notice, that in Python 3 the integer division
    # needs double slash
    return n*(n+1)//2

# using recursion
def sumUptoRec(x, counter, total):
    if(counter==x):
        return total+x
    else:
        return sumUptoRec(x, counter+1, total+counter)


# main function
def main():
    n=100
    print("sum from 1 to", n, "(for loop):", sumUpto(n))
    print("sum from 1 to", n, "(while loop):", sumUpto2(n))
    print("sum from 1 to", n, "(Gauss formula):", gaussFormula(n))
    print("sum from 1 to", n, "(recursive):", sumUptoRec(n,0,0))
Advertisements

One Response to “Basic algorithm 2: Sum of integers”

  1. […] Basic algorithm 2: Sum of integers […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: