10 не пригодившихся задач за май 2022

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

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

Что из этого может таки пригодиться - возможно, "непонятки" с union из #4, которые так и не удалось привести в мысленное соответствие со стандартами, "кольцевание" массива за O(N) из #6, "распараллеливание" задачи о ферзях из #9.

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

#include <iostream>
#include <vector>

using entry = std::pair<int, const char*>; //Вводим тип для сущности

void print (const std::vector<entry>& entries, std::ostream& out = std::cout) {
 bool first = true;
 for (const auto& e : entries) {
  if (!first) out << ", ";
  first = false;
  out << e.first << " " << e.second;
 }
 out << std::endl;
}

std::vector<entry> convert(int seconds) {
 static const entry time_table[] = {
  {7 * 24 * 60 * 60, "wk"}, 
  {24 * 60 * 60, "d"}, 
  {60 * 60, "hr"}, 
  {60, "min"}, 
  {1, "sec"}
 };
 std::vector<entry> result;
 for (const auto& e : time_table) {
  int time = seconds / e.first;
  if (time != 0) result.emplace_back(time, e.second);
  seconds %= e.first;
 }
 return result;
}

int main() {
 int test_table[] = { 7319 , 86401, 6000600 };
 for (const auto& e : test_table) {
  std::cout << e << " sec is "; print(convert(e));
 }
}

2. Файлы f.txt и g.txt состоят из некоторого количества строк. Создать файл h.txt, в котором чередуются нечётные по номеру строки файла f.txt (нумерация с 1) с чётными строками файла g.txt.

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

void error(string message, int errorcode) {
 cout << endl << message;
 exit(errorcode);
}

int main() {
 string line;
 ifstream f("f.txt"), g("g.txt");
 ofstream h("h.txt");
 if (!f || !g || !h) {
  error(string("Error opening file"), 1);
 }
 int fcnt = 0, gcnt = 0;
 do {
  f >> line;
  fcnt++;
  if (fcnt % 2 == 1) h << line << endl;
  g >> line;
  gcnt++;
  if (gcnt % 2 == 0) h << line << endl;
 } while (!f.eof() && !g.eof());
 h.close();
 cout << "Press Enter";
 return 0;
}

Файлы из теста этой задачи

Файлы f.txt и g.txt, разумеется, должны существовать и находиться (при профиле Debug) в той же папке, где Source.cpp

Файлы с данными в папке

3. Определить структуру для хранения действительной и мнимой частей комплексного числа, обе части могут быть как целыми, так и вещественными числами.

Переопределить оператор вывода в поток "<<" для структуры.

#include <iostream>

template <typename T> struct complex {
 T re, im;
 complex(T re = 0, T im = 0) {
  this->re = re; this->im = im;
 }
};

template <typename T> std::ostream& operator << (std::ostream& os, const complex <T>& p) {
 return os << p.re << (p.im < 0 ? "" : "+") << p.im << "i";
}

int main() {
 complex <int> i(1,-2);
 std::cout << i << std::endl;
 complex <double> d(3, 4.5);
 std::cout << d;
 return 0;
}

4. Решить предыдущую задачу при условии, что части комплексного числа могут интерпретироваться и как вещественные, и как целые числа. Использовать объединение (union).

#include <iostream>

union number {
 double d;
 int i;
 number (double d = 0.) {
  this->d = d;
  this->i = (int)d;
 }
};

struct complex {
 number re, im;
 complex(number re, number im) {
  this->re.d = re.d; this->im.d = im.d;
  this->re.i = re.i; this->im.i = im.i;
 }
};
std::ostream& operator << (std::ostream& os, const complex& p) {
 return os << (double)p.re.d << ((double)p.im.d < 0 ? "" : "+") << (double)p.im.d << "i";
}

int main() {
 number n1= {1 }, n2 = { -2 }, n3 = { 3 }, n4 = { 4.5 };
 complex i(n1,n2);
 std::cout << i << std::endl;
 complex d(n3, n4);
 std::cout << d << std::endl;
 std::cout << d.im.i; //==4 вышло в Studio
 return 0;
}

...хотя теоретически у union активно всегда только одно поле.

5. Вычислить значение y(n) = sqrt(1+sqrt(2+...+sqrt(n))...), где sqrt - квадратный корень, в двух вариантах - с помощью итераций и рекурсии.

#include <iostream>

double y_iter(unsigned n) {
 double result = 0;
 for (unsigned i = n; i >= 1; i--)
  result = sqrt(result + i);
 return result;
}

double y_recur(unsigned n, unsigned N) {
 if (n == 1) return sqrt(N);
 return sqrt(N - n + 1 + y_recur(n - 1, N));
}

int main() {
 unsigned n = 7;
 double n1 = y_iter(n);
 std::cout << n1 << std::endl;
 double n2 = y_recur(n, n);
 std::cout << n2 << std::endl;
 return 0;
}

Проверка в Excel:

=КОРЕНЬ(1+КОРЕНЬ(2+КОРЕНЬ(3+КОРЕНЬ(4+КОРЕНЬ(5+КОРЕНЬ(6+КОРЕНЬ(7)))))))
=1,757885646

6. Имеется массив из N натуральных элементов, можно заполнить его значениями 1, 2, ..., N. K первых элементов перемещаются в конец массива M раз, например при N = 5, K = 2, M = 2, имеем [ 1 2 3 4 5 ] , [ 3 4 5 1 2 ] , [ 5 1 2 3 4 ].

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>

int main() {
 int n = 5, k = 2, m = 20002; /* много перемещений */
 std::vector<int> v(n);
 std::iota(v.begin(), v.end(), 1);
 for (auto val : v) {
  std::cout << std::setw(3) << std::left << val;
 }

 int s = (k * m) % n;
 std::rotate(v.begin(), v.begin() + s, v.end());

 std::cout << std::endl;
 for (auto val : v) {
  std::cout << std::setw(3) << std::left << val;
 }
 return 0;
}

7. Прямоугольники на плоскости со сторонами, параллельными осям координат, описаны в виде структур {координата x, коррдината y, ширина, высота}. Определить, пересекаются ли два прямоугольника.

#include <iostream>

struct rect {
 double x, y, width, height;
};

bool valueInRange(double value, double min, double max) {
 return (value >= min) && (value <= max);
}

bool rectOverlap(rect A, rect B) {
 bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
  valueInRange(B.x, A.x, A.x + A.width);
 bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
  valueInRange(B.y, A.y, A.y + A.height);
 return xOverlap && yOverlap;
}

int main() {
 rect A {3,5,3,2}, B{0,0,4,6};
 std::cout << rectOverlap(A,B);
 return 0;
}

8. Задача о спящей красавице. Условие есть, например, в Вики. Проверим решение нашим любимым методом Монте-Карло.

#include <iostream>
#include <random>

int main() {
 const int experiments = 1000000;
 std::random_device dev;
 std::default_random_engine engine(dev());
 std::uniform_int_distribution<int> distribution(0, 1);
 int heads = 0, wakenings = 0;
 for (int i = 0; i < experiments; ++i) {
  ++wakenings;
  switch (distribution(engine)) {
  case 0: //орлы
   ++heads;
   break;
  case 1: //решки
   ++wakenings;
   break;
  }
 }
 std::cout << "Wakenings over " << experiments << " experiments: " << wakenings << std::endl;
 std::cout << "Sleeping Beauty should estimate a credence of: "
  << double(heads) / wakenings << std::endl;
 return 0;
}

Wakenings over 1000000 experiments: 1499903
Sleeping Beauty should estimate a credence of: 0.33342

9. Реализовать параллельный алгоритм решения задачи о 8 ферзях.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <thread>
#include <mutex>

std::mutex mx;

int main() {
 int const n = 8; //количество ферзей
 int const threadCount = 8; //количество потоков
 std::vector<std::vector<int>> mtx(threadCount, std::vector<int>(n));
 int cnt{};
 std::vector<std::thread> vt;
 int step = n / threadCount;
 int rem = n % threadCount;
 for (int i = 0; i < threadCount; ++i) {
  std::iota(mtx[i].begin(), mtx[i].end(), 0);
  int lb = i * step;
  int ub = lb + step + (i < threadCount - 1 ? 0 : rem);
  if (lb < ub) {
   std::swap(mtx[i][0], mtx[i][lb]);
   std::sort(mtx[i].begin() + 1, mtx[i].end());
   vt.emplace_back([&cnt, &mtx, i](int ub) {
    auto& vct = mtx[i];
    do {
     int i{};
     for (i = 0; i < vct.size() - 1; ++i) {
      for (int j = i + 1; j < vct.size(); ++j) {
       if ((vct[i] + (j - i)) == vct[j] || (vct[i] - (j - i)) == vct[j]) {
        goto ext;
       }
      }
     }
     mx.lock();
     ++cnt;
     for (auto it = vct.begin(); it != vct.end(); ++it) {
      std::cout << '(' << (it - vct.begin()) << ',' << *it << ") ";
     }
     std::cout << std::endl;
     mx.unlock();
ext:
     char c;
    } while (std::next_permutation(vct.begin(), vct.end()) && vct[0] < ub);
   }, ub);
  }
 }

 for (auto& t : vt) {
  t.join();
 }
 std::cout << "count: " << cnt;
 return 0;
}

Выводятся пары значений (x, y), где x и y - координаты полей (начиная с нуля), плюс общее количество решений.

(0,6) (1,0) (2,2) (3,7) (4,5) (5,3) (6,1) (7,4)
(0,5) (1,0) (2,4) (3,1) (4,7) (5,2) (6,6) (7,3)
...
(0,4) (1,7) (2,3) (3,0) (4,6) (5,1) (6,5) (7,2)
(0,3) (1,7) (2,4) (3,2) (4,0) (5,6) (6,1) (7,5)
count: 92

10. Для натуральных чисел, не превосходящих заданного натурального значения N, найти все простые числа, сумма цифр которых равна натуральному М.

#include <iostream>

bool isPrime (unsigned long long x) {
 if (x == 2) return true;
 if (x < 3 || (x & 1) == 0) return false;
 unsigned long long i, ii;
 for (i = 3, ii = 9; ii <= x; ii += (i << 2) + 4, ++++i)
  if (x % i == 0) return false;
 return true;
}

unsigned long long sumOfDigits (unsigned long long n) {
 unsigned long long sum = 0;
 do {
  sum += n % 10;
  n /= 10;
 } while (n);
 return sum;
}

int main() {
 unsigned long long N = 1000, M = 13, i, cnt = 0;
 for (i = 2; i <= N; i++) {
  if (sumOfDigits(i) == M && isPrime(i)) {
   std::cout << i << ' ';
   cnt++;
  }
 }
 std::cout << std::endl << "Count = " << cnt;
 return 0;
}

01.06.2022, 23:46 [561 просмотр]