[PDF] ISUP-python Récursion

Chapitre 3 informatique commune Algorithmes de tris

recherche d’un élément dans un tableau On sait que ce problème a un coût linéaire, mais si on prévoit de faire de nombreuses recherches, il peut être intéressant de commencer par trier ces données, car le coût d’une recherche dichotomique est logarithmique

1 Algorithmesdetri

F JUNIER 2012/2013 Chapitre: Algorithmiquepartie2: algorithmesdetri ISN 2 Letriparsélection 2 1 Algorithme Considérons un joueur decartesqui tient danssamain les cartesendésordredesadonne Onsuppose qu’on adéfinisur les cartes

Université Paris Dauphine IUP Génie Mathématique et Informatique

IUP Génie Mathématique et Informatique - Mise à Niveau Informatique RECHERCHE DICHOTOMIQUE DANS UN TABLEAU D'ENTIERS #include /* Programm int main() e de recherche dichotomique d'un élément dans une liste d'entiers */

ISUP-python Récursion

language keywords forbidden lower/UPPER case discrimination ☝ expression with just comas →tuple dictionary collection integer, oat, boolean, string, bytes Identi ers ☺ a toto x7 y_max BigOne ☹ 8y and for x+=3 x-=2 increment ⇔ x= +3 decrement ⇔ x= -2 Conversions for lists, tuples, strings, bytes int("15") → 15

2 Quelquesalgorithmesdetri

On peut améliorer l’algorithme précédent en effectuant une recherche dichotomique de la place de l’élément à insérer dans la tranche qui le précède, puisqu’elle est triée Cela permet de ramener le nombredecomparaisonsàunO(nlog2n),maiscelan’évitepaslesdécalagesd’élémentsdutableau,

Programmation récursive 1 Quest-ce que la - LIPN

3 2 Récursivité simple : recherche dichotomique On stocke des paires (index, objet) dans un tableau Le tableau est rangé par index (des chaînes en ordre alphabétique) L'utilisateur fournit un index et on doit lui renvoyer l'objet associé public class DichoMap {MapObject table[] ; MapObject getObject(String index)

Algorithmes et programmation en Pascal

6 Algorithmes et programmation en Pascal Edouard Thiel I Les variables en Pascal 1 Premiers programmes 1 1 Le programme bonjour Un programme est une suite d’instructions, certaines etan t des mots cl es

Exo7 - Cours de mathématiques

Algorithmes et mathématiques Chapitre 1 Vidéo — partie 1 Premiers pas avec Python Vidéo — partie 2 Ecriture des entiers Vidéo — partie 3 Calculs de sinus, cosinus, tangente

QCM - Epidocs

[PDF] exemple de manuel de procedure informatique

[PDF] organisation d une dsi type

[PDF] manuel de procédures informatiques

[PDF] cyberlux 8

[PDF] organisation d'un service informatique dans une entreprise

[PDF] cyberlux 8 crack

[PDF] exemple dossier exploitation informatique

[PDF] cyberlux 8 full

[PDF] bibliographie de max weber

[PDF] max weber pdf

[PDF] max weber économie et société tome 2 pdf

[PDF] max weber le savant et le politique pdf

[PDF] max weber économie et société fiche de lecture

[PDF] max weber économie et société tome 1 résumé

[PDF] max weber économie et société pdf

ISUP-pythonRécursion

Larécursion•Exempledefactorielle

Larécursion•Exempledefactorielle

6a11aExercises61

Exercise6a5aTheAckermannfunctionc AnmcnmcisdeÞned:

Anmcnm=

t u p u l nr1ifm=d

Anmt1c1mifm>dandn=d

Anmt1cAnmcnt1mmifm>dandn>da

SeeaWrite afunctionnamed

thatevaluatesAckermannÕ sfunctionaUse yourfunctiontoevaluatecwhichshould be

1x5aWhathappens forlarger valuesof and?Solution:

a Exercise6a6aApalindrome isawordthatisspelled thesamebackward andforwardclike ÒnoonÓ andÒredivider ÓaRecursivelycawordisapalindr omeiftheÞrstandlast lettersare thesameand the middleisa palindromea Thefollowingar efunctionsthat takeastringargumentand returnthe Þrstclastc andmiddleletters:

WeÕllseehowtheywork inChapter8a

1aType thesefunctionsintoaÞle namedandtestthem outaWhathappens if

youcallwithastring withtwoletters? Oneletter?What abouttheempty stringc whichiswritten andcontainsno letters? xaWrite afunctioncalledthattakesa stringar gumentandr eturnsifit isapalindr omeandotherwiseaRememberthat youcanuse thebuilt.infunction tocheckthe lengthofa stringa

Solution:a

Exercise6a7aAnumberc acisapowerof bifitisdivisibleby banda obisa powerofb aW ritea functioncalledthattakesparameters andandreturns ifisapower ofaNote: youwillhave tothinkabout thebase casea Exercise6a8aThegreatest commondivisornGCDmofa andbis thelargest numberthatdivides bothofthem withnor emaindera Onewayto ÞndtheGCD oftwo numbersisbased ontheobservation thatifr isther emainderwhen ais dividedbybctheng cdnacbm=gcdnbcrmaAsa basecasecwe canuse gcd nacdm=aa Retour sur ce qu'on a vu Sequence Containers Indexing

Base Types

Python 3 Cheat Sheet

©2012-2015 - Laurent Pointal

License Creative Commons Attribution 4

Latest version on :

0783-192int

9.23-1.7e-60.0float

TrueFalsebool

"One\nTwo" 'I\'m' str """X\tY\tZ

1\t2\t3"""

×10

-6 escaped tab escaped new line

Multiline string:

Container Types

list[1,5,9]["x",11,8.9]["mot"][] tuple (1,5,9)11,"y",7.4("mot",)() dict {1:"one",3:"three",2:"two",3.14:"π"} {"key":"value"} set {1,9,3,0} ◾ ordered sequences, fast index access, repeatable values set() ◾ key containers, no a priori order, fast key acces, each key is unique {"key1","key2"}

Non modiable values (immutables)

Variables assignment

x=1.2+8+sin(y) y,z,r=9.2,-7.6,0 a...zA...Z_ followed by a...zA...Z_0...9 ◽ diacritics allowed but should be avoided ◽ language keywords forbidden ◽ lower/UPPER case discrimination ☝ expression with just comas →tuple dictionary collection integer, %oat, boolean, string, bytes

Identiers

☺ a toto x7 y_max BigOne ☹ 8y and for x+=3 x-=2 increment ⇔ x=x+3 decrement ⇔ x=x-2

Conversions

for lists, tuples, strings, bytes... int("15") → 15 int("3f",16) → 63can specify integer number base in 2 nd parameter int(15.56) → 15truncate decimal part float("-11.24e8") → -1124000000.0 round(15.56,1)→ 15.6rounding to 1 decimal (0 decimal → integer number) bool(x)False for null x, empty container x , None or False x ; True for other x str(x)→ "..."representation string of x for display (cf. formating on the back) chr(64)→'@'ord('@')→64code ↔ char repr(x)→ "..."literal representation string of x bytes([72,9,64]) → b'H\t@' list("abc") → ['a','b','c'] dict([(3,"three"),(1,"one")]) → {1:'one',3:'three'} set(["one","two"]) → {'one','two'} separator str and sequence of str → assembled str ':'.join(['toto','12','pswd']) → 'toto:12:pswd' str splitted on whitespaces → list of str "words with spaces".split() → ['words','with','spaces'] str splitted on separator str → list of str "1,4,8,2".split(",") → ['1','4','8','2'] sequence of one type → list of another type (via comprehension list) [int(x) for x in ('1','29','-3')] → [1,29,-3] type(expression) lst=[10, 20, 30, 40, 50] lst[1]→20 lst[-2]→40 01234
-5-4-3-1-2Individual access to items via lst[index] positive index negative index

012354

-5-4-3-1-2negative slice positive slice Access to sub-sequences via lst[start slice:end slice:step] len(lst)→5 lst[1:3]→[20,30] lst[::2]→[10,30,50] lst[-3:-1]→[30,40] lst[:3]→[10,20,30] lst[:-1]→[10,20,30,40] lst[3:]→[40,50] lst[1:-1]→[20,30,40] lst[:]→[10,20,30,40,50] Missing slice indication → from start / up to end. On mutable sequences (list), remove with del lst[3:5] and modify with assignment lst[1:4]=[15,25]

Conditional Statement

if age<=18: state="Kid" elif age>65: state="Retired" else: state="Active"

Boolean Logic

Statements Blocks

parent statement: statement block 1... parent statement: statement block2... next statement after block 1 i n d e n t a t i o n

Comparators: < > <= >= == !=

a and b a or b not a logical and logical or logical not one or other or both both simulta- -neously if logical condition: statements block statement block executed only if a condition is true

Can go with several elif, elif... and only one

8nal else. Only the block of 8rst true

condition is executed. lst[-1]→50 lst[0]→10 ⇒ last one ⇒ rst one x=None" undened » constant value Maths

Operators: + - * / // % **

integer ÷÷ remainder a b from math import sin,pi... sin(pi/4)→0.707... cos(2*pi/3)→-0.4999... log(e**2)→2.0 ceil(12.5)→13 floor(12.5)→12 escaped ' ☝ %oating numbers... approximated valuesangles in radians (1+5.3)*2→12.6 abs(-3.2)→3.2 round(3.57,1)→3.6 pow(4,3)→64.0 for variables, functions, modules, classes... names

Mémento v2.0.4

str(ordered sequences of chars / bytes) (key/value associations) ☝ pitfall : and and or return value of a or of b (under shortcut evaluation). ⇒ ensure that a and b are booleans. (boolean results) a=b=c=0assignment to same value multiple assignments a,b=b,avalues swap a,*b=seq *a,b=seq unpacking of sequence in item and list bytes bytes b"toto\xfe\775" hexadecimaloctal

0b0100xF30o642

binaryoctalhexa empty dict(a=3,b=4,k="v")

Items count

☝ keys=hashable values (base types, immutables...) True False

True and False constants

☝ congure editor to insert 4 spaces in place of an indentation tab. lst[::-1]→[50,40,30,20,10] lst[::-2]→[50,30,10]

1) evaluation of right side expression value

2) assignment in order with left side names

☝ assignment ⇔ binding of a name with a value ☝ immutables

On mutable sequences (list), remove with

del lst[3] and modify with assignment lst[4]=25 del xremove name x b"" @ → matrix × python3.5+numpy ☝ index from 0 (here from 0 to 4) frozenset immutable set

Priority (...)

☝ usual priorities modules math, statistics, random, decimal, fractions, numpy, etc. (cf. doc)

Modules/Names Imports

from monmod import nom1,nom2 as fct module truc⇔le truc.py →direct acces to names, renaming with as import monmod →acces via monmod.nom1 ... ☝ modules and packages searched in python path (cf sys.path) yes no shallow copy of sequence yesno and ☝ with a var x: if bool(x)==True:⇔ if x: if bool(x)==False:⇔ if not x:

Exceptions on Errors

raise Exception(...)

Signaling an error:

Errors processing:

try: normal procesising block except Exception as e: error processing block normal processing error processing error processing raise raise null ☝ finally block for nal processing in all cases. "modele{} {} {}".format(x,y,r) "{selection:formating!conversion}" ◽ Selection : 2 nom 0.nom

4[key]

0[2] str

Display

print("v=",3,"cm :",x,",",y+4) print options: ◽ sep=" "items separator, default space ◽ end="\n"end of print, default new line ◽ file=sys.stdoutprint to 8le, default standard output items to display : literal values, variables, expressions loop on dict/set ⇔ loop on keys sequences use slices to loop on a subset of a sequence Conditional Loop Statementstatements block executed as long as condition is true while logical condition: statements block s = 0 i = 1 while i <= 100: s = s + i**2 i = i + 1quotesdbs_dbs5.pdfusesText_10