Tous les concours d'algorithmique et de programmation

Et comme il n'y a que le pire cas qui importe, utiliser vector ici c'est nul.

Pole4 > De toute façon, ici on parle d'un reserve juste après la construction, donc peu importe la diminution impossible.

Thomas > Entre un tableau statique qui dépend forcément des limites de l'exercices et une allocation dynamique qui, si les limites d'entrée sont changées, va (selon la qualité de l'algorithme derrière) permettre de fonctionner malgré cet imprévu, je sais ce que je préfère. =)
Au passage, tu peux donner un inconvénient de vector ?

Equinoxe: +1

=D

Un inconvénient de vector ?
Euh, les tableaux multi-dimensionnels ?

Forcément, c'est pas fait pour.
Mais ils sont :
- Facilement émulables avec une simple boucle de resize() au début
- Gérés par boost.multiarray sans aucun souci
Un autre inconvénient, peut-être ? =)
(Et, de toute façon, allez pas me dire qu'un tableau de taille dynamique sans boucle de new c'est faisable.)

Ah mais un tableau statique convient très souvent pour ceux qui font de l'algo :P
Et les multidimensionnels sont bien pratiques.
Pour avoir l'adresse du premier élément, ou un itérateur dessus, il faut faire &v[0] ou v.begin() à la place de v.

PS : Dans la plupart des compétitions d'algo, on n'a pas le droit à boost.

Et c'est reparti pour un troll d'une dizaine de page xD

Cela dit je trouve aussi que les tableaux statiques ça pue, c'est pas scalable comme solution. Et euh ouai on écrit v.begin() pour obtenir un itérateur vers le début du tableau, mais honnêtement je vois pas trop le problème. À moins que quand tu écrives du code ça soit critique de gagner 10sec en économisant 4 caractères de tapés ...

"permettre de fonctionner malgré cet imprévu"
Ouais pour Prologin c'est utile je l'avoue.

"- Facilement émulables avec une simple boucle de resize() au début"
Beurk du code inutile.

"- Gérés par boost.multiarray sans aucun souci"
Double beurk, non standard.

"(Et, de toute façon, allez pas me dire qu'un tableau de taille dynamique sans boucle de new c'est faisable.)"
Et pourquoi j'aurai besoin d'un tableau dynamique ?

Bon j'ai un peu été grillé par Paul en fait.
Et longue vie à "int t[N_MAX];" ! (avec t global bien sûr :D)

"du code inutile"
Si tu veux un tableau de taille dynamique, c'est la seule façon ne prenant que le standard (à part indicer soi-même avec y * nbCols + x)

"non standard"
Boost était disponible à la finale prologin, cette année. Donc rien à dire. =p

"Et pourquoi j'aurai s besoin d'un tableau dynamique ?"
Parce que sinon c'est de l'anti-économie mémoire ?

"longue vie à "int t[N_MAX];" ! (avec t global bien sûr :D)"
C'est bien de ce genre de choses que je parle quand je dis la mauvaise influence des IOI sur la programmation.

A noter que, dans mon message comme dans ceux d'avants, je ne parle pas uniquement d'un concours d'algorithmique, mais plutôt de la création d'un programme entier qui se base sur un algorithme. Parce que c'est bien beau de dire "il n'y aura pas plus de N entrées", mais dans un vrai programme on ne peut jamais être sûr de ça - sauf si on empêche l'utilisateur de le demander, ce qui serait un peu bête. Mieux vaut présenter un algorithme qui ne répond pas dans la seconde que dire "mon algorithme que j'ai bêtement codé avec un tableau de taille statique ne peut pas gérer cette taille d'entrée sans planter, donc non, revenez un autre jour", voire, pire, causer un buffer overflow si l'on oublie cette simple vérification.

Et, pour le t global, tant que t est bien nommée, est dans un fichier restreint à un seul algorithme et est dans un namespace anonyme, ça ne me dérange pas. Sinon, ça devient imho anti-productif.
Ou bien, il faut que la variable globale aie une utilité en tant que variable globale, et que son rôle ne puisse pas être mieux rempli par autre chose. Bref, qu'on n'aie pas d'autre choix. Et même là, il faut penser à bien la documenter dans son header, pour ne pas risquer de se tromper dans son utilisation. Par exemple, la variable globale boost::extends (de boost.multiarray) peut difficilement être autre chose, car on ne peut pas appeler une fonction avec les [].

Voilà, j'ai donné mon avis. =)
[Edit: Et j'ai encore pondu un pavé.]

"il faut que la variable globale ai t "
"qu'on n'ai t "
Vengeance !
Et puis moi je parlais dans le futur. :P

"dans mon message comme dans ceux d'avants"
avant*

"Mieux vaut présenter un algorithme qui ne répond pas dans la seconde"
C'est pas de l'algo c'est du code. Mauvaise influence des nouveaux programmes de l'éducation nationale ?

"il faut que la variable globale aie"
ait*

Dans le contexte général, mieux vaut structurer son code correctement, donc les variables globales sont à éviter.
Les tableaux statiques ou pas, ça dépend toujours de l'utilisation, et franchement c'est pas plus mal.
De toute façon tu peux forcément borner le nombre de cases à allouer, mais lorsqu'il est trop gros tu n'as plus le choix.
Maintenant on peut aussi se simplifier la vie avec des vecteurs (puisque la stl prévoit nombre d'opérations sur eux).

Dans le cas de concours où les contraintes sont fixées, les données d'entrée certifiées, et le programme court et basé autour d'un unique algorithme, ça ne fait que complexifier le code de passer par autre chose que du statique.
La mémoire statique étant initialisée à 0, ça nous évite au moins une boucle, et des passages en paramètres qui alourdissent \^\^.

ps : C'est trop facile Equinoxe de justifier ton absence de france-ioi par un traumatisme :p Va bosser plutôt, c'est pas comme s'il y avait les IOI derrière ;)
édité : Et les IOI, c'est cool :p (Oui Thomas)

Ouai non mais vous avez raison, les tableaux statiques c'est cool, on devrait tous se utiliser des tableaux de taille Sys.max_array_length dans nos programmes, comme ça serait du O(1) et y a plus de problème de mémoire ... xD

Voilà :)

Thomas > Argument ad hominem. Et encore. Donc vengeance refusée. =p

Artix >
Pour avant, typo.
Pour "des nouveaux programmes de l'éducation nationale" => ?
Quand je dis ça, je parle bien du binaire compilé à partir d'un code se basant sur un algorithme. C'est mieux comme ça ?

Sur le reste, on est d'accord. Dans le cadre d'un concours uniquement. Le souci, c'est que le "longue vie à "int t[N_MAX];" !' laisse à penser une utilisation en dehors d'un concours. Ce qui me semble être une des pires erreurs imaginables, dès qu'on sort du strict cadre d'un concours.

[Edit: TLN > +Sys.max_array_length]

Je parle dans le cadre d'un concours bien sûr.

Yeah TLN brandit le V de la Victoire!

Honte sur moi !
J'avais oublié le deuxième paramètre du constructeur de vector.
Du coup, même un tableau à trois dimensions se fait relativement facilement (typedef vector\<int> vi; typedef vector\<vi> vvi; typedef vector\<vvi> vvvi; vvvi t(x, vvi(y, vi(z, 0)));) (voire, en mode code-réutilisable, code template :
template \<int NDim, typename Type>
struct Vect {
typedef std::vector\<typename Vect\<NDim - 1, Type>::type> type;
static type init(int * Dims, Type default = Type()) {
return type(*Dims, Vect\<NDim - 1, Type>::init(Dims + 1));
}
};
template \<typename Type>
struct Vect\<0, Type> {
typedef Type type;
static type init(int * Dims, Type default = Type()) {
return default;
}
};
// S'utilise :
int Dims[] = {2, 4, 3};
Vect\<3, int>::type T(Vect\<3, int>::init(Dims, 0)); // Initialize un tableau de 2 * 4 * 3 à 0

Comme ça, ça rentre dans le code préparé à l'avance, et il n'y a rien à réécrire.

Même dans le cadre d'un concours, « int t[N_MAX] » c'est moyennement pratique. Dès que tu commences à vouloir y mettre autre chose (genre des paires ou des structs à toi), puis qu'il faut réseter le contenu entre deux instances ... ben dans un cas tu fais machin.clear() / machin.resize(). Dans l'autre tu t'en sors encore avec une boucle ...
Et pour faire un tableau à 2 dimensions, « vector > tableau (n, vector (m, 0)) » c'est trop long à écrire ?

Ne me faites pas rire en me disant que d'écrire à la place un « int tableau[n][m] » ça vous aura permis de gagner 10sec et d'obtenir un meilleurs classement au concours ... Oui après quand on veut faire un tableau à 3 dimensions ça devient plus chiant ... mais honnêtement ça sert peu, et même si c'était le cas, je vous invite à utiliser des « typedef vector > matrix » ou des « #define V vector » dans votre code (même si le deuxième est un peu moche).

Ah mon dieu quelle horreur !
Et le "code préparé à l'avance" beurk. Je considère cela comme de la triche, ou du topcoderisme aigu (je me souviens encore du coup de la dichotomie avec un flot max derrière :/ Quand tu vois les codes des autres avec leur flot max déjà codé dans un namespace... Beurk !)