# Séance 4 : Strings & Listes & Tuples (fin)

## Preliminary remarks
__Cours d'Analyse I__
* Cadeau: https://docdro.id/4Gvs6U2
* Forum Moodle, groupes Facebook ?
* Résolution online: [WolframAlpha](https://www.wolframalpha.com/input/?i=int+sinx%2Fx+dx%2C+x%3D0..infinity&lk=3)
* Cours particuliers ? ListMinut.Be, Superprof.be
* Toutes les synthèses Latex sur Github: https://github.com/Gp2mv3/Syntheses

__Aide-mémoire Python__
* Ressource intéressante [ICI](http://sixthresearcher.com/wp-content/uploads/2016/12/Python3_reference_cheat_sheet.pdf)
* Créez le vôtre à la main ou via hackmd.io ?

## A. In the previous episode
* __A1. Indentation et boucle `while`__
* __A2. Variables globales vs locales__
* __A3. Comment appeler une fonction ?__
* __A4. String & List (cfr. [slides](https://drive.google.com/file/d/1DHrH5SKMyyrDHHTi8eAaYgmUb-3p4Ajk/view?usp=sharing))__
* Méthodes intéressantes à retenir
* `lst.append()`
* `lst.split()`
* `lst.sort()`
* __A5. Listes imbriquées: Création d'une matrice__

        matrix = []
        for i in range(2):
            row = []
            for j in range(3):
                row.append(0.0)
            matrix.append(row)

* __A6. Que se passe-t-il en mémoire ?__ => [Python Tutor Visualization Online](http://pythontutor.com/visualize.html#code=matrix%20%3D%20%5B%5D%0Afor%20i%20in%20range%282%29%3A%0A%20%20%20%20row%20%3D%20%5B%5D%0A%20%20%20%20for%20j%20in%20range%283%29%3A%0A%20%20%20%20%20%20%20%20row.append%280.0%29%0A%20%20%20%20matrix.append%28row%29%0A%20%20%20%20&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false)
* __A7. Tuples__
* Tuple = Liste __immutable__
* Prend moins de place en mémoire => rapidité ++
* Mêmes opérations que Liste, sauf l'affectation !
<div style="text-align:center">
<img src="https://i.imgur.com/xXTfXRI.png" width=400>
</div>
* Méthodes intéressantes à retenir
* `enumerate` -> returns a list of tuples `[(index,val),...]`

            lst = ["eat","sleep","repeat"] 
              for enum in enumerate(lst): 
                # Unpacking the tuple
                index, val = enum

* `"-".join(my_tuple)`
* `list(my_tuple)`
---
## B. Theorie

### B1. Algorithmes de recherche
| Linear Search | Binary Search |
| -------- | -------- |
| `linear_search('mango',lst)` <img src="https://i.imgur.com/oIDFFRs.png" width="1600"> | <img src="https://i.imgur.com/JSAwDdo.png" width="800"> <img src="https://i.imgur.com/uQtV7x5.png" width="800">
| Le temps d'exécution sera proportionnel à $n$, le nombre d'éléments contenus dans `lst` | Le temps d'exécution sera proportionnel à ??? :wink:

### B2. Références
* A reference is a name that refers to the specific location in memory of a value.
* References take the form of variables, attributes, and items.
* __Variable = (adresse vers) zone de mémoire (contenant une valeur)__
* Exemple 1 (Click [here](http://www.pythontutor.com/visualize.html#code=a%20%3D%205%0Ab%20%3D%205%0Alst%20%3D%20%5Ba,%22hello%22,True%5D%0A&cumulative=false&curInstr=0&heapPrimitives=true&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false))

a = 5
b = 5
lst = [a,"hello",True]
print(a == b)
print(a is b)

* Exemple 2

lst1 = [1, 2, 3]
lst2 = [1, 2, 3]
lst3 = [lst1,lst2]
print(lst1 == lst2)
print(lst1 is lst2)

---

## C. Exercices

### C1. Matrices avec [Python Tutor Visualize](http://www.pythontutor.com/visualize.html#mode=edit)

# MAUVAISE IMPLEMENTATION
matrix1 = []
row = []

for i in range(2):
    row.append(0)

for j in range(3):
    matrix1.append(row)

'''
matrix1[1][2] = 1
'''

# MAUVAISE IMPLEMENTATION
matrix2 = []
for i in range(2):
    row = []
    
for j in range(3):
    row.append(0)
    matrix2.append(row)

'''
print(matrix2)
matrix2[1][2] = 1
print(matrix2)
'''

# Matrix 3
matrix3 = []
for x in range(2):
    row = []
    for y in range(3):
        row.append(0)
    matrix3.append(row)

'''
print(matrix3)
matrix3[1][2] = 1
print(matrix3)
'''

### C2a. Session 4: Diff count

'''
The method diff_count(lst) returns the number of different elements contained in the list lst.
- If lst equals [3, 5, 3] then the method should return 2.
- If all the elements are the same, it should return 1.
- If the list lst is empty, it should return 0.
'''

### C2b. Session 4: Q* Equations du second degré ([ici](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-exercises/PART_II/MISSION_4/complement))

def solution(a, b, c):
    """
    pre:  a, b et c sont 3 nombres réels
    post: la valeur de retour de cette fonction dépend du nombre
          de solutions de l'équation ax^2 + bx + c = 0.
    - 0 solution: retourne la liste vide
    - 1 solution: retourne une liste contenant la solution de l'équation
    - 2 solutions: retourne une liste contenant les deux solutions,
                  la plus petite solution en première place
    """
    
>>> solveur([[1, 1, -1], [4, 4, 1], [1, 2, 3], [-1, 2, 3]])
[[-1.618033988749895, 0.6180339887498949], [-0.5], [], [-1.0, 3.0]]

### C3. Session 5: Compteur d'événement (2 questions)

### C4. Interrogation

def count_digits(nombre):
    pass

def trouver_doublon(lst):
    pass

# Idée: retourner la personne dont le mot de passe, numérique, est le plus long de la liste. Veuillez utiliser `count_digits`.

def plus_frequent(s):
    pass

### C5. Session 5: Recherche binaire