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

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

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

1. Заданы 2 целочисленных матрицы одинакового размера. Вывести только те элементы, которые встречаются в каждой из матриц. Не использовать больше двух вложенных циклов.

Учтём тот факт, что элементы матрицы последовательно упорядочены в памяти по строкам.

#include <iostream>
using namespace std;

int main() {
 const int n = 3, m = 3;
 int a[n][m] = {
  {1,2,3},{4,15,6},{7,8,9}
 },
  b[n][m] = {
  {1,12,13},{2,15,16},{17,18,9}
 };
 int* pa = &a[0][0], * pb = &b[0][0];
 cout << endl;
 for (int i = 0; i < n * m; i++) {
  int* pb0 = pb;
  for (int i = 0; i < n * m; i++) {
   if (*pa == *pb0++) {
    cout << *pa << " ";
    break;
   }
  }
  pa++;
 }
 cin.get();
 return 0;
}

2. Составить программу, которая вводит составные части структуры данных, приведённой в задании, как десятичные числа и формирует из них заданную упакованную структуру как 16-ричное число. Программа выводит упакованную структуру как 16-ричное число и значения отдельных её составных частей как десятичные числа.

структура
структура
#include <iostream> 
#include <iomanip>
#include <bitset>
using namespace std;

struct profile { //структура с битовыми полями
 unsigned short int g:8, s:4, p:1, reserved:3;
};

int main() {
 profile my;
 unsigned short int g, s, p;
 cout << "G from [0;255] ="; cin >> g;
 cout << "S from [0;15] ="; cin >> s;
 cout << "P from [0;1] ="; cin >> p;
  //вводим части структуры (без проверки правильности)
 my.g = g;
 my.s = s;
 my.p = p;
  //заполняем битовые поля структуры
 unsigned short int number = (my.g << 8 | my.s << 4 | my.p << 3) & 0xfff8;
  //формируем и выводим структуру как 16-ричное число
 cout << hex << number;
  //проверка в двоичном виде
 bitset<16> set(number);
 cout << endl << "Binary: " << set.to_string();
  //вводим 16-ричное
 cout << endl << "Hex from 4 digits ="; cin >> hex >> number;
  //извлекаем битовые поля
 my.g = (number & 0xff00) >> 8;
 my.s = (number & 0x00f0) >> 4;
 my.p = (number & 0x0008) >> 3;
  //выводим как обычные числа
 cout << dec << my.g << " " << dec << my.s << " " << dec << my.p;
 cin.get();
 return 0;
}

3. Найти периметр многоугольника на плоскости. Вершины описаны как vector <pair <double, double>>

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

int main(void) {
 vector <pair <double, double>> v;
 v.push_back(make_pair(0, 0));
 v.push_back(make_pair(4, 0));
 v.push_back(make_pair(4, 3));
 size_t n = v.size();
 double len = sqrt(pow(v[0].first - v[n -1].first, 2) + pow(v[0].second - v[n-1].second, 2));
 for (size_t i = 0; i < n - 1; i++) {
  double x1 = v[i].first, y1 = v[i].second,
   x2 = v[i + 1].first, y2 = v[i + 1].second;
  len += sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
 }
 cout << fixed << len;
  //12; тест на пифагоровом треугольнике
 cin.get(); return 0;
}

4. С начала отсчёта прошло N секунд. Вывести текущее время отсчёта в формате hh:mm:ss

#include <iostream>
using namespace std;

int main() {
 size_t n, h, m, s;
 cout << "N= ";
 cin >> n;
 if (!cin.good()) {
  cout << "Bad data, please input integer positive value";
  return -1;
 }
 h = n / 3600;
 m = n / 60 % 60;
 s = n % 60;
 cout << h / 10 << h % 10 << ":" << m / 10 << m % 10 << ":" << s / 10 << s % 10;
 return 0;
}

5. Определить класс-строку. В класс включить два конструктора: для определения класса строки строкой символов и копированием другой строки (объекта класса строки). Определить операторы / для поиска количества вхождений подстроки в строку, == для сравнения строк и << для вывода объекта строки в консоль.

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

class String {
 string data;
public:
 String (string _data) {
  data = _data;
 }
 String (String& _data) {
  data = _data.data;
 }
 size_t operator / (string s) {
  size_t n = 0;
  string::size_type p = 0;
  while ((p = this->data.find(s, p)) != string::npos) {
   p++;
   n++;
  }
  return n;
 }
 bool operator == (String& _data) {
  return this->data == _data.data;
 }
 friend ostream& operator << (ostream& os, String & _data) {
  os << endl << _data.data;
  return os;
 }
};

int main() {
 String s1("Hello");
 cout << s1;
 String s2(s1);
 cout << s2;
 cout << endl << s1 / "l"; //2
 cout << endl << (s1 == s2); //1
 return 0;
}

6. Заполнить список std::list случайными целыми числами из заданного диапазона [a;b]. Найти в списке некоторый элемент, и, если он встречается, вставить после него копию элемента.

#include <iostream>
#include <list>
#include <ctime>
#include <cstdlib>
using namespace std;

int main() {
 list <int> myList; // объявляем пустой список
 srand(time(NULL));
 const int a = 5, b = 15;
 for (int i = 0; i < 15; i++) {
  myList.push_back(a + rand() % (b - a + 1)); 
   // добавляем в список новые элементы из диапазона [a;b]
 }
 cout << "List 1: ";
 copy(myList.begin(), myList.end(), ostream_iterator<int>(cout, " "));
 
 //Просто для примера, взяли из list последний элемент для поиска
 //Можно было ввести или задать число: int val = 10;
 auto last = end(myList);
 int val = *(prev(last)); 

 for (auto it = myList.begin(); it != myList.end(); it++) {
  if (*it == val) { //если val найдена в списке
   myList.insert(++it, val); //вставить после нее ещё одну val
   break;
  }
 }

 cout << endl << "List 2: ";
 copy(myList.begin(), myList.end(), ostream_iterator<int>(cout, " "));

 return 0;
}

7. Реализовать рекурсивную функцию для вычисления по формуле вида КОРЕНЬ(1+КОРЕНЬ(2+КОРЕНЬ(3+КОРЕНЬ(4+КОРЕНЬ(5)))))

#include <iostream>
#include <cmath>

double sqrt_summa(int n, int s) {
 return sqrt (s + (s < n - 1 ? sqrt_summa(n, s + 1) : sqrt(n)));
}

int main() {
 std::cout << sqrt_summa(5, 1);
 return 0;
}

8. Задан массив с названиями цветов радуги. Вывести названия k цветов радуги, начиная с цвета номер n.

#include <iostream>
#include <string>

int main() {
 std::string colors[7] = { "Red", "Orange", "Yellow", "Green", "Blue", "Indigo", "Violet" };
 int n = 3, k = 2; //Нумерация в C++ с нуля!
 for (int i = n; i < n + k; i++) {
  std::cout << std::endl << colors[i];
 }
 return 0;
}

9. Отсортировать элементы вектора std::vector и убрать повторы элементов.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
 int my_nums[] = { 10, 40, 20, 10, 30, 50, 30, 10 };
 int n = sizeof(my_nums) / sizeof(my_nums[0]);
  //Ещё один способ узнать не заданную явно длину массива
 vector <int> my_vec(my_nums, my_nums + n);
  //...и инициализировать этим массивом вектор
 sort(my_vec.begin(), my_vec.end());
  //Стандартная сортировка
 vector <int>::iterator it; 
  //Создаём итератор для типа данных своего вектора
 it = unique(my_vec.begin(), my_vec.end());
  //Стандартная фильтрация повторяющихся элементов
 my_vec.resize(distance(my_vec.begin(), it));
  //Убиваем "хвост" из лишних элементов, фильтрация этого не сделала
 for (it = my_vec.begin(); it != my_vec.end(); ++it)
  cout << *it << " "; 
  //Типовой вывод в консоль с помощью итератора
 cin.get(); return 0;
}

10. Организовать "новый" контейнер STL, описав матрицу как вектор векторов.

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

int main(void) {
 const int n = 3, m = 4;
 vector <vector <double>> matrix(n, vector<double>(m));
  //Вектор, состоящий из векторов double, инициализовали
  //n элементами, каждый из которых - вектор из m элементов.
  //Получилась матрица n * m
 for (int i = 0; i < n; i++) {
  cout << endl;
  for (int j = 0; j < m; j++) {
   matrix[i][j] = i + j;
   cout << setw(5) << matrix[i][j];
  }
 }
 cin.get(); return 0;
}

11. Оля задала Васе такую загадку. Она загадала некоторое число x, в котором было как минимум две цифры. Затем она отрезала от числа x последнюю цифру, и получила число y. Далее она сложила x и y и получила число z. Она просит Васю по данному числу z определить, какое было исходное число x. Помогите Васе решить эту загадку.

Входные данные - число z, выходные данные - число x.

#include <iostream>
 
int main() {
 unsigned long long z = 42;
 std::cout << (z - (z - 10)/11 - 1);
 return 0;
}

12. Реализовать функцию инвертирования K бит исходной битовой последовательности размером N, начиная с T бита. Нулевой позицией считается старший бит первого байта. Обязательно использование поразрядных операций для выполнения задания, математические операции с индексами и счётчиками разрешены.

#include <iostream>
#include <bitset>
#include <sstream>

unsigned int invert (unsigned int a, size_t t, size_t k, size_t n) {
 if (t > n - 1) t = n - 1;
 if (t + k > n) k = n - t - 1;
 for (size_t i = t; i < t + k; i++) a ^= 1 << (n - 1 - i);
 return a;
}

template <typename T> static std::string toBinaryString (const T& x) {
 std::stringstream ss;
 ss << std::bitset<sizeof(T) * 8>(x);
 return ss.str();
}

int main() {
 unsigned int b = 0xFF, a = invert(b, 3, 7, sizeof(b) * 8);
 std::cout << toBinaryString(b) << std::endl << toBinaryString(a);
 return 0;
}

Вывод этого примера:

00000000000000000000000011111111
00011111110000000000000011111111

Заодно в коде показана шаблонная функция печати числа в двоичном виде, отсутствующая в списке стандартных форматов std::cout.

13. Найти все перестановки букв слова, сохранённого в строке std::string.

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

int main() {
 string s("State"); //Очередное слово
 vector <char> v(s.begin(), s.end());
 int len = v.size();
 size_t k = 0;
 //Сортируем буквы, не различая строчных и прописных:
 sort (v.begin(), v.end(), 
  [](const char& a, const  char& b) { return tolower(a) < tolower(b); }
 );
 //Ищем перестановки:
 do {
  string next_variant(v.begin(), v.end()); //Очередной вариант слова
  cout << setw(6) << (++k) << "  " << next_variant << endl;
 } while (next_permutation(v.begin(), v.end(), 
    [](const char & a, const  char & b) { return tolower(a) < tolower(b); }
   ));
 cin.get(); return 0;
}

14. Реализовать шаблонный класс "Матрица" со следующими возможностями:

  • реализация хранения данных с помощью контейнеров STL (сделано на std::vector, но на std::array было бы лучше);
  • возможность обращения к элементам матриц через переопределённые двойные квадратные скобки [][] (реализовано в помощью вспомогательного класса MatrixRow);
  • реализация умножения матрицы на число в "две стороны", в виде A * 2 и 2 * A;
  • реализация умножения двух матриц и её проверка на матрицах различных размерностей;
  • вывод матрицы в консоль с помощью переопределённого оператора <<

В отличие от примера 10, код инкапсулирован в класс. Дополнительные пояснения есть в коде.

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

template <typename T> class Matrix {
 size_t mRows, mCols; //Размерности
 vector <vector<T>> mData; //Данные, ещё лучше было применить std::array
public:
 Matrix(size_t rows, size_t cols) : mRows(rows), mCols(cols),
  mData(rows, vector<T>(cols)) { //Основной конструктор
 }
 Matrix(const Matrix& op2) : mRows(op2.mRows), mCols(op2.mCols) { //Конструктор копирования
  mData = op2.mData;
 }
 Matrix& operator = (const Matrix& op2) { //Оператор =
  if (this != &op2) {
   mRows = op2.mRows;
   mCols = op2.mCols;
   mData = op2.mData;
  }
  return *this;
 }
 Matrix operator * (const double src) { //Умножение на число справа, A * 2
  Matrix dest(mRows, mCols);
  for (size_t i = 0; i < mRows; i++)
   for (size_t j = 0; j < mCols; j++)
    dest.mData[i][j] = mData[i][j] * src;
  return dest;
 }
 Matrix operator * (const Matrix& b) { //Умножение матриц
  if (mCols != b.mRows) return *this;
  Matrix c(mRows, b.mCols);
  for (size_t i = 0; i < mRows; i++) {
   for (size_t j = 0; j < b.mCols; j++) {
    c[i][j] = 0;
    for (size_t k = 0; k < mCols; k++)
     c[i][j] += mData[i][k] * b.mData[k][j];
   }
  }
  return c;
 }
 class MatrixRow { //Встроенный служебный класс "строка матрицы",
                   //служит для двойного индексирования [][]
  Matrix& _matr;
  size_t _row;
 public:
  MatrixRow(Matrix& _m, size_t row) : _matr(_m), _row(row) {}
  MatrixRow(T* _arr) : _row(_arr) {}
  T& operator [] (size_t _col) { return _matr.mData[_row][_col]; }
 };
 MatrixRow operator [] (size_t index) {
  return MatrixRow(*this, index);
 }
 friend ostream& operator << (ostream& os, const Matrix& _a) { //Вывод в консоль
  os.precision(2);
  for (size_t i = 0; i < _a.mRows; i++) {
   os << endl;
   for (size_t j = 0; j < _a.mCols; j++) {
    os << fixed << setw(8) << _a.mData[i][j];
   }
  }
  return os;
 }
 template <typename T> friend Matrix <T> operator * (const double src, const Matrix <T>& op2);
 //Умножение на число слева
};

template <typename T> Matrix <T> operator * (const double src, const Matrix <T>& op2) {
 //Умножение на число слева, 2 * A, членом класса не сделать, 
 //т.к. слева от бинарной операции должен быть объект класса.
 //Можно было не делать friend, если бы были методы-геттеры для доступа 
 //к приватным свойствам класса.
 Matrix <T> dest(op2.mRows, op2.mCols);
 for (size_t i = 0; i < op2.mRows; i++)
  for (size_t j = 0; j < op2.mCols; j++)
   dest.mData[i][j] = src * op2.mData[i][j];
 return dest;
}

int main() {
 const int n = 2, m = 2;
 Matrix <double> a(n, m);
 for (size_t i = 0; i < n; i++)
  for (size_t j = 0; j < m; j++)
   a[i][j] = (double)(1 + i + j);
 cout << "A" << a << endl;
 Matrix <double> b = 2 * a;
 cout << "B=2*A" << b << endl;
 Matrix <double> c = a * b;
 cout << "C=A*B" << c << endl;
 Matrix <double> d(2, 2);
 d = a * 4;
 cout << "D=A*4" << d << endl;
 Matrix <double> e(3, 2);
 for (size_t i = 0; i < 3; i++)
  for (size_t j = 0; j < 2; j++)
   e[i][j] = (double)(10 - i - j);
 cout << "E" << e << endl;
 Matrix <double> f(2, 3);
 for (size_t i = 0; i < 2; i++)
  for (size_t j = 0; j < 3; j++)
   f[i][j] = (double)(i + j);
 cout << "F" << f << endl;
 Matrix <double> g = e * f;
 cout << "G=E*F" << g << endl;
 cin.get(); return 0;
}

30.04.2021, 22:30 [372 просмотра]


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