26 не пригодившихся задач за ноябрь-декабрь 2022
В основном, все задачи предполагали реализацию с помощью классов и алгоритмов STL и проверялись в консоли Visual Studio 2019 или 2022 из пустого проекта.
Предыдущая заметка серии была здесь.
Кое-что из написанного вполне может ещё пригодиться, например, СЛАУ 2×2 (#7), Timer (#15), Lagrange (#22), DateInterval (#23), слон и ладья (##24-25).
1. Найти в текстовом файле строку, содержащую наибольшее количество символов '*'. Предполагается, что файл сохранён в однобайтовой кодировке, в текущей при запуске приложения папке под именем 1.txt
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
int main() {
std::ifstream f("1.txt");
if (!f) {
std::cout << "File open error"; return 1;
}
std::string str, result;
int max = 0, cnt = 0;
while (1) {
if (f.eof()) break;
std::getline(f, str);
cnt = std::count(str.begin(), str.end(), '*');
if (cnt > max) {
max = cnt;
result = str;
}
}
f.close();
std::cout << "Cnt=" << max << ", string=\"" << result << "\"";
return 0;
}
2. Допустимые значения времени суток записываются в виде ЧЧММСС, где ЧЧ - двузначное значение часов (от 00 до 23), ММ - минут (от 00 до 59), СС - секунд (от 00 до 59).
Среди чисел ЧЧММСС найти такое, разложение на простые множители которого содержит наибольшее количество сомножителей в произведении.
Если подумать, то ответ совершенно тривиален и без счёта.
#include <iostream>
#include <vector>
#include <string>
std::string padLeft(std::string str, const size_t num, const char paddingChar = ' ') {
//Вернуть строку, дополняющую строку str до длины num символом paddingChar слева
std::string result(str);
if (num > str.size()) result = str.insert(0, num - str.size(), paddingChar);
return result;
}
void primeFactors(unsigned int n, std::vector<int>& r) {
//Пишет простые множители числа n в вектор r
int f = 2;
if (n < 2) r.push_back(n);
else {
while (true) {
if (!(n % f)) {
r.push_back(f);
n /= f;
if (n == 1) return;
}
else f++;
}
}
}
int main() {
std::size_t h,m,s;
std::string str, result;
std::vector <int> pf;
int max = 0, cnt = 0;
for (h = 0; h < 24; h++) {
for (m = 0; m < 60; m++) {
for (s = 0; s < 60; s++) {
str= padLeft(std::to_string(h), 2, '0') +
padLeft(std::to_string(m),2,'0') +
padLeft(std::to_string(s), 2, '0');
unsigned int n=std::stoul(str);
primeFactors(n, pf);
cnt = pf.size();
std::cout << str << ' ' << cnt << std::endl;
if (cnt > max) {
max = cnt;
result = str;
}
pf.clear();
}
}
}
std::cout << "Cnt=" << max << ", string=\"" << result << "\"";
return 0;
}
3. Разложить достаточно большое число на простые множители и показать их. В тему предыдущей задачи, ссылка та же.
#include <iostream>
#include <vector>
void primeFactors(unsigned long int n, std::vector<unsigned long int>& r) {
int f = 2;
if (n == 1) r.push_back(1);
else {
while (true) {
if (!(n % f)) {
r.push_back(f);
n /= f;
if (n == 1) return;
}
else f++;
}
}
}
int main() {
std::vector <unsigned long int> pf;
unsigned long int n = 29102022;
primeFactors(n, pf);
for (auto i = pf.begin(); i != pf.end(); i++) {
std::cout << *i << (i == pf.end() - 1 ? '=' : '*');
}
std::cout << n << std::endl;
return 0;
}
4. Преобразовать std::string в нижний и верхний регистры с учётом локали.
#include <iostream>
#include <string>
#include <algorithm>
#include <clocale>
#include <cctype>
#include <windows.h>
std::string tolower(std::string &str) {
std::transform(str.begin(), str.end(), str.begin(),
[](unsigned char c) { return std::tolower(c); });
return str;
}
std::string toupper(std::string& str) {
std::transform(str.begin(), str.end(), str.begin(),
[](unsigned char c) { return std::toupper(c); });
return str;
}
int main() {
setlocale(LC_ALL, ".1251"); SetConsoleCP(1251); SetConsoleOutputCP(1251);
std::string str("TesT, ТесТИК");
std::cout << tolower(str) << std::endl << toupper(str);
return 0;
}
5. Реализовать простой класс "Календарь на месяц" со свойствами "месяц" и "год" и методами "показать календарь", "задать день недели для 1-го числа месяца". Переопределить в классе оператор += для перехода на указанное количество месяцев.
#include <iostream>
#include <iomanip>
class Calendar { //год >=0, месяц 0..11, день недели 0..6 == вс..сб
size_t m, y, wd;
bool leap() { return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0); }
public:
Calendar (size_t y, size_t m = 0, size_t wd = 0) : y(y), m(m % 12), wd(wd % 7) {}
void startWidth (size_t wd) { this->wd = wd; }
void show() {
int n[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
std::string wds[7] = { "Su", "Mo", "Tu", "We", "Th", "Fr", "Sa" };
if (leap()) n[1] = 29;
std::cout << "Month " << m + 1 << " of " << y << std::endl;
for (size_t d = 1, w = wd; d <= n[m]; d++, w++) {
std::cout << wds[w % 7] << "," << std::setw(2) << std::setfill('0') << d << " ";
}
std::cout << std::endl;
}
void operator += (size_t m0) {
size_t next = y * 12 + m + m0;
y = next / 12;
m = next % 12;
}
};
int main() {
Calendar c(2022, 11 - 1, 2);
c.show();
c += 25;
c.startWidth(0);
c.show();
return 0;
}
6. Реализовать простой класс "Время" со свойствами часы, минуты, секунды. Время хранится в 24-часовом формате. Реализовать в классе метод для отображения времени и оператор +=, прибавляющий к времени указанное количество минут.
#include <iostream>
#include <iomanip>
class Time { //формат 24 часа
int h, m, s;
public:
Time(int h = 0, int m = 0, int s = 0) : h(h % 24), m(m % 60), s(s % 60) {}
void ShowTime() {
std::cout << std::setw(2) << std::setfill('0') << h << ":" <<
std::setw(2) << std::setfill('0') << m << ":" <<
std::setw(2) << std::setfill('0') << s << std::endl;
}
void operator += (int m0) { //время + минуты
int next = h * 3600 + (m + m0) * 60 + s;
h = (next / 3600) % 24;
m = (next / 60) % 60;
s = (next % 60);
}
};
int main() {
Time time(23, 59, 0);
time.ShowTime();
time += 2;
time.ShowTime();
return 0;
}
7. Реализовать простой класс для решения СЛАУ из двух уравнений с двумя неизвестными, предусмотреть методы для вывода и решения СЛАУ, переопределить в классе оператор ! для проверки единственности решения.
Наверное, в данном случае проще всего методом Крамера.
#include <iostream>
class SLAU {
double a, b, c, d, e, f, x, y;
//a*x + b*y = e
//c*x + d*y = f
double det() { return a * d - b * c; }
public:
SLAU(double a, double b, double e, double c, double d, double f) :
a(a), b(b), e(e), c(c), d(d), f(f) {}
void show() {
std::cout << std::endl << a << "*x+" << b << "*y=" << e <<
std::endl << c << "*x+" << d << "*y=" << f << std::endl;
}
bool solve() {
if (!(*this)) {
x = (e * d - b * f) / det();
y = (a * f - e * c) / det();
}
return !(*this);
}
bool operator ! () { return det() != 0; }
void printsolve() {
std::cout << x << ", " << y << std::endl;
}
void checksolve() {
std::cout << a * x + b * y - e << ", " << c * x + d * y - f << std::endl;
}
};
int main() {
SLAU a(1, 2, 3, 4, 5, 6); //-1, 2
//SLAU a(1, 2, 4, 2, 4, 6); //не решается, определитель равен 0
a.show();
std::cout << "Solvable: " << !a << std::endl;
if (!a) {
a.solve();
a.printsolve();
a.checksolve();
}
return 0;
}
8. Найти сумму всех цифр в векторе натуральных чисел.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int main() {
std::vector <long unsigned int> v{1234,5678,9}, r;
std::for_each(v.begin(), v.end(),
[](long unsigned int &i) {
int sum = 0; while (i) { sum += i % 10; i /= 10; }
i = sum;
}
);
long unsigned int sum = std::accumulate(v.begin(), v.end(), 0,
[](int x, const long unsigned int y) { return x + y; }
);
std::cout << "Sum of digits = " << sum;
return 0;
}
9. Из вектора натуральных значений source получить вектор target, содержащий квадраты значений исходного вектора.
#include <vector>
#include <iostream>
#include <numeric> // iota
#include <algorithm> // for_each, transform
using namespace std;
int main() {
vector<int> source(100);
iota(source.begin(), source.end(), 1); // v = [1, 2, ..., 100]
vector<int> target(source.size());
transform(source.begin(), source.end(), target.begin(),
[](int& a) {return a * a; }); // v = [1, 4, ..., 10000]
for_each(target.begin(), target.end(), [](int a) {cout << a << ' '; });
return 0;
}
10. Проверить содержит ли множество вещественных значений хотя бы один отрицательный элемент.
#include <iostream>
#include <set>
#include <algorithm>
int main() {
std::set<double> s{ 1.1, -0.9, 2.4, 10.1, 3.1415 };
bool test = std::any_of(s.begin(), s.end(), [](double x) {return x < 0; });
std::cout << test;
return 0;
}
Строчка вызова алгоритма не поменяется, если вместо set будет использован другой контейнер, например, list, vector, array или unordered_set.
11. Подсчитать количество вхождений строки в вектор строк и удалить найденные записи (с помощью алгоритмов STL).
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<std::string> v = { "fgh", "abc", "de", "123", "abc" };
size_t test = std::count(v.begin(), v.end(), "abc");
std::cout << test << std::endl; //2
//Удалим найденные записи:
v.erase(std::remove(v.begin(), v.end(), "abc"), v.end());
copy(v.begin(), v.end(), std::ostream_iterator<std::string>(std::cout, " "));
return 0;
}
12. Подсчитать в векторе строк количество вхождений строки с однобайтовой кириллицей независимо от регистра символов (с помощью алгоритмов STL).
Мы применили здесь две вложенных лямбды.
#include <iostream>
#include <vector>
#include <algorithm>
#include <clocale>
#include <cctype>
#include <Windows.h>
int main() {
setlocale(LC_ALL, ".1251"); SetConsoleCP(1251); SetConsoleOutputCP(1251);
std::vector<std::string> v = { "ПРИВЕТ", "Abc", "привет", "123", "прив" };
size_t test = std::count_if(v.begin(), v.end(),
[](std::string str) {
std::transform(str.begin(), str.end(), str.begin(),
[](unsigned char c) { return std::tolower(c); });
return str == "привет";
}
);
std::cout << test << std::endl; //2
copy(v.begin(), v.end(), std::ostream_iterator<std::string>(std::cout, " "));
return 0;
}
13. Обменять местами все значения в двух контейнерах std::vector (с помощью алгоритмов STL).
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main() {
std::vector <int>v{1,2,3},b{4,5,6};
v.swap(b);
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
std::copy(b.begin(), b.end(), std::ostream_iterator<int>(std::cout, " "));
return 0;
}
14. Обменять местами все вхождения максимального и минимального элементов в заданном векторе целых чисел (с помощью алгоритмов STL).
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector <int> v = { 12,23,-10,45,32,17,-10,45 };
std::vector<int>::const_iterator
max = std::max_element(v.begin(),v.end()),
min = std::min_element(v.begin(), v.end());
std::cout << *min << ", " << *max << std::endl;
std::vector <int> r(v.size());
std::transform (v.begin(), v.end(), r.begin(),
[min, max](int i) { return (i == *min ? *max : (i == *max ? *min : i)); }
//1. Так лямбда может выполнить захват внешней переменной
//2. Результаты нужно писать в новый контейнер достаточной размерности
);
copy(r.begin(), r.end(), std::ostream_iterator<int>(std::cout, " "));
return 0;
}
15. На основе библиотеки chrono реализовать простейший класс Timer, позволяющий измерить время выполнения участка кода.
Мы измеряем на 10 миллионах тестов время выполнения цикла с составным и вложенными условными операторами, решающими одну и ту же учебную задачу (определение номера координатной четверти для точки на плоскости или 0, если точка находится хотя бы на одной из осей координат).
#include <iostream>
#include <chrono>
#include <random>
class Timer {
std::chrono::time_point <std::chrono::high_resolution_clock> start, stop;
double duration;
public:
Timer() { this->start = std::chrono::high_resolution_clock::now(); }
void Start() { this->start = std::chrono::high_resolution_clock::now(); }
double Stop() {
stop = std::chrono::high_resolution_clock::now();
duration = std::chrono::duration<double>(stop - start).count();
return duration;
}
};
int main() {
const size_t n = 1e7; //10 000 000 тестов, поэтому в "куче", стек переполнится
double* x = new double[n];
double* y = new double[n];
if (!x || !y) {
std::cout << "No memory";
return -1;
}
//Заполняем случайными равномерно распределёнными точками
std::default_random_engine generator;
std::uniform_real_distribution<double> distribution(-100., 100.);
for (size_t i = 0; i < n; ++i) {
x[i] = distribution(generator);
y[i] = distribution(generator);
}
double xx, yy;
size_t num = 0;
//Измеряем только время выполнения циклов
Timer* t = new Timer();
for (size_t i = 0; i < n; i++) { //Составной условный оператор
xx = x[i]; yy = y[i];
if (xx == 0 || yy == 0) num = 0;
else if (xx > 0 && yy > 0) num = 1;
else if (xx < 0 && yy > 0) num = 2;
else if (xx < 0 && yy < 0) num = 3;
else num = 4;
}
double t1 = t->Stop();
std::cout << t1 << std::endl;
t->Start();
for (size_t i = 0; i < n; i++) { //Вложенные условные операторы
xx = x[i]; yy = y[i];
if (xx == 0 || yy == 0) num = 0;
else {
if (xx > 0) {
if (yy > 0) num = 1;
else num = 4;
}
else {
if (yy > 0) num = 2;
else num = 3;
}
}
}
double t2 = t->Stop();
std::cout << t2 << std::endl;
return 0;
}
16. Для каждого из имён файлов, представленных строками std::string, указать, состоит ли имя файла только из маленьких латинских букв с типом .txt
Такие вещи, если речь не идёт о заведомо огромных наборах данных, удобно делать с помощью регулярных выражений.
#include <iostream>
#include <string>
#include <regex>
int main() {
std::string fnames[] = { "foo.txt", "bar.txt", "test", "a0.txt", "AAA.txt", "abc.dat"};
std::regex txt_regex("[a-z]+\\.txt");
for (const auto& fname : fnames)
std::cout << fname << ": " << std::regex_match(fname, txt_regex) << std::endl;
return 0;
}
17. Для задачи 16 извлечь найденные шаблоны из строк с именами файлов.
#include <iostream>
#include <string>
#include <regex>
int main() {
std::string fnames[] = { "foo.txt", "bar.txt", "test", "a0.txt", "AAA.txt" };
std::regex base_regex("([a-z]+)\\.txt");
std::smatch base_match;
for (const auto& fname : fnames) {
if (std::regex_match(fname, base_match, base_regex)) {
/* первый элемент std::smatch - вхождение всей строки,
второй - вхождение выражения в первых круглых скобках и т.д. */
if (base_match.size() == 2) {
std::cout << "sub-match[0]: " << base_match[0].str() << std::endl;
std::string base = base_match[1].str();
std::cout << fname << " sub-match[1]: " << base << std::endl;
}
}
}
return 0;
}
18. С помощью регулярного выражения удалить из строки символы, не являющиеся буквами, цифрами или разделителями.
#include <iostream>
#include <string>
#include <regex>
int main() {
std::string s("Hello, hello-hello, i'm crying o-lo-lo!");
std::cout <<
std::regex_replace(s, std::regex(R"([^\w\d\s])"), "");
return 0;
}
19. Описать класс «файл» с проверкой состояния файла и методами для чтения скалярной величины и строки std::string.
Пример содержимого файла data.txt:
123 stringstring 5.5
#include <iostream>
#include <fstream>
class File {
std::string Name;
int mode;
std::ifstream f;
public:
File(std::string Name) : Name(Name) {
f.open(Name);
mode = !f ? 0 : 1;
}
bool Readable() { return mode; }
template <typename T> T Read() {
T data;
f >> data;
return (T)data;
}
std::string ReadString() {
std::string data;
f >> data;
if (f.good()) return data;
else return "";
}
};
int main() {
File f("data.txt"); //файл из текущей папки
if (f.Readable()) {
std::cout << f.Read<int>() << std::endl;
std::cout << f.ReadString() << std::endl;
std::cout << f.Read<double>() << std::endl;
return 0;
}
}
20. Составим список всех слов файла (исключая «тонкие» операции по фильтрации знаков препинания и т.п.) и отсортируем его по частоте встречаемости слов (слова с одинаковой частотой отсортируем между собой по алфавиту).
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <windows.h>
//Метод для сортировки map по значениям
std::vector <std::pair<std::string, size_t>> mysort
(std::map <std::string, size_t>& M) {
std::vector <std::pair<std::string, size_t>> A;
for (auto& it : M) A.push_back(it); //C++14 и выше
sort(A.begin(), A.end(),
[](std::pair<std::string, size_t>&a,
std::pair<std::string, size_t> &b) {
return a.second == b.second ?
a.first < b.first : a.second < b.second;
}
);
return A;
}
int main() {
setlocale(LC_ALL, ".1251");
SetConsoleCP(1251); SetConsoleOutputCP(1251);
std::ifstream file("data.txt");
if (!file) {
std::cout << "Не могу открыть файл для чтения!";
return 1;
}
std::map <std::string, size_t> words;
std::string word;
while (file >> word) {
//возможно, отфильтровать word от знаков препинания,
//привести к одному регистру символов и т.п.
words[word]++;
}
file.close();
//for (auto it = words.begin(); it != words.end(); ++it)
// std::cout << it->first << ": " << it->second << std::endl;
//Требуется отсортировать map по значениям, что "напрямую"
//не реализуется
std::vector <std::pair<std::string, size_t>> A =
mysort(words);
for (auto& it : A) std::cout << it.first << "\t" <<
it.second << std::endl;
return 0;
}
21. Прочитаем файл в вектор строк и удалим пустые (или состоящие только из разделителей) строки.
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <windows.h>
int main() {
setlocale(LC_ALL, ".1251");
SetConsoleCP(1251); SetConsoleOutputCP(1251);
std::ifstream file("data.txt");
if (!file) {
std::cout << "Не могу открыть файл для чтения!";
return 1;
}
std::string str;
std::vector <std::string> v;
while (!file.eof()) {
getline(file,str);
v.push_back(str);
}
file.close();
std::cout << v.size() << " line(s)" << std::endl;
v.erase(std::remove_if(v.begin(),v.end(),
[](const std::string s) {
return s.find_first_not_of(" \t") == std::string::npos;
}
), v.end());
for (const auto& s : v) std::cout << s << std::endl;
std::cout << v.size() << " line(s)" << std::endl;
return 0;
}
22. Реализуем класс для полинома Лагранжа (как пример счётной задачи).
#include <iostream>
#include <vector>
#include <algorithm>
class Lagrange {
std::vector <std::pair<double, double>> v;
size_t n;
std::vector <std::vector <double>> a;
//разности x[i]-x[j], чтобы не считать их для каждой новой точки
public:
Lagrange(std::vector <std::pair<double, double>> v) {
size_t n = v.size();
if (n < 2) throw "Bad data size";
sort(v.begin(), v.end(),
[](const std::pair<double, double>& a, const std::pair<double, double>& b) {
return a.first < b.first;
}
);
//А ещё стоило бы "склеить" возможные одинаковые значения x
this->n = n;
this->v = v;
for (size_t i = 0; i < n; i++) { //A[i,j]=x[i]-x[j]
a.push_back(std::vector<double>());
for (size_t j = 0; j < n; j++)
a.back().push_back(v[i].first - v[j].first);
}
}
double Calc(double x) {
double q = 0, num, den; //значение, числитель, знаменатель
for (size_t i = 0; i < n; i++) {
num = den = 1.;
for (size_t j = 0; j < n; j++) {
if (j != i) {
num *= (x - v[j].first);
den *= a[i][j];
}
}
q += v[i].second * num / den;
}
return q;
}
};
int main() {
std::vector <std::pair<double, double>> v;
v.push_back(std::make_pair<double, double>(1, 0));
v.push_back(std::make_pair<double, double>(2, 5));
v.push_back(std::make_pair<double, double>(3, -4));
v.push_back(std::make_pair<double, double>(5, 1.5));
v.push_back(std::make_pair<double, double>(4, 2));
Lagrange* L;
try {
L = new Lagrange(v);
}
catch (const char* msg) {
std::cout << msg << std::endl;
return 1;
}
for (double x = 1.; x <= 5.; x += 0.25) {
std::cout << x << "\t" << L->Calc(x) << std::endl;
}
return 0;
}
23. Реализовать простой класс DateInterval для последовательного перебора календарных дат из заданного диапазона.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <ctime>
class DateInterval {
public:
static const size_t ONEDAY = 86400;
static std::string makeDateString(time_t t) {
struct tm* tm = localtime(&t);
std::stringstream stream;
stream << std::setfill('0') << std::setw(2) << tm->tm_mday << '.'
<< std::setfill('0') << std::setw(2) << (tm->tm_mon + 1) << '.'
<< std::setw(4) << (tm->tm_year + 1900);
return stream.str();
}
static time_t getDate(size_t day, size_t month, size_t year) {
struct tm tm = { 0 };
tm.tm_mday = day;
tm.tm_mon = month - 1;
tm.tm_year = year - 1900;
return mktime(&tm);
}
static bool correctDate(size_t day, size_t month, size_t year) {
size_t days[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) days[1] = 29;
if (year < 1 || day < 1 || day > days[month - 1] || month < 1 || month > 12)
return false;
return true;
} //В реальности "переход через месяц" работает, например, 32.03 == 01.04
};
int main() {
time_t start = DateInterval::getDate(27, 2, 2022);
time_t end = DateInterval::getDate(31, 3, 2022);
for (time_t t = start; t <= end; t += DateInterval::ONEDAY) {
std::cout << DateInterval::makeDateString(t) << std::endl;
}
return 0;
}
24. По заданным координатам слона на пустой шахматной доске найти количество полей, на которые он может пойти.
Считать, что строки и столбцы доски занумерованы сверху вниз и слева направо соответственно, 1, 2, ..., 8.
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
int main() {
size_t h[8][8];
for (size_t x = 1; x < 9; x++)
for (size_t y = 1; y < 9; y++)
h[y-1][x-1] = 14 - max(x, y) + min(x, y) - max(y, 9 - x) + min(y, 9 - x);
for (size_t y = 0; y < 8; y++) {
cout << endl;
for (size_t x = 0; x < 8; x++)
cout << setw(3) << h[y][x];
}
return 0;
}
Эта задача уже была поставлена вот здесь. Решим её по-другому, применяя только std::min и для доски произвольного размера n×n.
#include <iostream>
#include <iomanip>
#include <algorithm>
int main() {
const size_t n = 5;
for (size_t y = 1; y < n + 1; y++) {
for (size_t x = 1; x < n + 1; x++) {
size_t dx = std::min(x - 1, n - x),
dy = std::min(y - 1, n - y);
size_t f = (n - 1) + 2 * std::min(dx, dy);
std::cout << std::setw(3) << f;
}
std::cout << std::endl;
}
return 0;
}
25. Расставить на шахматной доске размерностью n×n k≤n ладей так, чтобы они не угрожали друг другу.
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <vector>
#include <random>
std::vector <size_t> gen(std::vector <size_t> x, const size_t k) {
//k случайных перемешанных значений из 1,2,...,n, n == x.size()
std::iota(x.begin(), x.begin() + x.size(), 1);
std::random_device r;
std::default_random_engine g(r());
std::shuffle(x.begin(), x.begin() + x.size(), g);
return std::vector <size_t>(x.begin(), x.begin() + k);
}
int main() {
const size_t n = 8, k = 6;
std::vector <size_t> x(n), y(n);
x = gen(x, k);
y = gen(y, k);
std::vector <std::pair<size_t, size_t>> rooks;
for (size_t i = 0 ; i < x.size(); i++)
rooks.push_back(std::make_pair(x[i],y[i]));
std::sort(rooks.begin(), rooks.end(),
[](std::pair<size_t, size_t>& a, std::pair<size_t, size_t>& b) {
return a.first == b.first ? a.second < b.second : a.first < b.first;
}
);
char board[n][n]; //???
for (size_t r = 1; r <= n; r++) {
for (size_t c = 1; c <= n; c++) {
std::pair<size_t, size_t> f = std::make_pair(c, r);
auto it = std::find_if(rooks.begin(), rooks.end(),
[f](std::pair<size_t, size_t> el) {
return el.first == f.first && el.second == f.second;
}
);
char ch = (it != rooks.end() ? '*' : '0');
board[r-1][c-1] = ch;
std::cout << std::setw(2) << ch;
}
std::cout << std::endl;
}
return 0;
}
Сколько чёрных ладей требуется на доске n×n, чтобы гарантированно поймать белую ладью при её ходе? На первый взгляд кажется, что n-1 для n = 1, 2, 3, ... (на доске 1×1 действительно нужно ноль, так как ладья самопоймана), а n-2 никогда не ловят, но так ли это? :)
26. Найти все даты 21 века, "число судьбы" которых (сумма сумм цифр дня, месяца и года для записи ДД.ММ.ГГГГ) совпадает с номером дня месяца.
Пример нужной даты: 08.12.2022, 8+1+2+2*3=17, 1+7=8.
Код легко построить на задачах 23 и 8.
Тем не менее, ясно также, что искомые суммы могут иметь значения только от 1 до 9 включительно и нужные дни будут идти циклами по 9, иногда дважды в году, например, 01-09.03.2022 и 01-09.12.2022, а иногда только раз, например, 01-09.04.2021. Было бы интересно, основываясь на признаках делимости, вывести общую формулу, но мы в этом учебном коде ограничимся перебором. Кстати, нашлось всего 33 года, в которых искомые цепочки дат встречаются дважды и 67 лет (помечены звёздочками справа в приложенном файле), где нужная цепочка всего одна.
Аналогично, незачем считать "вручную" количество дней в веке, поскольку оно равно 365,25*100 - 1 = 36524 (так как 2100-й год - не високосный), мы считаем значение all просто для проверки. Ответ = 1197 дат из 36524.
Максимальное "число судьбы" для нашего диапазона дат равно 40, очевидно, оно будет у даты 29.09.2099, но за две итерации не найдётся отнюдь не оно, а суммы цифр, равные 19, 28-29, 37-39.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <numeric>
#include <ctime>
#include <cctype>
class DateInterval {
public:
static const size_t ONEDAY = 86400;
static std::string makeDateString(time_t t) {
struct tm* tm = localtime(&t);
std::stringstream stream;
stream << std::setfill('0') << std::setw(2) << tm->tm_mday << '.'
<< std::setfill('0') << std::setw(2) << (tm->tm_mon + 1) << '.'
<< std::setw(4) << (tm->tm_year + 1900);
return stream.str();
}
static time_t getDate(size_t day, size_t month, size_t year) {
struct tm tm = { 0 };
tm.tm_mday = day;
tm.tm_mon = month - 1;
tm.tm_year = year - 1900;
return mktime(&tm);
}
static bool correctDate(size_t day, size_t month, size_t year) {
size_t days[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) days[1] = 29;
if (year < 1 || day < 1 || day > days[month - 1] || month < 1 || month > 12)
return false;
return true;
}
};
int main() {
time_t start = DateInterval::getDate(1, 1, 2001);
time_t end = DateInterval::getDate(31, 12, 2100);
std::string dt, dt0;
size_t sz, cnt = 0, all = 0;
for (time_t t = start; t <= end; t += DateInterval::ONEDAY) {
dt = DateInterval::makeDateString(t);
dt0 = dt; //так как dt "испортится" при поиске суммы цифр
int day = std::stoi(dt.substr(0, 2), &sz);
int sum = 0;
do {
sum = std::accumulate(dt.begin(), dt.end(), 0,
[](int x, const int y) { return x + (isdigit(y)?y-48:0); });
if (sum > 9) dt = std::to_string(sum);
else break;
} while (1);
if (sum == day) {
std::cout << dt0 << " ";
cnt++;
}
all++;
}
std::cout << std::endl << cnt << " date(s) from " << all;
return 0;
}
Открыть файл fatedays.txt с результатами счёта этой задачи (13 Кб)
14.12.2022, 02:45 [253 просмотра]