|
Reprise du dernier message de la page précédente :
Arbre binaire de recherche équilibré - AVL
Principe
Le principe d'un arbre équilibré est de garantir des opérations (recherche, suppression) en temps O(log n) dans un arbre binaire, en introduisant un système permettant à l'arbre de rester équilibré - c'est à dire que l'écart entre le nombre de fils de chaque noeud reste toujours optimal. C'est ce qui va permettre de rendre un arbre binaire de recherche réellement intéressant.
Le premier type d'arbre de ce genre inventé est l' arbre AVL, c'est aussi l'un des plus simple à mettre en oeuvre. Le principe est d'introduire un mécanisme de rotations des branches de l'arbre au cours de l'insertion et de la suppression pour garantir l'équilibre dudit arbre. se rapporter à la page Wikipédia pour plus d'informations.
Complexité
L'insertion et la suppression de clé se font en O(log n). Bien que ce soit moins bien qu'avec une Hashtable, les ABR équilibrés restent extrêmement utilisés, notament en raison d'une plus grande souplesse de gestion de mémoire O(n).
[C] Implémentation
La majorité des langages évolués fournissent ce genre d'outil. Ce type d'arbre existe certainement dans des bibliothèques C, mais ne fait pas partie de la lib standard. Voici une implémentation générique en C :
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172 | #include <stdlib.h>
/* structure de l'arbre binaire de recherche equilibre AVL */
typedef struct node
{
void* key; /* pointeur sur la cle */
unsigned h; /* hauteur du noeud */
struct node* fd; /* fils droit (superieur au noeud) */
struct node* fg; /* fils gauche (inferieur au noeud) */
}
tsearch_avl;
/* recherche recursive d'une cle */
void* search_key (tsearch_avl* abr, const void* key, int (*compar)(const void*, const void*))
{
while (abr != NULL)
{
if (compar(key, abr->key) == 0)
return abr->key;
else if (compar(key, abr->key) > 0)
abr = abr->fd;
else
abr = abr->fg;
}
return NULL;
}
#define _hauteur(a) ( a == NULL ? 0 : a->h )
/* calcule la hauteur d'un noeud a partir de ses sous-noeuds */
static inline void calc_hauteur (tsearch_avl* abr)
{
unsigned a, b;
abr->h = 1 + ( (a = _hauteur(abr->fg)) > (b = _hauteur(abr->fd)) ? a : b );
}
/* rotations AVL */
static inline tsearch_avl* rotate_g (tsearch_avl* p)
{
tsearch_avl *q, *v;
q = p->fd;
v = q->fg;
q->fg = p;
p->fd = v;
calc_hauteur(p);
calc_hauteur(q);
return q;
}
static inline tsearch_avl* rotate_d (tsearch_avl* q)
{
tsearch_avl *p, *v;
p = q->fg;
v = p->fd;
p->fd = q;
q->fg = v;
calc_hauteur(q);
calc_hauteur(p);
return p;
}
/* equilibrage suivant le principe AVL */
static tsearch_avl* equilibrage (tsearch_avl* abr)
{
unsigned hg = _hauteur(abr->fg), hd = _hauteur(abr->fd);
if (hg-hd == 2)
{
if ( _hauteur(abr->fg->fg) < _hauteur(abr->fg->fd) )
abr->fg = rotate_g (abr->fg);
abr = rotate_d (abr);
}
else if (hd-hg == 2)
{
if ( _hauteur(abr->fd->fd) < _hauteur(abr->fd->fg) )
abr->fd = rotate_d (abr->fd);
abr = rotate_g (abr);
}
return abr;
}
/* fonction recursive de suppression d'une cle dans l'arbre binaire de recherche */
void delete_key (tsearch_avl** abr, const void* key, int (*compar)(const void*, const void*))
{
tsearch_avl *tmp;
if (*abr != NULL)
{
/* si la cle est trouvee, on effectue la suppression */
if (compar(key, (*abr)->key) == 0)
{
if ((*abr)->fd == NULL && (*abr)->fg == NULL)
{
free(*abr);
*abr = NULL;
}
else if ((*abr)->fg == NULL)
{
tmp = *abr;
*abr = (*abr)->fd;
free(tmp);
}
else if ((*abr)->fd == NULL)
{
tmp = *abr;
*abr = (*abr)->fg;
free(tmp);
}
else
{
tmp = (*abr)->fd;
while (tmp->fg != NULL)
tmp = tmp->fg;
(*abr)->key = tmp->key;
delete_key (&(*abr)->fd, tmp->key, compar);
}
}
else if (compar(key, (*abr)->key) > 0)
delete_key (&(*abr)->fd, key, compar);
else
delete_key (&(*abr)->fg, key, compar);
/* reequilibre et recalcule la hauteur
le long de la remontee recursive */
if (*abr != NULL)
{
*abr = equilibrage (*abr);
calc_hauteur(*abr);
}
}
}
/* cree une nouvelle feuille allouee dynamiquement */
static tsearch_avl* new_leaf (const void* key)
{
tsearch_avl* leaf = malloc(sizeof *leaf);
if (leaf != NULL)
leaf->key = (void*) key, leaf->fg = NULL, leaf->fd = NULL, leaf->h = 1;
return leaf;
}
/* fonction recursive d'insertion d'une cle dans l'arbre */
void insert_key (tsearch_avl** abr, const void* key, int (*compar)(const void*, const void*))
{
if (*abr == NULL)
*abr = new_leaf(key);
else
{
if (compar(key, (*abr)->key) > 0)
{
insert_key(&(*abr)->fd, key, compar);
}
else if (compar(key, (*abr)->key) < 0)
{
insert_key(&(*abr)->fg, key, compar);
}
/* reequilibre et recalcule la hauteur
le long de la remontee recursive */
*abr = equilibrage (*abr);
calc_hauteur(*abr);
}
}
/* fonction de suppression de l'arbre binaire de recherche - libere la memoire allouee */
void tsearch_delete (tsearch_avl** abr)
{
if (*abr != NULL)
{
if ((*abr)->fg != NULL)
tsearch_delete (&(*abr)->fg);
if ((*abr)->fd != NULL)
tsearch_delete (&(*abr)->fd);
free(*abr), *abr = NULL;
}
}
|
Édité
le 07/10/2010 à 12:51:52
par yoch
|
|
|
|
Étudiant qui bosse... ou pas
|
Recherche de chemin: A*
Principe
A* est un algorythme de recherche de chemin axé sur la performance, c'est-à-dire qui trouvera un chemin assez rapidement mais pas forcément le plus court (généralement assez proche quand même), par opposition à un algorythme qui recherche à tout prix la solution la plus courte mais nécéssitant plus de temps ( algorythme de Dijkstra).
Vous trouverez plus de détails sur cet algorythme dans ce tutoriel.
Complexité
L'algorythme de Dijkstra étant en o((m+n)*ln(n)), on espère qu'A* est généralement meilleur pour un terrain pas trop accidenté. Il faut quand même noter qu'il met pas mal de temps avant de se rendre compte qu'un chemin est impossible sur de grand graphes, spécialement entre deux composantes connexes (typiquement, deux îles séparées par la mer sur une carte)
Java
Cette impémentation est indépendante des données manipulées. La seule restriction que vous avez est que chaque noeud doit implémenter l'interface Node et que la distance entre deux noeuds d'un même graphe soit cohérente.
L'interface Node que vous devez implémenter :
Code : Java | import java.util.*;
public interface Node {
public Iterable<? extends Node> getNeighbours (Object param) ;
public Iterable<? extends Node> getNeighbours () ;
public double getDistanceTo (Node node) ;
}
|
Puis l'algorythme proprement dit:
Code : Java 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99 | import java.util.*;
public class AStarPathFinder {
private class Item implements Comparable<Item> {
protected double cost1, cost2, totalCost;
protected Item parent;
protected Node node;
public Item () {}
public Item (double a, double b, double c, Item p, Node n) {
cost1=a;
cost2=b;
totalCost=c;
parent=p;
node=n;
}
public boolean equals (Object o) {
return ((Item)o).node.equals(node);
}
public int hashCode () {
return node.hashCode();
}
public int compareTo (Item it) {
if (this.totalCost<=it.totalCost) return -1;
else return 1;
}}
private NavigableSet<Item> openList = new TreeSet<Item>();
private Set<Item> closedList = new HashSet<Item>();
private Deque<Node> path = null;
private Node start, end;
private Item tmp = new Item();
private Object param;
private boolean impossible = false;
public AStarPathFinder (Node s, Node e, Object p) {
start=s;
end=e;
param=p;
}
public AStarPathFinder (Node s, Node e) { this(s,e,null); }
public AStarPathFinder () { this(null,null,null); }
public void clear () {
openList.clear();
closedList.clear();
path = null;
impossible = false;
}
private void calculatePath () {
clear();
openList.add(new Item(0, 0, 0, null, start));
browseOpenList();
}
private void browseOpenList () {
Item e;
while ((e = openList.pollFirst())!=null) {
closedList.add(e);
if (e.node.equals(end)) break;
browseNeighbours(e);
}
if (e!=null && e.node.equals(end)) buildPath(e);
else impossible = true;
}
private void browseNeighbours (Item it) {
for (Node n : it.node.getNeighbours(param)) {
tmp.node = n;
if (closedList.contains(tmp)) continue;
double cost1 = it.cost1 + it.node.getDistanceTo(n);
double cost2 = end.getDistanceTo(n);
double totalCost = cost1 + cost2;
if (openList.contains(tmp)) {
Item e = openList.ceiling(tmp);
if (e.totalCost <= totalCost) continue;
else {
openList.remove(e);
openList.add(new Item(cost1, cost2, totalCost, it, n));
}}
else openList.add(new Item(cost1, cost2, totalCost, it, n));
}}
private void buildPath (Item it) {
path = new LinkedList<Node>();
while (!it.node.equals(start)) {
path.addFirst(it.node);
it = it.parent;
}}
public Queue<Node> getPath () {
if (path==null && !impossible) calculatePath();
return path;
}
public Queue<Node> getPath (Node start, Node end, Object param) {
this.start = start;
this.end = end;
this.param = param;
calculatePath();
return path;
}
public Queue<Node> getPath (Node start, Node end) { return getPath(start,end,null); }
}
|
Qu'on peut très facilement utiliser de cette manière :
Code : Java | Collection<Node> path = new AStarPathFinder(noeudDépart, noeudARrivée, paramètre).getPath();
|
L'objet paramètre est une donnée utilisateur qui sera passée à chaque appel de getDistanceTo. ON peut ainsi passer des critères de recherches spécifiques par exemple.
Améliorations possibles: encore plus profiter de la généricité.
Voilà, amusez-vous bien !
Il y a 3 types de mathématiciens: ceux qui savent compter, et ceux qui ne savent pas.
Javascript, php, html, jeux, blagues, etc. == http://quentinc.net/
|
Ville : Annemasse
Pays : France métropolitaine
|
QuentinC 2>>l'indentation a pas du aimer le copier coller...
tout vient a point a qui sait attendre. 
|
Étudiant qui bosse... ou pas
|
CitationQuentinC 2>>l'indentation a pas du aimer le copier coller...
C'est pas grave. Il est plus que probable que celui qui en fera un copier-coller le fera dans un IDE qui le réindentera automatiquement.
La vraie raison c'est que je ne sais pas pourquoi...
Il y a 3 types de mathématiciens: ceux qui savent compter, et ceux qui ne savent pas.
Javascript, php, html, jeux, blagues, etc. == http://quentinc.net/
|
|
|
meci
|
Études : Paris 7 Denis Diderot
|
|
Trance forever :)
|
Spéciale dédicace, le PGCD :
Code : Autre1
| pgcd =: [: {. |/\@|.^:(*@{:)^:_ |
|
日本語を勉強する。
|
@Pouet-forever : En quel langage est-ce ?
|
Trance forever :)
|
En J. 
|
while (1337)
|
Hello !
Un petit AStar en C++, fait assez rapidement 
Secret (cliquez pour afficher)Code : C++ - AStar.h 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 | //
// Code by Yann Viens
// Started 18/01/2011
// AStar.h: Class AStar implements PathFinder interface
//
#ifndef ASTAR_H_
# define ASTAR_H_
# include "PathFinder.h"
// Code for some methods is defined in the header file so they are inline
class AStar: public PathFinder
{
public:
AStar();
~AStar();
void setStart(const int start)
{
_start = start;
}
void setEnd(const int end)
{
_end = end;
}
std::list<int> const& findPath(Graph& graph) throw (NoPathFound);
private:
int _start;
int _end;
struct HeurNode
{
HeurNode();
HeurNode(const float heur, const float dis, const int id, const int prev);
float _heur;
float _dis;
int _id;
int _prev;
};
typedef std::list<HeurNode> WorkList;
WorkList _openSet;
WorkList _closeSet;
void processVertex(Graph::tNode & nodes, HeurNode& toVisit);
float calcDist(Node const& actual, Node const& toGo);
bool isInWorkList(const int id, WorkList const& daList);
void insertInOpenList(int id, int prev, float heur, float dis, WorkList& daList);
std::list<int>const& buildBackWay();
};
#endif // ASTAR_H_
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143 | //
// Code by Yann Viens
// Started 18/01/2011
// AStar.cpp : Implementation of AStar class
//
#include <cmath>
#include "AStar.h"
AStar::AStar()
{
}
AStar::~AStar()
{
}
AStar::HeurNode::HeurNode()
{
}
AStar::HeurNode::HeurNode(const float heur, const float dis, const int id, const int prev): _heur(heur), _dis(dis), _id(id), _prev(prev)
{
}
//
// Check if a node is already in a list (open or close set)
//
bool AStar::isInWorkList(const int id, WorkList const& daList)
{
WorkList::const_iterator itListBegin = daList.begin();
const WorkList::const_iterator itListEnd = daList.end();
while (itListBegin != itListEnd)
{
if ((*itListBegin)._id == id)
return true;
++itListBegin;
}
return false;
}
//
// Insert a new node in the open set. The open set is sorted to optimize the algorithm.
//
void AStar::insertInOpenList(const int id, const int prev, const float heur, const float dis, WorkList& daList)
{
WorkList::iterator itListBegin = daList.begin();
const WorkList::iterator itListEnd = daList.end();
while (itListBegin != itListEnd && (*itListBegin)._heur < heur)
++itListBegin;
if (itListBegin != itListEnd)
daList.insert(itListBegin, HeurNode(heur, dis, id, prev));
else
daList.push_back(HeurNode(heur, dis, id, prev));
}
//
// Calcul the real distance between two nodes
//
float AStar::calcDist(Node const& actual, Node const& toGo)
{
return sqrt(pow(toGo.getPosX() - actual.getPosX(), 2) + pow(toGo.getPosY() - actual.getPosY(), 2) + pow(toGo.getPosZ() - actual.getPosZ(), 2));
}
//
// This method is called to run through the nodes
//
void AStar::processVertex(Graph::tNode & nodes, HeurNode& visiting)
{
std::list<int>const& adj = nodes[visiting._id]->getAdjList();
std::list<int>::const_iterator itAdjBegin = adj.begin();
const std::list<int>::const_iterator itAdjEnd = adj.end();
float heuristic, dis;
while (itAdjBegin != itAdjEnd)
{
if (isInWorkList(*itAdjBegin, _openSet) == false && isInWorkList(*itAdjBegin, _closeSet) == false)
{
// Heuristic calcul: distance between the next node and the end
heuristic = calcDist(*nodes[*itAdjBegin], *nodes[_end]);
dis = visiting._dis + calcDist(*nodes[visiting._id], *nodes[*itAdjBegin]);
insertInOpenList(*itAdjBegin, visiting._id, heuristic, dis, _openSet);
}
++itAdjBegin;
}
}
//
// When the end node is found, this methods is called to build back the way between the start and the end
//
std::list<int>const& AStar::buildBackWay()
{
std::list<int>* way = new std::list<int>();
HeurNode back = _closeSet.front();
WorkList::iterator itListBegin;
WorkList::iterator itListEnd;
while (back._id != _start)
{
way->push_front(back._id);
itListBegin = _closeSet.begin();
itListEnd = _closeSet.end();
while (itListBegin != itListEnd && (*itListBegin)._id != back._prev)
++itListBegin;
back = *itListBegin;
}
way->push_front(back._id);
return *way;
}
//
// Method to call to build a way from a graph
//
std::list<int>const& AStar::findPath(Graph& graph) throw (NoPathFound)
{
Graph::tNode const& nodes = graph.getNodes();
if (nodes.find(_start) == nodes.end() || nodes.find(_end) == nodes.end())
throw NoPathFound(_start, _end);
HeurNode toVisit;
bool found = false;
_openSet.clear();
_closeSet.clear();
_openSet.push_front(HeurNode(0, 0, _start, 0));
while (_openSet.size() && found == false)
{
toVisit = _openSet.front();
_openSet.pop_front();
_closeSet.push_front(toVisit);
if (toVisit._id == _end)
found = true;
else
processVertex(const_cast<Graph::tNode&>(nodes), toVisit);
}
if (found == false)
throw (NoPathFound(_start, _end));
return buildBackWay();
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | //
// Code by Yann Viens
// Started 18/01/2011
// PathFinder.h: Class PathFinder is an interface for path finding algorithms
//
#ifndef PATHFINDER_H_
# define PATHFINDER_H_
# include <list>
# include "Graph.h"
# include "Exception/NoPathFound.h"
class PathFinder
{
public:
virtual ~PathFinder() {}
virtual void setStart(const int start) = 0;
virtual void setEnd(const int start) = 0;
virtual std::list<int>const& findPath(Graph& graph) throw (NoPathFound) = 0;
};
#endif // PATHFINDER_H_
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | //
// Code by Yann Viens
// Started 17/01/2011
// Graph.h: Class Graph is class used to defined a graph
// In this program, a graph is defined by a map of vertex (tNode)
// Each vertex (or node), contains a list of adjacent vertex
//
#ifndef GRAPH_H_
# define GRAPH_H_
# include <map>
# include "Node.h"
// Code for some methods is defined in the header file so they are inline
class Graph
{
public:
Graph();
~Graph();
typedef std::map<int, Node*> tNode;
void addNode(Node* newNode)
{
_nodes[newNode->getId()] = newNode;
}
tNode const & getNodes() const
{
return _nodes;
}
void addLink(const int id, const int adjVertex);
#ifdef _PATHFINDERDEBUG
void displayGraph() const;
#endif
private:
tNode _nodes;
};
#endif // !GRAPH_H_
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 | //
// Yann Viens
// Started 17/01/2011
// Node.h: A node represents a Vertex in a graph
// Each Node has an adjacent vertex list, that describe the adjacents roads
//
#ifndef NODE_H_
# define NODE_H_
# include <list>
# include "Room.h"
// Code for some methods is defined in the header file so they are inline
class Node: public Room
{
public:
Node();
~Node();
void addAdjVertex(const unsigned int id)
{
_adjList.push_back(id);
}
// Getter & Setter
int getId() const
{
return _id;
}
void setId(const int id)
{
_id = id;
}
std::list<int>const& getAdjList() const
{
return _adjList;
}
private:
int _id;
std::list<int> _adjList;
};
#endif // !NODE_H_
|
J'ai mis ici uniquement le code des structures de données utilisées, et celui de l'algo. Si vous voulez un exemple concret d'utilisation de cet algo, vous en trouverez un ici : http://yannshu.com/code/cpp/PathFinder-Bin+Code.zip
Cet exemple contient un exécutable compilé pour windows, ainsi que la totalité du code source.
|
|
File de priorité - avec itérateurs (C++)
Bonjour,
Ayant eu besoin d'une file de priorité itérable en C++, ce qui n'est pas possible avec le conteneur <priority_queue>, voici ma mouture personnelle :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | #ifndef _P_QUEUE_H
#define _P_QUEUE_H
#include <vector>
#include <algorithm>
template <typename T>
class p_queue : private std::vector<T>
{
public:
typedef typename std::vector<T>::const_iterator const_iterator;
p_queue();
void push (const T& x) { std::vector<T>::push_back(x); push_heap( std::vector<T>::begin(), std::vector<T>::end() ); }
void pop () { pop_heap( std::vector<T>::begin(), std::vector<T>::end() ); std::vector<T>::pop_back(); }
inline const T& top() const { return std::vector<T>::front(); }
inline bool empty() const { return std::vector<T>::empty(); }
inline size_t size() const { return std::vector<T>::size(); }
inline const_iterator begin() { return std::vector<T>::begin(); }
inline const_iterator end() { return std::vector<T>::end(); }
};
#endif
|
Le principe est très simple : on réutilise le conteneur <vector>, que l'on utilise conjointement avec les fonction push_heap() et pop_heap() (définies dans <algorithm>) pour gérer la file de priorité.
Et enfin, un typedef pour redéfinir les itérateurs. Seuls les const_iterator sont fournis, pour que l'utilisateur ne puisse pas corrompre le heap.
Édité
le 20/03/2011 à 11:42:06
par yoch
|
while (1337)
|
Sympa 
Ça me rappelle une std::stack mutante itérable que j'avais codé il y a quelques temps.. J'vais essayer de retrouver ça !
Par contre, ajouter des éléments dans un vector avec des push_back, c'est pas génial il me semble...
Citation : http://www.cplusplus.com/reference/stl/vector/push_back/This effectively increases the vector size by one, which causes a reallocation of the internal allocated storage if the vector size was equal to the vector capacity before the call.
|
|
Citation : YannshuPar contre, ajouter des éléments dans un vector avec des push_back, c'est pas génial il me semble...
Comprends pas le problème, avec quoi tu voudrais ajouter des éléments (un par un) sinon ?
Et puis, les réallocation sont censées arriver plutôt rarement :
Citation : http://www.cplusplus.com/reference/stl/vector/push_back/This effectively increases the vector size by one, which causes a reallocation of the internal allocated storage if the vector size was equal to the vector capacity before the call.
|
Chieur professionnel
|
C'est du O(1) en amorti le push_back.
Les caisses sont vides
Traité européen de 1965 :
Citation : Traité
FONCTIONNAIRES ET AGENTS DES COMMUNAUTÉS EUROPÉENNES
Article 12
Sur le territoire de chacun des États membres et quelle que soit leur nationalité, les fonctionnaires et autres agents des Communautés:
a) jouissent de l'immunité de juridiction pour les actes accomplis par eux, y compris leurs paroles et écrits, en leur qualité officielle, sous réserve de l'application des dispositions des traités relatives, d'une part, aux règles de la responsabilité des fonctionnaires et agents envers les Communautés et, d'autre part, à la compétence de la Cour pour statuer sur les litiges entre les Communautés et leurs fonctionnaires et autres agents. Ils continueront à bénéficier de cette immunité après la cessation de leurs fonctions,
|
|
|
Bonjour j'aimerai proposer ma propre version du quicksort en Ocaml en version list. Elle ressemble beaucoup a celle déjà faites mais bon je veut quand même partager 
Quicksort
Code : OCaml 1
2
3
4
5
6
7
8
9
10
11
12
13
14 | let rec partition l p=
match l with
| [] -> ([],[])
|a::q when a<p ->
let (x,y)= partition q p in
(a::x,y)
|a::q -> let (x,y)= partition q p in
(x,a::y);;
let rec quicksort l =
if l=[] then []
else let a =List.hd l and q = List.tl l in
let x,y = partition q a in
(quicksort x)@(a::(quicksort y));;
|
Il a été écrit en C et je l'ai pas vu en Ocaml alors le voila Pour l'explication vous pouvez aller voir le premier post sur ce sujet. La grande différence c'est que j'utilise True et False au lieu de chiffre dans mon tableau
Code : OCaml 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | let crible n =
let t = Array.make (n+1) true in
for i = 2 to n/2 do (*racine de n marche mieux (en complexité) car a partir de racine de n, k est tj plus grand que n et donc la suite est inutile *)
if t.(i) then
(
let k = ref (i*i) in
while !k <= n do
t.(!k)<- false;
k:= !k +i;
done;
)
done; (* la c'est fini il reste plus qu'a les afficher *)
for i = 2 to n do
if t.(i) then (print_int(i);print_string" ";)
done;;
|
Ok puisque j'y suis voici un Quicksort avec des vecteur en Ocaml
Code : OCaml 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | let partition t d f =
let i = ref d and j = ref f in
while !i < !j do
if t.(!i+1) <= t.(!i) then
(
swap t !i (!i+1);
incr i;
)
else
(
swap t (!i+1) !j;
decr j;
)
done;
!i;;
let quicksort t =
let rec aux d f =
if d < f then
let i = partition t d f in
aux d (i-1);
aux (i+1) f;
in
aux 0 ((Array.length t)-1);;
|
Édité
le 11/04/2011 à 00:17:28
par MichaM
|
You Are Not Alone
Ville : Paris
Pays : France métropolitaine
|
Pathfinder : Dijkstra
Principe
L'algorithme de Dijkstra (du nom de son inventeur) permet de parcourir un graphe quelconque pondéré (à la différence du BFS) et d'en déduire le plus court chemin d'un noeud A à tous les autres noeuds du graphe.
Le principe de l'algorithme est le suivant, pour chaque noeud considéré (le premier étant le noeud de départ) on ajoute ses voisins (si ils n'ont pas déjà été vus) dans une structure qui va nous permettre de déterminer efficacement lequel de tous les noeuds ajoutés non visité est le plus proche.
La structure la mieux adaptée pour répondre à cette question est un tas (ou file à priorité), on code un tas en utilisant un arbre binaire ou tout simplement on se sert du conteneur prioirty_queue de la stl prévu à cet effet.
L'algorithme s'arrête quand tous les noeuds du graphe ont été visités (ou quand le noeud d'arrivé est atteint, selon implémentation).
Attention, les pondérations se doivent d'être positives.
Complexité
On considérera qu'un noeud contient comme information sa distance au noeud de départ.
Le pseudo code de notre algorithme est le suivant :
Ajoute noeud de départ dans tas
Tans que le tas n'est pas vide
|noeud_courrant = sommet du tas
|enleve noeud du tas
|
|Pour chaque voisin
||Si le voisin n'a jamais été vu
|||Marquer le voisin à vu
|||noeud_voisin.distance = noeud_courrant.distance + poids_arête[noeud_courrant][noeud_voisin]
|||distance_noeud_depart[noeud_voisin] = noeud_voisin.distance
|||Ajouter le noeud_voisin au tas
Les opérations d'ajout dans le tas se font en ln(nbNoeuds) et on passera par chaque arc une fois, soit une compléxité de :
O((nbNoeuds + nbArcs) * ln(nbNoeuds))
[C++] Implémentation avec priority queue
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82 | /* Par The Doctor pour le sdz */
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int NB_MAX_NOEUDS = 1000;
const int INFINI = 1000*1000*1000;
const int INDEFINI = -INFINI;
struct arrete
{
int idNoeudArrive;
int poidsArrete;
arrete() {}
arrete(int idNoeudArrive, int poidsArrete) : idNoeudArrive(idNoeudArrive), poidsArrete(poidsArrete) {}
};
struct noeud
{
int idNoeud;
int dist;
noeud() {}
noeud(int idNoeud, int dist) : idNoeud(idNoeud), dist(dist) {}
bool operator < (const noeud &autre) const
{
if(dist != autre.dist)
return dist > autre.dist;
return idNoeud > autre.idNoeud;
}
};
vector<arrete> voisinDuNoeud[NB_MAX_NOEUDS+2];
priority_queue<noeud> noeudsAVisiter;
int dist[NB_MAX_NOEUDS+2];
bool dejaVu[NB_MAX_NOEUDS+2];
int chemin[NB_MAX_NOEUDS+2];
int nbNoeuds, nbArretes, noeudDepart, noeudArrive;
void initDist()
{
for(int iCase = 0 ; iCase < NB_MAX_NOEUDS+2 ; iCase++)
dist[iCase] = INDEFINI;
}
int main()
{
scanf("%d%d%d%d", &nbNoeuds, &nbArretes, &noeudDepart, &noeudArrive);
initDist();
for(int iArrete = 0 ; iArrete < nbArretes ; iArrete++)
{
int noeud1, noeud2, poids;
scanf("%d%d%d", &noeud1, &noeud2, &poids);
voisinDuNoeud[noeud1].push_back(arrete(noeud2, poids));
voisinDuNoeud[noeud2].push_back(arrete(noeud1, poids));
}
noeudsAVisiter.push(noeud(noeudDepart, 0));
while(!noeudsAVisiter.empty())
{
int idNoeudEnCours = noeudsAVisiter.top().idNoeud;
int distNoeudEnCours = noeudsAVisiter.top().dist;
noeudsAVisiter.pop();
if(!dejaVu[idNoeudEnCours])
{
dejaVu[idNoeudEnCours] = true;
dist[idNoeudEnCours] = distNoeudEnCours;
for(int iVoisin = 0 ; iVoisin < (int)voisinDuNoeud[idNoeudEnCours].size() ; iVoisin++)
noeudsAVisiter.push(noeud(voisinDuNoeud[idNoeudEnCours][iVoisin].idNoeudArrive, dist[idNoeudEnCours]+voisinDuNoeud[idNoeudEnCours][iVoisin].poidsArrete));
}
}
printf("Distance minimale %d -> %d : %d\n", noeudDepart, noeudArrive, dist[noeudArrive]);
}
|
The Doctor
|
=]:-)--|--<
Études : Ecole Supérieure de l'ETML
|
|
|
Groupe : Bannis
|
@The Doctor: on aurait aimé un peu plus d'encapsulation. Là tu exposes complètement la structure que tu utilises… c'est pas très joli-joli. 
|
You Are Not Alone
Ville : Paris
Pays : France métropolitaine
|
Je fais de l'algo moi, pas de la prog.
|
X-No-Archive: yes
|
(The Doctor, il n'y a qu'un seul r à arête)
|
You Are Not Alone
Ville : Paris
Pays : France métropolitaine
|
Oups, décidément je ne le retiendrai jamais.
|
|
|
Calcul du plus petit commun multiple de deux nombres entiers positifs : PPCM
Principe
Le PPCM (lowest common multiple LCM en anglais mais j'ai trouvé d'autres acronymes comme Integer Less Common Multiple) est utilisé dans différentes opérations, il permet notamment de réduire des fractions. Il est très utilisé dans les opérations de chiffrement.
Le PPCM constitue le plus petit entier qui soit un multiple commun des nombres dont on recherche le PPCM. Ainsi le PPCM des nombres A et B divise tous les multiples communs de A et de B. Ainsi le PPCM de 12 est 10 est 60 (12 x 5 = 10 x 6 = 60).
La plupart des algorithmes que j'ai trouvé ne traitent que deux nombres à la fois, celui que je vous propose peut en traiter davantage, je pense que la limite tant du nombre de nombres traités que de leur taille sera celle de votre processeur. J'ai choisi une méthode acceptée par mon ordinateur, les deux autres ne fonctionnaient pas dès lors que les nombres traités dépassaient quelques dizaines.
Complexité
Le PPCM s'enseigne en collège, l'algorithme ne me semble donc pas très compliqué.
Il existe plusieurs méthodes pour extraire le PPCM. La première consiste à calculer de manière croissante les n premiers multiples de chaque nombre et de les comparer jusqu'à trouver le premier, donc le plus faible, multiple commun.
La seconde nécessite de décomposer chaque nombre en produit de facteurs premiers puis de comparer cette décomposition.
J'ai essayé ces deux premières méthodes mais si elles fonctionnent bien avec de petits nombres, je suis rapidement arrivé aux limites de capacité de mon ordinateur. Je me suis donc rabattu sur la troisième méthode qui nécessite de passer par le PGCD (plus grand commun diviseur : il s'agit du plus grand entier naturel par lequel chacun des nombres considérés puisse être divisé avec un reste égal à 0. Ainsi le PGCD de 12 et 10 est 2 : 12 /2 = 6, c'est un entier et 10/ 2 = 5, entier également. En anglais le PGCD se nomme greatest common divisor - GCD, integer greatest common factor ou highest common factor).
En effet le calcul du PGCD de deux nombres par l'algorithme d'Euclide est assez rapide. Il consiste à effectuer des divisions en cascade, le plus grand des deux nombres est d'abord divisé par le plus petit puis le diviseur est divisé par le reste et ainsi de suite.
Je suis parti de la formule qui veut que le produit du PPCM et du PGCD soit égal au produit des nombres, soit pour deux nombres A et B :
Par conséquent :
L'algorithme utilise le principe de la récursivité pour calculer le PPCM (et le PGCD), à partir d'une fonction qui calcule le PPCM de deux nombres. En effet :
 L'algorithme comporte plusieurs fonctions, la fonction PPCM(A,B) qui calcule le PPCM de deux nombres entiers positifs. Cette fonction fait appel à la fonction PGCD(A,B) qui calcule le PGCD de deux nombres entiers positifs. La fonction PPCM_TAB calcule le PPCM de plusieurs nombres saisis dans un tableau à une dimension. Ainsi pour calculer le PPCM de A,B,C et D il faudra passer un tableau (array(A,B,C,D)) en paramètre.
Mon algorithme fait appel à des fonctions dont les caractéristiques se trouvent assez facilement sur internet, j'ai tout de même rencontré quelques difficultés à trouver des implémentations en PHP. Ma plus-value réside surtout dans les tests de sécurité (je vérifie que les paramètres sont bien des entiers non nuls) et dans la possibilité de traiter plusieurs nombres et pas seulement deux.
Ma formation scientifique étant assez lointaine je ne sais pas si cet algorithme est particulièrement efficace ni sûr, ce qui est certain c'est qu'il m'a permis de résoudre mes problèmes de temps de traitement. On verra bien les remarques et améliorations qui seront proposées.
[PHP] Implémentation
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86 | function pgcd($nb1,$nb2)
// ******************************************************************************
// * *
// * CALCULE LE PGCD DE DEUX ENTIERS POSITIFS *
// * @$nb1 : entier positif *
// * @$nb2 : entier positif *
// * *
// ******************************************************************************
{
if (($nb1 > 0) AND ($nb2 > 0) AND is_integer($nb1) AND is_integer($nb2))
// Vérification : $nb1 et $nb2 sont des entiers positifs
{
while(($nb1>1) AND ($nb2 != 0)) // Tant que le reste n'est pas nul et le
// diviseur supérieur à 1
{
$reste = $nb1%$nb2; // division entière
$nb1=$nb2;
$nb2=$reste;
}
}
else $nb1 = false; // en cas d'erreur la fonction renvoie false
return $nb1; // retourne le résultat
}
//
// ===============================================================================
//
function ppcm($nb1, $nb2)
// ******************************************************************************
// * *
// * CALCULE LE PPCM DE DEUX ENTIERS POSITIFS *
// * @$nb1 : entier positif *
// * @$nb2 : entier positif *
// * *
// ******************************************************************************
{
if (is_integer($nb1) AND is_integer($nb1)) // Vérification : entiers
{
if (($nb1 > 0) AND ($nb2 >0)) // Vérification : entiers positifs
{
$le_pgcd = pgcd($nb1, $nb2);
if (is_integer($le_pgcd) AND is_integer($le_pgcd))
$le_ppcm = ($nb1 * $nb2) / $le_pgcd;
else $le_ppcm = $nb1 * $nb2; // Sinon le ppcm est égal au produit des 2 nb
}
}
else $le_ppcm = false; // en cas de problème la fonction renvoie faux
return $le_ppcm;
}
//
// ===============================================================================
//
function ppcm_tab($tab_nb)
// ******************************************************************************
// * *
// * CALCULE LE PGCD DE PLUSIEURS ENTIERS POSITIFS *
// * @$tab_nb : tableau à une dimension d'entiers *
// * // // ******************************************************************************
{
sort($tab_nb); // tri du tableau pour réinitialiser les clés
$taille = count($tab_nb);
$retour = false;
if (is_array($tab_nb))
{ // if 1
switch ($taille)
{ // switch 1
case 1 :
if (is_integer($tab_nb[0]) AND ($tab_nb[0] != 0)) $retour = $tab_nb[0]; // s'il n'y a qu'un seul nombre, c'est lui le PPCM !
break;
case 2 :
if (is_integer($tab_nb[0]) AND is_integer($tab_nb[1]) AND ($tab_nb[0] != 0) AND ($tab_nb[1] != 0)) $retour = ppcm($tab_nb[0], $tab_nb[1]);
// s'il y a deux nombres, après avoir vérifié signe et type, c'est simple, on appelle la fonction PPCM
break;
default :
if (is_integer($tab_nb[0]) AND ($tab_nb[0] != 0))
{
$tab_reduit = array_slice($tab_nb, 1);
$retour = ppcm($tab_nb[0],ppcm_tab($tab_reduit));
}
// s'il y a plusieurs nombres, on construit un tableau qui compte une case en moins (la première) et on appelle récursivement la fonction sur le nouveau tableau.
} // switch 1
} // if 1
return $retour;
}
|
|
Inscris-toi au e-camp "Héberge ton jeu Facebook sur Azure" de Microsoft vendredi 25 mai à 13h30 !
yoch
| 
Trouvez une formation
Suggestions
Facebook
Google+