samedi 27 décembre 2014

`std::set_intersection` elementary usage

I practice the c++ standard library. Here is one problem I have with the usage of set_intersection:


I try to solve the problem 45 of project Euler:




Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, ...
It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.


here is my tricks-free code for this:



using bint = unsigned long long;

auto pb045()->bint
{

for (auto max_nb = 1024;; max_nb = max_nb << 1) {

auto tris = std::vector<bint>{};
tris.reserve(max_nb);

auto pentas = std::vector<bint>{};
pentas.reserve(max_nb);

auto hexas = std::vector<bint>{};
hexas.reserve(max_nb);
for (auto i = 0; i < max_nb; i++) {
tris.push_back(i * (i + 1) / 2);
pentas.push_back(i * (3 * i - 1) / 2);
hexas.push_back(i * (2 * i - 1));
}

auto intersection1 = std::vector<bint>(max_nb);

std::sort(tris.begin(), tris.end());
std::sort(hexas.begin(), hexas.end());
std::sort(pentas.begin(), pentas.end());

auto
begin = intersection1.begin(),
end =
std::set_intersection(hexas.begin(), hexas.end(),
pentas.begin(), pentas.end(),
intersection1.begin());

auto intersection = std::vector<bint>(end - begin);

std::set_intersection(begin, end,
tris.begin(), tris.end(),
intersection.begin());

if (intersection.size() > 3) {
// [0] -> 0
// [1] -> 1
_ASSERT(intersection[2] == 40755);
return intersection[3];
}
}


here:



  • the algorithm does not gives the good solution

  • if I comment the sort lines, it crashes (on MS VC++) with the message sequence not ordered in debug mode, and runs for long in release mode (but the numbers are inserted in increasing order, so the sort is useless).


I thinks that I miss something here.


Aucun commentaire:

Enregistrer un commentaire