Если вы уже решили большое количество задач, написали множество программ и считаете, что уже неплохо знаете С++, то этот сборник задач для вас. Тут собраны достаточно сложные задачи, но все же они не самые сложные.
В таблице ниже представлен список задач, которые являются типовыми задачами в программировании. Список задач со временем будет пополняться все новыми и новыми задачами. Как и раньше, в таблице есть столбец — «Статус», если в статусе стоит зеленая галочка, значит на нашем сайте есть уже решение к данной задаче. Вы можете попытаться написать программу, не подглядывая в исходный код, который выложен на нашем сайте. Возможно ваше решение задачи будет изящнее, и в качестве примера альтернативного решения, по вашему согласию, мы опубликуем это решение на сайте.
Если же ячейка статуса — пустая, то готового, рабочего исходного кода к этой задаче у нас на сайте пока нет. Вы можете первыми решить эту задачу и отправить решение нам, а мы выложим ваш исходный код на сайте, от вашего имени. Если вы решите задачу каким-то другим способом, отправьте решение нам. Мы опубликуем его на сайте, в качестве альтернативного решения.
КАК ЧИТАТЬ И ПОНИМАТЬ С/C++ КОД?
| 1 | Аналоги строковых функций С++ | admin |
| 2 | Выполнить сортировку массива двумя способами | liliia |
| 3 | Действия над считанными из файла матрицами | |
| 4 | Квадратная матрица, главная и побочные диагонали | admin |
| 5 | Класс зоомагазин | |
| 6 | Класс Массив, описывающий одномерный массив | NaikoN |
| 7 | Класс Матрица, описывающий двумерный массив | admin |
| 8 | Класс множество: трехмерный массив | admin |
| 9 | Класс Призма | admin |
| 10 | Класс, реализующий операции со строками | liliia |
| 11 | Массив структур «Знак зодиака» | admin |
| 12 | Матрица, главные диагонали | admin |
| 13 | Найти простые числа, используя Решето Эратосфена | admin |
| 14 | Наследование, работа супермаркета | admin |
| 15 | Номер min элемента, произведение элементов массива | admin |
| 16 | Переписать положительные элементы матрицы | admin |
| 17 | Переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик | admin |
| 18 | Построение графика функции | |
| 19 | Самое часто встречающееся слово в тексте | admin |
| 20 | Слова сформированные из первых букв слов каждой строки файла | admin |
| 21 | Удалить из массива дубликаты элементов | admin |
Поделиться:
Создание сборщика мусора | С
Новое
- Особенности Qt: слоты и сигналы, описание QObject и QApplication, виды окон и т.д.
- Первая программа на Qt:
- Введение — графическая библиотека Qt
- Наследование классов
- Перегрузка операторов в С++ (часть 2)
Источник: cppstudio.com
Сложные программы на си
Построение нового, собственного типа переменных.
Цель. Построить новый тип из уже имеющихся.
1 Структуры языка Си
В первом подразделе будет показано как создавать новый тип данных, являющийся составленым из ранее уже имеющихся типов данных.
1.1 Переменные
Допустим в программе нужно обрабатывать сложные объекты, например, точки. Под термином – сложный – понимается, что объект состоит из связанных между собой базовых типов языка Си. Например, точка будет состоять из её компонент, двумерная точка состоит из двух чисел с плавающей точкой.
Важным моментом связанным с объектами является его целостность. Так при выполнении вычислений с такими объектами использую только то, что было ранее введено (т.е. без понятия структур), возникнут ряд сложностей описанных ниже.
Объявление При объявлении сложность заключается в том, что необходимо объявить переменные так, чтобы потом было ясно какие из переменных образует единый объект. В частности, какие из переменных являются компонентами точки и какой у них порядок.
Так, если нужно объявить одну точку, то можно написать код и так:
1 double x,y; // о д н а т о ч к а
Но, если точек больше, например две, то придется например вводить индекс:
1 double x0,y0; // п е р в а я т о ч к а
2 double x1,y1; // в т о р а я т о ч к а
В дальнейшем в программе необходимо помнить о том, что переменные с одним и тем же индексом (суффиксом) образуют единый объект, в рассматриваемом случае: первая точка задается как ( x 0 , y 0 ) , а вторая как ( x 1 , y 1 ) . При таком подходе сам пользователь отвечает за согласованность переменных: при инициализации, копировании, при вычислениях, при передачу в функции и тому подобное. Последнее не удобно и в большинстве случаев ведет к ошибкам.
Язык Си позволяет задавать такие объекты естественным образом, что возлагает большую часть согласованности при взаимодействии с объектом на сам язык. Последние позволяет пользователю сконцентрироваться на самой сути программы. Языковая конструкции языка Си заключается в следующем:
1 struct point_2d
2 <
3 double x, y; // с о с т а в н ы е ч а с т и о б ъ е к т а
4 >;
Внутри фигурных скобок пишутся объявления переменных (определять их там нельзя!), которые называются полями структуры. Поля описывают сложные объект. В данном случае они являются координатами точки.
Поля в обще говоря могут быть разных типов. Более того, они, как будет показано нижу, могу в свою очередь быть тоже типом некой структуры. Считается, что поля задают сам объект в целом.
Когда нужный тип данных определен объявления переменных можно записать следующим образом:
1 struct point_2d p; // о д н а т о ч к а
2 struct point_2d p0, p1; // е щ ̈e д в е т о ч к и .
В первой строчке была объявлена переменная p, а во второй строчке объявлено сразу две переменные p0 и p1. Все перечисленные переменные (p, p0 и p1) имеют тип struct point_2d, т.е. являются структурами (составными объектами) с именем (типом) point_2d.
Последнее очень похоже на объявления переменных стандартных типов. Разница как раз заключается в том, что тип в данном случае struct point_2d. Можно такое название везде в программе и использовать, но это не всегда удобно (слишком длинно). Поэтому его принято сократить за счет использования конструкции переопределения .
Переопределение Заметим, что при объявлении приходится всегда писать вначале термин struct до название самого нашего типа (point_2d). Этого можно избежать использую другую языковую конструкцию языка Си: typedef . Она позволяет заменять любой сложный тип на более короткое название, сокращение:
1 typedef int myintarray[5];
2 // .
3 myintarray a; // У a т и п int [5].
4 a[0]=5;
5 a[4]=a[0]+1;
6 myintarray b=;
В последнем примере сложный тип (целочисленный массив из 5 элементов) заменяется на некое обозначение (myintarray). Последнее позволяет далее в программе использовать именно его, а не громоздкое первоначальное (в котором легко ошибиться и в какой-то из очередных объявлений вместо 5 написать, например, 4). В частности, когда решено изменить размер массива (придется везде поменять 5 на, например, 4). Последнее означает, что хорошей практикой проектирования программного обеспечения является использование конструкции typedef.
По аналогии с выше написанном, рассматриваемую конструкцию можно применить и к структурам:
1 typedef struct point_2d point2d;
2 // Т е п е р ь м о ж н о т а к :
3 point2d p0, p1; // б е з т е р м и н а struct .
Последнее явно читабельнее и удобнее ранее показанного способа объявления переменных с типом структура.
Вложенные объявления Объекты в Си можно определять не только посредством встроенных типов данных, но и через уже ранее определенные типы. Объект типа прямая (отрезок) можно задать как:
1 struct line_2d
2 <
3 // Н а ч а л ь н а я и к о н е ч н а я т о ч к а п р я м о й ( о т р е з к а )
4 point2d p0, p1;
5 double weight;
6 >;
7 typedef struct line_2d line2d;
В данном определении структуры задается объект отрезок двумя точками. Также добавлено ещё одно поле weight с отличным от предыдущих типом double. Последним показана возможность использования в структурах полей с разным типом данных.
Этим полем можно задавать, например, вес (важность данного отрезка). Последнее важно например в задачах на графах.
1.2 Вычисления
В предыдущем подразделе было показано как описывать свой тип данных и как потом создавать соответствующего типа переменные.
В первом параграфе будет показано как инициализировать (задавать первичное значение) переменным, во втором как выполнять простейшие вычисления над переменными имеющие тип структура.
Инициализация Переменные стандартных типов, как мы знаем, можно инициализировать в момент объявления:
1 double x0=1,y0=2; // п е р в а я т о ч к а
2 double x1=3,y1=y0+2.; // в т о р а я т о ч к а
Переменные являющиеся структурами такая возможность тоже имеется. В конце концов все сводится к:
1 point2d p0=, p1=;
2 line2d ll0=<, , 3.0>;
3 line2d ll1=
;
Таким образом значение рассматриваемых переменных задается списком значений, задаваемый парными фигурных скобок. Если какое либо из значений предполагает структуру, то оно задается соответствующим типом: либо ранее объявленной переменной (см. первое поле в стр. 3 ), либо как и ранее фигурными скобками (см. первое и второе поле в стр. 2 , а также второе поле в стр. 3 ), последнее означает, что фигурные скобки будут вложенными.
Простые вычисления Для начала покажем как выполнять простейшие вычисления, а именно – вычисления над полями сложных переменных. Все конечно сводится к переменной имеющий встроенный тип, например, числовой тип.
Пусть, например, программа вычисляет параллельный сдвиг точки:
1 // П а р а л л е л ь н ы й с д в и г :
2 x0 += x1; // П о м н и м о т о м , ч т о о б ъ е к т с о с т о и т
3 y0 += y1; // и з б о л е е ч е м о д н о й п е р е м е н н о й .
Как уже ранее отмечалось в данном случае пользователю самому приходится помнить из чего составлен каждый из объектов. В данном случае, что точки составлены из компонент.
В случае если данные уже определены, то можно переписать этот код как:
1 // П а р а л л е л ь н ы й с д в и г :
2 p0.x += p1.x; // У к а з ы в а е т с я и м я п е р е м е н н о й , а д а л е е ч е р е з
3 p0.y += p1.y; // т о ч к у (.) и м я п о л я .
Такой подход явно более удобен.
В ещё более явно это проявляется, когда нужно копировать весь объект. Например
1 point2d left_most;
2 if ( p0.x < p1.x )
3 left_most = p0;
4 else
5 left_most = p1;
1.3 Ввод/вывод сложных типов
Помимо вычислений важным является и ввод вывод сложных объектов. Иначе как и ранее было уже отмечено, будет сложно увидеть результат работы программы. В принципе все что было уже сказано ранее достаточно для понимания того как это делать, так как когда происходит переход к полю с базовым типом оно уже ничем не отличается от обычной переменной. А для них все было уже рассказано.
Но тем не менее покажем как это делать.
Вывод данных Стандартные функции вывода (printf и тому подобное) естественно ничего не знают о нашем типе данных. Поэтому и вывести его самостоятельно не смогут:
1 // Т а к в ы в е с т и к о м п о н е н т ы т о ч к и н е п о л у ч и т с я :
2 printf(«(%f, %f)», p0); // О ш и б к а .
Для того чтобы они напечатались необходимо перейти к соответствующим полям самостоятельно:
1 // В ы в о д и м з н а ч е н и я к о м п о н е н т о в п е р в о й т о ч к и :
2 printf(«(%f, %f)», p0.x, p0.y); // П е ч а т а е м п о л я п е р в о й
3 printf(«(%f, %f)», p1.x, p1.y); // т о ч к и , а п о т о м в т о р о й .
4 // Г л а в н о е н е о ш и б и т ь с я п р и к о п и р о в а н и и с т р о ч к и :
5 printf(«(%f, %f)», p0.x, p1.y); // Н е т с о о т в е т с т в и я !
Ввод данных Продолжая предыдущее, такой же подход необходимо помнить при вводе данных:
1 // С ч и т ы в а е м к о м п о н е н т ы п е р в о й т о ч к и :
2 scanf(«%lf%lf», y0); // С о о т в е т с т в у ю щ и е п е р е м е н н ы е
3 scanf(«%lf%lf», y1); // С ч и т а л и в т о р у ю т о ч к у .
4 // Т а к о й к о м а н д о й с ч и т а е т с я с к о р е е в с е г о н е т о , ч т о х о т е л и
5 scanf(«%lf%lf», y1); // Н е т с о о т в е т с т в и я !
Упражнение. Реализовать сортировку по какому-либо из полей.
1.4 Функции
Вызов функции Допустим нужно вычислить расстояние до точки. В случае единственной точки:
1 // Р а с с т о я н и е д о т о ч к и
2 double dist= sqrt( x ∗ x + y ∗ y );
В случае если их большей одной необходимо помнить какие переменные между собой соотносятся. Например расстояние до первой точки ищется как:
1 // Р а с с т о я н и е д о п е р в о й т о ч к и
2 double dist = sqrt( x0 ∗ x0 + y0 ∗ y0 );
3 // Н е п р а в и л ь н ы м б у д е т н а п и с а т ь :
4 double dist2 = sqrt( x1 ∗ x1 + y0 ∗ y0 );
При вызове функции необходимо будет передать все поля объекта и убедиться что они относятся к одному объекту.
1 double length( double x, double y)
2 <
3 return sqrt( x ∗ x + y ∗ y);
4 >
5 // . и д е т н е к и й к о д
6 // п р и в ы з о в е ф у н к ц и и н у ж н о п е р е д а т ь с о о т в е т с т в у ю щ и е
7 double l = length(x0, y0); // п о л я о б ъ е к т а , к о м п о н е н т ы .
Это уже создает нагромождение переменных, что увеличит шанс ошибки. Тем более, если нужно будет передать больше одной точки:
1 double dist( double x0, double y0, double x1, double y1)
2 <
3 double dx = x1 − x0; // р а з н и ц а м е ж д у п е р в ы х к о м п о н е н т
4 double dy = y1 − y0; // м е ж д у в т о р ы м и . А к к у р а т н о !
5 return sqrt( dx ∗ dx + dy ∗ dy);
6 // В м е с т о э т о г о м ы м о г л и б ы в ы з в а т ь :
7 // return length ( dx , dy );// Т а к п р а в и л ь н е е .
8 >
9 // . и д е т н е к и й к о д
10 // п р и в ы з о в е ф у н к ц и и н у ж н о п е р е д а т ь с о о т в е т с т в у ю щ и е
11 double d = dist(x0, y0, x1, y1); // п о л я о б ъ е к т о в , д в у х !.
Достаточно легко ошибиться даже если использовать структуры.
Выходом являются структуры. Они позволяют передать объект как единое целое, что избавляет от ошибок связанных с полями.
1 double length2(point2d p)
2 <
3 return sqrt( p.x ∗ p.x + p.y ∗ p.y);
4 >
5 // . и д е т н е к и й к о д
6 // п р и в ы з о в е ф у н к ц и и н у ж н о п е р е д а т ь п р о с т о
7 double l = length(p0); // с о о т в е т с т в у ю щ и й о б ъ е к т а .
1 double dist2(point2d p0, point2d p1)
2 <
3 double dx = p1.x − p0.x; // р а з н и ц а м е ж д у п о л я м и
4 double dy = p1.y − p0.y; // м е ж д у в т о р ы м и . А к к у р а т н о !
5 return sqrt( dx ∗ dx + dy ∗ dy);
6 // В м е с т о э т о г о м ы м о г л и б ы в ы з в а т ь :
7 point2d dd = ;
8 return length( dd ); // Т а к п р а в и л ь н е е .
9 >
10 // . и д е т н е к и й к о д
11 // п р и в ы з о в е ф у н к ц и и н у ж н о п е р е д а т ь с о о т в е т с т в у ю щ и е
12 double d = dist( p0, p1); // д в а о б ъ е к т а .
Указатели Указатели нужны для сокращения объема передаваемой памяти:
1 double dist2(point2d ∗ p0, point2d ∗ p1)
2 <
3 double dx = p1 − >x − p0 − >x; // р а з н и ц а м е ж д у п о л я м и
4 double dy = p1 − >y − p0 − >y; // м е ж д у в т о р ы м и . А к к у р а т н о !
5 return sqrt( dx ∗ dx + dy ∗ dy);
6 // В м е с т о э т о г о м ы м о г л и б ы в ы з в а т ь :
7 point2d dd = ;
8 return length( dd ); // Т а к п р а в и л ь н е е .
9 >
10 // . и д е т н е к и й к о д
11 // п р и в ы з о в е ф у н к ц и и н у ж н о п е р е д а т ь с о о т в е т с т в у ю щ и е
12 double d = dist( p1); // д в а о б ъ е к т а .
Вместо точки (.) используется указатель (->).
Упражнение. Реализовать функцию swap.
Источник: xn--80akaaied0aladi2a9h.xn--p1ai
Усложняя стандартный пример
Стандартная библиотека С++ предлагает не только набор классов, но также определяет способ написания программ. В рамках данной статьи рассматриваются общие требования к реализации программ при помощи STL.
Рассмотрим следующую задачу:
Считать из файла input.txt массив целых чисел, разделенных пробельными символами. Отсортировать их и записать в файл output.txt
Можно написать следующее решение:
#include #include #include int main() < // открываем input.txt для чтения std::ifstream fin(«input.txt»); // открываем output.txt для записи std::ofstream fout(«output.txt»); // объявление и инициализация пустого целочисленного вектора std::vectorv; // сложная магия, благодаря которой из потока чтения вставляются элементы в конец вектора std::copy(std::istream_iterator(fin), std::istream_iterator(), std::inserter(v, v.end())); // алгоритм сортировки std::sort(v.begin(), v.end()); // сложная магия, благодаря которой элементы из вектора копируются в поток записи std::copy(v.begin(), v.end(), std::ostream_iterator(fout, » «)); return 0; >
Несколько слов о «магии» в коде:
- Одной из основ библиотеки являются итераторы, а также полуинтервалы, ими определяемые. По семантике (читай — по поведению) они совпадают с указателями. То есть, опреатор разыменования * вернет вам элемент, на который ссылается итератор, ++ переведет итератор на следующий элемент. В частности, любой контейнер представляется его концевыми итераторами [begin, end), где begin указывает на первый элемент, end — за последний;
- Алгоритмы, работающие с контейнерами, в качестве параметров принимают начало и конец контейнера (или его части);
- Алгоритм копирования copy просто переписывает элементы из одного полуинтервала в другой. Если в целевом контейнере не выделена память, то поведение непредсказуемо [copy];
- Функция inserter вставляет значение в контейнер перед указанным итератором [inserter]
- istream_iterator и ostream_iterator предоставляют доступ к потокам в стиле контейнеров [istream_iterator, ostream_iterator]
В файле input.txt хранится список, содержащий информацию о людях: фамилия, имя, возраст (каждая строка это запись, данные разделены пробелом). Считать эти данные в массив, отсортировать их по возрасту и записать в файл output.txt. Вывести на экран информацию о человеке, чей возраст более 20, но менее 25 лет.
В принципе, решение будет практически таким же. Однако, для сохранения решения необходимо провести подготовительную работу, а именно:
-
Объявить структуру данных. — можно определить что-то служное, но в конкретном случае достаточно struct:
struct man< std::string firstname, secondname; size_t age; >;
std::ostream operator >> (std::istream p)< in >> p.firstname >> p.secondname >> p.age; return in; >
bool comparator(const man p2)
struct predicate < size_t begin, end; predicate(int p1, int p2): begin(p1), end(p2) <>bool operator ()(const man return (p.age >begin) (p.age < end); >>;
int main() < std::ifstream fin(«input.txt»); std::ofstream fout(«output.txt»); std::vectorv; std::copy(std::istream_iterator(fin), std::istream_iterator(), std::inserter(v, v.end())); std::sort(v.begin(), v.end(), comparator); std::copy_if(v.begin(), v.end(), std::ostream_iterator(std::cout, «n»), predicate(20, 25)); std::copy(v.begin(), v.end(), std::ostream_iterator(fout, «n»)); return 0; >
Как можно заметить, изменения функции main минимальные, касаются только типа элементов вектора. Плюс добавлен вызов алгоритма copy_if. Этот полезный алгоритм появился со стандартом С++11, он копирует элементы из одного контейнера в дргой только те элементы, которые удовлетворяют условию.
Какие можно сделать из этого выводы?
- Знание и активно использование алгоритмов стандартной библиотеки существенно ускоряет разработку (точнее говоря, доводит до автоматизма).
- Полезным является объявление различных конструкторов и операторов копирования для структур данных. Они используются в различных ситуациях, в частности, при вставке элементов в контейнеры.
- Для удобства можно перегрузить операторы ввода и вывода, а также оператор сравнения и оператор упорядочения.
- Функторы — мощный инструмент, который позволяет реализовать функции с «памятью» или дополнительным поведением
- … возможно, еще каккие-либо.
Весь код программы:
an_example.cpp
#include #include #include #include #include #include struct man< std::string firstname, secondname; size_t age; >; std::ostream operator >> (std::istream p)< in >> p.firstname >> p.secondname >> p.age; return in; > bool comparator(const man p2) < return p1.age < p2.age; >struct predicate < size_t begin, end; predicate(int p1, int p2): begin(p1), end(p2) <>bool operator ()(const man return (p.age >begin) (p.age < end); >>; int main() < std::ifstream fin(«input.txt»); std::ofstream fout(«output.txt»); std::vectorv; std::vector::iterator i; std::copy(std::istream_iterator(fin), std::istream_iterator(), std::inserter(v, v.end())); std::sort(v.begin(), v.end(), comparator); std::copy_if(v.begin(), v.end(), std::ostream_iterator(std::cout, «n»), predicate(20, 25)); std::copy(v.begin(), v.end(), std::ostream_iterator(fout, «n»)); return 0; >
Библиография:
- Stepanov Al. Lee Meng, The Standard Template Library, 1995
- CPP Reference, copy
- CPP Reference, inserter
- CPP Reference, istream_iterator
- CPP Reference, ostream_iterator
- Wiki, функтор
- STL
- с++ программирование
Источник: habr.com