Казанский (Приволжский) Федеральный университет

Ордена Ленина и ордена Трудового Красного знамени

Институт вычислительной математики и информационных технологий

Кафедра системного анализа и информационных технологий

Андрианова А.А., Васильев А.В., Галимзянов И., Дябилкин Д.А., Мухтарова Т.М., Тагиров Р.Р., Шаймухаметов Р.Р.

Лабораторные работы по курсу

«Основы программирования, Информатика, ООП, Языки программирования»

Семестр 1

Основы программирования и информатика

Методическое пособие

Казань – 2015

Краткий план и мысли по поводу

Часть 1 – Основы программирования и информатика

Часть 2 – Объектно-ориентированное программирование

Часть 3 – Языки программирования

- языки программирования C++,C#, [Java,Python,Ruby]

- выбрать для каждой части набор тем (7-10)

- для каждой темы вступление – цель этой лабораторной работы

- краткое напоминание основных терминов (без соплей) и ключевые слова – 1 страница

- пример: условие задачи + словесное описание алгоритма + реализация на разных языках С++ и С#

- 10-15 простых задач + 5-10 сложных задач + несколько для самостоятельной работы + несколько страшных задач для продвинутых детей

- для каждой темы задач объявить минимальный обязательный набор средств, частей в решении и т.д. Например, обязательно ввод из текстового файла и вывод в текстовый файл и на экран. Строго описать формат ввода и вывода. Что должно быть оформлено в виде отдельных функций. Какие параметры или глобальные константы.

- простые (обязательные) задачи – краткое условие

- для каждой самостоятельной и трудной задачи несколько примеров входных и соответствующих выходных данных

Отдельный пункт – комплексное задание по нескольким темам одновременно?

Что должно содержать в отчёте по каждой лабораторной работе – чётко перечислить

Может быть делать 1 общий отчёт по всем работам или по группе тем?

Не обязательно задачи каждой темы давать для самостоятельной работы

Для каждой задачи подготовить полусекретный набор тестовых данных – не для печати – для проверки решений детей

Дополнение для части 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!

Исходные данные:

5

Результат:

120

1.0.1.5.Число сочетаний. Даны натуральные числаNиM(0 <=M<=N). Написать программу нахождения и печати числа сочетаний изNпоMпо формуле.

Исходные данные:

5 2

Результат:

10

1.0.1.6. НОД. Даны натуральные числа А и В. Написать программу нахождения и печати наибольшего общего делителя этих чисел.

Исходные данные:

12 18

Результат:

6

1.0.1.7. НОК. Даны натуральные числа А и В. Написать программу нахождения и печати наименьшего общего кратного этих чисел.

Исходные данные:

12 18

Результат:

36

1.0.1.8. Простота. Дано натуральное число. Напечатать слово "ПРОСТОЕ", если это число является простым, т.е. не делится ни на какое число, кроме 1 и самого себя. В противном случае напечатать слово "СОСТАВНОЕ".

Исходные данные:

12

Результат:

СОСТАВНОЕ

1.0.1.9. Совершенство. Дано натуральное число. Напечатать слово "СОВЕРШЕННОЕ", если это число является совершенным, т.е. оно равно сумме всех своих собственных делителей (кроме самого себя). В противном случае напечатать слово "НЕ СОВЕРШЕННОЕ".

Например, число 4 не совершенное, т.к. 4 != 1+2. Число 6 - совершенное, т.к. 6 = 1+2+3.

Исходные данные:

28

Результат:

СОВЕРШЕННОЕ

1.0.1.10. Пифагоровы числа. Даны натуральные числа А и В. Написать программу для печати всех чисел из диапазона [A..B], которые представимы в виде суммы двух квадратов натуральных чисел. Например, число 17 = 1*1 + 4*4.

Исходные данные:

2 12

Результат:

2 5 8 10

1.0.1.11. Дано натуральное числоN. Напечатать это число цифрами наоборот.

Исходные данные:

27351

Результат:

15372

1.0.1.12.EXP. Вычисление ряда 1 +x+x²/2! +x³/3! + … для заданного аргументаXс заданной точностью eps. Результат напечатать с 3 знаками после запятой.

Исходные данные:

1.0 0.001

Результат:

2.718

1.0.1.13. Написать программу для вычисления (1+z)(1+z+z²)(1+z+z²+z³) …(1+z+z²… +zⁿ) для заданного вещественного числаzи натурального числаn. Результат напечатать с 3 знаками после запятой.

Исходные данные:

1.0 3

Результат:

24.0

1.0.1.14. Написать программу для вычисления значения (2+z)(3+2z+z²)(4+3z+2z²+z³) …(n+1+nz+(n-1)z²… +zⁿ) для заданного вещественного числаzи натурального числаn. Результат напечатать с 3 знаками после запятой.

Исходные данные:

1.0 3

Результат:

180.0

Задачи для самостоятельного решения

1.0.2.1. Даны натуральные числа А и В (A<=B). Написать программу, которая напечатает все простые числа из диапазона от А до В.

Исходные данные:

10 23

Результат:

11 13 17 19 23

1.0.2.2. Даны натуральные числа А и В (A<=B). Написать программу, которая напечатает все совершенные числа из диапазона от А до В.

Исходные данные:

2 30

Результат:

6 28

1.0.2.3. Пифагоровы числа. Даны натуральные числа А и В (A<=B). Написать программу для печати всех чисел из диапазона от А до В, которые представимы в виде суммы двух квадратов натуральных чисел несколькими способами. Например, число 50 = 5*5 + 5*5 = 1*1 + 7*7 (2 способа).

Исходные данные:

49 51

Результат:

50

1.0.2.4. Быстрое возведение числа в натуральную степень. Написать программу, которая возведёт число А в натуральную степень В за log₂В операций умножения, используя двоичное представление числа В.

Исходные данные:

2 21

Результат:

2097152

1.0.2.5. Рассматриваются все числа от 1 доn. Написать программу, которая вычислит и напечатает общее количество всех цифр во всех этих числах вместе взятых.

Исходные данные:

17

Результат:

25

1.0.2.6. Написать программу приближенного вычисления и печати числапо формуле... Вычисления проводить до тех пор, пока не будет достигнута точностьeps, т.е. два последних вычисленных значения не станут отличаться меньше, чем на малое положительное eps. Результат напечатать с 3 знаками после запятой.

Исходные данные:

0.0001

Результат:

3.142

1.0.2.7.SIN. Написать программу приближенного вычисления и печати суммы рядаx+x³/3! +x⁵/5! + … для заданного аргументаXс заданной точностью eps, т.е. очередное слагаемое не станет меньше малого положительного eps. Результат напечатать с 3 знаками после запятой.

Исходные данные:

3.141 0.001

Результат:

0.000

1.0.2.8.COS. Написать программу приближенного вычисления и печати суммы ряда 1 +x²/2! +x⁴/4! + … для заданного аргументаXс заданной точностью eps, т.е. очередное слагаемое не станет меньше малого положительного eps. Результат напечатать с 3 знаками после запятой.

Исходные данные:

3.141 0.001

Результат:

-1.000

1.0.2.9. С натуральным числомnвыполняются следующие преобразования (операции): если оно четно, то делится пополам, а если нечетно, то умножается на 3 и прибавляется 1. С полученным числом опять выполняется преобразование до тех пор, пока не получится число 1. Для заданного интервала чисел отAдоBвычислить и напечатать количество выполняемых операций (преобразований) для каждого числа из этого интервала.

Исходные данные:

2 30

Результат:

6 28

1.0.2.10. Зарплата. В отделе работают 3 сотрудника, которые получают заработную плату в рублях. Требуется определить: на сколько зарплата самого высокооплачиваемого из них отличается от самого низкооплачиваемого. В единственной строке записаны размеры зарплат всех сотрудников через пробел. Каждая заработная плата – это натуральное число, не превышающее 10⁵. Вывести одно целое число — разницу между максимальной и минимальной зарплатой.

Исходные данные:

100 500 1000

Результат:

900

1.0.2.11. Написать программу для решения уравнения . Вещественные значенияa,b,cвводятся.

Исходные данные:

Результат:

1.0.2.12. Написать программу для решения уравнения . Вещественные значенияa,b,cвводятся.

Исходные данные:

Результат:

1.0.2.13. Написать программу для вычисления корня квадратного из положительного вещественного числа х по итерационной формуле Ньютона U_k=U_k-1/2 +X/2/U_k-1.

Исходные данные:

Результат:

1.0.2.14. Написать программу для вычисления корня кубического из положительного вещественного числа х по итерационной формуле Ньютона U_k= 2/3U_k-1+X/3/U_k-2/U_k-2.

Исходные данные:

Результат:

Продвинутые задачи

1.0.3.1. Обобщённый алгоритм Эвклида.

Для заданных натуральных чисел AиBнайти пару целых чиселPиQтаких, что

A*P + B*Q = 1

Исходные данные:

2 3

Результат:

2 -1

1.0.3.2. Даны коэффициенты линейного уравненияAx+By+C= 0 (A,B,C) и пределы изменения переменныхX1 <=x<=X2 иY1 <=y<=Y2. Сколько целочисленных решений (парxиy) существует в указанных пределах.

Исходные данные:

3 5

Результат:

3 7

4 2

5 5

1.0.3.3. Вырубка деревьев. Король решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы. После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев и соседние деревья находились на равном расстоянии друг от друга.

Входные данные содержат два целых числа n и m (0 ≤ m , n ≤ 1000). В единственную строку вывести одно целое число — искомое число способов.

Исходные данные:

5 3

Результат:

4

Примечание:

Если обозначить условно исходное расположение деревьев перед дворцом как «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).

Исходные данные:

5

Результат:

184528125

1.0.3.5. Произведение цифр. Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N (0 ≤ N ≤ 10⁹). Вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.

Исходные данные:

90

Результат:

259