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))
Learntofish's Blog said
[…] Basic algorithm 2: Sum of integers […]