{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Loops" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## While" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "while \\:\n", "
\\ \\
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is the same as _if_, with the difference that:\n", "
_if_: block is executed 0 times or 1 time\n", "
_while_: block is executed 0,1,2,... times, until the logical expression remains true.\n", "\n", "This implies that if nothing changes the logical expression, block is executed an infinite amount of times" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i=0\n", "while i<5:\n", " print(i)\n", " i=i+1 # do not forget this statement!!! " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i=0\n", "while i<5:\n", " print(i)\n", "i=i+1 # do not forget this statement!!!\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Draw its flowchart and draw the flowchart with the statement outside the block." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercises" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What does this program do? In particular, state exactly which numbers does it print." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i = 0\n", "while i < 5:\n", " i=i+1\n", " print(i)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i = 0\n", "while i < 5:\n", " i=i+2\n", " print(i)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i = 0\n", "while i != 5:\n", " i=i+2\n", " print(i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Define a function **printNumbers** that takes as parameter a number not smaller than 1 and prints all the integer numbers from 1 to that number.\n", "
Do not worry, this function will not return anything." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def printNumbers(n):\n", " i=1\n", " while i<=n:\n", " print(i)\n", " i=i+1\n", "\n", "def printNumbers(n):\n", " i=0\n", " while iStrategy: this problem was solved by Gauss with a simple formula which is $N(N+1)/2$, but here I do not want you to use Gauss' formula but to set a while loop which sums up all the numbers from $1$ to $N$." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "def sumNumbers(N):\n", " i=1\n", " result=0\n", " while i<=N:\n", " result=result+i\n", " i+=1\n", " return result" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "55\n" ] } ], "source": [ "print(sumNumbers(10))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Factorial" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write a function which given N, calculates the product of $1\\cdot2\\cdot3\\cdot4\\cdot...\\cdot N$. \n", "

Strategy: this calculation is called factorial and indicated with $N!$ (literally, an exclamation mark). The task is solved exactly in the same way as before, but now you have to pay attention since you may not start from 0..." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "def factorial(N):\n", " result=1\n", " i=2 # you can also set i=1, but multiplying things by 1 does not modify anything\n", " while i<=N:\n", " result=result*i\n", " i+=1 \n", " return result" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2432902008176640000\n" ] } ], "source": [ "print(factorial(20))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Draw its flowchart" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Your task now is to rewrite it, but starting from $N\\cdot(N-1)$" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def factorial(N):\n", " result=N\n", " i=N-1\n", " while i>=1:\n", " result=result*i # its nerdish equivalent is result*=i\n", " i-=1 \n", " return result" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2432902008176640000\n" ] } ], "source": [ "print(factorial(20))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## break" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "break instruction simply interrupts the current loop and jumps suddenly to its end." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the previous loop:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i=0\n", "while i<5:\n", " print(i)\n", " i=i+1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Which of the following prints the same things?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i=0\n", "while i<5:\n", " if False:\n", " break\n", " print(i)\n", " i=i+1" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i=0\n", "while i<5:\n", " print(i)\n", " i=i+1\n", " break" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i=0\n", "while True:\n", " print(i)\n", " i=i+1\n", " if i>=5:\n", " break" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "i=0\n", "while i<5:\n", " print(i)\n", " i=i+1\n", " if i<5:\n", " print(i)\n", " i=i+1\n", " else:\n", " break" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Multiple assignment" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There is a dirty trick with which functions can return more than one value. The trick is having them return a list separated by commas. A list is a Python type and can also be used in other circumstances, such as assignment." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def trick(n):\n", " return n+1,n+2,n+25\n", "\n", "a,b,c = trick(5)\n", "print(a)\n", "print(b)\n", "print(c)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "d,e = 78,\"bla bla\"\n", "print(d)\n", "print(e)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercises" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What does s,t=t,s do ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s=20\n", "t=-3\n", "s,t=t,s\n", "print(s)\n", "print(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Computational Complexity" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Computers are slow. No, not because the streaming of your favourite tv series gets stuck whenever you try to watch it from the cellar of your mountain hut (that is the network which is slow) but because your processor can make a huge but still limited number of calculations per second." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time\n", "\n", "startTime=time.time()\n", "n=0\n", "while n<5000000:\n", " z=43534534.*n\n", " n=n+1\n", "endTime=time.time()\n", "print(endTime-startTime)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Usually multiplications and divisions are much slower than additions and subtractions which are much slower than comparisons. Try to do manually 43876*29807, 43876+29807 and 43876==29807 and you'll understand why!\n", "\n", "Usually operations with float are much slower than operations with int which are much slower than operations with bool. This is because float usually need 8 bytes, int 4 bytes and bool 1 bit. Try to do manually 43875380+29806128 and 4387+2980 and 1+0 and you'll see.\n", "\n", "\n", "For this reason, to get an idea of the program's speed we shall count only **heavy operations**. They are multiplications and divisions of float and, only if they are absent or if they are negligible, we shall count multiplications and divisions of int, then additions and subtractions of float... and so on." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's go back to the previous loops and calculate their **computational complexity**, i.e. the amount of heavy operations based on the amount of input they receive." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- 5 integer additions\n", "- 5 comparisons of integer (and 1 int addition)\n", "- 5 int add\n", "- 5 int add\n", "- 5 int add\n", "- n int add\n", "- n int add\n", "- n int add\n", "- n int mult\n", "- n int mult\n", "- and so on..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write a proceudre called showStars that takes as parameter an integer rows, checks that it is positive and integer and prints a triangle of stars. For example, if rows is 5, it should print the following:\n", "
*\n", "
* *\n", "
* * *\n", "
* * * *\n", "
* * * * *" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "* \n", "* * \n", "* * * \n", "* * * * \n" ] } ], "source": [ "def showStars(rows):\n", " if type(rows)!=int or rows<1:\n", " print \"bad words\"\n", " else:\n", " i=1\n", " while(i<=rows): # rows comparisons of int\n", " print \"* \"*i # rows str multiplications\n", " i=i+1 # rows int additions\n", "# function finished\n", "\n", "# comp complexity is rows str multiplic\n", " \n", "showStars(4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Computational complexity\n", "\n", "Which operations it is doing?\n", "\n", "A comparison at the beginning. This comparison is performed only once\n", "
A comparison for the while condition. This comparison is performed for i=1, for i=2, for i=3.... at the end it will be performed rows-times\n", "
Then a multiplication of a string by an int (we can imagine this as an int multiplication.\n", "
How many times is it performed? Same as above, rows times\n", "
Then an addition, which again is performed rows times.\n", "\n", "At the end we have rows+1 comparisons, rows additions and rows multiplications.\n", "\n", "So complexity is rows multiplications.\n", "
It means that if you pass as input argument a very large number, the algorithm will take a very large time.\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "* \n", "* * \n", "* * * \n", "* * * * \n", "\n" ] } ], "source": [ "# now we RETURN all the asterisks \n", "# triangle instead of printing it!\n", "def showStarsR(rows):\n", " rows=int(rows)\n", " if rows<1:\n", " print \"bad words\"\n", " else:\n", " result=\"\"\n", " i=1\n", " while(i<=rows):\n", " result = result + \"* \"*i + \"\\n\"\n", " i=i+1\n", " return result\n", "# function finished\n", " \n", "print showStarsR(4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write a function isPrime that takes a parameter N and returns a boolean indicating whether it is prime or not.\n", "

Strategy: after having thought at the problem, if you can't come up with a working algorithm click below to reveal it. I said after having thought\n", "

Strategy: I remind you that to check whether a number is prime or not you go from 2 up to N-1 and check whether N is divisible by any number. If it is, it is not prime.\n", "
Therefore, to check it we need a loop which returns False as soon as it finds any divisor and returns True if it ends as usual.
" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "False\n" ] } ], "source": [ "def isPrime(N):\n", " i=2\n", " while(i<=N-1): # N-2 int comparisons\n", " if N%i==0: # N-2 int divisions and comparisons\n", " return False\n", " i=i+1 # N-2 int additions\n", " return True\n", "\n", "# complexity IN THE WORST CASE is N int divisions\n", "\n", "print isPrime(15)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write a function factors that takes a parameter N and prints all the prime numbers that are divisors of N. \n", "

Strategy: after having thought at the problem, if you can't come up with a working algorithm click below to reveal it. I said after having thought\n", "

Strategy: you obviously use the previous function to check whether a number is a prime or not, rewriting the previous code would be crazy. You go through all the numbers from 2 to N-1 and you check whether that number is a prime and a divisor of N.
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# we know that complexity of isPrime is N int mult\n", "def factors(N):\n", " i=2\n", " while(i<=N-1): # N int compar\n", " if isPrime(i) and N%i==0: # i int mult at every step + 1 int mult at every step\n", " print i\n", " i=i+1 # N int additions\n", " print \"I am finished\"\n", " \n", "# N int mult + 2+3+4+5+6+7+...+N-1 =\n", "# approx N^2 /2 int mult\n", "\n", "# complexity is N + N^2/2 int mult\n", " \n", " \n", "factors(150043)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.12" } }, "nbformat": 4, "nbformat_minor": 2 }