ОП4
.docx
Министерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
Функции
Лабораторная работа №4 по дисциплине «Основы программирования»
Отчет по лабораторной работе
Студент гр. 739-1
_______Климанов М. Д.
02.05.2020
Принял
Доцент кафедры БИС
_______Харченко С.С.
02.05.2020
Томск 2020
1 Введение
Цель работы: овладеть навыками использования функций в программировании и рекурсивным подходом решения задач, понять отличия рекурсивного и итеративного подхода решения задачи.
Задание 1: Даны 4 натуральных числа. Найти наибольший общий делитель(НОД) для этих четырех чисел.
Задание 2: Организовать бинарный поиск заданного числа в массиве (массив предварительно нужно отсортировать)
2 Теоретические сведения
2.1 Функции
Функция – именованный фрагмент программного кода, к которому можно обратиться из другого места программы. Функция может принимать на вход параметры и должна возвращать некоторое значение, возможно пустое. Входные параметры могут быть обязательными и не обязательными. Функции, которые возвращают пустое значение или не возвращают его(в зависимости от языка программирования) принято называть процедурами. Объявление функции, кроме имени, содержит список имён и типов передаваемых параметров, а также, тип возвращаемого функцией значения. В Си-подобных языках программирования процедуры еще называют void-функциями, поскольку вместо указания типа возвращаемого значение указывается ключевое слово void, которое означает, что функция не возвращает значение. Для того, чтобы использовать ранее определённую функцию, необходимо в требуемом месте программного кода указать имя функции и перечислить передаваемые в функцию параметры.
В C# можно создавать пользовательские функции. Собственно говоря, мы с самого начала создавали функции: Main – не что иное, как главная функция пользователя или точка входа в приложение. В языке C# и фреймворке
.Net Framework, которые мы до сих пор использовали имеется огромное количество встроенных библиотек с набором функций, однако их не всегда достаточно для решения той или иной задачи. Каждая библиотека может содержать в себе одно или несколько пространств имен. Для подключения пространства имен используется запись вида - using System.IO; где «using» это ключе- вое слово, а «System.IO» - название пространства имен, содержащего функции для работы с файловой системой.
Функция определяет локальную область видимости, куда входят входные параметры, а также те переменные, которые объявляются непосредственно в теле самой функции. После выполнения тела функции локально переменные функции буду недоступны. Внутри функции можно вызывать другие функции. Существует возможность вызвать функцию внутри самой себя – рекурсивный вызов, а сам процесс последовательных вложенных друг в друга вызовов функций называют рекурсией.
Рекурсия – определение части функции через саму себя, то есть это функция, которая вызывает саму себя, непосредственно в своём теле или косвенно через другую функцию. Количество вложенных вызовов функции называется глубиной рекурсии. Использование рекурсии позволяет осуществлять повторяющиеся вычисления и/или действия без явных повторений или организации циклов в программе, однако также как у цикла с условием должно быть четко оговорено условие остановки рекурсивных вызовов, для предотвращения зацикливания программы. Вторая составляющая любой рекурсивной функции это условие продолжения(шаг рекурсии), где идет рекурсивное обращение.
3 Ход работы
Задание 1 Даны 4 натуральных числа. Найти наибольший общий делитель(НОД) для этих четырех чисел.
Для начала составим Алгоритм А:
А.1 ввод a, b;
А.2 a != b, то повторять;
A.3 если a>b ;
A.4; a= b
A.5 b = b-a;
A.6 возвращаем а;
A.7присваиваем I = 2;
A.8 присваиваем массив;
A.9 если i<полученное общее элементов массива
A10 то nod = массиву
A.11 i+1
A.12 возвращаем nod
A.13 присваивание массива 4
A.14 если i=0, i<4, i+1 то
A.15 введите число {i + 1}
A.16 вывод NOD
Затем составим блок-схему, изображенную на рисунке 3.1.
Реализация данного алгоритма на языке C# представлена в приложении 1.
Результат работы программы представлен на рисунке 3.2.
Рисунок 3.2 Результат работы программы
Задание 2: Организовать бинарный поиск заданного числа в массиве (массив предварительно нужно отсортировать)
Для начала составим Алгоритм B:
B.1 присваиваем а, массив, первое, последнее значение
B.2 если первое значение > последнего то
B.3 элемент не найдет
B.4 возвращаемся и -1
B.5 присваиваем среднее значение = (first + last) / 2
B.6 присваиваем массив middleValue = mass[middle]
B.7 иначе, если middleValue > a
B.8 возвращаем вызов поиска для левой части массива
B.9 или возвращаем вызов поиска для правой части массива
Реализация данного алгоритма на языке C# представлена в приложении 2.
Результат работы программы представлен на рисунке 3.4.
Рисунок 3.4 — Результат работы программы
4 Заключение
В результате выполнения лабораторной работы были получены навыками использования функций в программировании и рекурсивным подходом решения задач. Отчет оформлен согласно ОС ТУСУР.
5 Литература
Харченко С.С. Основы программирования (учебно-методическое пособие). 2020г.
6 Приложение 1
using System;
namespace Op_lab4_1
{
class Program
{
public static int gcd(int a, int b)
{
while (a != b)
{
if (a > b)
{
int tmp = a;
a = b;
b = tmp;
}
b = b - a;
}
return a;
}
public static int NODOf4Number(int[] mass)
{
int i = 2;
int NOD = gcd(mass[0], mass[1]);
while (i < mass.Length)
{
NOD = gcd(NOD, mass[i]);
i++;
}
return NOD;
}
static void Main(string[] args)
{
int[] mass = new int[4];
for (int i = 0; i < 4; i++)
{
Console.Write($"Введите число {i + 1}: ");
mass[i] = Convert.ToInt32(Console.ReadLine());
}
int NOD = NODOf4Number(mass);
Console.WriteLine($"НОД = {NOD}");
Console.ReadLine(); }
}
}
}
7 Приложение 2
using System;
namespace OP_lab_2_2
{
class Program
{
public static int BinarySearch(int a, int[] mass, int first, int last)
{
if (first > last)
{
//элемент не найден
return -1;
}
//средний индекс подмассива
int middle = (first + last) / 2;
int middleValue = mass[middle];
if (middleValue == a)
{
return middle;
}
else
{
if (middleValue > a)
{
//вызов поиска для левой части массива
return BinarySearch(a, mass, first, middle - 1);
}
else
{
//вызов поиска для правой части массива
return BinarySearch(a, mass, middle + 1, last);
}
}
}
static void Main(string[] args)
{
Console.Write("Введите n: ");
int n = Convert.ToInt32(Console.ReadLine());
int[] mass = new int[n];
for (int i = 0; i < n; i++)
{
Console.Write($"Введите {i} элемент массива: ");
mass[i] = Convert.ToInt32(Console.ReadLine());
}
Array.Sort(mass);
Console.WriteLine($"Отсортированный массив: ");
for (int i = 0; i < n; i++)
{
Console.WriteLine($"{i} элемент массива: { mass[i]}");
}
Console.Write("Введите искомое число: ");
int a = Convert.ToInt32(Console.ReadLine());
int PositionInMass = BinarySearch(a, mass, 0, n - 1);
if (PositionInMass < 0)
{
Console.Write("Элемент не найден");
}
else
{
Console.Write($"Элемент найден - его позиция в массиве = {PositionInMass}");
}
Console.ReadLine();
}
}
}