π
<-
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)

Unread postby critor » 18 Apr 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: Select all
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
[tr][td]
Code: Select all
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: Select all
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: Select all
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: Select all
?→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: Select all
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: Select all
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;

[/td][/tr]

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
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 93.9%
 
Posts: 32632
Images: 8517
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

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

Unread postby Mingerton » 18 Apr 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: Select all
KfPart((2^N-1)/K
Last edited by Mingerton on 18 Apr 2015, 15:55, edited 1 time in total.
User avatar
MingertonAnimat.
Niveau 13: CU (Calculateur Universel)
Niveau 13: CU (Calculateur Universel)
Level up: 69.6%
 
Posts: 655
Images: 2
Joined: 13 May 2014, 19:36
Location: À l'infini
Gender: Male
Calculator(s):
Class: Américaine

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

Unread postby Lionel Debroux » 18 Apr 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.
User avatar
Lionel DebrouxModo.G
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Level up: 4.4%
 
Posts: 6330
Joined: 23 Dec 2009, 00:00
Location: France
Gender: Male
Calculator(s):
Class: -
GitHub: debrouxl

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

Unread postby Bisam » 19 Apr 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 !
User avatar
BisamAdmin.
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 47.4%
 
Posts: 5420
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

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

Unread postby critor » 19 Apr 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.
Last edited by Bisam on 19 Apr 2015, 09:40, edited 1 time in total.
Image
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 93.9%
 
Posts: 32632
Images: 8517
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

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

Unread postby critor » 19 Apr 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
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 93.9%
 
Posts: 32632
Images: 8517
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

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

Unread postby critor » 19 Apr 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
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 93.9%
 
Posts: 32632
Images: 8517
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

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

Unread postby Bisam » 19 Apr 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.
User avatar
BisamAdmin.
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 47.4%
 
Posts: 5420
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

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

Unread postby critor » 19 Apr 2015, 10:10

Bisam wrote: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
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 93.9%
 
Posts: 32632
Images: 8517
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

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

Unread postby critor » 19 Apr 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
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 93.9%
 
Posts: 32632
Images: 8517
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Next

Return to News Examens / Concours

Who is online

Users browsing this forum: No registered users and 2 guests

-
Search
-
Featured topics
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 !
123
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...

Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety 
-
Stats.
345 utilisateurs:
>331 invités
>10 membres
>4 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)