π
<-
Chat plein-écran
[^]

Correction algo BAC S spécialité 2015 (Inde - avril 2015)

Toutes les news concernant les examens (BAC, DNB, etc.) et concours scolaires

Correction algo BAC S spécialité 2015 (Inde - avril 2015)

Message non lude critor » 18 Avr 2015, 14:37

Le Baccalauréat 2015 a démarré cette semaine, avec les premiers sujets tombés en Inde.

Le sujet de mathématiques pour séries S proposait en exercice pour spécialistes un travail sur les nombres de Mersenne et un algorithme.

4)a)
Pour savoir ce que répond cet algorithme, programmons-le sur notre calculatrice graphique :

Algorithme
Programme
Code: Tout sélectionner
Initialisation :
   Demander la valeur de n.
   Affecter à k la valeur 2.
Traitement :
   Tant que MOD(2ⁿ-1,k)≠0 et k≤√(2ⁿ-1)
      Affecter à k la valeur k+1.
   Fin de Tant que.
Sortie :
   Afficher k.
   Si k>√(2ⁿ-1) alors
      Afficher "CAS 1"
   sinon
      Afficher "CAS 2"
   Fin de Si
Code: Tout sélectionner
Prompt N
2→K
While reste(2^N-1,K)≠0 et K≤√(2^N-1)
   K+1→K
End
Disp K
If K>√(2^N-1)
Then
   Disp "CAS 1"
Else
   Disp "CAS 2"
End

Code: Tout sélectionner
Prompt N
2→K
While remainder(2^N-1,K)≠0 and K≤√(2^N-1)
   K+1→K
End
Disp K
If K>√(2^N-1)
Then
   Disp "CAS 1"
Else
   Disp "CAS 2"
End

Code: Tout sélectionner
Define indess2015(n)=
Prgm
   2→k
   5→b
   While mod(2ⁿ-1,k)≠0 and k≤√(2ⁿ-1)
      k+1→k
   EndWhile
   Disp k
   If k>√(2ⁿ-1) Then
      Disp "CAS 1"
   Else
      Disp "CAS 2"
   EndIf
EndPrgm

Code: Tout sélectionner
?→N
While MOD(2^N-1,K)≠0 And K≤√(2^N-1)
   K+1→K
WhileEnd
K◢
If K>√(2^N-1)
Then "CAS 1"
Else "CAS 2"
IfEnd


Code: Tout sélectionner
Input n
2⇒k
While mod(2^n-1,k)≠0 and k≤√(2^n-1)
   k+1⇒k
WhileEnd
Print k
If k>√(2^n-1)
Then
   "CAS 1"
Else
   "CAS 2"
IfEnd


Attention :

L'exécution avec n=33 prend étrangement 2min30s sur fx-CP400.
La réponse était pourtant quasiment immédiate sur tous les autres modèles.
Code: Tout sélectionner
EXPORT INDESS15(N)
BEGIN
   K:=2;
   WHILE irem(2^N-1,K)≠0 AND K≤√(2^N-1) DO
      K:=K+1
   END;
   PRINT(K);
   IF K>√(2^N-1) THEN
      PRINT("CAS 1")
   ELSE
      PRINT("CAS 2")
   END;
END;


D'après notre calculatrice graphique, l'algorithme affiche donc :
  • pour k=33 :
    7
    CAS 2
  • pour k=7 :
    12
    CAS 1



4)b)
L'algorithme se termine si l'on sort de la boucle 'Tant que'. Si cette boucle se termine, c'est que la condition de poursuite
$mathjax$MOD(2^n-1,k)≠0~et~k≤\sqrt{2^n-1}$mathjax$
n'est plus vérifiée, et qu'il y a réalisation de son contraire
$mathjax$MOD(2^n-1,k)=0~ou~k>\sqrt{2^n-1}$mathjax$
.
Autrement dit, la boucle 'Tant que' se termine sur la réalisation d'une des deux conditions suivantes :
  • $mathjax$MOD(2^n-1,k)=0$mathjax$
  • $mathjax$k>\sqrt{2^n-1}$mathjax$

Dans le cas n°2, on n'a pas
$mathjax$k>\sqrt{2^n-1}$mathjax$
puisque nous sommes dans le bloc 'sinon' de l'instruction conditionnelle, et nous avons donc pas conséquent le contraire
$mathjax$k≤\sqrt{2^n-1}$mathjax$
.
Donc forcément, la boucle s'est terminée sur la réalisation de l'autre condition
$mathjax$MOD(2^n-1,k)=0$mathjax$
.
Le nombre k trouvé par l'algorithme vérifiant donc
$mathjax$MOD(2^n-1,k)=0$mathjax$
et
$mathjax$k≤\sqrt{2^n-1}$mathjax$
est tout simplement le plus petit diviseur différent de 1 du nombre de Mersenne
$mathjax$2^n-1$mathjax$
.
Comme ce diviseur a été trouvé, le nombre de Mersenne
$mathjax$2^n-1$mathjax$
considéré n'est donc pas premier.



4)c)
Dans le cas n°1, nous avons
$mathjax$k>\sqrt{2^n-1}$mathjax$
.
Or, les diviseurs du nombre de Mersenne
$mathjax$2^n-1$mathjax$
différents de ce même nombre sont forcément inférieurs ou égaux à
$mathjax$\sqrt{2^n-1}$mathjax$
.
Aucun diviseur répondant à ces critères n'ayant été trouvé, le nombre de Mersenne
$mathjax$2^n-1$mathjax$
considéré est donc premier.





Liens
:
Image
Avatar de l’utilisateur
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Prochain niv.: 79%
 
Messages: 31040
Images: 7340
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
Classe: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude Mingerton » 18 Avr 2015, 15:53

A noter que la fonction remainder()/reste() n'existe qu'a partir de l'OS 2.53MP sur TI-84+SE. Il faut donc exclure toutes les TI-82 parues jusqu'à présent, ainsi que toutes les TI-83+ qui sont en dessous de la TI-83+.fr USB ;).

A remplacer par ce code sur les modèles non compatibles :
Code: Tout sélectionner
KfPart((2^N-1)/K
Dernière édition par Mingerton le 18 Avr 2015, 15:55, édité 1 fois.
Avatar de l’utilisateur
MingertonAnimat.
Niveau 13: CU (Calculateur Universel)
Niveau 13: CU (Calculateur Universel)
Prochain niv.: 69.6%
 
Messages: 655
Images: 2
Inscription: 13 Mai 2014, 19:36
Localisation: À l'infini
Genre: Homme
Calculatrice(s):
Classe: Américaine

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude Lionel Debroux » 18 Avr 2015, 18:13

Merci Mingerton :)

L'incroyable lenteur de la fx-CP400 frappe encore, je vois...
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Avatar de l’utilisateur
Lionel DebrouxModo.G
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 1%
 
Messages: 6082
Inscription: 23 Déc 2009, 00:00
Localisation: France
Genre: Homme
Calculatrice(s):
Classe: -

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude Bisam » 19 Avr 2015, 09:35

Pour gagner un temps considérable dans l'exécution de l'algorithme, il suffit de calculer et de stocker une bonne fois pour toutes la valeur de
$mathjax$\sqrt{2^n-1}$mathjax$
dans une variable "r" par exemple et de faire les comparaisons de k avec r.
En moyenne, on économise r/2 calculs d'une racine carrée coûteuse sur un nombre relativement grand.

Les concepteurs du sujet auraient sans doute pu rajouter cette petite amélioration !
Avatar de l’utilisateur
BisamAdmin.
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 45.8%
 
Messages: 5400
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
Classe: Prof de Math en Maths Spé PSI

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude critor » 19 Avr 2015, 09:37

Mais à part sur fx-CP400 où il met 2min30, l'algorithme ne pose aucun problème sur les autres modèles.
La réponse y est quasi immédiate.
Dernière édition par Bisam le 19 Avr 2015, 09:40, édité 1 fois.
Image
Avatar de l’utilisateur
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Prochain niv.: 79%
 
Messages: 31040
Images: 7340
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
Classe: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude critor » 19 Avr 2015, 09:57

Voilà Bisam, j'ai testé ton astuce :
Image

On passe à 2min20. :P

Je me demande si ce n'est pas la fonction mod() qui est mal programmée...
Image
Avatar de l’utilisateur
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Prochain niv.: 79%
 
Messages: 31040
Images: 7340
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
Classe: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude critor » 19 Avr 2015, 10:06

Allez, on continue en supprimant le recalcul de 2^n-1 à chaque itération :
Image

Résultat... 2min15

Il ne reste plus grand chose d'effectué à chaque itération.
Donc soit la fonction mod() a été particulièrement mal programmée, soit la fx-CP400 de façon générale gère mal les grands nombres.
Image
Avatar de l’utilisateur
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Prochain niv.: 79%
 
Messages: 31040
Images: 7340
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
Classe: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude Bisam » 19 Avr 2015, 10:07

Certes... mais c'est un principe de base de l'algorithmie : plutôt que de faire un même calcul ne serait-ce que 2 fois, on stocke son résultat.
De plus, ici, le nombre d'itération est tout petit (2^7-1=127 donc sa racine carrée vaut moins de 12, donc 10 itérations et 2^33-1 est divisible par 7 donc 6 itérations), mais si la boucle devait aller jusqu'au bout, la différence se ferait vraiment sentir.

Par exemple, si tu prend n=31, ça prend un temps dingue (j'ai stoppé ma V200 après 10 minutes de calcul) !
Avec n=17, l'algorithme proposé prend 43,35s sur ma V200 alors qu'en stockant simplement la valeur approchée de la racine carrée, on tombe à 6,80s.

Je ne pensais pas particulièrement à la CP400 qui a clairement un problème majeur de calcul !!

PS : tu devrais forcer l'évaluation approchée de la racine carrée pour gagner du temps.
Avatar de l’utilisateur
BisamAdmin.
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 45.8%
 
Messages: 5400
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
Classe: Prof de Math en Maths Spé PSI

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude critor » 19 Avr 2015, 10:10

Bisam a écrit:PS : tu devrais forcer l'évaluation approchée de la racine carrée pour gagner du temps.


Oui tu as raison - peut-être que la fx-CP400 travaille en mode CAS et non en mode numérique/approché.
Ce qui effectivement ferait perdre plus de temps sur les grands nombres.

Mais nous avions déjà tenté de rajouter une instruction 'SetDecimal' en début de programme, et cela n'avait strictement rien changé. :(
Image
Avatar de l’utilisateur
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Prochain niv.: 79%
 
Messages: 31040
Images: 7340
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
Classe: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Re: Correction algo BAC S spécialité 2015 (Inde - avril 2015

Message non lude critor » 19 Avr 2015, 10:17

Non finalement c'est bon avec 'SetDecimal' on dirait.
Image

Cela se termine en une poignée de secondes.

J'étais pourtant sûr d'avoir testé avec 'SetDecimal' et de n'avoir constaté aucune différence.
Mais c'était sur la version sans tes améliorations...
Image
Avatar de l’utilisateur
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Prochain niv.: 79%
 
Messages: 31040
Images: 7340
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
Classe: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Suivante

Retourner vers News Examens / Concours

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 6 invités

-
Rechercher
-
Sujets à la une
"NumWorks++": Challenge de modification matérielle pour rajouter une puce de mémoire Flash !
Offre TI-Planet/Jarrety pour avoir la TI-83 Premium CE avec son chargeur pour 79,79€ port inclus !
Offre TI-Planet/Jarrety pour avoir la TI-Nspire CX CAS à seulement 130€ TTC port inclus!
Jailbreake ta TI-Nspire avec Ndless et profite des meilleurs jeux et applications !
Transforme ta TI-Nspire CX en console Game Boy Advance!
12345
-
Donations/Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
PayPal : paiement en ligne sécurisé - secure online payments
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety 
-
Stats.
413 utilisateurs:
>387 invités
>20 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)