13 не пригодившихся задач за апрель 2023

Поскольку C++ в этом сезоне особо уже не ожидается, публикую остаток задач, предыдущая заметка по теме находится здесь.

Все задачи выполнялись в консоли Visual Studio 2019 или 2022 из пустого проекта с единственным добавленным файлом Source.cpp.

Спрашивали про мини-задачи #4 (считалка), #11 (площадь пятиугольника как сумма площадей трёх треугольников) и #13 (точка на плоскости внутри треугольника). Если ещё что-то добавится, пополню эту заметку.

1. Не применяя массивов или иных контейнеров, сгенерировать миллион случайных чисел со значением 0 или 1 и найти длину максимальной цепочки одинаковых значений.

#include <iostream>
#include <cstdlib>
#include <ctime>

int main() {
 int cnt = 1, max = 1, prev = -1, curr;
 srand(time(NULL)); //инициализировать генератор случайных чисел
 for (int x = 0; x < 1e6; x++) {
  curr = rand() % 2; //0 или 1
  if (curr == prev) {
   cnt++;
   if (cnt > max) max = cnt;
  }
  else cnt = 1;
  prev = curr;
 }
 std::cout << max;
 return 0;
}

2. Заполнить статический массив случайными числами из диапазона значений [0;99] и найти среднее арифметическое этих чисел.

#include <iostream>
#include <iomanip>
#include <cstdlib> /* srand, rand */
#include <ctime> /* time */

int main() {
 const int n = 5; 
  //размерность статического массива всегда задаем константой
 int arr[n];
 double sum = 0;
 srand(time(NULL));
  //инициализировать генератор случайных чисел
 for (int i = 0; i < n; i++) {
  arr[i] = rand() % 100; //число от 0 до 99
  std::cout << arr[i] << ' ';
  sum += arr[i];
 }
 std::cout << std::endl << "Average is " << 
  std::fixed << std::setprecision(2) << (sum / n);
 return 0;
}

3. Решить нелинейное уравнение методом простых итераций. Здесь f(x) - исходная функция из уравнения f(x) = 0, phi(x) - функция из уравнения, приведённого к виду x = phi(x).

/* Пример численного решения уравнения методом
 простых итераций*/
#include <iostream>
#include <cmath>

double f(double x) {
 return 2 * pow(x, 3) - 3 * pow(x, 2) + 5 * x - 3;
}

double phi(double x) {
 return (-2 * pow(x, 3) + 3 * pow(x, 2) + 3) / 5.;
}

int main() {
 //исходное уравнение: f(x) = 0: 2*x^3 - 3*x^2 + 5*x - 3 = 0
 //эквивалентная форма x = phi(x): x = (- 2*x^3 + 3*x^2 + 3) / 5
 double xn0 = 1, xn, eps = 1e-12;
 int n = 0; //сходимость может зависеть от начальной точки xn0!
 do { //метод простых итераций:
  xn = phi(xn0);
  if (abs(xn - xn0) < eps || n > 1000) break;
  xn0 = xn;
  n++;
 } while (1);
 std::cout.precision(15);
 std::cout << "x=" << xn << ", " << n << " step(s)" <<
  std::endl << "check f(x)=" << std::fixed << f(xn);
 return 0;
}

4. Детская считалка. n человек стоят по кругу, считалка состоит из k слов, ведущий начинает отсчёт слов с себя. Если он выходит, ведущим становится следующий стоящий против часовой стрелки. Мальчик Вася такой умный, что всегда может заранее сказать, кто выйдет, а Вы? Люди нумеруются также с единицы против часовой стрелки, начиная с ведущего.

#include <iostream>

int main() {
 int k = 11, n = 4;
 while (n > 1) {
  std::cout << (k % n == 0 ? n : k % n) //формула для "выходящего" предельно проста
   << " from "<< n << std::endl;
  n--;
 }
 return 0;
}

5. Взять методом средних прямоугольников определённый интеграл в пределах интегрирования от 0 до π для f(x) = sin(x), шаг по x равен одной сотой.

#include <iostream>
#define _USE_MATH_DEFINES
#include <math.h>

double f(double x) { return sin(x); }

int main() {
 double a = 0, b = M_PI, dx = 0.01, s = 0;
 for (double x = a; x <= b; x += dx) {
  s += dx * f(x + dx / 2.);
 }
 std::cout << s;
 return 0;
}

6. Решить СЛАУ из 2 уравнений методом Крамера. Проверить найденное решение. Вместо матрицы a[n][m] использовать в подпрограммах "псевдоматрицу" - вектор длиной n*m, для которого обращение к элементу a[i][j] соответствует обращению к a[m*i+j].

/*
 Решение СЛАУ вида
 a[1][1]*x[1] + a[1][2]*x[2] = b[1]
 a[2][1]*x[1] + a[2][2]*x[2] = b[2]
 размерностью 2x2 методом Крамера.
 Используем "псевдоматрицу" - массив a[n][m]
 интерпретируем как a[n*m]
*/
#include <iostream>
#include <iomanip>
#include <cmath>

double det2x2(double* a) {
 //Определитель матрицы 2x2 - без проверки данных!
 return a[0] * a[3] - a[1] * a[2];
}

double* replace_column(int n, int m, double* a, int c, double* b) {
 //Замена столбца c в матрице a[n][m] на вектор b - без проверки данных!
 double* new_a = new double[n * m];
 if (!new_a) return nullptr;
 for (int i = 0; i < n; i++)
  for (int j = 0; j < m; j++)
   new_a[m * i + j] = (j == c ? b[i] : a[m * i + j]);
 return new_a;
}

double* mmul(int n, int m, int p, double* a, double* b) {
 //a[n][m] * b[m][p] = c[n][p]
 double* c = new double[n * p];
 if (!c) return nullptr;
 for (int i = 0; i < n; i++) {
  for (int k = 0; k < p; k++) {
   c[p * i + k] = 0;
   for (int j = 0; j < m; j++)
    c[p * i + k] += a[m * i + j] * b[p * j + k];
  }
 }
 return c;
}

int main() {
 const int n = 2;
 //Замените статическое определение вводом данных
 double a[n * n] = {
  1.5,-2.5,
  0.7, 3.4
 };
 double b[n] = { 1, 2 };
 //Проверям существование решения
 double det = det2x2(a);
 if (det == 0) {
  std::cout << "No solution, det(A) = 0";
  return -1;
 }
 //Считаем и выводим решение
 double* a0 = replace_column(n, n, &a[0], 0, &b[0]);
 double* a1 = replace_column(n, n, &a[0], 1, &b[0]);
 double det0 = det2x2(a0), det1 = det2x2(a1);
 double x[n];
 x[0] = det0 / det;
 x[1] = det1 / det;
 std::cout << "Solution: ";
 std::cout.precision(3);
 for (int j = 0; j < n; j++)
  std::cout << std::setw(8) << std::fixed << x[j];
 std::cout << std::endl;
 //Проверяем решение
 double* new_b = mmul(n, n, 1, a, x);
 std::cout << "Errors:   ";
 for (int j = 0; j < n; j++)
  std::cout << std::setw(8) << std::fixed << abs(b[j] - new_b[j]);
 delete[] a1;
 delete[] a0;
 delete[] new_b;
 return 0;
}

7. Для случайно сгенерированного массива целых чисел размерностью не менее 100 элементов реализовать алгоритмы сортировки выбором, пузырьком, вставками. Предусмотреть динамическое изменение размерности массива, режим включения и выключения вывода отсортированного массива в консоль, интерфейс для выбора действия, измерение и вывод времени сортировки в секундах.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <chrono>

class Timer {
 std::chrono::high_resolution_clock::time_point start;
public:
 Timer() {
  start = std::chrono::high_resolution_clock::now();
 }
 double stop() {
  std::chrono::high_resolution_clock::time_point end =
   std::chrono::high_resolution_clock::now();
  std::chrono::duration <double>
   time_span = std::chrono::duration_cast <std::chrono::duration<double>>(end - start);
  return time_span.count();
 }
};

template <typename T> void fill_array(const int n, T a[], T low, T hi) {
 srand((unsigned int)time(NULL));
 for (int i = 0; i < n; i++)
  a[i] = low + rand() % (hi - low + 1);
}

template <typename T> void swap(T& a, T& b) {
 T c = a; a = b; b = c;
}

template <typename T> void type_array(const int n, T a[]) {
 std::cout << std::fixed;
 for (int i = 0; i < n; i++)
  std::cout << std::setw(5) << a[i];
 std::cout << std::endl;
}

void selection_sort(const int n, int a[]) {
 int min, imin, i, j;
 for (i = 0; i < n; i++) {
  min = a[i]; imin = i;
  for (j = i + 1; j < n; j++) {
   if (a[j] < min) {
    min = a[j]; imin = j;
   }
  }
  swap <int >(a[imin], a[i]);
 } 
}

void bubble_sort(const int n, int a[]) {
 int i, j;
 for (i = 0; i < n - 1; i++) { //внешний цикл отвечает за номер прохода
  for (j = n - 1; j > i; j--) { //внутренний - за перебор элементов в одном проходе
   if (a[j - 1] > a[j]) swap <int >(a[j-1], a[j]);
  }
 }
}

void inserting_sort(const int n, int a[]) {
 int i, j, temp;
 for (i = 1; i < n; i++) {
  temp = a[i];
  for (j = i; j > 0 && temp < a[j - 1]; j--) {
   a[j] = a[j - 1];
  }
  a[j] = temp;
 }
}

void refresh() {
 std::cin.clear();
 std::cin.ignore(100, '\n');
}

int main() {
 int n = 10000;
 int* a = new int[n];
 if (!a) {
  std::cout << "No memory!" << std::endl;
  return -1;
 }
 double time;
 bool show = true;
 do {
  std::cout << "Select the action:" << std::endl <<
   "1 - Selection sorting" << std::endl <<
   "2 - Bubble sorting" << std::endl <<
   "3 - Inserting sorting" << std::endl <<
   "4 - New array size (now is " << n << ")" << std::endl <<
   "5 - Show sorted: now is " << (show ? "on" : "off") << ")" << std::endl <<
   "0 - Exit" << std::endl;
  char choice;
  std::cin >> choice;
  refresh();
  switch (choice) {
  case '1':
  case '2':
  case '3':
   fill_array(n, a, -n, n);
   { //только чтобы описать внутри таймер
    Timer t;
    switch (choice) {
    case '1': selection_sort(n, a); break;
    case '2': bubble_sort(n, a); break;
    case '3':  inserting_sort(n, a); break;
    }
    time = t.stop();
   }
   if (show) type_array(n, a);
   std::cout << "time: " << std::fixed << time << " sec." << std::endl;
   break;
  case '4':
   do {
    std::cout << "Current size is " << n << std::endl <<
     "Put new size (integer >99): ";
    std::cin >> n;
    if (!std::cin.good() || n < 100) {
     refresh(); continue;
    }
    else break;
   } while (1);
   if (a) {
    delete[] a; a = nullptr;
    a = new int[n];
    if (!a) {
     std::cout << "No memory!" << std::endl;
     return -1;
    }
   }
   break;
  case '5': show = !show; break;
  case '0': exit(0);
  default:
   std::cout << "Bad action, repeat it, please" << std::endl;
   break;
  }
 } while (1);
 return 0;
}

Расширенная версия программки и теория есть здесь.

8. Функция y=sin(x) на интервале по x = [0;π/2] хорошо приближается разложением y0 = x - x3/3! + x5/5!. Напишите программу, которая для заданного значения аргумента x подсчитывает по этой формуле y0 и сравнивает его с точным значением, вычисленным с помощью стандартной функции.

#include <iostream>
#include <iomanip>        //Чтобы были манипуляторы ввода
#define _USE_MATH_DEFINES //Чтобы была константа для 
#include <math.h>         //числа "Пи" и математика
using namespace std;

int main() {
 double x = M_PI / 10, //x от 0 до Пи/2
  y = sin(x),
  y0 = x - pow(x, 3) / 6 + pow(x, 5) / 120;
 cout << "   y=" << setprecision(12) << y <<
  endl << "my y=" << y0 <<
  endl << "diff=" << fixed << abs(y - y0);
 return 0;
}

9. Напишите программу, которая алгоритмически определяет день недели для произвольной даты dd.mm.yyyy, корректность вводимой даты можно не проверять.

#include <iostream>
using namespace std;

int main() {
 unsigned int d, m, y, wd;

 cout << "Input d m yyyy: ";
 cin >> d >> m >> y;
 if (!cin) {
  cout << "Get me correct date, please";
  return -1;
 }

 if (m < 3) {
  m += 12; y--;
 }
 int c = y / 100;
 y %= 100;
 wd = (d + 13*(m+1)/5 + y + y/4 +c/4 + 5*c) % 7;
 cout << "Weekday is " << wd << endl;
 cout << "[0-Sa, 1-Su, 2-Mo, 3-Tu, 4-We, 5-Th, 6-Fr]";
 return 0;
}

10. Напечатать в консоли простейшую шахматную доску и проверить, находится ли размещённый на ней король под боем хотя бы одной из двух ладей.

#include <iostream>
#include <iomanip>

const int size = 8;
char b[size + 1][size + 1]; //нумеруем с единицы

void init() {
 for (int y = 1; y <= size; y++)
  for (int x = 1; x <= size; x++)
   b[x][y] = ' ';
}

void print() {
 for (int y = 1; y <= size; y++) {
  std::cout << std::endl;
  for (int x = 1; x <= size; x++) {
   char c = (x + y) % 2 == 0 ? ' ' : '*';
   if (b[x][y] != ' ') c = b[x][y];
   std::cout << c;
  }
 }
}

bool set(char f, int x, int y) {
 if (x < 1 || x > size || y <1 || y >size) return false;
 if (b[x][y] != ' ') return false;
 b[x][y] = f;
 return true;
}

int main() {
 int r1x = 8, r1y = 1, r2x = 4, r2y = 4, k1x = 8, k1y = 4;
 init();
 if (!set('R', r1x, r1y) ||
  !set('R', r2x, r2y) ||
  !set('k', k1x, k1y)) {
  std::cout << "Bad position"; return -1;
 }
 print();
 std::cout << std::endl << "King is " <<
  (k1x == r1x || k1x == r2x || k1y == r1y || k1y == r2y ?
   "" : "not ") << "checked";
 return 0;
}

11. Найти площадь пятиугольника как сумму площадей трёх треугольников.

#include <iostream>
#include <cmath>

// Функция для вычисления сторон 
double Distance(double x1, double x2, double y1, double y2) {
 return std::hypot(x2 - x1, y2 - y1);
}

//Функция для площади треугольника (Герона)
double Stri(double ab, double bc, double cd) {
 double p = (ab + bc + cd) / 2;
 return std::sqrt(p * (p - ab) * (p - bc) * (p - cd));
}

int main() {
 // Значения для координат.
 double x1 = 2.5, y1 = 1.5;
 double x2 = 1.3, y2 = 2.1;
 double x3 = 3.1, y3 = 2.9;
 double x4 = 5.4, y4 = 2.5;
 double x5 = 4.9, y5 = 1.8;

 // Расчет сторон:
 double ab = Distance(x1, y1, x2, y2);
 double bc = Distance(x2, y2, x3, y3);
 double cd = Distance(x3, y3, x4, y4);
 double de = Distance(x4, y4, x5, y5);
 double ea = Distance(x5, y5, x1, y1);
 double da = Distance(x4, y4, x1, y1);
 double db = Distance(x4, y4, x2, y2);

 // Расчет площадей:
 double Sabd = Stri(ab, db, da);
 double Sade = Stri(bc, cd, db);
 double Sbcd = Stri(ea, da, de);
 double S5 = Sabd + Sade + Sbcd;

 // Вывод на экран:
 std::cout << "S(ABD)= " << Sabd << std::endl;
 std::cout << "S(ADE)=" << Sade << std::endl;
 std::cout << "S(BCD)=" << Sbcd << std::endl;
 std::cout << "S(ABCDE)=" << S5 << std::endl;
}

Картинка с графиком есть в этой заметке.

12. Найти значение числа π с помощью ряда Мадхавы. Реализовать версии программы с критерием точности |u|≤&eps;, где u - очередное слагаемое ряда и с заданным предельным количеством итераций n.

Ряд Мадхавы, он же ряд Лейбница - старинный способ вычисления числа Пи.

Если точность задана константой eps (ниже 10^-15 смысла задавать нет):

#include <iostream>
#include <iomanip>
#include <cmath>
#define _USE_MATH_DEFINES
#include <math.h>


int main() {
 double eps = 1e-15, a = 1, u = 1, pi = 1;
 int n = 0;
 while (abs(u) > eps) {
  n++;
  a *= -3;
  u = 1 / a / (2 * n + 1);
  pi += u;
 }
 pi *= sqrt(12);

 std::cout.precision(15);
 std::cout << "pi = " << std::fixed << pi << 
  std::endl << "pi = " << M_PI << " (standard)";
 return 0;
}

Если задано количество итераций n:

#include <iostream>
#include <iomanip>
#include <cmath>
#define _USE_MATH_DEFINES
#include <math.h>


int main() {
 double a = 1, u = 1, pi = 0;
 int n = 1000000, k = 0;
 do {
  pi += u;
  k++;
  a *= -3;
  u = 1 / a / (2 * k + 1);
 } while (k <= n);
 pi *= sqrt(12);

 std::cout.precision(15);
 std::cout << "pi = " << std::fixed << pi << 
  std::endl << "pi = " << M_PI << " (standard)";
 return 0;
}

13. Определить, находится ли точка на плоскости внутри треугольника, заданного координатами трёх различных между собой вершин.

#include <iostream>

//Площадь треугольника с вершинами (x1, y1), (x2, y2), (x3, y3)
double area(double x1, double y1, double x2, double y2, double x3, double y3) {
 return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
}

//Лежит ли точка P(x,y) внутри треугольника A(x1, y1), B(x2, y2), C(x3, y3)
bool isInside(double x1, double y1, double x2, double y2, double x3, 
              double y3, double x, double y) {
 double A = area(x1, y1, x2, y2, x3, y3); //ABC
 double A1 = area(x, y, x2, y2, x3, y3); //PBC
 double A2 = area(x1, y1, x, y, x3, y3); //PAC
 double A3 = area(x1, y1, x2, y2, x, y); //PAB
 return (A == A1 + A2 + A3);
}

int main() {
 //P в треугольнике A(0, 0), B(4, 0), C(4, 3)
 double P[2] = { 2.5, 2};
 std::cout << (isInside(0, 0, 4, 0, 4, 3, P[0], P[1]) ? "Yes": "No");
 P[0] = 3;
 std::cout << std::endl << (isInside(0, 0, 4, 0, 4, 3, P[0], P[1]) ? "Yes" : "No");
 return 0;
}

13.04.2023, 10:38 [310 просмотров]