TP #6 : Fonctions

Exemple simple avec fonction

Écrire un algorithme permettant de calculer le salaire hebdomadaire d’un ouvrier connaissant le nombre d’heures effectuées dans la semaine et le salaire horaire. Les 35 premières heures sont payées au salaire horaire, les 10 suivantes avec un supplément de 50% et les autres avec un supplément de 75%.

PGCD

Difficulté facile

Écrire un algorithme permettant de calculer le PGCD de deux entiers positifs donnés. Rappel: Soient a et b deux entiers positifs. On a:

pgcd(a,b) = a si b = 0,
pgcd(a,b) = pgcd(b,reste(a,b)) si b != 0 avec reste(a,b) le reste de la division entière de a par b.

Fibonacci

Difficulté attendu

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: ` 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…` By considering the terms in the Fibonacci sequence whose values do not exceed four millions, find the sum of the even-valued terms. –source Project Euler

Approximation de la fonction exponentielle

Difficulté attendu

On rappelle le développement limité en 0 de $e^x$: $E_n = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$ Écrire une fonction puissance et une fonction factorielle. Écrire ensuite une fonction exp_aprox qui permet de calculer une valeur approchée de $e(x)$ à l’ordre $k$ (donné par l’utilisateur).

Exponentiation rapide

Difficulté attendu

On va améliorer le calcul de $x^n$ en faisant moins de $n$ opérations. La méthode expliquée ici a pour nom exponentiation rapide. Voici un exemple:

$x^{23} = x \times (x^2)^{11}$

$x^{23} = (x \times x^2) \times (x^4)^5$

$x^{23} = (x \times x^2 \times x^4) \times (x^8)^2$

$x^{23} = x \times x^2 \times x^4 \times x^{16} $

Donc, si on calcule les puissances paires de $x$ au fur et à mesure, on réalise moins d’opérations (combien, sur l’exemple ?).

En nommant les différentes parties de l’égalité: res, puiss et k judicieusement, obtenir l’invariant de boucle suivant: A chaque tour de boucle, on a $res*puiss^k=x^n$. Comment obtenir res, puiss, k à la boucle suivante ? Quand s’arrête-t-on ?
Écrire la fonction puiss_dicho qui prend en argument les entiers x et k et qui calcule x^k avec cet algorithme.
Tester sur plusieurs exemples.

Longest Collatz sequence

Difficulté attendu

The following iterative sequence is defined for the set of positive integers:

$n \rightarrow n/2$ (n is even)

$n \rightarrow 3n + 1$ (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

$13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Nombres premiers

Difficulté difficile

Écrire une fonction qui détermine si un nombre n est premier ou non.
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
By listing the first six prime numbers: $2$, $3$, $5$, $7$, $11$, and $13$, we can see that the $6^{th}$ prime is $13$. What is the $10001^{st}$ prime number?
The sum of the primes below $10$ is $2 + 3 + 5 + 7 = 17$. Find the sum of all the primes below two million.
The number, $197$, is called a circular prime because all rotations of the digits: $197$, $971$, and $719$, are themselves prime. There are thirteen such primes below $100$: $2$, $3$, $5$, $7$, $11$, $13$, $17$, $31$, $37$, $71$, $73$, $79$, and $97$. How many circular primes are there below one million?