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 messagesequence not ordered
in debug mode, and runs for long in release mode (but the numbers are inserted in increasing order, so thesort
is useless).
I thinks that I miss something here.
Aucun commentaire:
Enregistrer un commentaire