Download

# First step in imperative programming

### Conditional jump, function and loop

System Message: WARNING/2 (<string>, line 6)

Title underline too short.

```Conditional jump, function and loop
----------------------------------```
• In python, conditional jumps can be written with the following syntax :
```sage: a = 30
....: if( a % 2 == 0 ):
....:     print( "a est even." )
....: else:
....:     print( "a est odd." )```

### Exercise :

Let "a" be the age of an human, give an algorithm that returns :

• "child", if it's age is lesser than 13
• "teenager", if it's age is greater that 13 and lesser than 18
• "adult", if it's age is greater or equal to 18
• "Alien", otherwise ;).
```sage: a = -3
....: if a > 0 and a < 13:
....:    print('child')
....: elif a >= 13 and a< 18:
....:    print('teenager')
....: elif a>=18:
....:    print('adult')
....: else:
....:    print('alien')```

### Function :

A function can be declared with the keyword def. Come back to the last exercise and create a function characteristic(age) that takes as parameter the age of an human and returns the previous characteristic.

```sage: def characteristic(age):
....:    if a > 0 and a < 13:
....:        return('child')
....:    elif a >= 13 and a< 18:
....:        return('teenager')
....:    elif a>=18:
....:        return('adult')
....:    else:
....:        return('alien')
sage: characteristic(12)```

Exercise: Write a function that takes, in parameter, a real x and then returns the maximum between x^2 and 2x+1

`sage:`

### The Loops

Find in the documentation how to use the function range().

`sage: range?`

Exercise : List, by using the function range, all the even values running from -5 to 21.

`sage:`

### The loop For :

In python, we can repeat the execution of some code. We call a loop each run of that code.

Writing loop can be done in the following way :

```sage: i=2
....: n=10
....: for i in range(n):
....:     print(i)
....: print("C est la fin")
....: print(i)

sage: for e in Subsets(4):
....:    print( e )```

Exercise: Write a function f that takes an integer n and then returns the value u_n defined by u_n=u_{n-1}+u_{n-1} with u_{0}=0 and u_1=1.

`sage:`

### The loop WHILE :

Loops can be written with the following format:

```sage: n=10
....: i=2
....: while i < n:
....:     print(i)
....:     i = i+1
....: print("sortie i : " + str(i))```

Exercise: Give a function that takes an integer n as parameter and return the integer part of log_2(n).

`sage:`

### The lists

• In python, lists are written by using with brackets. For example, the list

System Message: WARNING/2 (<string>, line 155)

Bullet list ends without a blank line; unexpected unindent.

[1, 2, 3, 4] can be coded with those lines :

```sage: l = [1,2,3,4]
sage: l
sage: l.append(10)
sage: l```
• We can write some lists by using loops :
```sage: l = []
....: for i in range(10):
....:    l.append(i)
....: l```
• We can also make it in one line :
`sage: [i^2 for i in range(10)]`
• We can create list of different objects. For example, the following code generate all the permutations of size 4:
`sage: [p for p in Permutations(4)]`
• In fact it is possible to write :
```sage: P = Permutations(4)
sage: P```
• It is possible to use loops and conditional jumps inside lists. In the next example, we select all the permutations that finish on a descent. We recall that i is a descent in a permutation p if p(i) ge p(i+1).
`sage: [p for p in Permutations(5) if p(4)>p(5) ]`
• It is possible to obtain the size of a list :
```sage: l = [p for p in Permutations(5) if p(4)>p(5)]
sage: len( l )```

Exercise: Write a function to list all fixed points of a given permutation. Then, write another function that lists all permutations without fixed point.

`sage:`
• We can generate the generating function of all permutations that have no fixed points. We will assume that x counts the size of the permutations.
```sage: def nb_without_fp(n):
....:     return len(
....:         [
....:             p
....:             for p in Permutations(n)
....:             if len(fixed_points(p))==0
....:         ]
....:     )
sage: S = sum( nb_without_fp(n)*x^n for n in range(8) )
sage: S```
• We can collect the sequence and obtain information about that sequence with OEIS.
`sage: oeis([ nb_sans_pf(n) for n in range(8) ])`

### Exercises

• By using the previous examples, write a program that gives the list of all even integers that are lesser than 30.
`sage:`
• Propose an algorithm that computes the binomial binom{n}{k} by using the Pascal triangle : binom{n+1}{k}=binom{n}{k}+binom{n}{k-1}.
`sage:`
• In fact, the function binomial exists in Sage. Find that function.
`sage:`

### The dictionaries

• Dictionaries are data structures that allow to associate an object called key

System Message: WARNING/2 (<string>, line 281)

Bullet list ends without a blank line; unexpected unindent.

to another object called value. In a dictionary, all keys are different. In fact a dictionary is a map with finite support.

```sage: D = {1:4, 2:6, 3:6, 8:6}
sage: D
{1: 4, 2: 6, 3: 6, 8: 6}```
`sage: D.keys()`

Question: How do you proceed to :

• determine if a dictionary contains a particular key;
• get a value associated to a key;
• get the number of keys.
`sage:`

Exercise Write a function that takes as parameter a list of integers and then returns a dictionary where

• keys are all the integers present inside the list
• values, associated with the key, are the number of key repetitions inside the list.
`sage:`

### The generators

• Generators are programs that are useful to enumerate objects on demand. For example, Permutations(3) contains a generator of permutations of size 3. We obtain that generator by typing :
`sage: generator = iter( Permutations(3) )`
• We can enumerate those permutations by writing :
```sage: print( next( generator ) )
sage: print( next( generator ) )
sage: print( next( generator ) )
sage: print( next( generator ) )
sage: print( next( generator ) )
sage: print( next( generator ) )```
• An error is raised when iterator reach the end of the iterator function.
`sage: print( next( generator ) )`
• Generators allow to obtain object one by one without computing a list of all the elements. This is useful when the list is big or infinite. For example, we can compute a generator for all the permutations:
```sage: generator = iter(Permutations())
sage: print( next(generator) )
sage: print( next(generator) )
sage: print( next(generator) )
sage: print( next(generator) )
sage: print( next(generator) )
sage: print( next(generator) )
sage: print( next(generator) )
sage: print( next(generator) )```
• It is possible to use iterators inside a loop :
```sage: gen = iter( Permutations(3) )
....: for p in gen:
....:     print( p )```
• You can implement your own generator. It suffices, during the enumeration, to return the current value by using the keyword yield. At the first use of yield, python will create a generator that stores in memory all the states of the calculus. At each next the generator will continue the calculus and will return the next value of the enumeration.
```sage: def generator( n ):
....:      for i in range(n):
....:          yield i**2
sage: gen = generator( 30 )
....: print( next(gen) )
....: print( next(gen) )
....: print( next(gen) )
....: print( next(gen) )
....: print( next(gen) )
....: print( next(gen) )```

### Exercises :

• Write a generator that enumerates all permutations of size n (without using the Sage generator of Permutations).
`sage:`
• Write a generator that enumerates all the compositions of an integer. A composition of n is a list l_1, l_2, ldots, l_k of integers such that l_1 + l_2 + ldots + l_n = n.
`sage:`
• Find in the Sage documentation a composition generator.
`sage:`

### Euler project

• Train yourself by solving problems from the Euler Project Website :

https://projecteuler.net/

## Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.
• [get | view] (2016-12-03 14:31:55, 316.9 KB) [[attachment:First steps in Sage--Solution.ipynb]]
• [get | view] (2016-11-21 20:41:01, 18.1 KB) [[attachment:First steps in Sage.ipynb]]
• [get | view] (2016-11-22 10:07:49, 802.7 KB) [[attachment:Polytope playground.ipynb]]
• [get | view] (2016-11-22 09:18:53, 440.8 KB) [[attachment:VincentDelecroix-beamer_jerusalem_2016.pdf]]
• [get | view] (2016-11-22 09:23:40, 512.6 KB) [[attachment:VincentDelecroix-notebook_Jerusalem_2016.ipynb]]
• [get | view] (2016-11-22 09:23:55, 551.0 KB) [[attachment:VincentDelecroix-notebook_Jerusalem_2016.pdf]]
• [get | view] (2016-11-23 07:48:46, 11.4 KB) [[attachment:graphs_and_lp.ipynb]]
• [get | view] (2016-11-23 07:48:54, 119.6 KB) [[attachment:graphs_and_lp.pdf]]
• [get | view] (2016-12-03 16:29:31, 26.9 KB) [[attachment:introduction_to_imperative_programming--Solution.ipynb]]
• [get | view] (2016-11-22 01:04:56, 14.6 KB) [[attachment:introduction_to_imperative_programming.ipynb]]
• [get | view] (2016-11-22 01:04:13, 8.2 KB) [[attachment:introduction_to_imperative_programming.rst]]
• [get | view] (2016-12-03 15:41:46, 27.6 KB) [[attachment:object_oriented_python--Solution.ipynb]]
• [get | view] (2016-11-21 21:42:57, 21.3 KB) [[attachment:python_object_oriented.ipynb]]
• [get | view] (2016-11-21 13:12:56, 14.9 KB) [[attachment:repr_theory_tutorial.ipynb]]
• [get | view] (2016-11-21 13:11:10, 609.7 KB) [[attachment:scrimshaw_talk.pdf]]

You are not allowed to attach a file to this page.