Bonjour a tous, je deviens fou avec ce probleme, je n'arrive vraiment pas a voir d'ou ca peut venir...
Quelqu'un pourrait il m'aider svp?
Merci d'avance

Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
 
#include <iostream>
#include "MyHashSet.h"
 
bool Included (const MyHashSet *setCover, const MyHashSet &W);
int MySetCover(const MyHashSet &W, MyHashSet setsArr[], int arrSize);
bool AllVisited(MyHashSet setsArr[], int arrSize);
 
// Creates a set cover and return the minimum number of subsets including the
// whole W.
// W is the set representing the world of elements.
// Sets arr are a lot of hash sets.
// Arrsize is the size of the setsArr.
int MySetCover(const MyHashSet &W, MyHashSet setsArr[], int arrSize)
{
    int minimalSoFar=0;
    int currentSize=0;
    // Returns -1 if there is not a set cover.
    int numberOfSets=0;
 
    // We initialize it 100 so that it will work for the first iteration.
    int minimumSize=100;
    MyHashSet* setCover = new MyHashSet;
    while (!Included(setCover, W))
    {
        // If we already visited all of setArr, there is no set cover.
        if (AllVisited(setsArr, arrSize))
            return -1;
 
        // 1/ Looking for the Ui that gets most elements inside all that were
        // not taken in W until A includes W.
        // ie : the Ui that makes the set W.reduce(A.union(Ui)) minimal.
        for (int i=0; i<arrSize; i++)
        {
            if (setsArr[i].IsVisited())
                continue;
            MyHashSet* tempUnion = setCover->Union(setsArr[i]);
            MyHashSet* toAdd = W.Reduce(*tempUnion);
            currentSize = toAdd->Size();
            if (currentSize < minimumSize)
            {
                minimalSoFar = i;
                minimumSize = currentSize;
            }
            delete tempUnion;
            delete toAdd;
        }
 
        // 2/ Adding the best candidate so far and setting visited to true.
        MyHashSet* setCoverUnion = setCover->Union(setsArr[minimalSoFar]);
        delete setCover;
        MyHashSet* setCover = new MyHashSet;
 
        // 3/ Copy it to the "final set cover".
        for (int i=0; i<HASH_SIZE; i++)
        {
            MyLinkedList* ll = setCoverUnion->GetLinkedList(i);
            MyLinkedList::Iterator* it1 = new MyLinkedList::Iterator(ll);
            while (it1->HasNext())
            {
                setCover->Add(it1->Next());
            }
            delete ll;
            delete it1;
        }
 
        // 4/ Delete the temporary setCoverUnion.
        delete setCoverUnion;
        // Attention ICI.
        setsArr[minimalSoFar].SetVisited();
        numberOfSets++;
        minimalSoFar=0;
        minimumSize = 100;
    }
    delete setCover;
    return numberOfSets;
}
 
// Check if all the subsets have been visited return true if yes.
bool AllVisited(MyHashSet setsArr[], int arrSize)
{
    for (int i=0; i<arrSize; i++)
    {
        if (!setsArr[i].IsVisited())
            return false;
    }
    return true;
}
 
// Returns true iff W is included in A.
bool Included (const MyHashSet *setCover, const MyHashSet &W)
{
    // We need to check that everything that's inside W is also in setCover.
    for (int i=0; i<HASH_SIZE; i++)
    {
        MyLinkedList* ll = W.GetLinkedList(i);
        MyLinkedList::Iterator it(ll);
        while (it.HasNext())
        {
            // Adding element of current list.
            if (!setCover->InHashSet(it.Next()))
            {
                delete ll;
                return false;
            }
        }
        delete ll;
    }
    // W is included in A.
    return true;
}