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 просмотра]