10 не пригодившихся задач за октябрь 2021
Небольшой отрицательный рост количества задач в этой заметке по сравнению даже с предыдущей порцией обусловлен, конечно, происками врагов - приезжают к нам, ставят вакцины
воруют задачи, а потом в Гейропе справки покупают, что привиты Кембриджем!
Тем не менее, чтобы фарш не протухал и его покупали (в моём "супермаркете" путинский килограмм "домашнего" фарша, то есть, 700 грамм, в этом году стабильно превратился в 400 грамм при сохранении цены), скину лог сейчас, к календарному окончанию месяца.
Все программы выполнялись в консоли актуальной сборки Visual Studio 2019, для поиска на странице нужных слов нажимайте комбинацию клавиш Ctrl+F в браузере.
Темами для мини-исследований могут послужить задачи 3-4, 6, 7.
1. Представить строку std::string в однобайтовой кодировке ASCII как совокупность двоичных значений (байт).
#include <iostream>
#include <string>
using namespace std;
int main() {
string src = "ABCАБВ", dest;
for (size_t i = 0; i < src.size(); i++) {
for (unsigned char j = 0x80; j; j >>= 1)
dest += j & src[i] ? '1' : '0';
dest += " ";
}
cout << dest;
return 0;
}
2. Вывести расстояние от точки x до ближайшей границы интервала [k;l]. Если точка не принадлежит интервалу, расстояние выводится как отрицательное значение.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
double k = -2, l = 5, x = 2;
cout << min(x - k, l - x);
return 0;
}
3. Найти угол в градусах между часовой и минутной стрелками на 12-часовом циферблате.
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
double hh = 6, mm = 16.36; //Исходное время в часах и минутах
double hour_angle = 0.5 * (hh * 60 + mm);
double minute_angle = 6 * mm;
double angle = abs (hour_angle - minute_angle);
angle = min (360 - angle, angle);
cout << angle;
return 0;
}
Если округлять минуты до целых, вот примерное время, когда угол между стрелками будет 90 градусов. Всего 44 раза в сутки.
struct hm { size_t h,m; };
hm tm[] = {
{00,16}, {00,49}, {01,22}, {01,55}, {02,27}, {03,00}, {03,33}, {04,05}, {04,38}, {05,11},
{05,44}, {06,16}, {06,49}, {07,22}, {07,55}, {08,27}, {09,00}, {09,33}, {10,05}, {10,38},
{11,11}, {11,44}, {12,16}, {12,49}, {13,22}, {13,55}, {14,27}, {15,00}, {15,33}, {16,05},
{16,38}, {17,11}, {17,44}, {18,16}, {18,49}, {19,22}, {19,55}, {20,27}, {21,00}, {21,33},
{22,05}, {22,38}, {23,11}, {23,44}
};
4. По заданному натуральному углу между часовой и минутной стрелками (от 0 до 180 градусов) найти все комбинации значений часов и минут, когда угол между стрелками составляет заданную натуральную величину u (от 0 до 180 градусов).
Так как решение задачи сводится к невозможному в общем виде решению диофантова уравнения вида 2*u = 60*h - 11*m, где u - заданный угол между стрелками в градусах, h и m - неизвестные часы и минуты, кроме того, заданный угол почти всегда достигается не в целое значение минут (см. предыдущую задачу), остановимся пока на таком вот переборном решении с "допуском" в 3 минуты.
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
size_t calcAngle(size_t hh, size_t mm) {
double hour_angle = 0.5 * (hh * 60. + mm);
double minute_angle = 6. * mm;
double angle = abs(hour_angle - minute_angle);
return abs((long)angle) % 180;
}
int main() {
double hh = 0, mm = 12; //Исходное время в часах и минутах
size_t s = 90; //Требуемый угол между стрелками в градусах, от 0 до 180
size_t k = 0;
for (size_t h = 0; h < 24; h++)
for (size_t m = 0; m < 60; m++) {
size_t u = calcAngle(h, m);
if (abs((long)(s-u)) < 4)
cout << setfill(' ') << setw(3) << ++k << " " <<
setfill('0') << setw(2) << h << ":" << setw(2) << m << " " << u << endl;
//Вывести счетчик, затем время с лидирующими нулями и угол
}
return 0;
}
5. Написать функцию для выделения памяти под массив целых значений с помощью malloc. Функция принимает два аргумента - указатель и размерость массива и имеет тип void, то есть, ничего не возвращает. После работы функции в указателе должен сохраниться адрес начала созданного массива.
#include <cstdlib>
#include <iostream>
void custom_malloc(int *&array, const size_t size) {
array = static_cast<int*>(std::malloc(size * sizeof(int)));
}
int main() {
int *array = nullptr;
const int n = 10;
custom_malloc (array, n);
for (int i = 0; i < n; i++) {
array[i] = i + 1;
std::cout << array[i] << ' ';
}
return 0;
}
6. Заменить в заданном числе одну цифру так, чтобы новое число делилось на 3 и было максимально возможным. Алгоритм решения пытается быть быстрым, а можно ли лучше?
#include <iostream>
#include <numeric>
int main() {
std::string n("371");
int sum = std::accumulate(n.begin(), n.end(), 0,
[](int i, int v) { return i + v - '0'; });
int val = 3 - sum % 3;
bool b = false;
for (auto& it : n) {
if (it - '0' + val > 9) continue;
it += val;
while (it - '0' + 3 <= 9) it += 3;
b = true;
break;
}
if (!b) n.back() -= val % 3 != 0 ? 3 - val : val;
std::cout << n;
return 0;
}
7. Нарисовать в текстовой консоли Windows цветной рисунок по образцу (попугай).
цветной попугай для консоли
Мы интерпретировали рисунок как массив структур {x, y, c}, где (x,y) - столбец и строка в консоли (нумеруются с нуля), c - код цвета для консоли. Установлена кодовая страница DOS-866, чтобы пользоваться символом псевдографики-"квадратиком" с кодом 219.
#include <iostream>
#include <windows.h>
using namespace std;
void SetColor(int background, int text) {
HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdOut, (WORD)((background << 4) | text));
}
void gotoxy(int xp, int yp) {
COORD new_xy; HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
new_xy.X = xp; new_xy.Y = yp;
SetConsoleCursorPosition(hStdOut, new_xy);
}
int main() {
SetConsoleCP (866);
SetConsoleOutputCP (866);
SetColor (15,0);
system("cls");
system("mode con cols=80 lines=25");
struct node { int x,y,c; };
const node parrot[] = {
{ 6, 0, 0},{ 7, 0, 0},{ 8, 0, 0},{ 9, 0, 0},
{ 4, 1, 0},{ 5, 1, 0},{ 6, 1,12},{ 7, 1,12},{ 8, 1,12},{ 9, 1,12},{10, 1, 0},{11, 1, 0},
{ 3, 2, 0},{ 4, 2,12},{ 5, 2,12},{ 6, 2,12},{ 7, 2,12},{ 8, 2,12},{ 9, 2,12},{10, 2,12},{11, 2,12},{12, 2, 0},
{ 2, 3, 0},{ 3, 3,12},{ 4, 3,12},{ 5, 3,12},{ 6, 3,12},{ 7, 3,12},{ 8, 3,12},{ 9, 3,12},{10, 3,12},{11, 3,12},{12, 3,12},{13, 3,0},
{ 2, 4, 0},{ 3, 4,12},{ 4, 4,12},{ 5, 4,12},{ 6, 4,12},{ 7, 4,12},{ 8, 4,12},{ 9, 4,12},{10, 4,12},{11, 4,12},{12, 4,12},{13, 4,0},
{ 1, 5, 0},{ 2, 5,12},{ 3, 5,15},{ 4, 5,15},{ 5, 5,12},{ 6, 5,12},{ 7, 5,12},{ 8, 5,12},{ 9, 5,12},{10, 5,12},{11, 5,15},{12, 5,15},{13, 5,12},{14, 5, 0},
{ 1, 6, 0},{ 2, 6,15},{ 3, 6,15},{ 4, 6,15},{ 5, 6,15},{ 6, 6,12},{ 7, 6,12},{ 8, 6,12},{ 9, 6,12},{10, 6,15},{11, 6,15},{12, 6,15},{13, 6,15},{14, 6, 0},
{ 1, 7, 0},{ 2, 7,15},{ 3, 7,15},{ 4, 7, 0},{ 5, 7,15},{ 6, 7,12},{ 7, 7,12},{ 8, 7,12},{ 9, 7,12},{10, 7,15},{11, 7, 0},{12, 7,15},{13, 7,15},{14, 7, 0},
{ 1, 8, 0},{ 2, 8,12},{ 3, 8,15},{ 4, 8,15},{ 5, 8,15},{ 6, 8,12},{ 7, 8,12},{ 8, 8,12},{ 9, 8,12},{10, 8,15},{11, 8,15},{12, 8,15},{13, 8,12},{14, 8, 0},
{ 2, 9, 0},{ 3, 9,12},{ 4, 9,12},{ 5, 9,15},{ 6, 9, 0},{ 7, 9, 0},{ 8, 9, 0},{ 9, 9, 0},{10, 9,15},{11, 9,12},{12, 9,12},{13, 9, 0},
{ 2,10, 0},{ 3,10,12},{ 4,10,12},{ 5,10,12},{ 6,10, 0},{ 7,10, 0},{ 8,10, 0},{ 9,10, 0},{10,10,12},{11,10,12},{12,10,12},{13,10, 0},
{ 3,11, 0},{ 4,11,12},{ 5,11,12},{ 6,11,12},{ 7,11, 0},{ 8,11, 0},{ 9,11,12},{10,11,12},{11,11,12},{12,11,0},
{ 2,12, 0},{ 3,12,14},{ 4,12,12},{ 5,12,12},{ 6,12,12},{ 7,12,12},{ 8,12,12},{ 9,12,12},{10,12,12},{11,12,12},{12,12,14},{13,12, 0},
{ 1,13, 0},{ 2,13, 1},{ 3,13,14},{ 4,13,12},{ 5,13,12},{ 6,13,12},{ 7,13,12},{ 8,13,12},{ 9,13,12},{10,13,12},{11,13,12},{12,13,14},{13,13, 1},{14,13, 0},
{ 1,14, 0},{ 2,14, 1},{ 3,14, 1},{ 4,14,12},{ 5,14,12},{ 6,14,12},{ 7,14,12},{ 8,14,12},{ 9,14,12},{10,14,12},{11,14,12},{12,14, 1},{13,14, 1},{14,14, 0},
{ 1,15, 0},{ 2,15, 1},{ 3,15, 1},{ 4,15,12},{ 5,15,12},{ 6,15,12},{ 7,15,12},{ 8,15,12},{ 9,15,12},{10,15,12},{11,15,12},{12,15, 1},{13,15, 1},{14,15, 0},
{ 1,16, 0},{ 2,16, 1},{ 3,16, 0},{ 4,16,12},{ 5,16,12},{ 6,16,12},{ 7,16, 0},{ 8,16, 0},{ 9,16,12},{10,16,12},{11,16,12},{12,16, 0},{13,16, 1},{14,16, 0},
{ 0,17, 6},{ 1,17, 6},{ 2,17, 0},{ 3,17, 6},{ 4,17, 0},{ 5,17, 0},{ 6,17, 0},{ 7,17, 6},{ 8,17, 6},{ 9,17, 0},{10,17, 0},{11,17, 0},{12,17, 6},{13,17, 0},{14,17, 6},{15,17, 6},
{ 0,18, 6},{ 1,18, 6},{ 2,18, 6},{ 3,18, 6},{ 4,18, 6},{ 5,18, 6},{ 6,18, 6},{ 7,18, 6},{ 8,18, 6},{ 9,18, 6},{10,18, 6},{11,18, 6},{12,18, 6},{13,18, 6},{14,18, 6},{15,18, 6},
{ 0,19, 6},{ 1,19, 6},{ 2,19, 6},{ 3,19, 6},{ 4,19, 6},{ 5,19, 6},{ 6,19, 6},{ 7,19, 6},{ 8,19, 6},{ 9,19, 6},{10,19, 6},{11,19, 6},{12,19, 6},{13,19, 6},{14,19, 6},{15,19, 6},
{ 5,20, 0},{ 6,20,12},{ 7,20,12},{ 8,20,12},{ 9,20,12},{10,20, 0},
{ 6,21, 0},{ 7,21,12},{ 8,21,12},{ 9,21, 0}
};
int size = sizeof(parrot)/sizeof(parrot[0]);
unsigned char fill = 219;
for (int i=0; i < size; i++) {
SetColor(15, parrot[i].c);
gotoxy (parrot[i].x, parrot[i].y);
cout << fill;
}
SetColor(15,0);
gotoxy (0,22);
system("pause");
return 0;
}
Как насчёт более удобного формата данных для этой задачи? Например, я бы посмотрел в сторону Tiled map editor с последующей интерпретацией его файлов.
8. Написать функцию, которая принимает в качестве аргументов другую функцию и положительное целое число. Последняя функция выполняется количество раз, равное целому числу.
#include <iostream>
template <typename Function>
void repeat(Function f, unsigned int n) {
for (unsigned int i = n; 0 < i; i--)
f();
}
void example() {
std::cout << "Example\n";
}
int main() {
repeat(example, 4);
repeat([] {std::cout << "Example\n"; }, 4); //работает начиная с C++11
return 0;
}
9. Написать функцию, дублирующую заданную первым аргументом строку std::string указанное вторым аргументом количество раз.
#include <string>
#include <iostream>
std::string repeat(const std::string& word, int times) {
std::string result;
result.reserve(times * word.length());
//избегать повторного перераспределения памяти
for (int a = 0; a < times; a++)
result += word;
return result;
}
int main() {
std::cout << repeat("Foo", 5) << std::endl;
return 0;
}
10. Строка с повторами. Задана std::string, состоящая из символов нулей и единиц. Определить, является ли она строкой, в которой последовательность первых N символов повторяется как минимум дважды. Исходная строка может быть усечена справа до размерности, соответствующей двум или более вхождениям подстроки. В случае неоднозначности учитывается самая длинная из возможных подстрок, например, в строке "1010101010" дважды повторяется фрагмент "1010", но не пять раз фрагмент "10".
#include <iostream>
#include <string>
#include <vector>
#include <regex>
bool is_repstring(const std::string& teststring, std::string& repunit) {
std::string regex("^(.+)\\1+(.*)$");
std::regex e(regex);
std::smatch what;
if (std::regex_match(teststring, what, e)) {
std::string firstbracket(what[1]);
std::string secondbracket(what[2]);
if (firstbracket.length() >= secondbracket.length() &&
firstbracket.find(secondbracket) != std::string::npos) {
repunit = firstbracket;
}
}
return !repunit.empty();
}
int main() {
std::vector<std::string> teststrings{
"1001110011",
"1110111011",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"00",
"1"
};
std::string theRep;
for (std::string myString : teststrings) {
std::cout << myString << ": ";
if (is_repstring(myString, theRep)) std::cout << " YES (" << theRep << ")";
else std::cout << " NO";
std::cout << std::endl;
theRep.clear();
}
return 0;
}
Результаты вывода программы:
1001110011: YES (10011) 1110111011: YES (1110) 1010101010: YES (1010) 1111111111: YES (11111) 0100101101: NO 0100100: YES (010) 101: NO 00: YES (0) 1: NO
31.10.2021, 10:43 [660 просмотров]