Discussion :

[Olimpe]

Bonsoir à tous,

Bonne année pour commencer !

Je bloque sur un petit exercice, et j'aimerais bien des pistes pour démarrer.

On me demande d'écrire un petit programme qui consiste à demander à l'utilisateur de rentrer une suite de nombre (dans un tableau 1*1), puis un chiffre d. Pour l'exemple on prendra :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
a = input('Please enter a: ');
d = input('Please enter d: ');
 
a = [3 5 1 21 23 19 9 16 13 15 11 7 27 28 25]
d = [4]

Ensuite on me demande en utilisant une double boucle (boucle au sein d'une autre boucle), de trouver la plus longue suite arithmétique possible dans a, avec pour raison d et d'afficher comme résultat la longueur de la suite, ici on récupéra donc 7, puisque la plus longue suite est : 3 7 11 15 19 23 27..

--

Je pense que l'utilisation d'un while pourrait m'aider. Ce que je voudrais faire, c'est prendre chaque élément de a, a(1), a(2),.. et vérifier si a+-4 se trouve aussi dans le tableau..

Par exemple pour 3 : -1 n'y est pas, mais 7 y est. Donc 3 et 7 serons dans ma suite.. Etc.. Le tout avec des fonctions simples.

Je n'arrive pourtant pas trop à me lancer. Si quelqu'un pouvait donner une piste ça serait sympa.

Merci d'avance !

[shaiHulud]

Bonsoir,

Commence par ordonner le vecteur a (tu ne cherches pas une sous-série dans un vecteur, mais une sous-série dans un ensemble) - en supposant d>0.

Ensuite, exprime un algorithme qui résous le problème. Une solution simple: j'essaye tous les points de départ x0 et je vérifie quels x0+k*d sont dans a (il y en a au maximum length(a)).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
meilleurx0=nan
meilleurk= 0
Pour chaque x0 dans a
   Pour chaque k dans 1:length(a)
      si x0+k*d n'est pas dans a; break % on a trouvé la plus longue suite comencant en x0, elle est de longueur k-1
       si k> meilleurk
             meilleurk=k
             meilleurx0= x0

Cette solution est loin d’être efficace (ça ne sert a rien par exemple de prendre pour point de départ un point ou on est déjà passé !!) et n'utilise pas la vectorisation matlab

[Olimpe]

Salut !

Merci pour la méthode, j'essaie donc de faire ça.

Quand tu parles d'ordonner a, tu veux dire sort(a) par exemple ?

Merci.

[shaiHulud]

Oui, c'est ce que je voulais dire, mais avec cet algo non optimisé, ça ne changera rien puisqu'on passe par tous les points. C'était surtout pour souligner une ambiguïté dans ton énoncé (la sous séquence dans a n'a pas besoin d'y apparaitre dans l'ordre, comme montré par ton exemple).

Quand je parlais de vectorisation, on peut par exemple remplacer la boucle interne en utilisant ismember(suite_arith, a) qui s’exécutera plus vite.

Enfin il faut vérifier la valeur de k après un break de la boucle (la suite étant de longueur k+1 et non k-1 comme précisé, à vérifier)

[Olimpe]

D'accord, je vais essayer de faire un premier truc avec tout ça, et je posterai ici ce que j'ai fais..

Pour l'instant ça ne donne pas grand chose, je tatonne un peu. Je te tiens au courant.

Merci pour les pistes en tout cas !

[Olimpe]

Re

J'ai essayé de réfléchir un peu sur l'exo, et je tiens à apporter une petite précision tout d'abord : on n'a pas le droit d'utiliser sort pour cette exercice. (Selon la consigne).
Ce n'est pas un exercice à rendre, mais c'est un exo type exam, donc j'essaie de le faire dans les conditions. Pas de sort donc.

En gros je bloque au début toujours, en gardant les même données que dans mon premier post pour a et d.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
for i=1:length(a)
    for k=1:length(a)
        if a==a(i)+k*d
            disp('a(i)');
        else
            disp('none');
        end
    end
end

En gros j'essaie de faire les choses petits à petits, là j'ai écris ça car je voudrais simplement que matlab "scanne" mon tableau a, et me dise si dedans il y a des éléments tel que a(i) quelconque dans a = a(i)+k*d (dans a également).
Sinon si il n'y a rien, je veux qu'il m'affiche none.
Pour le moment c'est ça que je veux faire.

Je pige pas vraiment pourquoi il me sort pas quelque chose de correct là, mon code est faux à ce point.. ?

Merci d'avance.

[tachmou]

Bonjour,

Tu n'as peut-être pas le droit d'utiliser "sort", mais tu peux très bien écrire une fonction de tri qui fera la même chose. Et ici, je pense que tu vas en avoir besoin...

Si on analyse ton sujet :
- tu dois utiliser une double boucle
- trouver la plus longue suite (pas la peine de toutes les enregistrer)
- afficher la longueur de la suite

Dans l'ordre, je te conseille donc de procéder ainsi :
- écris une fonction1 qui tri tes éléments dans l'ordre croissant, en supprimant les doublons (entrée : "a_initial" / sortie : "a" trié sans doublon)
- écris une fonction2 qui teste si l'élément (a(k) + d) est présent dans a. Si oui, tu repères l'indice correspondant "ind" en sortie. Sinon, tu enregistres "ind = -1" (entrée : "a", "k", "d" / sortie : "ind")
- écris une fonction3 qui va exécuter la fonction2 et enregistrer la suite d'indices obtenues en boucle jusqu'à obtenir "-1" (entrée : "a", "k_initial", "d" / sortie : "suite")
- écris une fonction4 qui va exécuter la fonction3 et enregistrer la liste des suite d'indices pour chacun des éléments contenus dans "a" (entrée : "a", "d" / sortie : "Liste")

Une fois que tu as fait ces 4 fonctions, l'algo ressemblera à peu près à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
a = fonction1(a_initial)
Liste{:} = fonction4(a)
longueur = [];
for k = 1:length(Liste)
    longueur(k) = length(Liste{k});
end
max(longueur)

Ta double boucle est dans fonction4 & fonction3. Pour les faire apparaître il suffit de ne plus utiliser de fonctions et de mettre le code de bout en bout dans un seul fichier.

Mais je te conseille de procéder comme je viens de dire, ça te permettra d'avoir une méthode très fonctionnelle.

Cordialement,