БлогNot. 15 не пригодившихся задач за март 2022

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

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

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

В будущем можно будет вернуться к задачам 1 (поиск целых чисел в строке), 10 (шаблон для пятизначной сводки), 15 (поиск индексов всех вхождений образца в строке за линейное время).

1. Задана строка текста std::string. Извлечь из неё слова, являющиеся записью целых чисел.

В такой задаче, пожалуй, единственный "тонкий" момент - как "ловить" переполнения, числа вроде 1e99999. Если на этом не акцентироваться, то показаны 2 варианта функции. Как минимум, можно делать ещё на sscanf или на регулярных выражениях.

#include <iostream>
#include <sstream>
#include <string>
#include <climits>
using namespace std;

bool is_int(string n) {
 try { int i = stoi(n); }
 catch (...) { return false; }
 return true;
 /*
 //другой вариант кода функции
 int val;
 istringstream reader(n);
 reader >> val;
 return reader.fail() ? false : true;
 */
}

int main() {
 cout << "Enter the string: ";
 string str;
 getline(cin, str);
      
 string word;
 stringstream s(str);
 int max = INT_MIN, min = INT_MAX;
 while (s >> word) {
  if (is_int(word)) {
   int val = stoi(word);
   if (val < min) min = val;
   if (val > max) max = val;
  }
 }
 cout << min << "," << max;
 return 0;
}

2. Найти количество цифр в натуральном числе, не используя оператора цикла.

На самом деле, это нельзя рассматривать как формулу O(1), потому что вычисление логарифма стандартной библиотекой всё равно предполагает цикл.

#include <iostream>
#include <cmath>

unsigned numOfDigits(long long unsigned n) {
 return n > 0 ? (int)log10((double)n) + 1 : 1;
}

int main() {
 std::cout << " 0:" << numOfDigits(0) << std::endl;
 std::cout << " 10:" << numOfDigits(10) << std::endl;
 std::cout << " 101:" << numOfDigits(101) << std::endl;
 std::cout << " 9998:" << numOfDigits(9998) << std::endl;
 std::cout << " 75363:" << numOfDigits(73563) << std::endl;
 std::cout << " 2157034567:" << numOfDigits(2157034567) << std::endl;
 return 0;
}

3. Числа без цифры. Заполнить массив целыми числами от 0 до 99, в записи которых нет цифры "3".

#include <iostream>

int main() {
 const int d[] { 0, 1, 2, 4, 5, 6, 7, 8, 9 };
 const int n = 50;
 int a[n];
 for (int i = 0; i < n; i++) {
  a[i] = d[rand() % 9] * 10 + d[rand() % 9]; //заполнение двузначными без "троек"
  std::cout << a[i] << ' ';
 }
 return 0;
}

4. Табулирование функции двух аргументов с выводом "ровных" столбцов, функция задана просто в коде.

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

int main() {
 cout.precision(3);
 cout << setw(10) <<"x" << setw(10) << "y" << setw(10) << "f(x,y)" << endl; 
 for (double x = -2; x <= 2; x += 0.1) {
  for (double y = -2; y <= 2; y += 0.1) {
  double f = x * x + y * y;
  cout << setw(10) << fixed << x << setw(10) << 
   fixed << y << setw(10) << fixed << f << endl; 
  } 
 }
 return 0;
}

5. Преобразование статической матрицы в вектор построчно, с выводом матрицы и вектора.

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

int main() {
 const int n = 3, m = 4;
 int a[n][m], b[n*m];
 cout.precision(2);
 for (int i = 0, k = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
   a[i][j] = -10 + rand() % 21; //от -10 до 10 
   cout << setw(4) << fixed << a[i][j];
   b[k++] = a[i][j];
  }
  cout << endl;
 }
 cout << endl;
 for (int i = 0; i < n*m; i++) cout << setw(4) << fixed << b[i];
 return 0;
}

6. Сортировка строк матрицы "пузырькоподобным" методом, O(n3)

#include <iostream>
using namespace std;

int main() {
 const int n = 4, m = 5;
 int b[n][m] = {
  {5, 3, 4, 1, 2},
  {25, 53, 34, 1, 42},
  {15, 33, 4, 41, -12},
  {75, 3, 4, 81, 2}
 };
 for (int k = 0; k < n; k++) {
  for (int i = 0; i < m-1; i++) {
   for (int j = i+1; j < m; j++) {
    if (b[k][i] > b[k][j]) {
     int temp = b[k][i]; b[k][i] = b[k][j]; b[k][j] = temp;
    }
   }
  }
  for (int i=0; i<m; i++) cout << b[k][i] << " "; 
  cout << endl;
 }
 return 0;
}

7. В каждой строке текстового файла определить количество знаков арифметических операций (+, -, *, /).

//Средствами C++: string/algorithm
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

void error (string message, int errorcode) { 
 //Выход с кодом errorcode и сообщением об ошибке message
 cout << endl << message;
 exit (errorcode);
}

int main() {
 string filename, line;
 cout << "Type the file name: ";
 getline(cin, filename); //Ввести имя файла
 ifstream file(filename);
 if (!file) { //Не удалось открыть файл
  error(string("Error opening input file"), 1);
 }
 size_t n = 0; //Номер строки
 while (getline(file, line)) { //Читаем файл построчно
  size_t cnt = count(line.begin(), line.end(), '*') +
   count(line.begin(), line.end(), '/') +
   count(line.begin(), line.end(), '+') +
   count(line.begin(), line.end(), '-'); //Считаем нужные символы через std::count
  cout << "String " << ++n << ": " << cnt << " operation(s)" << endl;
 }
 file.close();
 return 0;
}

8. Решить задачу 7 средствами языка C (cstdio/char *)

//Средствами C: cstdio/char *
#define _CRT_SECURE_NO_WARNINGS /*Отключаем в Studio предупреждение об "устаревших функциях"*/
#include <cstdlib>
#include <cstdio>
#include <cstring>

void error (const char * message, int errorcode) { 
 //Выход с кодом errorcode и сообщением об ошибке message
 printf ("\n%s", message);
 exit (errorcode);
}

int main() {
 char filename[80], c;
 printf ("Type the file name: ");
 scanf("%s",filename); //Ввести имя файла
 FILE *file = NULL;
 file = fopen (filename, "rt");
 if (!file) { //Не удалось открыть файл
  error("Error opening input file", 1);
 }
 size_t n = 0, cnt = 0; //Номер строки и счетчик символов
 //Так длина строки по условию не ограничена, будем читать файл посимвольно
 while (1) { //"Устойчивый" цикл чтения файла, не теряющий и не читающий дважды последний символ
  fscanf(file,"%c",&c);
  if (feof(file)) break; //Наступит после чтения последнего символа
  if (c == '\n') { //Кончилась строка - выводим информацию и меняем счётчики
   printf ("String %u: %u operation(s)\n", ++n, cnt);
   cnt = 0;
  }
  else if (strchr("+-*/", c)!=NULL) cnt++;
 }
 if (cnt) printf("String %u: %u operation(s)\n", ++n, cnt); 
  //В последней строке могли остаться необработанные символы
 fclose(file);
 return 0;
}

9. Проверить делимость большого натурального числа на 11.

Число делится на 11, если суммы цифр в чётных и нечётных позициях равны или отличаются на число, которое тоже делится на 11. От способа нумерации позиций результат зависеть не должен. "Большое число" представим строкой std::string.

#include <iostream>
#include <string>

bool isDiv11 (std::string num) {
 int n = num.length();
 long long unsigned next, odd_sum = 0, even_sum = 0;
 for (int i = 0; i < n; i++) {
  next = (long long unsigned)num[i] - '0';
  if (i % 2 == 0) odd_sum += next;
  else even_sum += next;
 }
 return ((odd_sum - even_sum) % 11 == 0);
}

int main() {
 std::cout << isDiv11("2547039") << std::endl; //1
 std::cout << isDiv11("13165648") << std::endl; //0
 return 0;
}

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

#include <algorithm>
#include <iostream>
#include <ostream>
#include <vector>
#include <tuple>

template <std::size_t> struct int_ {}; //тип для беззнакового целого

template <class Tuple, size_t Pos> //обёртки для std::get, чтобы получать индексы
std::ostream& print_tuple (std::ostream& out, const Tuple& t, int_<Pos>) {
 out << std::get < std::tuple_size<Tuple>::value - Pos >(t) << ", ";
 return print_tuple(out, t, int_<Pos - 1>());
}

template <class Tuple>
std::ostream& print_tuple (std::ostream& out, const Tuple& t, int_<1>) {
 return out << std::get <std::tuple_size<Tuple>::value - 1>(t);
}

template <class... Args> //вывод кортежа в поток
std::ostream& operator << (std::ostream& out, const std::tuple<Args...>& t) {
 out << '(';
 print_tuple(out, t, int_<sizeof...(Args)>());
 return out << ')';
}

template <class RI> //медиана
double median(RI beg, RI end) {
 if (beg == end) throw std::runtime_error("Range is empty");
 auto len = end - beg;
 auto m = len / 2;
 if (len % 2 == 1) return *(beg + m);
 return (beg[m - 1] + beg[m]) / 2.0;
}

template <class C> auto fivenum(C& c) { //основной метод
 std::sort(c.begin(), c.end());
 auto cbeg = c.cbegin();
 auto cend = c.cend();
 auto len = cend - cbeg;
 auto m = len / 2;
 auto lower = (len % 2 == 1) ? m : m - 1;
 double r2 = median(cbeg, cbeg + lower + 1);
 double r3 = median(cbeg, cend);
 double r4 = median(cbeg + lower + 1, cend);
 return std::make_tuple(*cbeg, r2, r3, r4, *(cend - 1));
}

int main() {
 using namespace std;
 vector<vector<double>> tests = { //Тесты из Вики
     { 0, 0, 1, 2, 63, 61, 27, 13 },
     { 1, 2, 3, 4, 20, 202, 392, 4, 38, 20 }
 };
 for (auto& c : tests) cout << fivenum(c) << endl;
 return 0;
}

11. Известно время начала и окончания работы автобусного маршрута с одним автобусом на линии (например, 6:30 и 23:00), а также протяженность маршрута в один конец и время отдыха на конечных остановках (в минутах). Напишите программу, которая составляет суточное расписание этого маршрута (моменты отправления с конечных пунктов) без учета времени на обед и пересмену.

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

int main() {
 int h1 = 6, m1 = 30, h2 = 23, m2 = 0, interval = 45, pause = 15;
 for (int t = h1 * 60 + m1; t <= h2 * 60 + m2; ) {
  int h = t / 60, m = t % 60;
  cout << setfill ('0') << setw(2) << h << ":" << m;
  t += interval;
  h = t / 60; m = t % 60;
  cout << " - " << setfill ('0') << setw(2) << h << ":" << m << endl;
  t += pause;
 }
 return 0;
}

12. Найти максимальные элементы строк матрицы.

#include <iostream>
using namespace std;

int main() {
 const int n = 3, m = 3;
 double a[n][m] = { 
  {11,2,3}, 
  {4,15,6}, 
  {17,8,9} 
 };
 for (int i = 0; i < n; i++) {
  double max = a[i][0];
  for (int j = 1; j < m; j++) {
   if (a[i][j] > max) max = a[i][j];
  }
  cout << "String " << (i+1) << ", max=" << max << endl;
 }
 return 0;
}

13. Сравнить точность вычислений при возведении вещественного числа в натуральную степень различными способами: 1) вычислением произведения в цикле; 2) вычислением с помощью стандартной функции возведения в степень; 3) вычислением с помощью стандартных функций экспоненты и натурального логарифма.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
 double x = 3, px = x; //число и контейнер для произведения
 int pw = 5; //показатель степени
 for (int p = 1; p < pw; p++) px *= x;
 cout << fixed << setprecision(15) << px << endl;
 cout << fixed << setprecision(15) << pow(x, pw) << endl;
 cout << fixed << setprecision(15) << exp(pw * log(x)) << endl;
 return 0;
}

14. Задана символьная матрица размерностью n x m. Определить количество различных элементов матрицы, считая повторяющиеся элементы один раз.

#include <iostream>
#include <vector>
#include <set>
#include <iterator>
#include <random>
#include <optional>

using namespace std;
using MatrixRow = vector<int>;
using Matrix = vector <MatrixRow>;

int main() {
 size_t rows, cols;
 cout << "Enter the number of rows and cols (space delimited): ";
 cin >> rows >> cols;
 Matrix matrix(rows, MatrixRow(cols));
 
 const int diap = 60; //Диапазон разброса случайных символов
 random_device rd;
 mt19937 gen(rd());
 uniform_int_distribution<int> dist(33, 33 + diap); //с 1-го символа после пробела
 auto rand = [dist, &gen]() { return dist(gen); };

 cout << "Matrix is" << endl;
 for (auto& row : matrix) {
  generate(row.begin(), row.end(), rand);
  copy(row.begin(), row.end(), ostream_iterator<char>(cout, " "));
  cout << endl;
 }

 set<int> uniqueElements;
 for (const auto& row : matrix) {
  uniqueElements.insert(row.begin(), row.end());
 }

 cout << endl << "List of unique elements is" << endl;
 copy(uniqueElements.begin(), uniqueElements.end(), ostream_iterator<char>(cout, " "));

 return 0;
}

15. Реализовать поиск образца в строке за линейное время. Применяем Z-алгоритм, только настоящий, а не то, о чём вы могли подумать в марте-2022.

#include <iostream>
using namespace std;

void getZarr(string str, int Z[]) { //Заполнить Z-массив для строки str
 int n = str.length();
 int L, R, k;
 // [L,R] определяет "окно", соответствующее префиксу из строки
 L = R = 0;
 for (int i = 1; i < n; ++i) {
  if (i > R) { // Если i>R, ничего не совпадает и Z[i] получается нативно:
   L = R = i;
   //Сначала R - L == 0, проверяем с индекса 0. Например, 
   //для строки "ababab" и i = 1, полчится R = 0 и Z[i] станет = 0. 
   //Для строки "aaaaaa" и i = 1, Z[i] и R станут == 5:
   while (R < n && str[R - L] == str[R]) R++;
   Z[i] = R - L;
   R--;
  }
  else {
   //k == i-L, поэтому соответствует числу, совпадающему с интервалом [L, R]:
   k = i - L;
   //Если Z[k] < оставшегося интервала, Z[i] == Z[k]. Например, str = "ababab", i = 3, R = 5 и L = 2:
   if (Z[k] < R - i + 1) Z[i] = Z[k];
   else {
    //Начинаем с R и проверяем вручную :
    L = i;
    while (R < n && str[R - L] == str[R]) R++;
    Z[i] = R - L;
    R--;
   }
  }
 }
}

void search(string text, string pattern) { //Вывести в консоль индексы выхождения pattern в text
 string str = pattern + "$" + text; //Просто узнать общую длину строки
 int l = str.length();
 int *Z = new int [l];
 if (!Z) throw std::runtime_error("Memory allocation error");
 getZarr(str, Z);

 for (int i = 0; i < l; ++i) {
  if (Z[i] == pattern.length())
   cout << "Found at index " << i - pattern.length() - 1 << endl;
 }
 delete [] Z;
}

int main() {
 string text = "Vdol' dorog ili porogov probegaet Nosorogov.";
 string pattern = "orog";
 search(text, pattern);
 return 0;
}

24.03.2022, 13:27 [704 просмотра]


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

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