from IPython.core.display import HTML
HTML(open("custom.html", "r").read())
Programming is about writing programs. A program instructs your computer to solve a given problem. The problem might be a very basic problem or very complex.
Some examples for problems we can solve with a computer:
An algorithm is an informal specification of "basic" computation steps to solve a given problem.
The following algorithm computes the greatest common divisor (gcd) of two numbers a and b:
a is equal to b: a is the gcd. We stop.a is greater than b: replace a by a - bb by b - aExecute this algorithm with pen and paper to compute the greatest common divisor of $66$ and $78$. Start with a table with two colums for the actual value of a and b and add a line with updated values for every step.
Before we start to introduce a real programming language we start to play with so called pseudo code notation and will gain some insights how a computer works.
Programs use "Variables". You can imagine that data (as numbers) is stored in memory cells having a name. So we visualize the state of the memory using a table with two columns as you can see below.
The first minimal command is the assignment instruction. This instruction looks like
a ← 1.23
which places the number 1.23 in a cell named a. So after execution of this simple statement by the computer the memory looks like this:
| name | value |
|---|---|
| a | 1.23 |
If you chain the two instructions they are executed in the listed order, so after executing the minimal two line program
a ← 1.23
a ← 3.45
the value 1.23 is overwritten and the final state of the memory is
| name | value |
|---|---|
| a | 3.45 |
You can create a new variable by computations based on known variables. So the assignment
b ← a + 1
results in
| name | value |
|---|---|
| a | 3.45 |
| b | 4.45 |
So a variable may appear on both sides of ←:
To compute the average of two values the statement (/ is division)
mean ← (a + b) / 2
will complete the memory to
| name | value |
|---|---|
| a | 1.2 |
| b | 2.2 |
| mean | 1.7 |
As you can see above a variable name may contain more than one character. In most programming languages (including Python) you may use a mixture of alphabetic characters a to z, A to Z as well as numbers 0 to 9 and the so called "under score" _. We learn more details about variable names later.
Variables are not only used for the input data and the final result but can keep intermediate values. So our computation above can be written as
sum ← a + b
mean ← sum / 2
This can be used to shorten expressions and sometimes is needed as we see in the following exercise:
Assume your computers memory has two cells a and b containing different numbers. Can your write a sequence of three instructions to exchange the contents of both cells ? (Starting with a ← b or b ← a will not work !)
A program is a sequence of instructions which are executed by the computer sequentially. This flow of execution may branch based on specified conditions.
To give an example the following program computes the salary of an worker which worked for hours hours for a salary salary_per_hour. If he works more than 40 hours the over-hours are paid twice:
IF hours ≤ 40 THEN DO {
salary ← hours * salary_per_hour
}
ELSE DO {
salary_first_40 ← 40 * salary_per_hour
over_hours ← hours - 40
over_hour_salary ← 2 * over_hours * salary_per_hour
salary ← salary_first_40 + over_hour_salary
}
We use the curly braces to indicate which part of the code should be executed if the given condition is true and capitalized words for writing instructions and lower case words for variables aka memory cells.
Here the computer will execute the computations in the first block delimited by curly braces if hours is 40 or less. Else the second block will be executed.
Given you have values 39 and 12 in cells hours and salary_per_hour in your computers memory. Reproduce execution of the instructions above on a piece of paper !
Do the same for values 45 and 15.
For this we start with the setting
i ← 0
acc ← 0
(I use acc as an abbreviation for accumulator, you may choose other names).
Then we execute the following two instructions
i ← i + 1
acc ← acc + i
and we have
| name | value |
|---|---|
| i | 1 |
| acc | 1 |
Running the same two statements again:
i ← i + 1
acc ← acc + i
results in the following memory image
| name | value |
|---|---|
| i | 2 |
| acc | 3 |
Use a piece of paper and repeat the instructions above. What is the state of your memory after three extra repetitions ?
If we start with
i ← 0
acc ← 0
And repeat the block
i ← i + 1
acc ← acc + i
$n$ times the final memory will contain
| name | value |
|---|---|
| i | n |
| acc | 1 + 2 + ··· + n |
We can summarize the instructions from the last section in pseudo code as follows:
i ← 0
acc ← 0
REPEAT n TIMES {
i ← i + 1
acc ← acc + i
}
Here we use curly braces to indicate which part of the code should be repeated and again capitalized words for writing instructions and lower case words for variables aka memory cells.
Using REPEAT is not only a shorter notation: for an arbitrary value in a cell named n, running the same code will always compute the sum 1 + ··· + n !
Modify the last pseudo code above to compute the sum of the first $n$ square numbers (use multiplication for computing squares). Test your code with pen and paper !
Develop some pseudo code which computes the product of the first $n$ numbers. Test your code with pen and paper !
What does the following pseudo code compute ? (We use * for multiplication). Use pen and paper to follow the execution of the single statements assuming different values of n:
i ← 0
x ← 1
REPEAT n TIMES {
i ← i + 1
x ← 2 * x
}To demonstrate conditional execution in combination with repeated execution we modify the previous pseudo code to compute the sum of the even numbers in the range $1$ to $n$:
i ← 0
acc ← 0
REPEAT n TIMES {
i ← i + 1
IF i IS EVEN THEN {
acc ← acc + i
}
}
Trace the execution of the previous program with pen and paper for $n=5$ !
Without explaining Python details, our pseudo code algorithm for computing the sum of the first $n$ natural numbers can be transformed into a Python program only by replacing some notations:
← is written as = REPEAT n TIMES is written as for x in range(n):Comment: Take the for .. statement as given, we come introduce details later.
Note that = in a Python program expresses ←. So =
Always read = as "write to a memory cell" and nothing else
n numbers is independent of the programming language used. Just the notation will differ.So this is the result of the described transformation:
i = 0
acc = 0
for x in range(n):
i = i + 1
acc = acc + iTo complete the Python program we extend it so it interacts with an user and displays a result. For this
acc isAnd this is now our first usable Python program:
n = int(input("please enter n: "))
i = 0
acc = 0
for x in range(n):
i = i + 1
acc = acc + i
print("the sum is", acc)
For the moment accept the first and last line as they are, we will learn the details during the following script.
Sometimes we say "Python script" instead of "Python program".
If we talk about Python you should distinguish:
Python interpreter is the program which executes Python code. There are different Python interpreters for different operating systems and for different versions of the Python programming language.Python programming language is given by an formal specification how syntactically correct Python programs are spelled and how the Python interpreter executes (interprets) them. The language only varies depending of the version of the language (here we use 3.5 or newer).PyCharm which is one of many so called integrated development environments (IDEs). This is a program on top of the Python interpreter which assists writing and running code but which is not mandatory to run a Python program.PyCharm we have a text editor to write text which is conformant to the specificaton of the Python programming language, and we also have a button to start the Python interpreter to execute this text.