Для каждой задачи подготовить полусекретный набор тестовых данных – не для печати – для проверки решений детей
Дополнение для части 2 – обработка исключений
ОГЛАВЛЕНИЕ
Часть 1. Основы программирования и информатика
1.0. Разминка – введение в алгоритмы – элементарные алгоритмы
1.1. Геометрия
1.2. Последовательности
1.3. Массивы
1.4. Сортировки
1.5. Символьные строки (тексты)
1.6. Матрицы
1.7. Функции и рекурсия
1.8. Автоматы
1.9. Дополнительные задачи
В данном методическом пособии используются как классические задачи по программированию, так и задачи, взятые с сайтов по спортивному программированию.
Тема 1.0. Элементарные алгоритмы
Цель.
Изучение основных конструкций языка программирования. Умение построить алгоритм для решения задачи и записать его на языке программирования.
Основные понятия.
Решение задачи состоит в описании объектов и указания действий над ними с целью получения нужного результата.
Основной метод решения сложных задач - разбиение задачи на подзадачи - декомпозиция
Существует 3 механизма декомпозиции:
- линейная последовательность – задача разбивается на последовательность шагов (подзадач), которые выполняются друг за другом;
- ветвление по условию – задача разбивается на 2 или несколько параллельных подзадач и в зависимости от некоторого условия будет выполняться только одна из подзадач;
- многократное повторение – задача разбивается на последовательность одинаковых (подобных) подзадач. Эта подзадача будет выполняться несколько раз.
Эти 3 механизма используются при декомпозиции многократно до тех пор, пока задача не сведётся к очевидным (элементарным) действиям.
В каждой задаче (подзадаче) нужно уметь выделять объекты, над которыми будут выполняться действия.
Объекты характеризуются своим типом и в каждый момент времени имеют некоторое значение, которое хранится в оперативной памяти.
Действия задаются операторами и состоят в выполнении некоторых допустимых операций над объектами.
Структура простой программы:
подключения стандартных библиотек (#include)
определение главной функции (main). Внутри неё описываются объекты и операторы.
Ввод данных и печать результатов.
Ключевые слова.
Переменная, константа, Описание. Оператор. Программа. Оператор препроцессора #include.
ПРИМЕР.
Дано натуральное число. Напечатать все его делители в порядке возрастания.
Алгоритм.
Для решения этой задачи будем перебирать все натуральные числа от 1 до самого заданного числа. Те числа, на которые будет делиться без остатка заданное число, будем печатать.
Решение.
// C++
# include <iostream> // используется для подключения некоторых стандартных
# include <conio.h> // возможностей для ввода-вывода информации
using namespace std; // для использования некоторых стандартных имён
int main () // основная часть программы – главная функция
{
setlocale (LC_ALL, "RUS");
cout << "Вычисление делителей числа = ";
int n;
cin >> n;
for (int i=1; i <= n; i++)
if (n%i == 0)
cout << i << " ";
getch (); // задержка – смотреть результаты на экране
return 0;
}
// C#
using System;
class Program
{
static void Main (string [] args) // Main - обязательное имя
{
Console.Write ("Вычисление делителей числа = ");
int n = int.Parse (Console.ReadLine ());
for (int i=1; i <= n; i++)
if (n%i == 0)
Console.Write (" " + i);
Console.ReadKey ();
}
}
Дополнительные замечания.
Простой анализ программы показывает возможности ускорения в 2 раза. Во-первых, на числа 1 и n можно не делить, а из остальных проверять только числа от 2 до n/2.
Задачи для обязательного решения
1.0.1.1. Квадратное уравнение. Даны вещественные коэффициенты квадратного уравнения A*X^2 + B*X + C = 0. Коэффициент А!= 0. Написать программу для вычисления и печати корней этого уравнения. Ответ напечатать с точностью 2 знака после запятой. Если корней не существует, напечатать слово «НЕТ».
Исходные данные:
1 2 1
Результат:
-1 -1
1.0.1.2. Уравнение степени не выше 2-х. Даны вещественные коэффициенты A, B, C уравнения A*X^2 + B*X + C = 0. Некоторые коэффициенты могут быть нулями. Написать программу для вычисления и печати корней этого уравнения. Ответ напечатать с точностью 2 знака после запятой. Если корней не существует, напечатать слово «НЕТ». Если существует бесконечно много корней, напечатать «МНОГО».
Исходные данные:
0 2 1
Результат:
-0.50 -0.50
1.0.1.3. СЛАУ. Даны вещественные коэффициенты двух линейных алгебраических уравнений с двумя неизвестными: А1, В1, С1 и А2, В2, С2. Написать программу для вычисления и печати корней этой системы уравнений. Если корней не существует, напечатать слово «НЕТ». Если существует бесконечно много корней, напечатать «МНОГО». Уравнения имеют вид: A1*X + B1*Y = C1 и A2*X + B2*Y = C2.
Исходные данные:
1 1 2
2 2 4
Результат:
МНОГО
1.0.1.4. Факториал. Дано неотрицательное целое число K. Написать программу для вычисления и печати числа K!
Исходные данные:
Результат:
1.0.1.5. Число сочетаний. Даны натуральные числа N и M (0 <= M <= N). Написать программу нахождения и печати числа сочетаний из N по M по формуле 
.
Исходные данные:
5 2
Результат:
1.0.1.6. НОД. Даны натуральные числа А и В. Написать программу нахождения и печати наибольшего общего делителя этих чисел.
Исходные данные:
12 18
Результат:
1.0.1.7. НОК. Даны натуральные числа А и В. Написать программу нахождения и печати наименьшего общего кратного этих чисел.
Исходные данные:
12 18
Результат:
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.
Исходные данные:
2 12
Результат:
2 5 8 10
1.0.1.11. Дано натуральное число N. Напечатать это число цифрами наоборот.
Исходные данные:
Результат:
1.0.1.12. EXP. Вычисление ряда 1 + x + x2/2! + x3/3! + … для заданного аргумента X с заданной точностью eps. Результат напечатать с 3 знаками после запятой.
Исходные данные:
1.0 0.001
Результат:
2.718
1.0.1.13. Написать программу для вычисления (1+z)(1+z+z2)(1+z+z2+z3) …(1+z+z2… +zn) для заданного вещественного числа z и натурального числа n. Результат напечатать с 3 знаками после запятой.
Исходные данные:
1.0 3
Результат:
24.0
1.0.1.14. Написать программу для вычисления значения (2+z)(3+2z+z2)(4+3z+2z2+z3) …(n+1+nz+(n-1)z2… +zn) для заданного вещественного числа z и натурального числа n. Результат напечатать с 3 знаками после запятой.
Исходные данные:
1.0 3
Результат:
180.0
