Информатика и программирование - часть 1

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

Рекурсивность в постановке задачи проявляется, если решение для общего случая сводится к аналогичным задачам для меньшего количества входных данных. В таком контексте под рекурсией понимают прием последовательного сведения решения некоторой задачи к решению совокупности «более простых» задач такого же класса и получению на этой основе решения исходной задачи.

Рекурсия в широком смысле – это определение объекта посредством ссылки на себя. Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи,

подобные исходной.

Рекурсивный алгоритм – это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.

В языках программирования процедурной парадигмы предусмотрено использование рекурсивных функций в решении задач.

Функция называется рекурсивной, если в своем теле она содержит обращение к самой себе с измененным набором параметров. При этом количество обращений конечно,

так как в итоге решение сводится к базовому случаю, когда ответ очевиден.

Использование генератора случайных чисел.

При дальнейшей работе возникнет необходимость использования случайных чисел.

Для этого необходимо создать экземпляр системного класса System.Random и

использовать методы Next() и NextDouble()

Пример.

System.Random RND = new Random(); int j = RND.Next();

double k = RND.NextDouble();

Задачи для самостоятельной работы

Описать функцию Even(K) логического типа, возвращающую True, если целый параметр K является четным, и False в противном случае. С ее помощью найти количество четных чисел в наборе из 10 целых чисел.

Описать функцию Quarter(x, y) целого типа, определяющую номер координатной четверти, в которой находится точка с ненулевыми вещественными координатами (x, y).

С помощью этой функции найти номера координатных четвертей для трех точек с данными ненулевыми координатами.

Дны натуральные числа n, m, целые числа a1, a2, ..., an, b1, ..., bm, c1, ..., с10.

Получить: L = min (b1, …, bm) + min (a1, …, am ) + min (c1, …, c10).

Даны натуральные числа k, l, m, действительные числа x1, ..., xk, y1, ..., yl, z1, ..., zm.

Получить L = max(y1,…, yl) + max(z1,…, zm), если max(x1,…, xk) > 30.

Дано натуральное число n. Среди чисел 1, 2, 3, ..., n найти все те, которые можно представить в виде сумм квадратов двух натуральных чисел. Определить процедуру,

позволяющую распознавать полные квадраты.

Даны действительные числа x1, y1, x2, y2, ..., x10, y10. Найти периметр десятиугольника, вершины которого имеют соответственно координаты (x1, y1), (x2, y2),

..., (x10, y10).

Определить процедуру вычисления расстояния между двумя точками, заданными своими координатами.

Описать процедуру Swap(X, Y), меняющую содержимое переменных X и Y (X и Y —

вещественные параметры, являющиеся одновременно входными и выходными).

С ее помощью для данных переменных A, B, C, D последовательно поменять содержимое следующих пар: A и B, C и D, B и C и вывести новые значения A, B, C, D.

Даны действительные числа a, b, c, d, е. Найти площадь пятиугольника. Определить процедуру вычисления площади треугольника по трём сторонам.

Даны натуральное число n, действительные числа x1, y1, x2, y2, ..., xn, yn. Найти площадь n-угольника, вершины которого при некотором последовательном обходе имеют координаты (x1, y1), (x2, y2), ..., ( xn, yn). Определить процедуру вычисления площади n-

угольника по координатам его вершин.

Дано натуральное число n. Выяснить, имеются ли среди чисел n, n+1, ..., 2n простые числа, разность между которыми равна. Определить процедуру, позволяющую распознать простые числа.

Составить процедуру, результатом работы которой является истинное значение, если символ, заданный при обращении к процедуре, буква, и ложное значение в противном случае.

Составить процедуру, результатом работы которой является символ, заданный при обращении к процедуре, если этот символ не является буквой, и соответствующая строчная (малая) буква в противном случае.

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

Массивы.

Массивом называют упорядоченную совокупность элементов одного типа. Каждый элемент массива имеет индексы, определяющие порядок элементов. Индексы задаются целочисленным типом. Число индексов характеризует размерность массива. Если конечное значение задано константным выражением, то число элементов массива известно в момент его объявления и ему может быть выделена память ещё на этапе трансляции. Такие массивы называются статическими. Если же конечное значение зависят от переменной, то такой массив называют динамическим, поскольку память ему может быть отведена только динамически в процессе выполнения программы, когда становятся известными значения соответствующих переменных. Массиву, как правило, выделяется непрерывная область памяти.

В языке C# каждый индекс изменяется в диапазоне от 0 до некоторого конечного значения. Массивы в языке C# являются настоящими динамическими массивами. Как следствие этого, массивы относятся к ссылочным типам, память им отводится динамически в "куче". Массивы могут быть одномерными и многомерными.

Объявление одномерного массива выглядит следующим образом:

<тип>[] <объявители>;

Как и в случае объявления простых переменных, каждый объявитель может быть именем или именем с инициализацией. В первом случае речь идёт об отложенной инициализации. Нужно понимать, что при объявлении с отложенной инициализацией сам массив не формируется, а создаётся только ссылка на массив, имеющая неопределённое значение Null. Поэтому пока массив не будет реально создан и его элементы инициализированы, использовать его в вычислениях нельзя!!! Вот пример объявления трёх массивов с отложенной инициализацией:

int[] a, b, c;

Чаще всего при объявлении массива используется имя с инициализацией. И опять-

таки, как и в случае простых переменных, могут быть два варианта инициализации. В

первом случае инициализация является явной и задаётся константным массивом. Вот пример:

double[] x = { 5.5, 6.6, 7.7 };

Следуя синтаксису, элементы константного массива следует заключать в фигурные скобки. Если массив инициализируется константным массивом, то в динамической памяти создаётся константный массив с заданными значениями, с которым и связывается ссылка.

Во втором случае создание массива выполняется с помощью операции new.

int[] d = new int[5];

Здесь объявлен динамический целочисленный массив, в котором будут храниться 5

целых чисел. Массив создаётся в динамической памяти, его элементы получают

начальные нулевые значения, и ссылка связывается с этим массивом.

Как обычно задаются элементы массива, если они не заданы при инициализации?

Они либо вычисляются, либо вводятся пользователем. Рассмотрим пример работы с

массивами:

public void ExArray()

{

//объявляются три одномерных массива A,B,C int[] A = new int[5], B = new int[5], C = new int[5];

//заполняется данными с клавиатуры массив A

for (int i = 0; i < 5; i++) A[i] = int.Parse(Console.ReadLine()); // вычисляются элементы массива C

for (int i = 0; i < 5; i++) C[i] = A[i] + B[i];

//объявление массива с явной инициализацией double[] x = { 5.5, 6.6, 7.7 };

//объявление массивов с отложенной инициализацией int[] u, v;

u = new int[3];

for (int i = 0; i < 3; i++) u[i] = i + 1;

//v = {1,2,3}; // присваивание константного массива недопустимо! v = new int[4];

v = u; // допустимое присваивание – массивы одного класса

}

На что следует обратить внимание, анализируя этот текст:

Показаны разные способы объявления массивов. В начале объявляются одномерные массивы A, B и C. Значения элементов этих трёх массивов имеют один и тот же тип int. То, что они имеют одинаковое число элементов, произошло по воле программиста, а не диктовалось требованиями языка. Значения в массив А вводились, а в массив B - нет, но сложение элементов корректно, потому что при объявлении элементы массива B получили нулевые значения.

Массив x объявлен с явной инициализацией. Число и значения его элементов определяется константным массивом.

Массивы u и v объявлены с отложенной инициализацией. В последующих операторах массив u инициализируется в объектном стиле – его элементы получают значения в цикле.

Обратите внимание на закомментированный оператор присваивания! В отличие от инициализации, использовать константный массив в правой части оператора присваивания недопустимо. Эта попытка приводит к ошибке, поскольку v - это ссылка, и

ей нельзя присвоить константный массив. А вот ссылку присвоить можно. Что происходит в операторе присваивания v = u? Это корректное ссылочное присваивание:

хотя u и v имеют разное число элементов, но они являются объектами одного класса – оба массива целочисленные. В результате присваивания память, отведённая массиву v,

освободится, ею займется теперь сборщик мусора. Обе ссылки u и v будут теперь указывать на один и тот же массив, так что изменение элемента одного массива немедленно отразится на другом массиве. Имена u и v становятся синонимами (или псевдонимами друг друга…).

Далее определяется двумерный массив w и делается попытка выполнить оператор присваивания v = w. Это ссылочное присваивание некорректно, поскольку объекты w и v - разных классов (разноразмерные массивы) и для них не выполняется требуемое для присваивания согласование по типу.

Динамические массивы

Во всех вышеприведенных примерах объявлялись статические массивы, поскольку нижняя граница равна нулю по определению, а верхняя всегда задавалась в этих примерах константой. Напомню, что в C# все массивы, независимо от того, каким выражением описывается граница, рассматриваются как динамические, и память для них распределяется в "куче". Полагаю, что это отражение разумной точки зрения: ведь статические массивы, скорее исключение, а правилом является использование динамических массивов. В действительности реальные потребности в размере массива,

скорее всего, выясняются в процессе работы в диалоге с пользователем.

Чисто синтаксически нет существенной разницы в объявлении статических и динамических массивов. Выражение, задающее границу изменения индексов, в

динамическом случае содержит переменные. Единственное требование - значения переменных должны быть определены в момент объявления. Это ограничение в C#

выполняется автоматически.

public void DynamicArray()

{

//объявление динамического массива A Console.WriteLine("Введите число элементов массива A"); int size = int.Parse(Console.ReadLine());

int[] A = new int[size];

}

Многомерные массивы

Уже объяснялось, что разделение массивов на одномерные и многомерные носит исторический характер. Никакой принципиальной разницы между ними нет. Одномерные

массивы - это частный случай многомерных. Можно говорить и по-другому: многомерные массивы являются естественным обобщением одномерных. Одномерные массивы позволяют задавать такие математические структуры как векторы, двумерные - матрицы,

трехмерные - кубы данных, массивы большей размерности - многомерные кубы данных.

При работе с базами данных многомерные кубы, так называемые кубы OLAP,

встречаются сплошь и рядом.

В чем особенность объявления многомерного массива? Как в типе указать размерность массива? Это делается достаточно просто, за счет использования запятых.

Вот как выглядит объявление многомерного массива в общем случае:

<тип>[, ... ,] <объявители>; Число запятых, увеличенное на единицу, и задает размерность массива. Что

касается объявителей, то все, что сказано для одномерных массивов, справедливо и для многомерных. Можно лишь отметить, что хотя явная инициализация с использованием многомерных константных массивов возможна, но применяется редко из-за громоздкости такой структуры. Проще инициализацию реализовать программно, но иногда она все же применяется.

public void MultiArray()

{

int[,] arr = { { 1, 1 }, { 2, 2 } };

}

Теперь можно рассмотреть особый вид оператора цикла – оператор foreach. Его синтаксис:

foreach (тип идентификатор in массив) оператор

Цикл работает в полном соответствии со своим названием – тело цикла выполняется для каждого элемента в контейнере. Тип идентификатора должен быть согласован с типом элементов, хранящихся в массиве данных. Предполагается также, что элементы массива упорядочены. На каждом шаге цикла идентификатор, задающий текущий элемент массива, получает значение очередного элемента в соответствии с порядком, установленным на элементах массива. С этим текущим элементом и выполняется тело цикла - выполняется столько раз, сколько элементов находится в массиве. Цикл заканчивается, когда полностью перебраны все элементы массива.

В приведённом ниже примере показана работа с трёхмерным массивом. Массив создаётся с использованием циклов типа for, а при нахождении суммы его элементов,

минимального и максимального значения используется цикл foreach:

public void ExForeach()

{

int[, ,] arr3d = new int[10, 10, 10]; for (int i = 0; i < 10; i++)

for (int j = 0; j < 10; j++)

for (int k = 0; k < 10; k++)

arr3d[i, j, k] = int.Parse(Console.ReadLine()); long sum = 0;

int min = arr3d[0, 0, 0], max = arr3d[0, 0, 0]; foreach (int item in arr3d)

{

sum += item;

if (item > max) max = item; else if (item < min) min = item;

}

Console.WriteLine("sum = {0}, min = {1}, max = {2}", sum, min, max);

}

Серьёзным недостатком циклов foreach в языке C# является то, что цикл работает

только на чтение, но не на запись элементов. Так что наполнять массив элементами

приходится с помощью других операторов цикла.

Список задач

Даны натуральные числа n, A1, ..., An. Определить количество членов Ak

последовательности A1, ..., An:

являющихся нечётными числами;

кратных 3 и некратных 5;

являющихся квадратами чётных чисел;

Даны натуральные числа n, A1, ..., An. Найти те элементы Ak последовательности n,

A1,..., An, которые:

являются удвоенными нечётными числами;

при делении на 7 дают остаток 1,2 или 5;

Даны целые числа А1,..., А20. Получить сумму трёх членов данной последовательности,

которые:

кратны 5;

нечётны и отрицательны;

удовлетворяют условию |Ai| <i*2.

Даны натуральное число n, целые числа A1, ..., An. Найти количество и сумму тех членов последовательности, которые делятся на 5 и не делятся на 7.

Даны целые числа p, q, A1,...,A17 (p>q>0). В последовательности заменить нулями элементы, модуль которых при делении на p даёт в остатке q.

Даны натуральные числа n, p, целые числа A1, ..., An. Получить произведение элементов последовательности, кратных p.

Даны натуральное число n, действительные числа A1, ..., An. В последовательности получить удвоенную сумму всех положительных элементов.

Даны натуральное число n, действительные числа A1, ..., An. В последовательности все отрицательные числа увеличить на 0.5, а все неотрицательные на 0.1.

Даны натуральное число n, действительные числа A1, ..., An. В последовательности все элементы, меньше 2, заменить нулями. Кроме того, получить сумму элементов,

принадлежащих отрезку [3,7], а также число таких элементов.

Даны натуральное число n, действительные числа A1, ..., An. В последовательности все неотрицательные элементы, не принадлежащие отрезку [1,2], заменить на 1. Кроме того, получить число отрицательных элементов и число элементов, принадлежащих отрезку [1,2].

Даны натуральное число n, целые числа A1, ..., An. Получить сумму положительных и число отрицательных элементов последовательности.

Даны натуральное число n, целые числа A1, ..., An. Заменить все, большие 7, элементы последовательности числом 7. Вычислить количество таких элементов.

Даны целые числа A1, ..., A15. Получить число отрицательных элементов последовательности A1, ..., A15 и число нулевых элементов всей последовательности

A1,..., A15.

Даны натуральное число n, целые числа А, Х1, ..., Хn. Если в последовательности есть хотя бы один элемент, равный А, то получить сумму всех элементов, следующих за первым таким элементом; в противном случае ответом должно быть число 10.

Даны целые числа A1, ..., A20. Получить последовательность В1, ..., В20, которая отличается от исходной тем, что все нечётные элементы удвоены.

Даны натуральное число n, целые числа А, Х1, ..., Хn. Определить, каким по счёту идёт в последовательности элемент, равный А. Если такого элемента нет, то ответом должно быть число 0.

Даны натуральное число n, действительные числа А1, ..., Аn. Получить:

max (A1,...,An);

min (A1,...,An);

max (A2, A4, ...);

min (A1, A3,...);

min (A2, A4,...) + max (A1, A3, ...);

max (|A1|, ..., |An|);

max(-A1, A2, -A3, ..., (-1)n An);

(min (A1, ..., An))2 - min(A12, ..., An 2).

Дано натуральное число n. Выбросить из записи числа n цифры 0 и 5, а оставив прежним порядок остальных цифр. Например, из числа 59015509 должно получиться

919.

Даны натуральное число n, целые числа А1, ..., Аn. Найти:

наименьшее из чётных чисел, входящих в последовательность А1, ..., An.

наибольшее из нечетных и количество чётных чисел, входящих в последовательность

A1, ..., An, An+1.

Даны натуральное число n, действительные числа А1, ..., Аn. В последовательности определить число соседств:

двух положительных чисел;

двух чисел разного знака;

двух чисел одного знака, причём модуль первого числа должен быть больше модуля второго числа.

Даны целые числа С1, ..., С15. Имеются ли в последовательности:

два идущих подряд нулевых элемента;

три идущих подряд нулевых элемента.

Даны натуральное число n. Получить все такие натуральные q, что n делится на q2 и не делится на q3.

Даны натуральные числа m, n. Получить все их натуральные общие кратные, меньше mn.

Даны целые положительные числа m, n. Получить все их общие делители.

Даны натуральное число n, действительные числа А1, ..., Аn. Выяснить, является ли последовательность упорядоченной по убыванию.

Даны натуральное число n, целые числа А1, ..., Аn.

Выяснить, какое число встречается в последовательности раньше -

положительное или отрицательное. Если все элементы последовательности равны нулю, то сообщить об этом.

Найти номер первого чётного элемента последовательности; если чётных элементов нет, то ответом должно быть число 0.

Найти номер последнего нечётного элемента последовательности; если нечётных элементов нет, то ответом должно быть число n+1.

Алгоритмы циклической структуры с использованием одномерных массивов.

В массиве {Aj}, j=1, 2, 10 есть хотя бы один отрицательный элемент. Вычислить произведение элементов в массиве до первого отрицательного.

В массиве есть хотя бы один нуль.

Вычислить произведение элементов массива до первого нуля.

Вычислить сумму элементов массива до первого нуля.

В массиве существуют отрицательный и положительный элементы. Вычислить:

сумму положительных элементов;

сумму отрицательных элементов;

количество положительных элементов;

количество отрицательных элементов;

произведение положительных элементов;

произведение отрицательных элементов;

В массиве подсчитать количество элементов, больших 3.

Составить программу для вычисления суммы S элементов числовой последовательности А1, А2, ..., А10 по формуле S=A1+A2+...+A10.

Составить программу для вычисления суммы элементов последовательности целых чисел Р1, Р2, ..., Р10, имеющих чётные индексы и произведение элементов последовательности Р1, Р2, ..., Р10, имеющих нечётные индексы.

Вычисление с хранением последовательности значений

Даны действительные числа A1, ..., An, B1, ..., Bn. Вычислить (A1+Bn)×(A2+Bn-1)×...× (An+B1).

Даны действительные числа A1, А2, ..., A2n. Получить: A1, An+1, A2, An+2, ..., An, A2n;

A1, A2n, А2, A2n-1, A3, ..., An, An+1;

A1+A2n, A2+A2n-1, ..., An+An+1.

Даны действительные числа A1, А2, ..., A17. Получить:

A17, A1, A2, ..., A16;

A11, A12, ..., A17, A1, A2, ..., A10;

A11, A12, ..., A17, A10, A9, ..., A1;

A1, A3, ..., A17, A2, A4, ..., A16.

Даны действительные числа A1, ..., Аn. Если в результате замены отрицательных элементов последовательности их квадратами элементы будут образовывать неубывающую последовательность, то получить сумму элементов исходной последовательности; в противном случае их произведение.