1

Bonjour j'aurai aimé que l'on m'aide à créer un programme pour ma Ti-84+

En fait je cherche à sortir aléatoirement tous les chiffres de 1 à n.
J'arrive bien à faire sortir des chiffres aléatoirement avec rand, mais je ne sais pas comment faire pour faire vérifier à la machine que les nombres n'aient pas été déjà sortis.

Je prends un exemple: de 1 à 5, la calco peut me sortir 2 2 5 3 1
Alors que je voudrai par exemple 2 1 5 3 4

Je vous donne mon programme :
:Prompt N
:For (I,1,N)
:randInt(1,N)->A
grinisp A
:Pause
:End

Merci d'un coup de main! :-)
avatar

2

C'est en fait assez difficile, car la TI ne sais pas le faire directement. Il faut donc programmer soi-meme une routine plus longue:
il faut d'abord creer une liste contenant tous les n° voulus (ex: {5,4,3,2,1}).
Ensuite on fixe un compteur au nombres de numeros (ici 5->X), puis on cree une boucle qui agira ainsi:

For(X,5,1,-1) (on applique 5 fois la boucle avec X valant 5 au premier passage, puis 4, puis 3,2, et enfin 1)
randInt(1,X)->A (on tire au sort un n° de 1 à X car il y en a X nons nuls dans la liste, qui sont les X premiers puisqu'on trie la liste par ordre décroissant a chaque fois)
L1(A)->B (on donne la valeur correspondante dans les numeros non utilisés de la liste)
Pause B (affichage de B et pause en meme temps)
0->L1(X) (on efface ce n° puisqu'il est mainteant deja pris)
SortD(L1) (on retrie la liste par odre decroissant pour balancer le 0 a la fin)
End
<-- et à votre gauche une superbe peinture pointilliste du XVIe siècle #sisi# représentant - vous l'aurez deviné - une banane ...
http://www.ti83plus.online.fr/home.php...

3

Ca ne marche pas....
avatar

4

[nosmile]Salut !

Voilà ce que je propose :

:Prompt N
:seq(Z,Z,1,N->L1
:For(Z,0,N-1
:N-Z->dim(L1
:randInt(1,dim(L1
grinisp L1(Ans
:Pause
:0->L1(Ans
sorryortD(L1
:End


C'est le plus court que j'ai pu trouver.

5

Oups dsl pour les smileys, remplace les par D et S ^^

6

T'as une balise [nosmile] à mettre au début des posts (et à ne pas refermer), qui permet d'annuler les smileys.

7

Toi qui est modo, tu peux corriger mon post stp ?

8

Krysthine (./3) :
Ca ne marche pas....

Oui pardon, j'ai mis X au lieu de A :

{1,2,3,4,5}->L1
For(X,5,1,-1)
randInt(1,X)->A
L1(A)->B
Pause B
0->L1(A)
SortD(L1)
End


Et pour la génération de la liste de depart pour tout N, le seq utilisé par Baruch est idéal (d'ailleurs ton code me semble en effet totalement optimisé niveau taille, si ce n'est que j'irais de N à 1 pour le For et non de 0 à N-1 pour eviter le "N-Z->dim(L1", ca fait gagner 1 caractere grin (apres pour un debutant, faut mieux d'abord comprendre le code avant de penser a la taille du prog - un probleme de riches ^^))

Prompt N
seq(Z,Z,1,N->L1
et on remplace biensur le 5 dans le For( par N.
<-- et à votre gauche une superbe peinture pointilliste du XVIe siècle #sisi# représentant - vous l'aurez deviné - une banane ...
http://www.ti83plus.online.fr/home.php...

9

Baruch (./7) :

Toi qui est modo, tu peux corriger mon post stp ?

Voilà smile (mais tu peux toi aussi l'éditer)

10

[nosmile]

A oui dsl j'avais complètement zappé le lien ^^.

Eh non malheureux ! ^^ Si tu fais For(Z,1,N), tu as un bug à la ligne suivante lorsque Z=N, car N-Z=0
A oui, j'ai déplacé le Pause, car il est plus logique de le mettre après le plus de calculs possibles (vous devinez pk ?)
Au fait, j'ai testé et j'ai constaté qu'utiliser par exemple seq(Z,Z,1,6->L1 est bien plus long que de faire {1,2,3,4,5,6->L1, mais je ne sais pas si le seq devient intéressant pour d'autres N.
Mais bon de toute façon ici on ne connaît pas la taille de la liste, donc seq est obligé.
La découverte de la semaine : Pause 2 implique 2->Ans, contrairement à Disp.
Edit : j'ai trouvé mieux que le SortD(L1. Pour les grands N, le tri devient long, donc voyez ce que j'ai mis à la place.
Edit 3 (le 2 n'avait plus d'intérêt) : pk réduire la taille de la liste ? Il suffit de réduire l'amplitude du randInt. Ouf, là je crois que c'est vraiment le mieux possible (quoique ? ^^)
Edit 4 : Dsl, j'ai trouvé encore mieux, pour remplacer le N-Z

:Prompt N
:seq(Z,Z,1,N->L1
:For(Z,N,1,-1
:randInt(1,Z
grinisp L1(Ans
:L1(Z->L1(Ans
:Pause
:End

11

Eh non malheureux ! ^^ Si tu fais For(Z,1,N), tu as un bug à la ligne suivante lorsque Z=N, car N-Z=0

Oui, mais je disais bien de N à 1 moi, soit For(Z,N,1,-1) (et c'est ce que t'as finalement fait)
Par contre l'alternative au SortD est magnifique ici, gg !
Ne pas reduire la taille de la liste je le faisait deja, et le Pause X qui met X dans Ans c'est bon a savoir (et c'est d'ailleurs curieux; ils sont super logiques chez TI triso)
<-- et à votre gauche une superbe peinture pointilliste du XVIe siècle #sisi# représentant - vous l'aurez deviné - une banane ...
http://www.ti83plus.online.fr/home.php...

12

Ah ok dsl ^^

Oui effectivement, je trouve ça génial ^^.

13

Eh bien merci beaucoup Baruch et mastercalto! smile
J'ai pas compris grand chose, mais merci beaucoup!
avatar

14

De rien ! Ce petit prog va sûrement me servir. Si tu as des questions, n'hésite pas !

15

[nosmile]Tiens, j'ai encore trouvé une autre méthode.

:Prompt N
:seq(Z,Z,1,N->L1
:rand(N->L2
sorryortA(L2,L1
:For(Z,1,N
grinisp L1(Z
:Pause
:End

16

Joli ! grin
<-- et à votre gauche une superbe peinture pointilliste du XVIe siècle #sisi# représentant - vous l'aurez deviné - une banane ...
http://www.ti83plus.online.fr/home.php...

17

N'est-ce pas ? Mais bon la méthode précédente est meilleure pour l'utilisation demandée. C'était juste pour utiliser le SortA(L2,L1 , que je viens de découvrir.

18

( c'est joli mais plus couteux en théorie qu'une méthode normale.(le tri ça nous donne du N.log(N)) En pratique pour n<100 ça doit être plus rapide que de se taper des tests avec un tableau de bolenns, mais bon )

Intuitivement j'aurais fais un truc du genre:

dim(l2)<-N
L2 <- Fill(0)
For z, 1, N
  A <- rand(N
  while (L2(A) = 1 )
    A<-mod(A+1,N)
  End
  Disp A
  L2(A) <- 1
End


A vue d'oeil ça prends du N * moyenne_du_décallage = (au pifomètre équiréparti ) N * (1 + N/N-1 + ... + ... N/3 + N/2)/N -> N * (N.log(N)/N) -> N.log(N)
Bon bha en fait ça fait pas mieux que ton truc grin (j'pense même qu'on ne doit pas pouvoir faire mieux. A voir... )



( bon en fait le fait de faire +1 fait qu'on a un phénomène de bulle (mon hypothèse de l'équirépartition dans le calcul précédent, c'est faux..), prendre un +rand(N) c'est plus efficace en asymptotique, mais bon c'est pas gênant pour un petit N )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

19

hmmm je vois ^^

20

tin ça fait longtemps que j'ai pas fait de ti-basic, je met les flèches dans le mauvais sens grin
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

21

Tout ça m'a l'air très intéressant mais tu pourrais m'expliquer plus clairement tout ce que tu as dit plus haut ? (ok, ok jsui un noob)

22

Ben en fait en informatique théorique, on se pose la question de tout codeur: comment mesurer le 'temps' que met un programme pour faire une opération donnée, en fonction de la taille de l'entrée ?

Le but du jeu, c'est d'obtenir une 'mesure théorique' du temps d'un aglo qui ne dépend pas d'un ordi ou d'une mesure réelle (c'est pas contre les benchmarks réels, mais y'a bcp de raison qui font que c'est intéressant et complémentaire )

Comme ça si t'as deux algo qui font la même chose, (genre deux programme qui trient une liste ), on est capable de dire, juste à lire le (pseudo-)code, qui est le plus rapide, et qui utilise le plus de mémoire (même principe de la mesure)

Pour ça, on fixe en général une 'unité de calcul': si on voudrait être très précis ça pourrait être le nombre de cycles nécessaire à tel processeur, mais bon comme on est pas suicidaire on dit en général qu'une opération 'simple' (affectation, addition, multiplication, comparaison, ..) se fait en un temps de 'une unité de calcul' (c'est imagé )

Après, si je fais le programme de tri suivant:
dim(L1)->N
Pour i de 1 à N
  Pour j de 1 à N-1
    Si L1(j) > L1(j+1) alors
      L1(j) -> A
      L1(j+1) -> L1(j)
      A -> L1(j+1)
    FinSi
  FinPour
FinPour


on cherche à compter le nombre d'opération 'élémentaires' que fait le programme en fonction de la taille de la liste à trier, N
Si on compte méticuleusement:
1 opération pour l'affectation de N
N * (N-1) * (1 [comparaison] + (0 ou 3) [affections dans le cas du si] )

bref, si la liste est déjà triée, on fait jamais le bloc du 'si' et on va faire 1+N*(N-1) opérations
Dans les autres cas, au 'pire du pire' on aurait toujours le bloc du 'si' à faire, et donc on fait moins de 1+N*(N-1)*4

Bon, quand N devient grand, c'est un peu ridicule de compter le '+1', et N*(N-1) ~ N² pour N->infiny, on dit donc que le programme est en 4*N², voir O(N²) [on 'néglige' le facteur devant, ça donne un truc plus grossier mais plus simple. )

Maintenant si tu fais un programme de tri plus intelligent, (par exemple, le tri-rapide), on peut voir que la complexité en temps est de l'ordre de N*log(N)

Quand N est très grand, qu'importe les constantes devant, cste1*N.log(N) << cste2*N², donc on peut dire que le programme deux est plus rapide que le 1.

Bon après c'est une question de précision, on garde la constante numérique devant quand on veut faire des comparaisons précises, genre tu peux dire 'mon prog fait le truc en 9*N au lieu de 11*N donc il est meilleur', etc.


C'est assez corrélé à la réalité, pourvu qu'on fasse pas trop d'hypothèses dégueulasses, que le taille des entrées soit assez grande, que les deux progs soient 'aussi bien' codés (Par exemple si N=2, le fait de 'dégager' les +1 etc fait que bon celui censé être le plus lent peut en fait être le plus rapide)


Pour revenir à notre cas, comme N<100 (les listes ti-basic c'est limité à 99 ? ), et que les fonctions built-in sont parfois vraiment plus rapides que les mêmes faites à la main, ça donne qu'une idée très vague du truc qui sera le plus performant pour de vrai. Sauf si l'écart est super grand genre y'a un prog en 2*N et l'autre en exp(N), là dès que N dépassera 10 tu verra bien l'écart..

edit: français, pre
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

23

Wow, merci pour ce long post ! Je vais y méditer quelques temps ^^. La taille des listes est limitée à 999 (c'est tout ce que je peux corriger ^^).

24

Ouais, en fait, les infos pour la complexité c'est pas très adapté aux Ti (j'ai vu ça cette année).
Si tu veux, on nous a filé une carte ac des points et le but c'était de la colorier correctement sur pc.
Là c'est bcp plus important, parce que pour avoir une image correcte, faut faire au moins du 700*700 pxl, et donc tu te tapes facilement 500 000 fois la même opération.
Et là, vaut mieux avoir une bonne complexité, parce que si tu prends du O(n) (cad par exemple 4n), tu tombes sur un truc genre 4*500000, soit 2000000 opérations, alors qu'avec un algo en O(n²) (cad par exemple 1/2 n²), tu tombes sur 125000000000 opérations...
Et là ça fait très mal (juste qques années de calcul quoi...)

Et en gros, pour les complexité, du mieux au pire, on a:

O(1), O(log(n)), O(racine(n)), O(n), O(n*log(n)); O(polynome(n)); O(exp(n))...
Mais en fait, on simplifie le problème, parce que si on a
complexité(n) = cos(n); on dit: O(1)
c(n) = rac(n) + n; on dit: O(n)

Et donc en programmation par la suite, on essaye moins d'optimiser le code, et plus d'optimiser les algos... (diviser un an par deux, ça équivaut pas à faire tourner un meilleur algo pendant trois secondes)

25

( ben si certaines fois ça peut aussi être utile sur Ti. Entre le choix de deux aglos pour un truc important. Bon ça dispense pas d'optimiser le code après, c'est sur ! – mais en réalité, même sur PC en C/.., l'optimisation du code reste aussi important quand c'est bien critique. )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.