/* Topic des codeurs couche-tard [1] */

SoJaS · Le 29/06/2010, à 18:05

Je glisse bien de trois cases: V[3]='4' donc si je fais moins trois, '4' se retrouve en V[0], '5' en V[1], etc...

helly · Le 29/06/2010, à 18:06

Aparement n@nyl@nd arrive à reproduire le bug !!!!!

sweetly · Le 29/06/2010, à 18:31

Ok, je comprends.

grim7reaper · Le 29/06/2010, à 20:19

Bon en fait, je me rends compte que je m'écarte du codage d'un interpréteur de BF et que je m'approche plus d'un optimiseur/compilateur, ce qui est bien plus complexe .
Je ne sais pas si je continue (c'est intéressant) ou si je m'arrête (pas sûr que j'ai le niveau)…
On verra.

Pylades · Le 29/06/2010, à 21:17

SoJaS a écrit :

Salut.
J'ai un exo en c++ sur lequel je sèche:
Écrire une fonction qui effectue un glissement circulaire gauche de K positions sur un vecteur. Chaque élément ne doit être déplacé qu'une seule fois et votre fonction ne doit pas utiliser de vecteur de travail.
Alors voilà ce que j'ai fait jusque là:
void glissementG(int V[],int deplacements, int taille)
{
    int save1=V[0], position=0;
 
    for (int i=1; i<taille; i++)
    {
        V[position]=V[(position+deplacements)%taille];
        position=(position+deplacements)%taille;
    }
    V[taille-deplacements]=save1;
}
Voilà, ma fonction fait ce qu'il faut si la taille du vecteur est impaire, ou si elle est paire et que déplacements n'est pas un diviseur de taille. Mais si taille est paire et que déplacement est un diviseur de taille, ça merde... J'ai déjà testé pas mal de conditions en fonction de la parité, etc..., mais rien trouvé jusque là.
Donc si qqn pouvait me guider, ce serait cool...

Bonjour.
Comme la question n’est pas spécifique au C++, je me permets de répondre.

En fait, tu fais des trucs un peu bizarres dans dans ta boucle for. Je ne comprends pas vraiment ce que tu cherches à faire. J’ai essayé de trouver une solution algorithmique qui ne réaffecte qu’une fois chaque élément du tableau, mais je n’ai pas trouvé. Je propose donc une solution pas très élégante et un peu longue, mais qui fonctionne.

void glissementG(int* V, unsigned int deplacements, size_t taille)
{
    for (unsigned int i=0;i<deplacements;i++)
    {
        int save = *V;
        for (size_t j=0;j<taille-1;j++)
            V[j] = V[j+1];
        j[taille-1] = save;
    }
}

Elle a l’avantage de ne pas nécessiter de tableau temporaire, mais réaffecte plusieurs fois les éléments du tableau.
Le but est-il d’avoir de bonnes performances, ou est-ce juste un prétexte pour faire un exercice d’algorithmique ?

Si c’est pour le côté exercice, je ne peux pas aider. J’ai testé plusieurs pistes, mais elle ont toutes échoué. Et puis, je n’ai jamais fait d’algorithmique, donc il est peu probable que je trouve la solution dans un éclair de génie…
Dans ce cas, je ne suis pas très utile…

@grim7reaper : un compilateur ?
C’est à dire ? Ne me dis pas que que tu génères des exécutables à partir de code brainfuck…
(À moins que tu ne transcrives en C et ne donnes le résultat à manger à gcc…)

Dernière modification par Pylade (Le 29/06/2010, à 21:21)

tshirtman · Le 29/06/2010, à 21:41

ça doit pas être méchant de faire un compilateur avec bison… si y'en a qui veulent s'amuser

nesthib · Le 29/06/2010, à 21:44

pour le problème de SoJaS c'est purement algo, je vois les choses ainsi :
effectivement il faut utiliser une variable temporaire.

nous choisissons donc un décalage de 3 valeurs vers la gauche (soit un nombre impair)

soit un vecteur à nombre PAIR de valeurs :

|_|_|_|_|x|_|_|_|
         n

on commence par déplacer la valeur x du rang n au rang n-3 (on travaille bien sur avec des indices modulo la taille du vecteur) après avoir sauvé la valeur n-3 dans notre variable

|_|x|_|_|_|_|_|_|
   ^-----’

puis on fait de même avec la valeur n+3 que l'on place dans n :

|_|x|_|_|x|_|_|_|
         ^-----’

on continue comme ça en tout n-1 fois, la nième fois sera réalisée en utilisant la valeur stockée au départ

les choses se compliquent un peu avec un vecteur à nombre IMPAIR de valeurs.
en effet au bout d'un moment on retombe sur sur une valeur déjà remplacée alors que nous n'en sommes qu'à une étape intermédiaire

|_|x|_|_|_|_|_|_|_|
---^-----^-----^----

pour cette partie je vous laisse réfléchir un peu, ce n'est pas très compliqué, il suffit de se décaler d'un cran vers la droite au bout d'un certain nombre de déplacements et de continuer

grim7reaper · Le 29/06/2010, à 21:49

@Pylade : Pour l'instant je n'ai rien de concret, juste des idées et une vague idée de l'architecture.

Le premier point intéressant c'est surtout l'optimisation du code. Ce n'est pas très utile pour un interpréteur vu que ça fait des passes en plus (bon ça peut être intéressant dans certains cas), par contre pour un compilo ça apporte un vrai gain.

Après, aller jusqu'a produire un exécutable je ne pense pas que j'y arrive (je ne suis même pas sûr d'arriver à implémenter l'optimisation, alors…) mais on pourrai procéder par étape :
- optimisation
- BF optimisé -> C
- ou plus fou encore BF optimisé -> ASM (mais pas portable, en plus j'aime pas l'ASM des CISC ><")
- génération d'exécutable

Enfin, il y a peu de chance que je produise un truc fonctionnel mais au moins j'apprendrais des trucs.

@tshirtman : boarf, utiliser Bison ici j'ai un doute. Vu la grammaire du BF c'est vraiment utiliser une arme de guerre pour rien.

SoJaS · Le 29/06/2010, à 22:06

Bon, ça y est, enfin trouvé (et pas mal grâce à dionisos, en fait).
Le pb ne se pose pas en fonction de la parité de la taille du vecteur, mais seulement si la valeur "déplacements" est un diviseur de la valeur "taille".

  5 void glissementG(int V[],int deplacements, int taille)
  6 {
  7    int save1=V[0], save2=V[0], position=0, flag=-1;
  8 
  9    if (taille%deplacements==0)
 10         flag=deplacements;
 11 
 12     for (int i=1; i<taille; i++)
 13     {
 14         V[position]=V[(position+deplacements)%taille];
 15         position=(position+deplacements)%taille;
 16 
 17         if(position>=taille-flag)
 18         {
 19             V[position]=save2;
 20             flag--;
 21             position=deplacements-flag;
 22             save2=V[position];
 23             i++;
 24         }
 25     }
 26     if (flag==-1)
 27         V[taille-deplacements]=save1;
 28 }

Et la solution de dionisos, qui m'a bien aidée:

  5 int pgcd(int a, int b)
  6  {
  7    int r ;
  8   while (r = a % b) {
  9     a = b;
 10     b = r;
 11   }
 12   return b;
 13 }
 14 
 15 void glissementG(int V[],int deplacements, int taille)
 16 {
 17     int save1=V[0], position=0;
 18         int pgcdDT=pgcd(deplacements,taille);
 19         cout<<"pgcd="<<pgcdDT<<endl;
 20 
 21         for (int sous_tab = 0; sous_tab < pgcdDT; ++sous_tab)
 22         {
 23             position=0;
 24             save1=V[sous_tab];
 25             for (int i=0; i<(taille/pgcdDT); i++)
 26             {
 27                 V[position+sous_tab]=V[(position+deplacements+sous_tab)%taille];
 28                 position=(position+deplacements)%taille;
 29                 cout<<"position+sous_tab="<<position+sous_tab<<endl;
 30             }
 31             V[taille-deplacements+sous_tab]=save1;
 32         }
 33     
 34 }

nesthib · Le 29/06/2010, à 22:08

effectivement c'est bien un problème de diviseur

Pylades · Le 29/06/2010, à 23:30

@grim7reaper : oui, quand je parlais de génération d’exécutables, je faisais bien entendu référence à la compilation en asm, après il est évident que tu vas utiliser l’assembleur et le linker du système…
Mais après, le transcription en C ou en un autre langage « évolué » (:P), ça doit déjà être beaucoup plus faisable (et portable).

Donc tu vas le faire en C++ ? Ça me fait penser qu’il faudrait que je m’y mette un de ces jours…

@nesthib : ouais, mais c’était plus compliqué que ça ; j’ai essayé de plusieurs façon, mais sans réussir à ne devoir utiliser qu’un nombre fixé de variables intermédiaires. En puis, dans le premier code de SoJaS, il était évident qu’avec une valeur de déplacement supérieure ou égale à deux et congrue à zéro modulo la taille du vecteur, ça allait poser problème. Et il y avait probablement d’autres cas (je n’ai pas trop regardé le premier code, mais rien que ça c’était fatal). Après si tu veux essayer d’implémenter, tu te rendras compte que ce n’est pas si facile que ça.
Heureusement, SoJaS a trouvé un solution.

grim7reaper · Le 29/06/2010, à 23:33

Pylade a écrit :

@grim7reaper : oui, quand je parlais de génération d’exécutables, je faisais bien entendu référence à la compilation en asm, après il est évident que tu vas utiliser l’assembleur et le linker du système…
Mais après, le transcription en C ou en un autre langage « évolué » (:P), ça doit déjà être beaucoup plus faisable (et portable).
Donc tu vas le faire en C++ ? Ça me fait penser qu’il faudrait que je m’y mette un de ces jours…

Pour l'instant rien n'est décidé, mais si je le fais, oui ça sera du C++ (ça fera un bon exo pour apprendre).
Mais déjà faut je potasse la théorie, histoire de voir si c'est surmontable (je voudrais faire le truc sans outil externe tel que lex/yacc, histoire d'apprendre) par rapport à ma motiv'.

BN World !

Dernière modification par grim7reaper (Le 29/06/2010, à 23:37)

tshirtman · Le 29/06/2010, à 23:35

congrue à zéro modulo la taille du vecteur

ben non c'est le cas le plus simple… qui se résoud en en temps constant proche de 0…

if (decal% size == 0) return

non?

mais bon j'ai suivit d'un oeil distrait et je trouve vos solutions compliquées, j'ai du louper un truc…

helly · Le 30/06/2010, à 00:01

Bn

nesthib · Le 30/06/2010, à 00:32

@tshirtman : bien entendu il y a des solutions simples utilisant des possibilités toutes faites d'un langage mais là c'est clairement un problème d'algo (genre papier crayon)

@Pylade : pas le temps de me pencher trop là dessus mais en gros il faut faire comme j'ai détaillé plus haut en prenant en compte le cas où le déplacement est un diviseur de la taille du vecteur (et non pas une question de parité comme je l'ai écrit au départ)

Pylades · Le 30/06/2010, à 00:45

@tshirtman : oui, t’as dû louper un gros truc…

@nesthib : pas si simple !

cm-t · Le 30/06/2010, à 01:02

'Nuit;

edit: met 3 plombe a charger ton avatar Pylade

Dernière modification par cm-t (Le 30/06/2010, à 01:04)

\\Ouranos// · Le 30/06/2010, à 01:07

Sécu.

Vous avez pas un tuto sur Sequel sous la main ? Le site officiel est sympa masi assez austère et donne peu d'explications pour les codes.

Кຼزດ · Le 30/06/2010, à 01:16

plop

nesthib · Le 30/06/2010, à 01:29

@Pylade : pas si compliqué

Pylades · Le 30/06/2010, à 01:57

cm-t a écrit :

edit: met 3 plombe a charger ton avatar Pylade

@nesthib :

\\Ouranos// · Le 30/06/2010, à 02:11

Dodo !

Pylades · Le 30/06/2010, à 03:29

\\Ouranos// a écrit :

Dodo !

Flood !

samυncle · Le 30/06/2010, à 04:30

.

tshirtman · Le 30/06/2010, à 09:19

SoJaS a écrit :

Salut.
J'ai un exo en c++ sur lequel je sèche:
Écrire une fonction qui effectue un glissement circulaire gauche de K positions sur un vecteur. Chaque élément ne doit être déplacé qu'une seule fois et votre fonction ne doit pas utiliser de vecteur de travail.

ah oui j'avais loupé de des deux conditions foireuses…

…j'espère que ton prof est pas un adepte des débordements…

je vais y réfléchir, j'ai une petite idée (j'ai pas regardé vos code, mais je suppose que vous avez eu la même d'après vos commentaires).

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#726 Le 29/06/2010, à 18:05

Re : /* Topic des codeurs couche-tard [1] */

#727 Le 29/06/2010, à 18:06

Re : /* Topic des codeurs couche-tard [1] */

#728 Le 29/06/2010, à 18:31

Re : /* Topic des codeurs couche-tard [1] */

#729 Le 29/06/2010, à 20:19

Re : /* Topic des codeurs couche-tard [1] */

#730 Le 29/06/2010, à 21:17

Re : /* Topic des codeurs couche-tard [1] */

#731 Le 29/06/2010, à 21:41

Re : /* Topic des codeurs couche-tard [1] */

#732 Le 29/06/2010, à 21:44

Re : /* Topic des codeurs couche-tard [1] */

#733 Le 29/06/2010, à 21:49

Re : /* Topic des codeurs couche-tard [1] */

#734 Le 29/06/2010, à 22:06

Re : /* Topic des codeurs couche-tard [1] */

#735 Le 29/06/2010, à 22:08

Re : /* Topic des codeurs couche-tard [1] */

#736 Le 29/06/2010, à 23:30

Re : /* Topic des codeurs couche-tard [1] */

#737 Le 29/06/2010, à 23:33

Re : /* Topic des codeurs couche-tard [1] */

#738 Le 29/06/2010, à 23:35

Re : /* Topic des codeurs couche-tard [1] */

#739 Le 30/06/2010, à 00:01

Re : /* Topic des codeurs couche-tard [1] */

#740 Le 30/06/2010, à 00:32

Re : /* Topic des codeurs couche-tard [1] */

#741 Le 30/06/2010, à 00:45

Re : /* Topic des codeurs couche-tard [1] */

#742 Le 30/06/2010, à 01:02

Re : /* Topic des codeurs couche-tard [1] */

#743 Le 30/06/2010, à 01:07

Re : /* Topic des codeurs couche-tard [1] */

#744 Le 30/06/2010, à 01:16

Re : /* Topic des codeurs couche-tard [1] */

#745 Le 30/06/2010, à 01:29

Re : /* Topic des codeurs couche-tard [1] */

#746 Le 30/06/2010, à 01:57

Re : /* Topic des codeurs couche-tard [1] */

#747 Le 30/06/2010, à 02:11

Re : /* Topic des codeurs couche-tard [1] */

#748 Le 30/06/2010, à 03:29

Re : /* Topic des codeurs couche-tard [1] */

#749 Le 30/06/2010, à 04:30

Re : /* Topic des codeurs couche-tard [1] */

#750 Le 30/06/2010, à 09:19

Re : /* Topic des codeurs couche-tard [1] */

Pied de page des forums