Az előadás Solver osztálya letölthető erről a linkről:
solver.cpp, template-esítve.
Emlékeztető: ez arra képes, hogy egy érték-n-esekből álló
halmazból kiválassza azokat az elemeket, amelyek bizonyos feltételeknek megfelelnek. Például:
int main() {
Solver<int> s;
/* változók hozzáadása */
auto a = s.add_variable({1, 2, 3, 4, 5});
auto b = s.add_variable({1, 2, 3, 4, 5});
/* feltételek hozzáadása */
s.add_constraint([=] { return a() % 2 == 0; });
s.add_constraint([=] { return b() > a(); });
/* keresés és megoldások kiírása */
s.solve([=] {
std::cout << "a=" << a() << ", b=" << b() << std::endl;
});
}Ebben a kódban megkeressük azokat az (a,b)∈{1,2,3,4,5}² számpárokat, amelyeknél a páros, és b>a.
A Solver a sablonparaméterében megadott típusú értékekkel dolgozik. Az add_variable() ilyen értékekből álló
vektort vesz át paraméterként. A hozzáadott feltételeknek pedig igaz értékkel kell visszatérniük, ha teljesülnek.
Oldd meg az osztály használatával az alábbi feladatokat!
Pitagoraszi számhármasok
Melyek a 100-nál nem nagyobb számokból álló pitagoraszi számhármasok? (Tehát a<b<c és a2+b2=c2.) Ehhez érdemes egy külön programrésszel feltölteni egy vektort a számokkal.
Megoldás
int main() {
Solver<int> s;
std::vector<int> v;
for (int i = 1; i <= 100; ++i)
v.push_back(i);
auto a = s.add_variable(v);
auto b = s.add_variable(v);
auto c = s.add_variable(v);
s.add_constraint([=] { return a() < b(); });
s.add_constraint([=] { return b() < c(); });
s.add_constraint([=] { return a()*a() + b()*b() == c()*c(); });
s.solve([=] {
std::cout << a() << ' ' << b() << ' ' << c() << std::endl;
});
}Írj olyan lambda kifejezést, amelyik nem kiírja, csak megszámolja, hány ilyen számhármas van! (52 a megoldás.)
Megoldás
/* a számlálót referencia szerint kell! */
int count = 0;
s.solve([&count] { ++count; });
std::cout << count << " megoldás." << std::endl;Euler feladata
Egy gazda sertést, kecskét és juhot vásárolt, összesen 100 állatot, pontosan 600 aranyért. A sertés darabja 21 arany, a kecskéé 8 arany, a juhoké 3 arany. Hány darabot vett mindegyik állatból? (4 megoldás van, pl. 15, 6, 79 és 0, 60, 40.)
Megoldás
int main() {
Solver<int> solver;
std::vector<int> v;
for (int i = 0; i <= 100; ++i) /* 0 is lehet! */
v.push_back(i);
auto s = solver.add_variable(v);
auto k = solver.add_variable(v);
auto j = solver.add_variable(v);
solver.add_constraint([=] { return s() + k() + j() == 100; });
solver.add_constraint([=] { return s()*21 + k()*8 + j()*3 == 600; });
solver.solve([=] {
std::cout << s() << ' ' << k() << ' ' << j() << std::endl;
});
}
Térkép
Adott a képen látható térkép. Színezzük ki ezt kék, sárga, piros színekkel úgy, hogy a szomszédos országok különféle
színűek legyenek, és ha két ország határán < jel van, akkor a két szín ábécé-rendben megadott sorrendben kövesse
egymást! (Megoldás: A: sárga, B: piros, C: kék, D: kék, E: piros.)
Megoldás
int main() {
Solver<std::string> s;
auto a = s.add_variable({"kek", "sarga", "piros"});
auto b = s.add_variable({"kek", "sarga", "piros"});
auto c = s.add_variable({"kek", "sarga", "piros"});
auto d = s.add_variable({"kek", "sarga", "piros"});
auto e = s.add_variable({"kek", "sarga", "piros"});
/* a középső ország szomszédai */
s.add_constraint([=] { return a() != b() && a() != c() && a() != d() && a() != e(); });
/* körben */
s.add_constraint([=] { return b() != c() && c() != e() && e() != d() && d() != b(); });
/* a és b ábécésen */
s.add_constraint([=] { return a() > b(); });
/* d és e */
s.add_constraint([=] { return e() > d(); });
s.solve([=] {
std::cout << "A: " << a() << std::endl;
std::cout << "B: " << b() << std::endl;
std::cout << "C: " << c() << std::endl;
std::cout << "D: " << d() << std::endl;
std::cout << "E: " << e() << std::endl;
});
}