Часть 1 – Основы программирования и информатика
Часть 2 – Объектно-ориентированное программирование
Часть 3 – Языки программирования
- языки программирования C++,C#, [Java,Python,Ruby]
- выбрать для каждой части набор тем (7-10)
- для каждой темы вступление – цель этой лабораторной работы
- краткое напоминание основных терминов (без соплей) и ключевые слова – 1 страница
- пример: условие задачи + словесное описание алгоритма + реализация на разных языках С++ и С#
- 10-15 простых задач + 5-10 сложных задач + несколько для самостоятельной работы + несколько страшных задач для продвинутых детей
- для каждой темы задач объявить минимальный обязательный набор средств, частей в решении и т.д. Например, обязательно ввод из текстового файла и вывод в текстовый файл и на экран. Строго описать формат ввода и вывода. Что должно быть оформлено в виде отдельных функций. Какие параметры или глобальные константы.
- простые (обязательные) задачи – краткое условие
- для каждой самостоятельной и трудной задачи несколько примеров входных и соответствующих выходных данных
Отдельный пункт – комплексное задание по нескольким темам одновременно?
Что должно содержать в отчёте по каждой лабораторной работе – чётко перечислить
Может быть делать 1 общий отчёт по всем работам или по группе тем?
Не обязательно задачи каждой темы давать для самостоятельной работы
Для каждой задачи подготовить полусекретный набор тестовых данных – не для печати – для проверки решений детей
Дополнение для части 2 – обработка исключений
Часть 1. Основы программирования и информатика
1.0. Разминка – введение в алгоритмы – элементарные алгоритмы
1.5. Символьные строки (тексты)
1.7. Функции и рекурсия
1.9. Дополнительные задачи
В данном методическом пособии используются как классические задачи по программированию, так и задачи, взятые с сайтов по спортивному программированию.
Тема 1.0. Элементарные алгоритмы
Изучение основных конструкций языка программирования. Умение построить алгоритм для решения задачи и записать его на языке программирования.
Основные понятия.
Решение задачи состоит в описании объектов и указания действий над ними с целью получения нужного результата.
Основной метод решения сложных задач - разбиение задачи на подзадачи - декомпозиция
Существует 3 механизма декомпозиции:
- линейная последовательность – задача разбивается на последовательность шагов (подзадач), которые выполняются друг за другом;
- ветвление по условию – задача разбивается на 2 или несколько параллельных подзадач и в зависимости от некоторого условия будет выполняться только одна из подзадач;
- многократное повторение – задача разбивается на последовательность одинаковых (подобных) подзадач. Эта подзадача будет выполняться несколько раз.
Эти 3 механизма используются при декомпозиции многократно до тех пор, пока задача не сведётся к очевидным (элементарным) действиям.
В каждой задаче (подзадаче) нужно уметь выделять объекты, над которыми будут выполняться действия.
Объекты характеризуются своим типом и в каждый момент времени имеют некоторое значение, которое хранится в оперативной памяти.
Действия задаются операторами и состоят в выполнении некоторых допустимых операций над объектами.
Структура простой программы:
подключения стандартных библиотек (#include)
определение главной функции (main). Внутри неё описываются объекты и операторы.
Ввод данных и печать результатов.
Ключевые слова.
Переменная, константа, Описание. Оператор. Программа. Оператор препроцессора #include.
Дано натуральное число. Напечатать все его делители в порядке возрастания.
Для решения этой задачи будем перебирать все натуральные числа от 1 до самого заданного числа. Те числа, на которые будет делиться без остатка заданное число, будем печатать.
# include <iostream> // используется для подключения некоторых стандартных
# include <conio.h> // возможностей для ввода-вывода информации
using namespace std; // для использования некоторых стандартных имён
int main () // основная часть программы – главная функция
setlocale (LC_ALL, "RUS");
cout << "Вычисление делителей числа = ";
for ( int i=1; i <= n; i++ )
getch (); // задержка – смотреть результаты на экране
static void Main (string [] args) // Main - обязательное имя
Console.Write ("Вычисление делителей числа " + i);
Дополнительные замечания.
Простой анализ программы показывает возможности ускорения в 2 раза. Во-первых, на числа 1 и nможно не делить, а из остальных проверять только числа от 2 доn/2.
Задачи для обязательного решения
1.0.1.1. Квадратное уравнение. Даны вещественные коэффициенты квадратного уравненияA*X^2 +B*X+C= 0. Коэффициент А != 0. Написать программу для вычисления и печати корней этого уравнения. Ответ напечатать с точностью 2 знака после запятой. Если корней не существует, напечатать слово «НЕТ».
1.0.1.2. Уравнение степени не выше 2-х. Даны вещественные коэффициентыA,B,CуравненияA*X^2 +B*X+C= 0. Некоторые коэффициенты могут быть нулями. Написать программу для вычисления и печати корней этого уравнения. Ответ напечатать с точностью 2 знака после запятой. Если корней не существует, напечатать слово «НЕТ». Если существует бесконечно много корней, напечатать «МНОГО».
1.0.1.3. СЛАУ. Даны вещественные коэффициенты двух линейных алгебраических уравнений с двумя неизвестными: А1, В1, С1 и А2, В2, С2. Написать программу для вычисления и печати корней этой системы уравнений. Если корней не существует, напечатать слово «НЕТ». Если существует бесконечно много корней, напечатать «МНОГО». Уравнения имеют вид:A1*X+B1*Y=C1 иA2*X+B2*Y=C2.
1.0.1.4. Факториал. Дано неотрицательное целое числоK. Написать программу для вычисления и печати числаK!
1.0.1.5.Число сочетаний. Даны натуральные числаNиM(0 <=M<=N). Написать программу нахождения и печати числа сочетаний изNпоMпо формуле .
1.0.1.6. НОД. Даны натуральные числа А и В. Написать программу нахождения и печати наибольшего общего делителя этих чисел.
1.0.1.7. НОК. Даны натуральные числа А и В. Написать программу нахождения и печати наименьшего общего кратного этих чисел.
1.0.1.8. Простота. Дано натуральное число. Напечатать слово "ПРОСТОЕ", если это число является простым, т.е. не делится ни на какое число, кроме 1 и самого себя. В противном случае напечатать слово "СОСТАВНОЕ".
1.0.1.9. Совершенство. Дано натуральное число. Напечатать слово "СОВЕРШЕННОЕ", если это число является совершенным, т.е. оно равно сумме всех своих собственных делителей (кроме самого себя). В противном случае напечатать слово "НЕ СОВЕРШЕННОЕ".
Например, число 4 не совершенное, т.к. 4 != 1+2. Число 6 - совершенное, т.к. 6 = 1+2+3.
1.0.1.10. Пифагоровы числа. Даны натуральные числа А и В. Написать программу для печати всех чисел из диапазона [A..B], которые представимы в виде суммы двух квадратов натуральных чисел. Например, число 17 = 1*1 + 4*4.
1.0.1.11. Дано натуральное числоN. Напечатать это число цифрами наоборот.
1.0.1.12.EXP. Вычисление ряда 1 +x+x 2 /2! +x 3 /3! + … для заданного аргументаXс заданной точностью eps. Результат напечатать с 3 знаками после запятой.
1.0.1.13. Написать программу для вычисления (1+z)(1+z+z 2 )(1+z+z 2 +z 3 ) …(1+z+z 2 … +z n ) для заданного вещественного числаzи натурального числаn. Результат напечатать с 3 знаками после запятой.
1.0.1.14. Написать программу для вычисления значения (2+z)(3+2z+z 2 )(4+3z+2z 2 +z 3 ) …(n+1+nz+(n-1)z 2 … +z n ) для заданного вещественного числаzи натурального числаn. Результат напечатать с 3 знаками после запятой.
Задачи для самостоятельного решения
1.0.2.1. Даны натуральные числа А и В (A<=B). Написать программу, которая напечатает все простые числа из диапазона от А до В.
1.0.2.2. Даны натуральные числа А и В (A<=B). Написать программу, которая напечатает все совершенные числа из диапазона от А до В.
1.0.2.3. Пифагоровы числа. Даны натуральные числа А и В (A<=B). Написать программу для печати всех чисел из диапазона от А до В, которые представимы в виде суммы двух квадратов натуральных чисел несколькими способами. Например, число 50 = 5*5 + 5*5 = 1*1 + 7*7 (2 способа).
1.0.2.4. Быстрое возведение числа в натуральную степень. Написать программу, которая возведёт число А в натуральную степень В за log2В операций умножения, используя двоичное представление числа В.
1.0.2.5. Рассматриваются все числа от 1 доn. Написать программу, которая вычислит и напечатает общее количество всех цифр во всех этих числах вместе взятых.
1.0.2.6. Написать программу приближенного вычисления и печати числапо формуле . Вычисления проводить до тех пор, пока не будет достигнута точностьeps, т.е. два последних вычисленных значения не станут отличаться меньше, чем на малое положительное eps. Результат напечатать с 3 знаками после запятой.
1.0.2.7.SIN. Написать программу приближенного вычисления и печати суммы рядаx+x 3 /3! +x 5 /5! + … для заданного аргументаXс заданной точностью eps, т.е. очередное слагаемое не станет меньше малого положительного eps. Результат напечатать с 3 знаками после запятой.
1.0.2.8.COS. Написать программу приближенного вычисления и печати суммы ряда 1 +x 2 /2! +x 4 /4! + … для заданного аргументаXс заданной точностью eps, т.е. очередное слагаемое не станет меньше малого положительного eps. Результат напечатать с 3 знаками после запятой.
1.0.2.9. С натуральным числомnвыполняются следующие преобразования (операции): если оно четно, то делится пополам, а если нечетно, то умножается на 3 и прибавляется 1. С полученным числом опять выполняется преобразование до тех пор, пока не получится число 1. Для заданного интервала чисел отAдоBвычислить и напечатать количество выполняемых операций (преобразований) для каждого числа из этого интервала.
1.0.2.10. Зарплата. В отделе работают 3 сотрудника, которые получают заработную плату в рублях. Требуется определить: на сколько зарплата самого высокооплачиваемого из них отличается от самого низкооплачиваемого. В единственной строке записаны размеры зарплат всех сотрудников через пробел. Каждая заработная плата – это натуральное число, не превышающее 10 5 . Вывести одно целое число — разницу между максимальной и минимальной зарплатой.
1.0.2.11. Написать программу для решения уравнения . Вещественные значенияa,b,cвводятся.
1.0.2.12. Написать программу для решения уравнения . Вещественные значенияa,b,cвводятся.
1.0.2.13. Написать программу для вычисления корня квадратного из положительного вещественного числа х по итерационной формуле Ньютона Uk=Uk-1/2 +X/2/Uk-1.
1.0.2.14. Написать программу для вычисления корня кубического из положительного вещественного числа х по итерационной формуле Ньютона Uk= 2/3Uk-1+X/3/Uk-2/Uk-2.
Продвинутые задачи
1.0.3.1. Обобщённый алгоритм Эвклида.
Для заданных натуральных чисел AиBнайти пару целых чиселPиQтаких, что
1.0.3.2. Даны коэффициенты линейного уравненияAx+By+C= 0 (A,B,C) и пределы изменения переменныхX1 <=x<=X2 иY1 <=y<=Y2. Сколько целочисленных решений (парxиy) существует в указанных пределах.
1.0.3.3. Вырубка деревьев. Король решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы. После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев и соседние деревья находились на равном расстоянии друг от друга.
Входные данные содержат два целых числа n и m (0 ≤ m , n ≤ 1000). В единственную строку вывести одно целое число — искомое число способов.
Если обозначить условно исходное расположение деревьев перед дворцом как «TTTTT», то возможные результаты после вырубки следующие: «TTT..», «.TTT.», «..TTT», «T.T.T».
1.0.3.4. Сумма произведений. Требуется вычислить сумму произведений цифр каждого N-значного числа. При этом следует учесть, что если в числе встречается цифра 0, то произведение его цифр равно нулю. Для N=3 искомая сумма представлена следующим рядом: S = 1*0*0 + 1*0*1 + 1*0*2 + … + 9*9*8 + 9*9*9 = 91125 В единственной строке записано натуральное число N (N < 1000).
1.0.3.5. Произведение цифр. Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N (0 ≤ N ≤ 10 9 ). Вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.