Maximiser son fun - exercice 4 prologin 2017

Bonjour, Je m'excuse d'avance si c'est une erreur de ma part, mais le code a completer en C possede la ligne suivante :

1

struct piste* une_piste = malloc(sizeof(une_piste)); 

N'est-ce pas :

1

struct piste* une_piste = malloc(sizeof(*une_piste));

? (sur mon pc il y a une difference de 4octets entre la taille du pointeur, et la taille de la structure.)

Par ailleurs, je me posais plusieurs questions : Faut-il proteger ses allocations dynamiques ? Faut-il caster ses mallocs ? (j'entends par la, est-ce que cela compter dans la selection) Merci !

edit : je suis désolé, mais le retour a la ligne n'est pas prit en compte, et c'est assez difficile a relire, surtout pour les deux lignes de codes citées. :/

Bonsoir !

Le code était en effet faux, c'est corrigé.

Merci de l'avoir signalé !

lordrazmou

Faut-il proteger ses allocations dynamiques ? Faut-il caster ses mallocs ? (j'entends par la, est-ce que cela compter dans la selection)

Pas la peine de cast le résultat d'un malloc: le type void* dispose d'une conversion implicite vers tout autre type de pointeur. De plus, le cast te fait perdre en lisibilité.

Protéger ses allocations dynamique est une bonne pratique à l'impact pourtant limité, mais nous n'en tenons pas vraiment compte, la notation portant essentiellement sur les qualités algorithmiques de ton programme.

Cordialement,

J'aurai une autre question, concernant les restrictions en mémoire/temps. J'avais cru comprendre qu'il s'agissait de "bonus", prit en compte uniquement lors des tests de performance.

En envoyant mon code aujourd'hui pour l'exercice 4 (encore celui là ! :D ), j'ai eu le rapport d'erreur suivant :

Limite de mémoire dépassee (forcément, j'utilise une matrice de 7octects/cases, en cas de 1 000 * 1 000, je depasse un peu trop la restriction)

Est-ce réellement un problème de taille, ou bien est-ce un autre problème, et l'aspect optimisation vitesse/mémoire rentre-t-il donc uniquement en jeu pour le tests de performance ?

Merci beaucoup pour les réponses !

Salut lordrazmou,

Je pense que l'utilisation d'une matrice d'adjacence pour cet exercice est trop gourmand en mémoire. Il me semble que les performances de l'algorithme ne sont pas prises en compte pour la vérification de l'output de ton programme. Bien sûr; s'il est vraiment trop lent, le serveur n'attendra pas 30min la fin de l'exécution de ton programme et passera directement aux prochains test.

Salut AnselmeC

C'est dommage, il était plutôt rapide mon algo, mais il utilise justement une matrice d'adjacence, et j'ai pas encore eu d'idée pour le faire sans, ça m'arrange pas tout ça :p

Du coup, la vitesse n'est pas un élément éliminatoire - sauf cas extrême - mais la mémoire l'est ? C'est curieux ^^

Il me semble que la vitesse est également un élément éliminatoire. Sur ce problème-là, on a le droit à 1 seconde par test et à 1000 Ko par test, d'après l'énoncé.

ça me semble plus logique, effectivement.

Est-il possible de discuter d'algo en rapport avec les sélections sur le forum ?

La matrice d'adjacence est préférable lorsqu'un graphe est considéré comme "dense". En bref, lorsqu'il possède beaucoup d'arrêtes. Dans ce cas là tu utiliseras une grande partie de ta matrice. Mais si par exemple pour 50 nœuds ton graphe possède 10 arrêtes, alors tu te serviras "dans ton algorithme" de moins d'un pour cent de ton tableau... Beaucoup de mémoire, beaucoup d'itérations pour finalement peu d'arrêtes à traiter. Cela montre bien qu'en cas de graphe creux la matrice d’adjacence est peu efficace. Préfère une liste d'adjacence pour cet exercice !

Bien sûr c'est possible, à condition de ne pas demander des réponses, ou pire, les donner ! :p

En réalité, la matrice me permettait surtout de gérer les cas de boucles infinies.

J'avais reprit l'algorithme de Floyd-Warshall, revu un peu a ma sauce pour que les case où i = j ne soient pas figées, et donc, m'indiquent les boucles infinies non-nulle.

Ma première idée pour "contrer ça" était justement de me servir d'un tableau de liste chainées (où chaques cases correspond a mon x de départ), histoire de ne pas avoir toutes ses cases "inutiles" comme tu disais.

Malheureusement, cela rajoute beaucoup d'itération, je vais devoir parcourir un grand nombre de fois mes listes, meme si elles sont ordonnées.. Pas très cool !

Je vais réfléchir a quelques chose utilisant les listes d'adjacence dans ce cas, merci du conseil ! :)

(si jamais le fait que je site un nom d'algo est embêtant, j'éditerai.)

Moi je me demandait si sa dose de fun n'a pas de limite mais que elle fait que de diminuer (donc qu'elle temps vers -infini et non pas +infini) est-ce que il faut aussi renvoyer le texte : "OVERDOSE DE FUN" ?

Si on cherche quelque chose qui est le plus grand possible, je ne vois pas comment le fait que ça tende vers -inf puisse être prit en compte

Si jamais ton parcours fait :

0 1 -1337

1 0 -1

=> Tu tends vers -inf... mais la dose de fun la plus élevée est (edit) 0 :p

Ok c'est bien ce que je me disait merci

Non lordrazmou dans ton exemple la dose de fun la plus élevée est de 0 je crois

plasjp

Non lordrazmou dans ton exemple la dose de fun la plus élevée est de 0 je crois

Bien vue puisqu'il peut rester sur la plateforme sans bouger

Exact, j'ai édité x)