Arithmétique Suites (à venir) Extremum (à venir) Calculs approchés d'intégrales Solution approchée de f(x)=0 Equation du second degré (à venir) Approximation d'une solution d'une équation différentielle. (à venir)
Test de primalité (difficulté moyenne) (testé)
Explications |
Programme Casio |
Programme Texas |
|
On se donne un entier n |
Input n |
Prompt n |
|
Si il est plus petit ou égal à 1, il n'est pas premier. On l'affiche et on sort du programme |
If n<=1
Then
Print "non"
Return
Ifend |
if n<=1 then
disp "non"
return
endif |
|
Sinon, on le dit a priori premier, en donnant la valeur 1 à la variable p. |
1=>p |
1->p |
|
Puis on va diviser n par des entiers successifs en commençant par 2 et en allant jusqu'à la racine carée de n. Ces entiers seront désignés par la variable k. Et pour éviter de calculer à chaque fois la racine carrée de n, on la met dans la mémoire r. |
2=>k
n^0.5=>r |
2->k
n^0.5->r |
|
On effectue donc une boucle se terminant dès que k dépasse strictement r ou bien que p vaut 0 (ce qui signifie que n n'est pas premier) |
While k<=r and p=1 |
While (k<=r and p=1) |
|
Dans cette boucle on teste si le reste de la division de n par k est nul, dans ce cas n n'est pas premier et on affecte la valeur 0 à p. |
If mod(n,k)=0
then
0=>p
Ifend |
if mod(n,k)=0 then
0->p
endif |
|
Puis, à la fin de la boucle, on incrémente k |
k+1=>k
WhileEnd |
k+1->k
Endwhile |
|
Au sortir de la boucle on teste si p vaut 1 ou 0, ce qui nous donne que n est premier ou non. |
If p=0
then
print "non"
Else
Print "oui"
IfEnd |
if p=0 then
disp "non"
else
disp "oui"
endif |
Test de primalité de Fermat (version simple mais limitée)
Ce test est basé sur le fameux théorème : si n est premier alors pour tout a non congru à zéro modulo n, on a a^(n-1) qui est congru à 1 modulo n. En effet, si n est premier, (Z/nZ) privé de 0 est un groupe contenant n-1 éléments, et comme l'ordre de tout élément divise l'ordre du groupe, tout élément non nul de Z/nZ mis à la puissance n-1 sera congru à 1 modulo n.
Dans ce programme on a choisit a=2. Si a^(n-1) n'est pas congru à 1 modulo n alors on peut affirmer que n n'est pas premier, autrement n a de grandes chances d'être premier. Comme on choisit a=2, n doit bien sûr être strictement plus grand que 2. On peut remarquer que ce test marche parfaitement jusqu'à 340. Mais il indique que les nombres 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957 sont peut-être premiers alors qu'ils ne le sont pas. Pour améliorer ce test il faudrait aussi essayer une autre valeur pour a (a=3 par exemple).
Ce programme teste très rapidement les nombres jusqu'à 2011, mais donne une erreur de dépassement au delà (si ce n'est pas le cas c'est que vous n'êtes pas en mode exact).
Explications |
Programme Casio |
Programme Texas |
| On demande l'entier n qui doit être testé |
Input n |
Prompt n |
| On met dans la variable b le produit des (n-1) 2 modulo n. |
mod(2^(n-1),n)=>b |
mod(2^(n-1),n)->b |
| Si b vaut 1, n est sans doute premier, sinon il n'est pas premier |
If b=1
Then
Print "premier?"
Else
Print "Pas premier"
Ifend |
If b=1 then
Disp "premier?"
Else
Disp "Pas premier"
Endif |
Test de primalité de Fermat (difficulté moyenne)
Ce programme autorise le test de nombres plus grands. Mais il est loin d'être optimisé. Le principe est le suivant : comme il y a un dépassement pour des puissances supérieures à 2000, on effectue la division euclidienne de n-1 par 2000 : n-1=2000*q+r, on calcule 2^2000 modulo n, puis on le multiplie par lui même q fois modulo n avec une boucle, et enfin on multiplie le résultat par 2^r modulo n.
Explications |
Programme Casio |
Programme Texas |
| |
Input n |
|
| même chose que le précédent programme si n est plus petit que 2000. Sinon ... |
If n<2000
Then
mod(2^(n-1),n)=>b
Else |
|
| On effectue la division euclidienne de n-1 |
Int((n-1)/2000)=>q
mod(n-1,2000)=>r |
|
| Calculs intermédiaires |
mod(2^r,n)=>b
mod(2^2000,n)=>a |
|
| On multiplie b par la puissance q ième de a, en calculant cette puissance produit par produit à l'aide d'une boucle |
For 1=>i to q
mod(b*a,n)=>b
Next
IfEnd |
|
| On affiche la conlusion. |
If b=1
Then
Print "Premier?"
Else
Print "Pas premier"
IfEnd |
|
Test de primalité de Fermat : version optimisée (difficile mais intéressante !)
Le principe est le suivant : pour calculer a^(n-1) on va décomposer n-1 en base 2. Ainsi, on pourra calculer a^(n-1) uniquement avec les puissances de a dont les exposants sont des puissances de 2. Et ces derniers nombres sont faciles à calculer puisque : (a^(2^i))^2=a^(2^(i+1)).
Par exemple 2010=2^10+2^9+2^8+2^7+2^6+2^4+2^3+2. Si on appelle ai le nombre a^(2^i),
on a a^2010=a10*a9*a8*a7*a6*a4*a3*a1, soit 7 multiplications à effectuer, plus 9 carrés à calculer (au lieu de 2009 opérations)
Explications |
Programme Casio |
Programme Texas |
| a est déclarée locale pour éviter un encombrement de la mémoire. Dans le tableau a seront stockés les puissances de 2 dont les exposants sont des puissances de 2. |
Local a
Input n |
|
| On calcule la taille du tableau a. Une difficulté technique vient du fait que le tableau commence à l'indice 1 et non à l'indice 0. On est donc obligé de rajouter 1. |
Int(ln(n-1)/ln(2))+1=>k |
|
| On initialise le tableau à 0. |
seq(0,i,1,k)=>a |
|
|
On calcule les puissances de 2 à exposant puissance de 2. les nombres ai suivent la relation de récurrence a(i+1)=(ai)^2 et a0 vaut 2=(2^(2^0)).
a0 est stocké dans a[1] (décalage)
Bien sûr on calcule tout modulo n. |
2=>b
For 1=>i to k
b=>a[i]
mod(b^2,n)=>b
next |
|
| On va soustraire à p les puissances de 2, en commençant par la plus grande. En même temps on calcule le produit des ai correspondants pas à pas, le produit partiel est mis dans la variable b, qui est bien sûr initialisée à 1. |
n-1=>p
1=>b
While p>0
Int(ln(p)/ln(2))+1=>k
mod(b*a[k],n)=>b
p-2^(k-1)=>p
WhileEnd |
|
| Comme d'ab' |
If b=1
Then
Print "Premier?"
Else
Print "Pas premier".
Endif |
|
Décomposition d'un entier en produit de facteurs premiers (difficulté moyenne)
Explications |
Programme Casio |
Programme Texas |
|
On se donne un entier n |
Input n |
Prompt n |
|
Puis on va diviser n par des entiers successifs en commençant par 2 et en allant jusqu'à n. Ces entiers seront désignés par la variable k. Dans la variable m on met ce qui reste à factoriser. Au départ m vaut donc n. On aura toujours n qui sera égal à m multiplié par tous les facteurs affichés. |
2=>k
n=>m |
2->k:
n->m |
|
On effectue donc une boucle se terminant dès m vaut 1 (la factorisation est alors finie) |
While m>1 |
While (m>1) |
|
Dans cette boucle on teste si le reste de la division de m par k est nul, dans ce cas k est un nouveau facteur de n, on l'affiche puis on remplace m par m/k. Dans ce cas on n'incrémente pas k, car n peut contenir plusieurs fois le même facteur premier. |
If mod(m,k)=0
Then
Print k
m/k=>m
else |
if mod(m,k)=0
then
disp k
m/k->m
else |
|
Autrement, on incrémente k, si k n'est pas premier ce n'est pas grave, car alors k ne pourra pas diviser n. |
k+1=>k
IfEnd
WhileEnd |
k+1->k
endif
Endwhile |
Décomposition d'un entier en produit de facteurs premiers (plus difficile)
Ce dernier programme est plus efficace que le précédent qui continue de diviser m, même lorsque k dépasse la racine carrée de m. On rajoute donc ici la racine carrée de m dans la variable r et si jamais k dépasse cette valeur, au lieu de l'augmenter de 1, on lui donne directement la valeur m, ce qui termine assez rapidement le programme.
Explications |
Programme Casio |
Programme Texas |
|
On se donne un entier n |
Input n |
Prompt n |
|
Puis on va diviser n par des entiers successifs en commençant par 2 et en allant jusqu'à n. Ces entiers seront désignés par la variable k. Dans la variable m on met ce qui reste à factoriser. Au départ m vaut donc n. On aura toujours n qui sera égal à m multiplié par tous les facteurs affichés. |
2=>k
n=>m
m^0.5=>r |
2->k:
n->m
m^0.5->r |
|
On effectue donc une boucle se terminant dès m vaut 1 (la factorisation est alors finie) |
While m>1 |
While (m>1) |
|
Dans cette boucle on teste si le reste de la division de m par k est nul, dans ce cas k est un nouveau facteur de n, on l'affiche puis on remplace m par m/k. Dans ce cas on n'incrémente pas k, car n peut contenir plusieurs fois le même facteur premier. |
if mod(m,k)=0
then
Print k
m/k=>m
m^0.5=>r
else |
if mod(m,k)=0
then
disp k
m/k->m
m^0.5->r
else |
|
Autrement, on incrémente k, si k n'est pas premier ce n'est pas grave, car alors k ne pourra pas diviser n. Et si k dépasse la racine carrée de m, on lui affecte la valeur m directement.
Pourquoi ne pas mettre directement la racine carrée de m au lieu de r ?
Réponse : par souci d'efficacité. La racine carrée n'est pas calculée à chaque fois, mais une seule fois. |
k+1=>k
if k>r
m=>k
IfEnd
IfEnd
WhileEnd |
k+1->k
if k>r
m->k
Endif
endif
Endwhile |
Crible d'Eratosthène (plus difficile)
Ce programme affiche tous les nombres premiers inférieurs à 200.
Explications |
Programme Casio |
Programme Texas |
|
Déclaration de variables, cela permet d'éviter d'effacer d'autres variables et de ne pas encombrer la mémoire puisque ces variables sont effacées après exécution du programme |
Local i,j,n,a |
|
|
On va chercher les nombres premiers inférieurs à la valeur donnée à n.
On affecte 1 à tous les élements de la liste a, qui en contient autant que n. Dire que le ième terme de la liste a vaut 1 c'est dire que i est premier. Donc au départ tous les nombres sont considérés comme premiers (a priori) |
200=>n
seq(1,i,1,n)=>a |
|
| On regarde ces nombres du plus petit au plus grand, en commençant par 2. |
For 2=>i to n |
|
| Si i est premier, on l'affiche et on va faire le crible |
If a[i]=1
then
Print i |
|
| On commence le crible à partir de i*i, en effet les autres multiples de i ont déjà été repérés. |
i^2=>j |
|
| On continue le crible tant qu'on ne dépasse pas la valeur maximum (ici n) |
While j<=n |
|
| j est déclaré non premier en affectant la valeur 0 à a[j] |
0=>a[j] |
|
| On passe au multiple de i suivant. |
j+i=>j
WhileEnd |
|
| Fin du test et de la première boucle. |
IfEnd
Next |
|
Dichotomie
L'objectif est de trouver une valeur approchée d'une solution de f(x)=0. Si f est continue et change de signe entre a et b, on sait d'après le théorème des valeurs intermédiaires que f s'annule (au moins une fois) entre a et b.
Casio : on place l'expression de notre fonction dans la variable y1, en mode Graphe. On choisit également de calculer en valeurs approchées (settings, paramétrages, format de base, calcul décimal)
Explications |
Programme Casio |
Programme Texas |
| On demande les extrémités a et b de notre intervalle où la fonction change de signe. Aucune vérification est faite. Ensuite on demande une valeur maximum de l'erreur commise sur l'approximation du zéro de la fonction. |
Input a
Input b
Input e |
|
| On va poursuivre l'algorithme tant que les extrémités de l'intervalle sont éloignées de plus que e |
While abs(b-a)>e |
|
| On calcule le milieu du segment que l'on place dans la variable c. Puis on teste si f(c) et f(a) ont un signe différent, et dans ce cas c'est l'extrémité b qui est changée est qui vaut c. Dans l'autre cas, f(c) et f(b) ont des signes différents donc c'est la variable a qui prend la valeur c |
(a+b)/2=>c
If y1(a)*y1(c)<0
then
c=>b
else
c=>a
EndIf |
|
| Fin de la boucle |
WhileEnd |
|
| On affiche alors le milieu du dernier segment. Etant donné les erreurs éventuelles d'arrondi, on peut dire que ce nombre approche le zéro (ou plutôt un des zéros) de f avec une erreur inférieure à e. |
print (a+b)/2 |
|
|
Ce programme calcule simplement le terme de rang n dans l'alogrithme de Newton. Je rappelle que cet algorithme converge très rapidement vers la solution d'une équation du type f(x)=0 à condition que l'on puisse se placer dans un intervalle I contenant la solution et tel que f'' soit de signe constant. Il faut alors choisir un premier terme x0 tel que f(x0)f''(x0) soit strictement positif.
L'alogrithme est une simple récurrence : on trace la tangente en (xn,f(xn)), celle-ci coupe l'axe des abscisses en un point d'abscisse x{n+1}
Casio : on place l'expression de notre fonction dans la variable y1, en mode Graphe, et celle de sa dérivée dans la variable y2. On choisit également de calculer en valeurs approchées (settings, paramétrages, format de base, calcul décimal)
Explications |
Programme Casio |
Programme Texas |
| On demande le premier terme ainsi que le rang du terme que l'on va calculer. |
Input x
Input n |
|
| On effectue une boucle n fois |
For 1=>i to n |
|
|
A chaque passage on calcule le terme suivant en le plaçant dans la variable x.
Les fonctions y1 et y2 sont respectivement la fonction et sa dérivée |
x-y1(x)/y2(x)=>x |
|
| Fin de la boucle |
Next |
|
| On affiche le terme de rang n |
Print x |
|
Ce programme va calculer de trois façons une valeur approchée de l'intégrale d'une fonction sur un segment [a,b]. Ce que les méthodes ont en commun, c'est qu'elles calculent une moyenne coefficentée de la fonction f sur le segment [a,b]. Suivant les méthodes, on ne prend pas les valeurs de f aux mêmes endroits, ni avec les mêmes coefficients.
Le programme calcule donc une somme, puis la moyenne de cette somme.
Casio : on place l'expression de notre fonction dans la variable y1, en mode Graphe. On choisit également de calculer en valeurs approchées (settings, paramétrages, format de base, calcul décimal)
Explications |
Programme Casio |
Programme Texas |
| On commence par demander les bornes de l'intervalle, puis le nombre de subdivisions de cet intervalle. Suivant les méthodes, le nombre n n'est pas égal au nombre d'appels de la fonction. Il représente juste un découpage du segment. |
Input a
Input b
Input n |
|
| On calcule la longueur de chacun des intervalles de la subdivision, ce que l'on appelle le pas de la subdivision. |
(b-a)/n=>pas |
|
| med et tra sont des variables qui vont nous servir à calculer une somme de valeurs de la fonctions. med pour la méthode du point médian (le milieu de chaque petit intervalle), tra pour la méthode des trapèzes. |
0=>med
0=>tra |
|
| Les points de départ des deux méthodes : a pour la méthode des trapèzes, le milieu du premier sement [a,a+pas] pour la méthode du point médian. |
a+pas/2=>xmed
a=>xtra |
|
| On va calculer la somme de n termes |
for 1=>i to n |
|
| Calculs des sommes partielles |
med+y1(xtra)=>med
tra+y1(xtra)=>tra |
|
| On se décale de la valeur du pas |
xmed+pas=>xmed
xtra+pas=>xtra |
|
| Et on continue la boucle. |
Next |
|
| Il y a un petit correctif à faire pour la méthode des trapèzes : les coefficients des extrémités a et b doivent être égaux à 0.5, on a donc compté 0.5 valeur en a en trop et 0.5 valeur de la fonction en b en moins. En tout, on aura n-1 valeurs de la fonction strictement entre a et b, plus deux fois 1/2 valeur aux extrémités, soit n valeurs. |
tra+(-y1(a)+y1(b))/2=>tra |
|
| Calculs des moyennes |
tra/n=>itra
med/n=>imed |
|
| affichage |
print itra
print imed |
|
| Une surprise : on peut calculer la méthode de simpson à l'aide d'une moyenne des deux précédentes. Pour cette dernières méthodes, il y a eu 2n+1 appels à la fonction f. |
print (2*imed+itra)/3 |
|
|
