TI-Planet

by **critor** » 11 May 2013, 12:38

Salut à tous.

En attendant les prochains sujets de BAC fin mai, aujourd'hui continuons à réviser en nous entraînant en algorithmique et programmation avec l'algorithme qui est tombé en exercice 3 pour les Premières ES, L et Technologiques aux Olympiades Académiques dans l'Académie de Nice:

On étudie donc le nombre de cartes nécessaires pour construire un château à n étages.

Question 3:
On nous demande donc à quoi peut bien servir l'algorithme fourni.
Cette question arrivant rapidement en début d'énoncé, on peut se douter qu'il s'agit d'un calcul du nombre de cartes nécessaires.

Cet algorithme utilise de plus une expression factorisée qu'il suffit de développer pour retrouver la formule normalement normalement déterminée à la question 2: 1,5n²+0,5n.

Et même si l'on n'arrivait pas à voir cela, il suffisait de programmer cet algorithme sur nos calculatrices graphiques, et de se rendre compte que les résultats fournis étaient en accord avec ceux du tableau de valeurs de la question 2.

Voici le programme pour toutes les calculatrices TI-82 à TI-84:

Et effectivement, les résultats sont en accord avec le tableau de valeurs du nombre de cartes nécessaires fourni dans l'énoncé:

La même chose est réalisable sur nos calculatrices Casio Graph et Casio Prizm...

Ou même encore sur nos TI-Nspire:

Question 4)a)
Il nous faut donc maintenant créer un algorithme permettant de déterminer le nombre d'étages réalisables avec 500 cartes.

Je vous propose un algorithme autour d'une boucle 'tant que', qui va compter le nombre d'étages en incrémentant un compteur n, tant que l'on ne dépasse pas 500 cartes:

Code: Select all: Traitement: n prend la valeur 1 Tant que 0,5n(3n+1)≤500 n prend la valeur n+1 Fin tant que Sortie: Afficher n-1

La boucle s'arrêtant lorsque le nombre de cartes 0,5n(3n+1) dépasse strictement 500, en fin de boucle le résultat à afficher n'est pas n mais n-1.

Voici un programme implémentant cet algorithme pour toutes TI-82 à TI-84:

Le programme nous donne même la réponse, 18 étages, qui nous permettra de vérifier notre résultat dans la prochaine question 4)b):

Voici maintenant le programme pour toutes Casio Graph et Casio Prizm, qui heureusement nous confirme le même résultat:

Et voici enfin le programme pour toutes TI-Nspire:

A bientôt!

Lien:
Olympiades Académiques 2013 1ère ES/L/Technologiques (Nice)

by **critor** » 02 May 2013, 23:46

Après les algorithmes des Académies d'Aix-Marseille et Besançon dans deux news précédentes, regardons ce soir ensemble l'algorithme tombé en exercice 4 aux Olympiades Académiques de Mathématiques de Première S 2013, dans l'Académie de Mayotte cette fois-ci.

Il s'agit donc d'étudier les déplacements d'une cible chaque seconde entre trois positions 1, 2, 3 selon les règles suivantes:

la cible commence en 1
de 1 et de 3, la cible va en 2
de 2, la cible va en 1 ou 3 de façon équiprobable

L'on peut représenter cette situation à l'aide d'un graphe probabiliste:

Selon le graphe en partant de 1, après un nombre impair de secondes/déplacements, on est forcément en 2.
Après un nombre pair non nul de déplacements, on se retrouve de façon équiprobable, soit en 1, soit en 3.

Question A)1) 1/2
Question A)2)a) 0
Question A)2)b) 1
Question A)3)a) 1/2
Question A)3)b) 0

Question A)4) 0

Notons que cet algorithme est fort mal écrit - avec une fonction EntAlea() qui n'est ni du langage naturel ni du langage mathématique, des parenthèses pour des affichages et des points virgule de séparation de paramètres ou de ponctuation d'instructions.
Un excellent exemple de ce qu'il ne faut pas faire au BAC!

Cela ressemble fortement à un langage de programmation car il y a des contraintes de syntaxe et l'auteur en aurait donc rapidement traduit les instructions en français, ce qui justement n'est pas un algorithme.

Les trous à compléter dans l'algorithme correspondent simplement aux cas étudiés ci-dessus.
On peut donc les compléter de la façon suivante:

Code: Select all: Variables: n entier Début Entrer n Si n est impair alors Afficher "Cible à position 2" sinon Si EntAlea(0,1)=0 alors Afficher "Cible à position 1" sinon Afficher "Cible à position 3" FinSi FinSi Fin

L'on vérifie aisément le fonctionnement correct de l'algorithme en le traduisant en un programme pour notre calculatrice.

Le test de parité de N peut utiliser la fonction partie entière afin de vérifier si N est divisible par 2 ou non.

Voici un programme pour TI-82 à TI-84:

En voici maintenant un pour Casio Graph/Prizm:

Et enfin maintenant, voici une version TI-Nspire:

Encore un 'algorithme' assez mal écrit pour les mêmes raisons que le précédent, d'autant plus qu'il y a deux instructions 'Si' mais un seul 'FinSi'.

Cette fois-ci on utilise une boucle "pour i=... à n faire".
n étant le nombre de déplacements de la cible, nous allons mettre "pour i=1 à n faire" afin de passer exactement n fois dans la boucle.

La cible va en 2 lorsque qu'elle est en 1 ou 3.
Nous complétons donc l'instruction conditionnelle avec "Si C=2 ou C=3".

Enfin, nous avons des affectations de C avec 2 et 1, la dernière affectation correspond donc forcément par élimination à 3, et nous mettons "Sinon C←3".

Voici l'algorithme:

Code: Select all: Variables: n, C, i entiers Début Entrer n C←1 Pour i=1 à n faire Si C=1 ou C=3 alors C←2 sinon Si EntAlea(0,1)=0 alors C←1 sinon C←3 FinSi FinSi FinPour Afficher "la cible est en position", C Fin

L'on vérifie encore une fois que l'algorithme est bon en testant sur calculatrice.

Voici un programme traduisant cet algorithme pour TI-82 à TI-84:

Voici maintenant une version pour Casio Graph/Prizm:

Et voici enfin une version TI-Nspire:

Au final, quelles sont les différences entre ces deux algorithmes?

L'algorithme n°1 n'utilise aucune boucle. Il utilise simplement les règles de probabilité établies dans les questions précédentes.
Il s'exécute donc en un temps constant sur machine, quelle que soit la valeur de n. On dit que sa complexité est en o(1).

L'algorithme n°2 par contre a une toute autre approche et simule réellement à l'aide d'une boucle 'pour' la totalité des n déplacements de la cible.
C'est donc un algorithme linéaire de complexité en o(n), dont le temps d'exécution sur machine sera proportionnel à n.

En complexité, l'algorithme 1 serait donc meilleur et la simulation complète effectuée de l'algorithme n°2 serait inutile dans le contexte de ce qu'il doit renvoyer dans cet exercice.

Notons toutefois un petit bémol, avec le cas particulier n=0 interdit par l'énoncé.
Après 0 déplacement, la cible est par définition en position 1, la position d'origine.
L'algorithme n°2 qui simule tous les détails des déplacements est parfaitement d'accord avec ça.
Mais l'algorithme n°1 se plante une fois sur deux, en nous expliquant que la cible est en position 3 au temps 0, ce qui est impossible!

Lien:
Olympiades Académiques de Mathématiques 2013 - 1ère (Mayotte)

by **critor** » 02 May 2013, 17:05

Après l'algorithme des Olympiades Académiques 2013 d'Aix-Marseille dans une news précédente, intéressons-nous maintenant à l'algorithme tombé dans l'Académie de Besançon.

Question I)2):
On nous donne donc un algorithme à trous, destiné à calculer σ(n) pour tout entier naturel n non nul, où σ(n) est la somme de tous les diviseurs de n.

Lorsque le test "le reste de la division euclidienne de n par k est 0" est vérifié, cela veut dire que k est un diviseur de n.
Il faut donc l'ajouter à la somme des diviseurs déjà trouvée.
Il nous faut donc une variable pour cumuler les diviseurs trouvés au fur et à mesure, et c'est la variable σ initialisée à 0, élément neutre de l'addition, qui joue ici ce rôle.
(si on avait du multiplier les valeurs trouvées au lieu de les additionner, on aurait initialisé la variable à 1, élément neutre de la multiplication)
La dernière instruction manquante sera donc "Affecter à σ la valeur σ+k".

Ce test peut être écrit mathématiquement en utilisant la fonction partie entière E introduite en début de Première S.
On peut alors le récrire par exemple "E(n/k)=n/k".

Enfin, k jouant le rôle des diviseurs de n recherchés, on a 1≤k≤n, ce qui nous permet de compléter les bornes de la boucle 'pour':
"Pour k allant de 1 à n faire"

L'algorithme une fois complété nous donne donc:

Code: Select all: Entrée: n entier naturel non nul Initialisation: σ prend la valeur 0 Traitement: Pour k allant de 1 à n faire Si E(n/k)=n/k alors Affecter à σ la valeur σ+k FinSi FinPour Afficher σ

L'on traduit aisément l'algorithme en un programme pour nos TI-82 à TI-84:

Il est alors aisé de vérifier le résultat de la question I)1) précédente: σ(350)=744

Voici le programme pour Casio Graph/Prizm:

Et voici maintenant le programme pour TI-Nspire:

Une fois le programme fonctionnel, il est alors aisé et rapide de déterminer quelques valeurs de σ(n), ce qui va être utile pour les quelques exemples demandés par les questions suivantes!

Question II)1)
Il nous faut donc déterminer justement σ(n) pour n allant de 1 à 6.
Le programme nous répond rapidement que σ(1)=1, σ(2)=3, σ(3)=4, σ(4)=7, σ(5)=6 et σ(6)=12.

Question III)3)a)
Sachant qu'un nombre parfait n vérifie σ(n)=2n, il suffit de faire calculer quelques valeurs supplémentaires au programme:

On vérifie alors aisément dans la liste des résultats qu'avec σ(6)=12, 6 est le seul nombre parfait inférieur ou égal à 10.

Question III)5)a)
Sachant qu'un nombre presque parfait n vérifie σ(n)=2n-1, on obtient rapidement de façon similaire que les seuls nombres presque parfaits inférieurs ou égaux à 16 sont 1, 2, 4, 8 et 16 avec σ(1)=1, σ(2)=3, σ(4)=7, σ(8)=15 et σ(16)=31.
Tiens, ne seraient-ce pas les puissances de 2?...

Envie de faire un peu plus d'arithmétique et d'algorithmique? Pour une petite 10aine de jours, nous avons encore un concours sur les nombres premiers palindromes!

Lien:
Olympiades Académiques de Mathématiques 2013 - 1ère (Besançon)

by **critor** » 02 May 2013, 15:05

Après les tout premiers sujets de Français dans une news précédente, voici ce soir les tout premiers sujets d'Histoire-Géographie et de Sciences pour les candidats aux épreuves anticipées (Premières) du BAC Général 2013 au lycée français de Pondichéry en Inde!

Au menu:

Histoire-Géographie (Premières S)
Sciences (Premières ES/L)

Bonne découverte!

[tableborder=1 width=100%]Terminales S http://tiplanet.org/bacs2013 Terminales ES http://tiplanet.org/baces2013 Terminales L http://tiplanet.org/bacl2013 Terminales STG http://tiplanet.org/bacstg2013 Terminales ST2S http://tiplanet.org/bacst2s2013 Terminales STI2D http://tiplanet.org/bacsti2d2013 Terminales STD2A http://tiplanet.org/bacstd2a2013 [/table]

[tableborder=1]Premières S

http://tiplanet.org/bacs2013ea Premières ES

http://tiplanet.org/baces2013ea Premières L

http://tiplanet.org/bacl2013ea Premières Technologiques

http://tiplanet.org/bact2013ea [/table]

[tableborder=1]Troisièmes Générales/Collège http://tiplanet.org/dnb2013[/table]

by **critor** » 02 May 2013, 14:25

Après le BAC et le Concours Général, aux Olympiades Académiques 2013 de 1ère sont tombés de nombreux algorithmes.

Intéressons-nous aujourd'hui à l'algorithmique qui est tombé en exercice 3 pour les Premières S dans l'Académie d'Aix-Marseille:

Question 1)a):
Nous étudions donc l'équation (E) 81a+125b+149c=2013, où a, b et c sont des entiers naturels.

Nous avons donc b≥0 et c≥0.
On en déduit 125b≥0 et 149c≥0.
Par sommation des inégalités, 125b+149c≥0

Mais l'équation (E) peut aussi s'écrire 125b+149c=2013-81a.
On en déduit 2013-81a≥0,

D'où: 2013≥81a
2013/81≥a
a≤2013/81

Comme a est un entier positif et que 2013/81≈24,9 on en déduit que 0≤a≤24.

On montre de même que b≤2013/125 et c≤2013/149, ce qui donne 0≤b≤16 et 0≤c≤13.

Question 1)b):
On nous demande donc maintenant d'écrire un algorithme recherchant tous les triplets (a,b,c) solutions de (E).

Il s'agit donc de vérifier l'équation (E) pour tous les triplets de valeurs possibles pour (a,b,c).

L'on peut faire cela en imbriquant 3 boucles 'pour':

Code: Select all: Pour a de 0 à 24 faire Pour b de 0 à 16 faire Pour c de 0 à 13 faire Si 81a+125b+149c=2013 alors Afficher (a,b,c) FinSi FinPour FinPour FinPour

Remarquons que cet algorithme revient à tester 25*17*14=5950 triplets de valeurs.

Il est possible de traduire cet algorithme en un programme pour nos TI-Nspire, qui nous fournissent un seul triplet de solutions (15,4,2) en seulement quelques secondes!

Le même programme est réalisable sur nos TI-82 à TI-84 ou Casio Graph/Prizm, mais il faudra cette fois-ci patienter quelques dizaines de secondes avant d'obtenir les mêmes solutions:

Sans doute est-ce à cause de ce long temps de calcul que la question suivante fait cadeau de a=15!

Jusqu'à présent les boucles 'pour' sont peu fréquentes au BAC, au profit de boucles 'tant que'.
C'est donc une excellente chose d'en parler aujourd'hui, afin de ne pas avoir de trou de mémoire le jour J si jamais...

Lien:
Olympiades Académiques de Mathématiques 2013 - 1èreS (Aix-Marseille)