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": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5.597448825836182\n"
]
}
],
"source": [
"import time\n",
"\n",
"startTime=time.time()\n",
"n=0\n",
"while n<50000000:\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",
" 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: 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",
"
*\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",
"
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.