reperage d'île - Page 1

-

ca me fait un peu penser à kobox

faudrais déjà lire les groupes de haut en bas (vu l'ordre des numero)

cherche un X, remplace le par le num, cherche les X des 4 coté, si il y en a un, relance la fct de recherche sur celui ci ... ect
qt c fini, incremente le numero, et repart du debut à la recherche d'un X

un truc style comme ca :

check(x, y, num)
{ if(map[x][y] == 'X') map[x][y] = num ;
else return ;
check(x,y+1,num) ;
check(x,y-1,num) ;
check(x+1,y,num) ;
check(x-1,y,num) ;
}

main(void)
{

filetomap() ;

int num=0 ;

for(x=0;x<maxx;x++)
for(y=0;y<maxy;y++)
if(map[x][y] == 'X' ){ check(x,y,num+'0') ; num++ ; x=y=0 ; }

dispmap() ;

}

bah tout dépend des contraintes d'optimisations que tu te donnes... si bouffer N cases sur la pile te convient ou pas, si tu veux optimiser pour les formes "simples" ou pour le pire des cas, etc...

-

si tu ne connais pas le nb de collone c pas possible :/
ou bien tu compte le nb de char et tu en deduis le nb colonnes ac une division ^^

edit : division pas modulo ^^

-

Vite de même, en Java (nécessite quelques modification si en C) :

private char[][] mat = new Char[NB_LIN][NB_COL];

public static void main (String[] Args) {
String inStr = Args[0];
int pos = 0;
int motif = 0;

for (int i = 0; i < NB_LIN; i++) {
  for (int n = 0; n < NB_COL; n++) {
    mat[i][n] = inStr.charAt(pos++);
  }
}

for (int i = 0; i < NB_LIN; i++) {
  for (int n = 0; n < NB_COL; n++) {
    if (mat[i][n] == 'X') {
      explore(i, n, motif++);
    }
  }
}

for (int i = 0; i < NB_LIN; i++) {
  for (int n = 0; n < NB_COL; n++) {
    System.out.print(mat[i][n]);
  }
  System.out.println();
}

}

public static void explore(short x, short y, char motif) {
  if (mat[i][n] == 'X') {
     mat[i][n] = motif;
     if (i > 0) {
       explore(i - 1, n, motif);
     }
     if (n > 0) {
       explore(i, n - 1, motif);
     }
     if (i < (mat.length - 1)) {
       explore(i + 1, n, motif);
     }
     if (n < (mat[0].length - 1)) {
       explore(i, n + 1, motif);
     }
  }
}

Ce n'est sûrement pas optimal, mais c'est dans le cadre d'un exam, alors l'important c'est de faire la job...

[edit]
Ok, quelqu'un a posté avant moi
[/edit]

posté avant toi mais toi tu as fait du code bien plus clean

r043v :
posté avant toi mais toi tu as fait du code bien plus clean

Merci, mais le tien est pas mal plus court

r043v :
si tu ne connais pas le nb de collone c pas possible :/
ou bien tu compte le nb de char et tu en deduis le nb colonnes ac une division ^^

edit : division pas modulo ^^

Genre (où le fichier a été lu vers str) :

for (int i = 0; i < str.length(); i++) {
    if (str.charAt(i) == '\n') {
      NB_COL = i - 1;
      NB_LIN = str.length() / i; 
      break;
    }
}

Ça suppose que le fichier finit par '\n' ... (Sinon : NB_LIN = (str.length() + 1) / i ;

bah en rajouttant la fct qui crée la map, l'affiche, plus les test pour voir si on est pas au limite de la map c kifkif

oui, si '\n' est utilisé pour delimiter la ligne, sinon, on est obligé de partir de style 42 en taille et de reduire tant que strlen/taille != 0

edit : j'avais mal compris ton code, autt pour moi ^^

tiens, ce problème me rappel mes tous premiers pas dans la programmation, quand j'essayais de faire un démineur : le pb étais de trouver l'ago qui trouve les zones de zéros. J'ai mis au moins 3 ans à trouver l'algo .

Moi à part l'algo naïf de hibou, je ne saurais pas trop optimiser
Pollux ?

bah là c'est du O(n) en temps, on peut pas faire mieux, et du O(n*ln(n)) en espace, mais je pense pas qu'on puisse faire vraiment mieux dans le pire des cas... après évidemment on peut faire plein d'optimisations si les formes sont "presque" convexes (genre union de N trucs convexes, on doit pouvoir se débrouiller avec O(ln(n)) en espace et O(N*n) en temps)

r043v :
oui, si '\n' est utilisé pour delimiter la ligne, sinon, on est obligé de partir de style 42 en taille et de reduire tant que strlen/taille != 0

Je suis un peu perdu, qu'est-ce que tu veux dire par 42 en taille, pourquoi la ligne ne finirait pas par '\n' ?

Je sais que, sous MS, le délimiteur de fin de ligne est "\r\n" (ou "\n\r" je en suis pas sûr), mais ça fait juste qu'on doit écrire :

if (str.charAt(i) == '\n') {
NB_COL = i - 1;
NB_LIN = str.length() / (i + 1);
break;
}

Sinon, on peut lire ligne par ligne et là on a pas les fin de ligne, mais on peut compter le nombre de ligne que l'on a et, comme les lignes sont de taille fixe, on a dirrectement le nombre de colonnes avec strlen.

Pollux :
bah là c'est du O(n) en temps, on peut pas faire mieux, et du O(n*ln(n)) en espace, mais je pense pas qu'on puisse faire vraiment mieux dans le pire des cas... après évidemment on peut faire plein d'optimisations si les formes sont "presque" convexes (genre union de N trucs convexes, on doit pouvoir se débrouiller avec O(ln(n)) en espace et O(N*n) en temps)

Dans le fond, tu as raison, un algo qui s'exécute en N est assez rapide pour que, à moins qu'il soit exécuté très fréquemment, ce soit vraiment critique de l'optimiser ...

Orion_ a dit qu'on ne connais pas le nb de lignes ni de colones, j'en ai deduit qu'il n'y avais pas de char specifique pour detecter la fin de lignes,
donc, qu'il fallais compter tout les char jusqu'a la fin du fichier, puis tester des tailles jusqu'a ce que ca tombe juste ^^

> strlen/taille != 0
la g dit nimporte koi, finalement ct bien un modulo
ma methode etait : taille_totale%taille_presumé_de_la_ligne si c 0 ben c la bonne taille ^^
si c pas 0, on decremente la taille presumée et on recommence
je disais de commencer ac une taille presumé de 42, parseque 42

mais c sur que si les fin de lignes sont signalées, trouver les tailles de la matrice est bien plus simple ^^

Pollux g rien compris à ton post ^^""

-

Tiens ça me donne presque envie d'essayer :]

essaye plutot de faire un algo de destruction de base ennemi a la koboG c bien plus marrant

r043v :
Orion_ a dit qu'on ne connais pas le nb de lignes ni de colones, j'en ai deduit qu'il n'y avais pas de char specifique pour detecter la fin de lignes,
donc, qu'il fallais compter tout les char jusqu'a la fin du fichier, puis tester des tailles jusqu'a ce que ca tombe juste ^^

> strlen/taille != 0
la g dit nimporte koi, finalement ct bien un modulo
ma methode etait : taille_totale%taille_presumé_de_la_ligne si c 0 ben c la bonne taille ^^
si c pas 0, on decremente la taille presumée et on recommence
je disais de commencer ac une taille presumé de 42, parseque 42

mais c sur que si les fin de lignes sont signalées, trouver les tailles de la matrice est bien plus simple ^^

Ok c'est juste moi qui ne pigeait pas ...

r043v :
Pollux g rien compris à ton post ^^""

C'est pas compliqué, c'est une notation qui exprime la performance d'un algorithme. En gros, ça représente la croissance du nombre d'itérations p/r au nombre d'éléments ...

Exemple :

for n ... nb_elements
for i ... nb_elements
BLOC D'INSTRUCTIONS

S'exécute en O(n^2) i.e. que si tu a 1 élément, le bloc d'instruction est exécuté 1^2 fois donc une fois, pour 16 éléments, on saute à 16^2 soit 256. On remarque que c'est très lent vs un algo en O(n) où pour 16 éléments, ça donne 16 itérations.

Il y a des algo avec des complexités tellement élevées que même avec un ordinateur 1 milliard de fois plus puissant que le meilleur ordi que tu peux acheter n'aurait pas assez de temps d'ici le big crush (si ça arrive un jour) pour résoudre le problème (si il y a un nombre important d'éléments) : O(n^n) ou NP complete. Par exemple : pour trouver le plus court chemin entre 100 noeuds tous interconnectés en essayant tous les chemins et retenant le plus court, ça va prendre 100^100 soit 1 x 10^20 itérations (ou 100 - 1 ^ 100 - 1 ... ou autre chose, mais c'est très long) (algo de 'bouette' en passant, avec Dijkstra c'est une toute petite fraction des itérations).

Pour trouver la complexité, on regarde habituellement le pire des scénarios : ex recherche séquentielle = O(n) ...

S'exécute en O(n^2) i.e. que si tu a 1 élément, le bloc d'instruction est exécuté 1^2 fois donc une fois, pour 16 éléments, on saute à 16^2 soit 256. On remarque que c'est très lent vs un algo en O(n) où pour 16 éléments, ça donne 16 itérations.

C'est un peu plus compliqué que ça : c'est une notation où on exprime la complexité seulement pour n très très grand (O(n^2) = O(n^2 + n*ln(n))) et qui n'est défini qu'à un facteur près, (O(42 n^2) = O(n^2)) Pour plus d'informations, http://fr.wikipedia.org/wiki/Notations_de_Landau ^^

n'aurait pas assez de temps d'ici le big crush (si ça arrive un jour)

Ha si, si ça n'arrive pas, il aura assez de temps

O(n^n) ou NP complete

Un problème NP-complet n'est (par conjecture) pas soluble en temps polynomial, mais c'est pas pour autant que c'est exponentiel (un algo en O(n^ln(n)) est plus que polynomial, mais pas exponentiel pour autant)

Pollux :
Un problème NP-complet n'est (par conjecture) pas soluble en temps polynomial, mais c'est pas pour autant que c'est exponentiel (un algo en O(n^ln(n)) est plus que polynomial, mais pas exponentiel pour autant)

Depuis quand O(n^ln(n)) c'est NP complete ... Je ne met pas ta parole en doute, mais ça me fait penser qu'il faut vraiment que je réouvre mon livre ...

ok merci je connaissais pas la notation ^^
je regarderais ca demain qt je serais plus die %]

Quesoft
:

Pollux :
bah là c'est du O(n) en temps, on peut pas faire mieux, et du O(n*ln(n)) en espace, mais je pense pas qu'on puisse faire vraiment mieux dans le pire des cas... après évidemment on peut faire plein d'optimisations si les formes sont "presque" convexes (genre union de N trucs convexes, on doit pouvoir se débrouiller avec O(ln(n)) en espace et O(N*n) en temps)

Dans le fond, tu as raison, un algo qui s'exécute en N est assez rapide pour que, à moins qu'il soit exécuté très fréquemment, ce soit vraiment critique de l'optimiser ...

c pas que c'est assez rapide c'est que "O(n) en temps, on peut pas faire mieux", vu que tu as N cases à remplir

j'avais fait une implementation avec deux récursions pour un projet de paint sur ti à l'époque où j e programmais sur ti, pour économiser la pile
(en analysant les lignes verticale et horizontale à chaque récursion)

les posts de Pollux, ca sent les études d'ingénieur

BakaSama :
c pas que c'est assez rapide c'est que "O(n) en temps, on peut pas faire mieux", vu que tu as N cases à remplir

Comme complexité, on ne peux pas faire mieux, mais il y a souvent, comme le soulignait Pollux, moyen d'optimiser le code tout de même ...

L'implémentation d'un même algo, avec les mêmes données en entrée, peut prendre plus ou moins de temps à s'exécuter sur une machine particulière selon la façon doit il a été programmé...

Pollux :

Un problème NP-complet n'est (par conjecture) pas soluble en temps polynomial, mais c'est pas pour autant que c'est exponentiel (un algo en O(n^ln(n)) est plus que polynomial, mais pas exponentiel pour autant)

J'ai fouillé dans mon bouquin...

En fait, un NP complete est un problème qui est solvable en temps polynomial sur un ordinateur non déterministe. Je supose que si un algo en O(n^ln(n)) est NP, c'est qu'il serait de complexité O(n^k) sur une machine non déterministe (quelque chose de théorique). Mais dans le fond, j'imagine qu'une complexité de O(n^k) sur un odinateur déterministe pourrait être également de complexité polynomiale sur un ordinateur non déterministe, donc NP anyway, alors j'aurais effectivement dû parler de complexité exponentielle (c'est juste que plusieurs algos de problèmes NP s'exécutent en temps exponentiels sur nos machines déterministes).