Comme d’hab je raconte nimp, O(n) est possible seulement avec deux elements, la je suis dans quelque chose de vraiment bon, mais au pire en O(n^2).
C’est un backtracking tout simple, d’ailleurs ca m’etonnerait pas que ton prof s’attende a truc de ce genre. J’espere avoir bien compris l’ennonce…
En gros le but c’est de construire un tableau avec les occurences possibles, et parcourir les pioches possible jusqu’a trouver la bonne. Durant le chemin les nombres tires sont memorises pour les afficher a la fin.
[code]#include
#include
#include
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include
#include
using namespace std;
using namespace boost::lambda;
int ExtractNextAvailableValue(std::vector &vec, int iStart)
{
int iValue = 0;
for (std::vector::size_type i = iStart; (i < vec.size()) && (iValue == 0); ++i)
{
if (vec[i] > 0)
{
iValue = i;
–vec[i];
}
}
return iValue;
}
template <int _MaxVal, int _MaxDepth>
bool backtrack(std::vector &vec, int iSum, int iDepth, std::list &listPath)
{
if (iDepth >= _MaxDepth)
return false;
// optimiz0r pour la derniere profondeur
if (iDepth == (_MaxDepth - 1))
{
if (iSum > _MaxVal)
return false; // rien a tenter si notre somme est toujours superieure a _MaxVal
// il faut au moins une occurence de iSum
if (vec[iSum] > 0)
{
listPath.push_back(iSum);
return true;
}
else
{
return false;
}
}
for(int i = 1; i < vec.size(); ++i)
{
int iValue = ExtractNextAvailableValue(vec, i);
if (!iValue)
return false;
// no time wasted on values too great
if (iValue < iSum)
{
listPath.push_back(iValue);
if (backtrack<_MaxVal, _MaxDepth>(vec, iSum - iValue, iDepth + 1, listPath))
return true;
listPath.pop_back();
}
// put back
vec[iValue]++;
}
return false;
}
bool WillThereBeCake(int iSum, vector &Ingredients, list &listPath)
{
// on veut savoir si la combinaison est possible et presente…
// donc deja on extrait les occurences de chaque
vector Occurences(10);
int & (vector::* pf) (vector::size_type ) = &vector::at;
// O(n)
for_each(Ingredients.begin(), Ingredients.end(), ++bind(pf, &Occurences, _1));
// :o c’est beaucoup plus simple maintenant…
return backtrack<9, 3>(Occurences, iSum, 0, listPath);
}
int main(int argc, char **argv)
{
vector Recipee(10);
int i = 0;
generate(Recipee.begin(), Recipee.end(), var(i)++);
// there will be cake
vector Ingredients(30);
generate(Ingredients.begin(), Ingredients.end(), rand);
transform(Ingredients.begin(), Ingredients.end(), Ingredients.begin(), (_1 % 9) + 1);
list listPath;
cout << WillThereBeCake(15, Ingredients, listPath) << endl;
for_each(listPath.begin(), listPath.end(), cout << _1 << ‘.’);
cout << endl;
}[/code]
. Je me doute qu’il faut des boucles (for probablement) imbriquées, mais ça s’arrête là.
.
.
.