БлогNot. 26 не пригодившихся задач за ноябрь-декабрь 2022

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 [368 просмотров]


теги: c++ учебное список алгоритм

К этой статье пока нет комментариев, Ваш будет первым