22 не пригодившихся задачи за начало 2018 года
Весьма и бесплатно занят, почти нет времени на бложеки и жизнь. Но "не пригодившихся" задач что-то давно не было, так что выберу время скинуть накопившиеся учебные программки за начало года.
Задачи, как обычно, очень разные - от совсем простых до более-менее интересных. Все программы проверены в консоли Visual Studio 2015 и написаны на C++.
1. Дано трёхзначное число. Используя одну операцию деления нацело, вывести первую цифру данного числа (количество сотен).
#include <iostream> int main () { int n = 345; std::cout << n/100; system("pause>nul"); return 0; }
2. Для заданного целого числа n вычислить сумму ряда
сумма ряда
#include <iostream> int main () { int n = 10; double s = 0; for (int i=1; i<n; i++) s+=100./(i*i)+3*i; std::cout << s; system("pause>nul"); return 0; }
3. Найти произведение элементов ряда по заданной формуле:
P = (1-1/2)*(1-1/4)*...*(1-1/(2*n))
#include <iostream> int main () { int n = 10; double p = 1; for (int i=1; i<=n; i++) p *= 1-1/(2.*i); std::cout << p; system("pause>nul"); return 0; }
4. Птицы летят клином: в 1-м ряду —1 птица, во 2-м ряду — 3 птицы, в 3-м ряду — 5 птиц и т.д. Сколько птиц летит в 11 ряду? Сколько всего птиц летит в 11 рядах?
#include <iostream> int main () { int all = 0; for (int n=1; n<=11; n++) all += 2*n-1; std::cout << "11 column=" << 2*11-1 << std::endl << "All=" << all; system("pause>nul"); return 0; }
Ну или просто без цикла:
#include <iostream> int main() { constexpr int N = 11, an = 2 * N - 1; std::cout << an << " " << (1 + an) * N / 2 << std::endl; system("pause>nul"); return 0; }
Ответы - 21 и 121 птица
5. Дано количество покупателей n, количество касс m и массив T, i-ый элемент которого равен количеству минут, за которое i-ая касса обслуживает одного покупателя.
В предположении, что любой покупатель занимает любую свободную кассу, найти минимальное количество времени, за которые можно обслужить всех покупателей.
Думаю, цепи Маркова тут ни к чему, достаточно минимума и максимума.
#define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; int minNumber(int T[], int Tbusy[], int m) { //Номер минимальной по времени обслуживания не занятой кассы int mNumber = -1, min = INT_MAX; for (int i = 0; i < m; i++) { if (Tbusy[i] == 0 && T[i] < min) { min = T[i]; mNumber = i; } } return mNumber; } int maximum(int T[], int m) { //Максимум в массиве int max = T[0]; for (int i = 0; i < m; i++) if (T[i]>max) max = T[i]; return max; } int main() { int n = 100; //клиентов const int m = 8; //касс int T[m] = {3,3,2,2,3,4,1,1}; //время обслуживания каждой из касс int Tbusy[m] = { 0,0,0,0,0,0,0,0 }; //состояние "свободно-занято" для касс int time = 0; if (n <= m) time = maximum(T, m); //Если клиентов не больше, чем касс - просто берем самое долгое время обслуживания else { while (n) { int number; do { number = minNumber(T, Tbusy, m); if (number != -1) { Tbusy[number] = T[number]; n--; } } while (number != -1 && n > 0); //Пока не все обслужены и есть свободные кассы time++; //прошла минута if (n == 0) { time += maximum(Tbusy, m); //добавить время, пока с последней кассы не уйдет последний клиент break; } cout << endl << "Time=" << time << ", state="; for (int i = 0; i < m; i++) cout << Tbusy[i] << " "; for (int i = 0; i < m; i++) { //изменить текущее время обслуживания занятых касс if (Tbusy[i] > 0) Tbusy[i]--; } } } cout << endl << "Total time=" << time; cin.sync(); cin.get(); return 0; }
6. Создать шаблон функции для сортировки числового массива и проверить его на 2 различных типах данных.
#include <iostream> using namespace std; template <typename T> void swp(T &a, T &b) { T c = a; a = b; b = c; } template <typename T> void sort(T v[], int n) { for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) if (v[i]>v[j]) swp(v[i], v[j]); } template <typename T> void print(T v[], int n) { cout << endl; for (int i = 0; i < n; i++) cout << v[i] << " "; } int main() { int a[] = { 5,3,4,2,1 }; sort(a,5); print(a,5); double b[] = { 35.12,-3,-14.7,8.9 }; sort(b, 4); print(b, 4); cin.sync(); cin.get(); return 0; }
7. Задан вектор a из элементов <pair<int, int>>. Удалить все повторяющиеся по первому полю пары значений.
#include <iostream> #include <vector> #include <unordered_set> #include <algorithm> using namespace std; using IntPair = pair<int, int>; void cleanDuplicates (vector <IntPair> &vec) { unordered_set <int> distinct; auto it = remove_if (begin(vec), end(vec), [&distinct](const IntPair& p) { return !distinct.insert(p.first).second; }); vec.erase(it, end(vec)); } int main() { vector <pair<int, int>> a; a.push_back(make_pair(1, 2)); a.push_back(make_pair(2, 1)); a.push_back(make_pair(2, 2)); a.push_back(make_pair(1, 3)); a.push_back(make_pair(3, 3)); cleanDuplicates (a); //вывод вектора из элементов <pair<int, int>> (С++11) for (const auto& p : a) { cout << p.first << ", " << p.second << endl; } system("pause >nul"); return 0; }
8. Имеется класс Apple, описывающий яблоко и класс applesArray, описывающий массив яблок.
В классе Apple предусмотреть методы, определяющие, упало ли яблоко и съедание определённой в процентах части яблока, свойства - цвет яблока, статус (упало с дерева или нет), доля съеденного. Когда яблоко съедено, оно удаляется из массива яблок.
Примечательно в коде - как передавать перечисление enum в качестве аргумента конструктора класса.
Если оператор [] обращается к недопустимому номеру яблока, возвращается новое "пустое" яблоко.
#include <iostream> #include <string> #include <vector> using namespace std; class Apple { public: enum statuses { EMPTY, HANGING, FALLING }; private: string color; statuses status; int eated; int min (int a,int b) { return (a<b ? a : b); } string getStatus() { string statusStr[] = {"EMPTY","HANGING","FALLING"}; return statusStr[this->status]; } public: void fall() { this->status = FALLING; } int eat(int ps = 0) { if (this->status == FALLING) this->eated += min(100 - this->eated, ps); return 100 - this->eated; } Apple::Apple(string color, Apple::statuses status=HANGING) { this->color = color; this->status = status; this->eated = 0; } string Apple::get() { return "("+color+", "+this->getStatus()+", "+to_string(this->eated)+")"; } }; class applesArray { vector <Apple> apples; public: applesArray::applesArray() { } void applesArray::put(Apple a) { this->apples.push_back(a); } void applesArray::print() { int len = this->size(); for (int i = 0; i<len; i++) { if (this->apples[i].eat()==0) { this->apples.erase(this->apples.begin()+i); i--; len--; cout << endl << "Eated!"; } else cout << endl << this->apples[i].get(); } cout << endl << "Total size: " << len << " item(s)"; } const int applesArray::size () { return this->apples.size(); } Apple & applesArray::operator [] (int index) { if (index > -1 && index < this->size()) return this->apples[index]; return *(new Apple("empty",Apple::EMPTY)); } }; int main() { applesArray a; a.put(*(new Apple("green"))); //передаём объект в push_back a.put(*(new Apple("red"))); a.put(*(new Apple("yellow"))); a.print(); a[0].fall(); a[0].eat(25); a[1].eat(20); //не выйдет, не упало a.print(); a[2].fall(); a[2].eat(50); a[0].eat(100); //удалится a.print(); //нумерация яблок теперь изменилась! a[0].fall(); a[0].eat(200); a[1].eat(50); //удалили всё a.print(); //пусто a[1000].eat(); //недопустимый вызов a.print(); //пусто system("pause >nul"); return 0; }
9. Написать программу определения дня недели по заданным значениям "день", "месяц" и "год".
Примечание: используйте формулу Зеллера
nday= ( [26*(m+1)/10]+d+y+[y/4]+[c/4]-2*c )%7
Здесь [] – обозначение целой части числа, % - взятие остатка от деления, D- день месяца, M – номер месяца, Y – год столетия (0-99), C – номер столетия (=20 для 21 века), dday – полученный день недели (0-Сб, 1-Вс, …, 6-Пт). Январь и февраль считаются как месяцы 13 и 14 предыдущего года.
#include <cstdio> #include <cmath> int leapyear(int y) { //Високосный ли год y (1/0) return y % 4 == 0 && y % 100 != 0 || y % 400 == 0; } int lastday(int m, int y) { //Последний день месяца m года y switch (m) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: return 31; case 4: case 6: case 9: case 11: return 30; case 2: return (leapyear(y) ? 29 : 28); default: return 0; } } int weekday(int day, int month, int year) { // День недели по формуле Зеллера; // 1=Пн, ..., 7=Вс; 0=ошибка if (year<1 || month<1 || month>12 || day<1 || day>lastday(month, year)) { return 0; } if (month<3) { month += 12; year--; } int c = year / 100; int y = year % 100; int nday = ( (int)(floor(26 * (month + 1) / 10) + day + y + floor(y / 4) + floor(c / 4) - 2 * c)) % 7; return nday < 2 ? nday + 6 : nday - 1; } int main() { printf("\n%d", weekday(29, 2, 2000)); //2 - вт printf("\n%d", weekday(29, 2, 2100)); //0 - неверная дата printf("\n%d", weekday(1, 1, 2018)); //1 - пн getchar(); return 0; }
10. Реализовать и проверить функцию strins – вставку в строку другой строки, начиная с заданного номера позиции. Класс string не используем, только строки char *
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; /* В Studio права указателей ограничены, проще всего сделать за несколько проходов по строке */ char *strins(char *dest, const char *src, unsigned pos) { int lendest = strlen(dest); if (pos<0 || pos>lendest) return dest; // int lensrc = strlen(src); int newlen = lendest + lensrc + 1; char *newstr = new char[newlen]; strncpy(newstr, dest, pos); strncpy(&newstr[pos], src, lensrc); strncpy(&newstr[pos + lensrc], &dest[pos], lendest - pos + 1); newstr[newlen] = '\0'; return newstr; } int main() { char *src = "Hello"; //что вставляем char *dest = new char[80]; strcpy(dest, "12345"); //куда dest = strins(dest, src, 3); puts(dest); getchar(); return 0; }
11. Реализовать и проверить функцию memcpy – копирование строки в строку с ограничением максимального количества копируемых символов. Использовать строки char *
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; char *memcpy_(char *dest, const char *src, unsigned count) { char *addr = dest; for (int i = 0; i < count; i++) *dest++ = *src++; return addr; } int main() { char *dest = new char[80]; char src[80]; strcpy(src, "Hello, i'm a string from your program!"); dest = (char *)memcpy(dest, src, 19); //сделали стандартной функцией dest[19] = '\0'; puts(dest); dest = (char *)memcpy_(dest, src, 19); //и нашей dest[19] = '\0'; puts(dest); getchar(); return 0; }
12. Реализовать и проверить функцию memcmp – сравнение указанного количества байт в двух областях памяти. Использовать строки char *
#include <iostream> #include <cstring> using namespace std; int memcmp_(const char *buf1, const char *buf2, unsigned count) { for (unsigned i = 0; i<count; i++) { if (*buf1 != *buf2) return (int)*buf1 - (int)*buf2; buf1++; buf2++; } return 0; } int main() { char *s1 = "abcd"; char *s2 = "abcd"; char *s3 = "abc"; char *s4 = "abzd"; int i1 = memcmp_(s1, s2, 4); cout << endl << "s1 and s2 [4]: " << i1; int i2 = memcmp_(s1, s3, 4); cout << endl << "s1 and s3 [4]: " << i2; int i3 = memcmp_(s1, s3, 3); cout << endl << "s1 and s3 [3]: " << i3; int i4 = memcmp_(s1, s4, 4); cout << endl << "s1 and s4 [4]: " << i4; cin.get(); return 0; }
13. Реализовать и проверить функцию trim – удаление лишних разделителей в начале и конце строки. Использовать строки char *
#include <iostream> #include <cstring> using namespace std; bool is_div(char c) { return strchr(" \t\r\n\v", c) == nullptr ? false : true; } char *trim(const char *s) { int i = 0, n = strlen(s); while (is_div(s[i])) { i++; if (i == n) return ""; } int j = n - 1; while (is_div(s[j])) j--; char *news = new char[j - i + 2]; strncpy_s(news, j - i + 2, &s[i], j - i + 1); //безопасная версия strncpy news[j - i + 1] = '\0'; return news; } int main() { cout << endl << trim("\t abc "); cout << endl << trim("def"); cout << endl << trim(" \t\n"); cout << endl << trim(" 123 456 \r\n"); cin.get(); return 0; }
14. Реализовать и проверить функцию strcmp – сравнение двух строк char *
#include <cstring> #include <iostream> using namespace std; int strcmp_(const char *s1, const char *s2) { while (*s1 || *s2) { //пока одна из строк не кончилась if (*s1 == *s2) { //если очередные 2 символа равны s1++; s2++; //перейти к следующей паре символов } else return *s1 - *s2; //иначе вернуть разность кодов отличающихся символов } //Проверить случаи, когда кончилась только одна из строк if (*s1 == '\0' && *s2 != '\0') return 1; else if (*s1 != '\0' && *s2 == '\0') return -1; else return 0; //если обе кончились одновременно - это равенство! } int main() { char *s1 = "abcde"; char *s2 = "abcd"; cout << strcmp_(s1, s2); cin.get(); return 0; }
15. Реализовать и проверить функцию, возвращающую только те из символов строки s, которые встречаются в строке c. Использовать строки char *
#include <iostream> char *f(char *s, char *c) { int ls = strlen(s), lc = strlen(c); char *r = new char[ls]; int k = 0; for (int i = 0; i < ls; i++) { char next = s[i]; bool found = false; for (int j = 0; j < lc; j++) if (next == c[j]) { found = true; break; } if (found) r[k++] = next; } r[k] = '\0'; return r; } int main() { char *s = "Symbols from string"; char *c = "ybSstr"; std::cout << f(s, c); //Остались из s символы, входящие в c std::cin.get(); return 0; }
16. Из динамического целочисленного массива переписать все положительные элементы в новый динамический массив.
#include <iostream> #include <cstdlib> using namespace std; int *vvod(int n) { int *a = new int[n]; if (a == NULL) return NULL; for (int i = 0; i<n; i++) { cout << "a[" << (i + 1) << "]="; cin >> a[i]; } return a; } int *obrabotka(int *a, int n, int &bk) { int k = 0; bk = 0; for (int i = 0; i<n; i++) if (a[i]>0) k++; if (k == 0) return NULL; int *b = new int[k]; if (b == NULL) return NULL; for (int i = 0, k = 0; i<n; i++) if (a[i]>0) b[k++] = a[i]; bk = k; return b; } void vivod(int *a, int n) { cout << endl; for (int i = 0; i<n; i++) cout << a[i] << " "; } int main() { int n; cout << "Size of array N="; cin >> n; int *a = vvod(n); int bn = 0; int *b = obrabotka(a, n, bn); vivod(b, bn); system("pause >nul"); return 0; }
17. Средствами библиотеки iostream организовать ввод динамической матрицы вещественных чисел с проверкой корректности ввода.
#include <iostream> using namespace std; int main() { const int n = 3, m = 3; int i, j; double val; //Выделение памяти под матрицу double **a = new double *[n]; for (i = 0; i<n; i++) a[i] = new double[m]; //Ввод динамической матрицы с проверкой корректности ввода (через cin) for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { cout << endl << "Item A[" << i << "," << j << "]="; while (!(cin >> val)) { //Простой вариант без try-catch cin.clear(); while (cin.get() != '\n') continue; cout << "Error! Please, type it again" << endl; } a[i][j] = val; } } //Вывод матрицы по строкам for (i = 0; i < n; i++) { cout << endl; for (j = 0; j < m; j++) cout << a[i][j] << " "; } cin.get(); cin.get(); return 0; }
18. Продемонстрировать передачу динамически созданной целочисленной матрицы в качестве параметра функции. Функция возвращает вектор, состоящий из максимальных элементов строк матрицы.
#include <iostream> #include <cstdlib> using namespace std; int *maxRows(int n, int m, int **a) { int *r = new int[n]; if (!r) return NULL; for (int i = 0; i<n; i++) { r[i] = a[i][0]; for (int j = 1; j<m; j++) if (a[i][j]>r[i]) r[i] = a[i][j]; } return r; } int main() { const int n = 4, m = 2; int **a = new int *[n]; for (int i = 0; i < n; i++) a[i] = new int[m]; a[0][0] = 4; a[0][1] = 4; a[1][0] = 3; a[1][1] = 4; a[2][0] = 5; a[2][1] = 5; a[3][0] = 4; a[3][1] = 5; int *s = maxRows(n, m, a); for (int i = 0; i<n; i++) cout << s[i] << " "; cin.get(); return 0; }
19. Прочитать из текущей папки файл data.txt с символами кириллицы, показать коды символов. Учесть, что Visual Studio по умолчанию интерпретирует тип char как знаковый.
В несложных случаях с однобайтовой кодировкой, такой как стандартная Windows-1251, может помочь вот такой простой подход:
#include <iostream> #include <fstream> #include <cstdlib> using namespace std; void error(int c) { cout << "\nExitcode:" << c; system("pause>nul"); cin.get(); exit(c); } int main() { ifstream file("data.txt"); if (!file) error(1); char c; int ci; while (!file.eof()) { file.read(&c, 1); if (c < 0) ci = (int)c + 256; //для Studio, где по умолчанию char - знаковый //работаем с кодом символа ci как с unsigned char cout << ci << " "; } error(0); }
20. Заданы вектор A размерностью m, определяющий объем производимой продукции, и матрица X размерностью m*n, характеризующая распределение производимой продукции по n потребителям. Напишите программу, которая:
1. Вычисляет невязки в векторе А как разность между компонентой a[i] и суммой элементов i-ой строки матрицы X.
2. Вычисляет общую сумму невязок S в векторе A. Если S = 0, т.е. вся продукция распределена, то программа выводит на печать текст: “План перевозок оптимален”. При S, не равном нулю, печатается значение S и текст “План перевозок не оптимален”.
#include <iostream> using namespace std; int main() { const int m = 3, n = 4; int x[m][n] = { { 0, 0, 5, 5 }, { 10, 0, 0, 0 }, { 0, 5, 5, 0 } }; int a[m] = { 10, 10, 10 }; int r[m], s = 0, sumi, i, j; for (i = 0; i<m; i++) { sumi = 0; for (j = 0; j<n; j++) sumi += x[i][j]; r[i] = a[i] - sumi; s += r[i]; } cout.precision(2); cout << endl << "s=" << s; cout << endl << "Plan is" << (s ? " not " : " ") << "optimal"; cin.get(); return 0; }
21. Сравнить по быстродействию большой массив int[] с вектором той же размерности.
#include <cstdlib> #include <iostream> #include <ctime> #include <vector> using namespace std; int main() { const int size = 10000000; int *a; vector <int> v; int i, n; cout << "Type 1 (int *) or 2 (vector) "; cin >> n; long t1 = clock(); //время начала if (n == 1) { //заполнение средствами int * a = new int[size]; if (!a) { cout << "No memory for int *!"; exit(1); } for (i = 0; i < size; i++) a[i] = i; delete a; //время обработки <100 ms } else { //заполнение средствами vector <int> v.resize(size); int n = v.size(); if (n != size) { cout << "No memory for vector!"; exit(2); } for (i = 0; i < size; i++) v[i] = i; //c v.push_back(i) ещё намного медленее, >12000 ms v.clear(); //время обработки >3000 ms } long t2 = clock() - t1; //время окончания cout << t2 << "ms"; cout << endl; system("pause >nul"); return 0; }
Следует учесть, что по умолчанию в Studio выбрана конфигурация Debug, в ней vector и впрямь будет намного медленнее.
В конфигурации Release заметных отличий не будет.
Кстати, в QT 5.X vector медленнее всего в 1,5 - 2 раза.
22. В классе String, хранящем данные в строке Си, заданной указателем, перегрузить операцию "=" таким образом, что она скопирует строку без скобок всех видов.
Решение примитивно, буфер под строки всегда одинакового размера.
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstring> #define SIZE 256 using namespace std; class String { private: char *str; public: String(char *s = ""); ~String(); int length(); void print(); String& operator = (String &ob); }; String::String(char *s) { str = new char[SIZE]; strcpy(str, s); } String::~String() { //delete[] str; //не надо, будут объекты в стеке } int String::length() { return strlen(str); } void String::print() { cout << endl << str; } String & String::operator = (String &ob) { int l = ob.length(); char *divs = "(){}[]"; //а лучше std::string, #include <algorithm> и str.erase int k = 0; for (int i=0; i<l; i++) if (!strchr(divs, ob.str[i])) this->str[k++] = ob.str[i]; this->str[k]='\0'; return *this; } int main () { String str1 ("(Hello, [] {world})"); String str2 ("()"); String str3 = str2 = str1; str1.print(); str2.print(); str3.print(); cin.get(); return 0; }
18.01.2018, 14:09 [2123 просмотра]