7.1 Basic Problem: Summation¶

As mentioned before, all problem solving can be approached by using a combination of branches and loops. Understanding the dynamic control flow is the first step towards problem solving using programming, but the ultimate purpose is to combine and use basic control flows for solving problems. This chapter introduces several typical problems and discusses their solutions.

One of the most basic problems that can be solved by using loops is the problem of summation, which can be formulated as \(s =\sum_{i=m}^{n} f(i)\), where m and n are two integers, and m ≤ n. The simplest form of summation is \(s =\sum_{i=m}^{n} i\), which can be solved by the following program.

sum.py calculates the sum by accumulating its value incrementally. It uses two variables, i and s, to represent the current value to be added to the sum and the sum up to the current iteration, respectively. While s is initialized to 0, i is initialized to the beginning value m. The while statement uses i as the loop variable, which increases from m to n by a step size of 1. At each iteration, the value of i is added to the sum s, and then increased by 1. The key idea behind this program is the use of a sum value, which is incrementally updated in an iterative process. This basic way of thinking applies to many other problems, as will be shown throughout this book.

For a more complex example, consider the summation of all multiples of 3 from 1 to 100. There are many different ways to solve this problem. One solution is to iterate overall all multiples of 3, adding them to a sum value.

In contrast to sum.py, sum3.py takes a different strategy to perform the iteration: the initial value of i is set to 3 rather than 1, and the step size is also set to 3. In this way the values of i cover all multiples of 3 from 1 to 100. The other aspects of sum3.py are the same as sum.py. An execution of sum3.py yields the following output.

> python sum3.py
The sum of all multiples of 3 from 1 to 100 is 1683

An alternative solution to the problem above is to compute

sum3_f.py iterates over the integers from 1 to 100/3, which fall between 1 and 100 when multiplied by 3. At each iteration, it accumulates the value of \(f(i) = 3i\) into the sum. The execution of sum3_f.py gives the same outputs as the execution of sum3.py

Production. The method of summation can be generalized to solve the problem of production by changing the addition operation to the multiplication operation. For example, the factorial function n! can be calculated by the following program.

factorial.py follows the same strategy as sum.py, with the product s being initialized to 1 instead of 0, and the incremental operator being changed from += to *=. Execution of the program yields the following result.

> python factorial.py
10! = 3628800

Maximum. The problem of summation can also be generalized into the tasks of finding the maximum and minimum values of a function \(f(x)\), which can be formulated as \(\max_{}{} _{i=m}^{n} f(x)\) and \(\min_{}{} _{i=m}^{n} f(x)\), respectively. Take finding the maximum value for example. Again one solution can be based on sum.py, with the initial value of s being set to the negative infinity instead of 1, and the incremental operator being max rather than +=.

max.py finds the maximum value of \(\sin x^2\), where x is an integer that ranges from 0 to 100. It has a similar structure as sum.py except for the aforementioned changes to the initial value of s and the incremental operator. Here s is used to represent the current maximum value of f at each step. When the iterations finish, s will be the global maximum. The math module is used to calculate the value of \(\sin x^2\), and the expression float(‘-inf’) is used to obtain the negative infinity. The max function is a built-in function of Python; it can take two or more numerical arguments, and gives the maximum of its input arguments as the return value. An execution of max.py yields the following result.

> python max.py
The maximum value of the function is 0.9997657290235363

A common alternative implementation of max.py uses an if condition instead of the max function in the incremental step.

The if statement achieves the same purpose as the max function: it updates the current maximum value if the current value of f is higher than the maximum value in the previous iterations. max_if.py yields the same result as max.py. One advantage of this program is that it is easy to obtain the value of i that gives the maximum value of f, in addition to the maximum value of f itself.

argmax_if.py uses an additional variable, argmax, to store the value of i that corresponds to the maximum value of f. The initial value of argmax is not important. Whenever the value of s is updated, the value of argmax is also updated. An execution of the program gives the following output.

> python argmax_if.py
The maximum value of the function is 0.9997657290235363 achieved when the input is 75

Counting. Another problem that is related to the problem of summation is counting. The simplest form of counting can be regarded as \(\sum_{i=m}^{n}1\), a special case of summation: accumulating 1 on every iteration. In many situations, counting is conditional, and can be formulated as \(\sum_{i=m}^{n}count(i)\), where count(i) can be 0 or 1, based on a specific condition. This form of the count function can be implemented using an if statement. The following program counts the number of integers x between 1 and 100 for which the function \(sin(x^3)\) is positive.

An execution of the program above yields the following output.

The number of integers between 1 and 100 for which the function is positive is 60

© Copyright 2024 GS Ng.