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

12 не пригодившихся задач за декабрь 2021

Количество задач в этой уже ставшей традиционной рубрике, увы, почти сохраняет стабильность, но логичнее опубликовать в конце очередного учебного периода, чтобы не протухали.

Все программы выполнялись в консоли актуальной сборки Visual Studio 2019, для поиска на странице нужных слов нажимайте комбинацию клавиш Ctrl+F в браузере.

Пригодиться могут пример на filesystem (4), разбор формата std::string с помощью регулярного выражения (5), шаблонные функции для матрицы (6), простая консольная игра (8).

1. Посекундно меняем в цикле цвет консоли до нажатия клавиши.

#include <iostream>
#include <cstdlib>  //system() 
#include <thread>   //sleep_for()
#include <conio.h>  //_kbhit()
using namespace std;
using namespace chrono_literals;

int main() {
 system("cls");
 while (!_kbhit()) {
  system("color 17");
  this_thread::sleep_for(1s);
  system("color 27");
  this_thread::sleep_for(1s);
 }
 system("color 07");
 return 0;
}

2. Определить, сколько целых чисел начиная с единицы нужно сложить, чтобы сумма получилась больше sum.

Решаем формулой O(1) и проверяем "вручную".

#include <iostream>
#include <cmath>

int main() {
 int sum = 100;
 std::cout << ceil((-1 + sqrt(1 + (8 * sum))) / 2) << std::endl;
 int sum0 = 0, n = 0;
 do {
  sum0 += ++n;
 } while (sum0 <= sum);
 std::cout << "Checking: " << sum0 << " in " << n << " step(s)";
 return 0;
}

3. Ввести из консоли через cin натуральное значение n так, чтобы программа не "падала" при неправильном вводе.

Конечно, уже было, вот один из множества возможных простых вариантов.

#include <iostream>

int getN() {
 int val = 0;
 std::cout << std::endl << "Val=";
 while (!(std::cin >> val) || val < 1) {
  std::cin.clear();
  while (std::cin.get() != '\n') continue;
  std::cout << "Error, please, type it again" << std::endl;
 }
 return val;
}

int main(void) {
 int n = getN();
 std::cout << "N=" << n;
 return 0;
}

4. Создать случайное (в разумных пределах) количество папок и файлов во временном каталоге, названия файлов и папок также случайны и уникальны. Вывести список полученных файлов и папок.

Используем актуальные начиная со стандарта C++ 17 средства filesystem.

//Включить в свойствах проекта поддержку стандарта C++17:
//Project, Properties, C/C++, Language, C++ Language Standard, ISO C++17 (/std:c++17)
#define _CRT_SECURE_NO_WARNINGS /* std::tmpnam */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <filesystem>
#include <ctime>
#include <windows.h> /* SetConsoleCP, SetConsoleOutputCP */
namespace fs = std::filesystem;

int main() {
 SetConsoleCP(1251); SetConsoleOutputCP(1251); //только Windows
 std::srand(std::time(nullptr));
 int n = 5 + std::rand() % 10;
 fs::path path(fs::temp_directory_path() / "sandbox");
 fs::create_directories(path); //не гадим даже в temp, создадим там внутри папку
 fs::current_path(path);
 for (int i = 0; i < n; i++) {
  std::string name = fs::path(std::tmpnam(nullptr)).filename().string();
   //так как tmpnam вернёт файл с путём, а нам нужно только уникальное имя
  if (std::rand() % 2 == 0) {
   fs::create_directories(name);
  }
  else {
   std::ofstream ofs(name);
   ofs << name << '\n';
   ofs.close();
  }
 }
 for (auto& p : fs::recursive_directory_iterator(path)) {
  std::cout << p.path() << 
   (p.is_directory() ? " folder" : " file") << std::endl;
 }
 try { //Получится ли удалить - не факт
  fs::remove_all(path);
 }
 catch (const std::exception& ex) {
  std::cout << ex.what() << std::endl;
 }
 return 0;
}
Папки и файлы в консоли и в окне файл-менеджера
Папки и файлы в консоли и в окне файл-менеджера

5. Проверить, содержится ли в строке std::string дата в формате ДД.ММ.ГГГГ, проверка корректности даты не предусмотрена.

Применим регулярное выражение и итератор по нему.

#include <iostream>
#include <regex>
#include <string>

int main() {
 std::string str("Today is 23.12.2021...");
 std::regex rex("([0-9]{1,2}\.[0-9]{1,2}\.[0-9]{4})");

 std::sregex_iterator beg { str.cbegin(), str.cend(), rex };
 std::sregex_iterator end {};
 for (auto i = beg; i != end; ++i) {
  std::cout << i->str() << " (position=" << i->position() << 
   ") [length=" << i->length() << "]" << std::endl;
 }
 return 0;
}

6. Заполнить прямоугольные или квадратные матрицы A и B случайными вещественными числами, принадлежащими диапазону значений [-10, 10]. Найти матрицу, транспонированную по отношению к матрице A + B.

#include <iostream>
#include <iomanip>
#include <random>

struct Random {
 std::random_device randomDevice;
 std::mt19937 generator;
 std::uniform_real_distribution<double> distribution;
 Random(double min, double max) : 
  randomDevice{}, generator{ randomDevice() }, distribution{ min, max } {}

 double operator () () {
  return distribution(generator);
 }

 friend Random& operator >> (Random& random, double& value) {
  value = random();
  return random;
 }
};

template <typename T, std::size_t Height, std::size_t Width>
using Matrix = T[Height][Width];

template<typename T, std::size_t Height, std::size_t Width>
std::ostream& operator << (std::ostream& out, const Matrix<T, Height, Width>& m) {
 for (auto& row : m) {
  for (auto& i : row) {
   out << std::fixed << std::setprecision(3) << std::setw(8) << i;
  }
  out << std::endl;
 }
 return out;
}

template<typename T, std::size_t Height, std::size_t Width>
Random& operator >> (Random& random, Matrix<T, Height, Width>& m) {
 for (auto& row : m) {
  for (auto& i : row) {
   random >> i;
  }
 }
 return random;
}

template<typename T, std::size_t Height, std::size_t Width>
void add(const Matrix<T, Height, Width>& a, 
 const Matrix<T, Height, Width>& b, Matrix<T, Height, Width>& result) {
 for (std::size_t i = 0; i < Height; ++i) {
  for (std::size_t j = 0; j < Width; ++j) {
   result[i][j] = a[i][j] + b[i][j];
  }
 }
}

template<typename T, std::size_t Height, std::size_t Width>
void transpose(const Matrix<T, Height, Width>& source, 
 Matrix<T, Width, Height>& result) {
 for (std::size_t i = 0; i < Height; ++i) {
  for (std::size_t j = 0; j < Width; ++j) {
   result[j][i] = source[i][j];
  }
 }
}

int main() {
 Random random{ -10, 10 };

 Matrix<double, 3, 4> a;
 Matrix<double, 3, 4> b;

 random >> a;
 random >> b;

 std::cout << "A:" << std::endl << a << "B:" << std::endl << b;

 Matrix<double, 3, 4> c;
 add(a, b, c);

 std::cout << "C = A + B:" << std::endl << c;

 Matrix<double, 4, 3> d;
 transpose(c, d);
 std::cout << "Transposed C:" << std::endl << d;

 return 0;
}

7. Удалить из целочисленного массива arr элементы, значения которых попадают в заданный интервал [a;b].

Здесь происходит именно "ручное" сжатие массива от удаляемого элемента до текущей размерности, без использования контейнеров STL, методы которых, впрочем, также делают нечто подобное.

Размерность и массив вводятся с консоли "вручную" и без проверки корректности данных, словом, всё по-школьному.

#include <iostream>
#include <cstdlib>
#include <utility>
using namespace std;

int main() {
 int n, a, b, p = 0;
 cout << "n="; cin >> n;
 int* arr = new int[n];
 cout << "Enter " << n << " integer numbers:" << endl;
 for (int i = 0; i < n; i++) cin >> arr[i];
 cout << "Enter limits a,b: ";
 cin >> a >> b;

 if (a > b) swap(a, b);
 for (int i = 0; i < n; i++)
  if (arr[i]<a || arr[i]>b) arr[p++] = arr[i];
 n = p;
 cout << "Result:\n";
 for (int i = 0; i < n; i++)
  cout << arr[i] << " ";
 cout <<  endl;
 delete[]arr;
 return 0;
}

8. Простая консольная (только консоль Windows) игра "Змейка" с тремя классами - "поле", "еда", "змейка".

По сути, код показывает, как может выглядеть базовый игровой цикл в консоли.

Замечу, что даже если задача достаточно проста, всё равно хорошо, когда в проекте есть классы, представляющие основные сущности (у нас это "поле", "пища" и "змея"), логика приложения реализована отдельно, а оформление - отдельно, игровой цикл наглядно читается, понятно, как потом можно дальше с этим работать и модифицировать. Просто "набор функций", не связанных функционалом классов, увы, быстро превращается в хаотичную вещь, уж поверьте моему опыту.

#include <iostream>
#include <windows.h>

using namespace std;

struct position {
 int x, y;
};

class fieldClass {
 static const int height;
 static const int width;
 char** field;
 fieldClass(const fieldClass&);
 fieldClass operator=(const fieldClass&);
public:
 fieldClass() {
  field = new char* [fieldClass::height];
  for (int c = 0; c < fieldClass::height; ++c) {
   field[c] = new char[fieldClass::width];
  }
 }
 ~fieldClass() {
  for (int c = 0; c < fieldClass::height; ++c) {
   delete[] field[c];
  }
  delete[] field;
 }

 void print() {
  for (int c = 0; c < height; ++c) {
   for (int r = 0; r < width; ++r) {
    cout << field[c][r];
   }
   cout << endl;
  }
 }

 void clear() {
  for (int c = 0; c < height; ++c) {
   for (int r = 0; r < width; ++r) {
    field[c][r] = ' ';
   }
  }
 }

 int get_width() const { return width; }
 int get_height() const { return height; }

 void draw(int y, int x, char what) {
  //y = (y < 0) ? 0 : (y >= height ? height - 1 : y);
  //x = (x < 0) ? 0 : (x >= width ? width - 1 : x);
  field[y][x] = what;
 }

} field;

class foodClass {
 position pos;
 char symbol;
public:
 foodClass() : symbol('X'), pos() {
  pos.x = pos.y = -1;
 }

 void set_pos(int x, int y) {
  pos.x = x;
  pos.y = y;
 }

 void reposition(const fieldClass& field) {
  pos.x = rand() % field.get_width();
  pos.y = rand() % field.get_height();
 }

 int get_x() const { return pos.x; }
 int get_y() const { return pos.y; }
 char get_symbol() const { return symbol; }
} food;

class snakeClass {
 enum { UP, DOWN, LEFT, RIGHT } dir;
 char symbol, head_symbol;
 position pos[100];
 position& head;
 int speed;
 int size;
 bool can_turn;
public:
 snakeClass(int x, int y) :
  symbol('#'), head_symbol('@'), pos(),
  speed(1), size(1), dir(RIGHT),
  head(pos[0]), can_turn(true)
 {
  pos[0].x = x;
  pos[0].y = y;
 }

 bool check_food(const foodClass& food) {
  if (food.get_x() == head.x && food.get_y() == head.y) {
   size += 1;
   return true;
  }
  return false;
 }

 void get_input(const fieldClass& field) {
  if (GetAsyncKeyState(VK_UP) && dir != DOWN) {
   dir = UP;
  }
  if (GetAsyncKeyState(VK_DOWN) && dir != UP) {
   dir = DOWN;
  }
  if (GetAsyncKeyState(VK_LEFT) && dir != RIGHT) {
   dir = LEFT;
  }
  if (GetAsyncKeyState(VK_RIGHT) && dir != LEFT) {
   dir = RIGHT;
  }
 }

 void move(const fieldClass& field) {
  position next = { 0, 0 };
  switch (dir) {
  case UP:
   next.y = -speed;
   break;
  case DOWN:
   next.y = speed;
   break;
  case LEFT:
   next.x = -speed;
   break;
  case RIGHT:
   next.x = speed;
  }
  for (int c = size - 1; c > 0; --c) {
   pos[c] = pos[c - 1];
  }
  head.x += next.x;
  head.y += next.y;

  if (head.x < 0 || head.y < 0 || head.x >= field.get_width() || head.y >= field.get_height()) {
   throw "DEAD!";
  }
 }

 void draw(fieldClass& field) {
  for (int c = 0; c < size; ++c) {
   if (c == 0) {
    field.draw(pos[c].y, pos[c].x, head_symbol);
   }
   else {
    field.draw(pos[c].y, pos[c].x, symbol);
   }
  }
 }

 int get_x() const { return head.x; }
 int get_y() const { return head.y; }
 char get_symbol() const { return symbol; }
} snake(1, 1);

const int fieldClass::height = 24;
const int fieldClass::width = 79;

void hidecursor() {
 HANDLE consoleHandle = GetStdHandle(STD_OUTPUT_HANDLE);
 CONSOLE_CURSOR_INFO info;
 info.dwSize = 100;
 info.bVisible = FALSE;
 SetConsoleCursorInfo(consoleHandle, &info);
}

int main() {
 system("mode con cols=80 lines=25");
 hidecursor();

 field.clear();
 food.set_pos(5, 5);

 while (1) { //игровой цикл
  field.clear();

  snake.get_input(field);
  try {
   snake.move(field);
  }
  catch (const char* er) {
   field.clear();
   cerr << er << endl;
   system("pause");
   return -1;
  }
  snake.draw(field);
  field.draw(food.get_y(), food.get_x(), food.get_symbol());

  if (snake.check_food(food)) {
   food.reposition(field);
  }

  field.print();

  Sleep(1000 / 30);
  system("cls");
 }

 return 0;
}

9. Вставить в строку символ звёздочки перед каждой последовательностью из нескольких (более одного) подряд идущих пробелов, использовать обработку через указатель.

#include <iostream>
#include <cstring>
using namespace std;

char* ins (char* dest, const char* src) {
 char *res = dest;
 int cnt = 0;
 while (*src) {
  if (*src == ' ') cnt++;
  else {
   if (cnt) {
    if (cnt > 1) *dest++ = '*';
    for (int i = 0; i < cnt; i++) *dest++ = ' ';
    cnt = 0;
   }
   *dest++ = *src;
  }
  src++;
 }
 if (cnt) { //могли быть пробелы в конце
  if (cnt > 1) *dest++ = '*';
  for (int i = 0; i < cnt; i++) *dest++ = ' ';
 }
 *dest = '\0';
 return res;
}

int main() {
 const char *src = " Hello,   i  am a test   ";
 char *dest = new char[strlen(src) * 2];
  //на самом деле, в худшем случае вида "  a  b  c  " добавится примерно каждый 4-й символ
 cout << '[' << src << ']' << endl;
 cout << '[' << ins(dest, src) << ']' << endl;
 return 0;
}

10. Для заданного натурального числа проверить, делится ли оно без остатка на 2, 3, ..., 9. Нельзя использовать оператор % ("остаток от деления"), а только арифметику и битовые операции.

Пятёрку и девятку, для разнообразия, обработали отдельно. Для проверки делимости на другие натуральные числа можно составить аналогичные выражения например:

bool div_by_10 = div_by_2 && div_by_5;
bool div_by_11 = number * 3123612579u <= 390451572u;
bool div_by_12 = div_by_3 && div_by_4;
bool div_by_13 = number * 3303820997u <= 330382099u;
bool div_by_14 = div_by_2 && div_by_7;
bool div_by_15 = number * 4008636143u <= 286331153u;

Вот сама программа и копия её вывода.

#include <iostream>
#include <iomanip>

bool div248 (unsigned a, unsigned b) { //Делимость на 2, 4, 8
 if (!(b == 2 || b == 4 || b == 8)) return false;
 return (!(a & (b - 1)));
}

unsigned add (unsigned a, unsigned b) { //Сложение на битовых операциях, служебная
 return b == 0 ? a : add(a ^ b, (a & b) << 1);
}

bool div37 (unsigned a, unsigned b) { //Делимость на 3, 7
 if (!(b == 3 || b == 7)) return false;
 while (a > b) {
  unsigned sum = 0;
  while (a) {
   sum = add(a & b, sum);
   a >>= (b == 3 ? 2 : 3);
  }
  a = sum;
 }
 return a == 0 || a == b;
}

unsigned div5 (unsigned a) { //Делимость на 5
 return a * 0xCCCCCCCD <= 0x33333333;
}

bool div9 (unsigned a) { //Делимость на 9
 return a * 954437177u <= 477218588u;
}

int main() {
 std::cout << std::setw(4) << "A" 
  << std::setw(3) << "2" << std::setw(3) << "3"
  << std::setw(3) << "4" << std::setw(3) << "5"
  << std::setw(3) << "6" << std::setw(3) << "7"
  << std::setw(3) << "8" << std::setw(3) << "9"<< std::endl;
 for (unsigned a = 0; a < 29; a++) {
  std::cout << std::setw(4) << a <<
   std::setw(3) << div248(a, 2) << std::setw(3) << div37(a, 3) <<
   std::setw(3) << div248(a, 4) << std::setw(3) << div5(a) <<
   std::setw(3) << (div248(a, 2) && div37(a, 3)) << std::setw(3) << div37(a, 7) <<
   std::setw(3) << div248(a, 8) << std::setw(3) << div9(a) << std::endl;
 }
 return 0;
}
   A  2  3  4  5  6  7  8  9
   0  1  1  1  1  1  1  1  1
   1  0  0  0  0  0  0  0  0
   2  1  0  0  0  0  0  0  0
   3  0  1  0  0  0  0  0  0
   4  1  0  1  0  0  0  0  0
   5  0  0  0  1  0  0  0  0
   6  1  1  0  0  1  0  0  0
   7  0  0  0  0  0  1  0  0
   8  1  0  1  0  0  0  1  0
   9  0  1  0  0  0  0  0  1
  10  1  0  0  1  0  0  0  0
  11  0  0  0  0  0  0  0  0
  12  1  1  1  0  1  0  0  0
  13  0  0  0  0  0  0  0  0
  14  1  0  0  0  0  1  0  0
  15  0  1  0  1  0  0  0  0
  16  1  0  1  0  0  0  1  0
  17  0  0  0  0  0  0  0  0
  18  1  1  0  0  1  0  0  1
  19  0  0  0  0  0  0  0  0
  20  1  0  1  1  0  0  0  0
  21  0  1  0  0  0  1  0  0
  22  1  0  0  0  0  0  0  0
  23  0  0  0  0  0  0  0  0
  24  1  1  1  0  1  0  1  0
  25  0  0  0  1  0  0  0  0
  26  1  0  0  0  0  0  0  0
  27  0  1  0  0  0  0  0  1
  28  1  0  1  0  0  1  0  0

11. Решить предыдущую задачу в общем виде, реализовав функцию bool check(int x, int y), проверяющую, делится ли x на y без остатка с использованием только битовых операций и сдвига.

Разумеется, с точки зрения количества используемых операций этот подход весьма избыточен.

#include <iostream>
#include <iomanip>

int add(int summand, int addend) {
 int carry = 0x00;
 while (addend != 0x00) {
  carry = (summand & addend);
  summand = summand ^ addend;
  addend = (carry << 1);
 }
 return summand;
}

bool check(int x, int y) {
 int summ = 0;
 while (summ < x) {
  summ = add (summ, y);
 }
 return summ == x;
}

int main() {
 std::cout << std::setw(4) << "A";
 for (int b = 2; b < 16; b++) {
  std::cout << std::setw(3) << b;
 }
 std::cout << std::endl;
 for (int a = 0; a < 29; a++) {
  std::cout << std::setw(4) << a;
  for (int b = 2; b < 16; b++) {
   std::cout << std::setw(3) << check(a, b);
  }
  std::cout << std::endl;
 }
 return 0;
}

12. Записать в текстовый файл все перестановки четырёх слов.

Конечно, всё это делается однотипно, ведь библиотека STL - это шаблоны функций, применимые к любым типам данных.

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
 
 
int main() {
 const int n = 4;
 std::string words[n] = { "lorem", "ipsum", "skazal", "burzum" };
 std::ofstream f ("words.txt");
 std::sort (words, words + n);
 do {
  for (int i = 0; i < n; i++) f << words[i] << ' '; 
  f << std::endl; 
 } while (std::next_permutation(words, words + n));
 f.close();
 return 0;
}

Помните, что с ростом n количество перестановок растёт как факториал от n, то есть, очень быстро. При n == 24, скажем, получится 620448401733239439360000 строк в файле, вряд ли хватит диска какой угодно ёмкости :)

burzum ipsum lorem skazal 
burzum ipsum skazal lorem 
burzum lorem ipsum skazal 
burzum lorem skazal ipsum 
burzum skazal ipsum lorem 
burzum skazal lorem ipsum 
ipsum burzum lorem skazal 
ipsum burzum skazal lorem 
ipsum lorem burzum skazal 
ipsum lorem skazal burzum 
ipsum skazal burzum lorem 
ipsum skazal lorem burzum 
lorem burzum ipsum skazal 
lorem burzum skazal ipsum 
lorem ipsum burzum skazal 
lorem ipsum skazal burzum 
lorem skazal burzum ipsum 
lorem skazal ipsum burzum 
skazal burzum ipsum lorem 
skazal burzum lorem ipsum 
skazal ipsum burzum lorem 
skazal ipsum lorem burzum 
skazal lorem burzum ipsum 
skazal lorem ipsum burzum

30.12.2021, 14:59 [684 просмотра]


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

показать комментарии (1)