Attachment 'introduction_to_imperative_programming.rst'

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.

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