Методические указания по выполнению лабораторных и практических работ по мдк
 Скачать 3.25 Mb.
|
|
Задание 1 1. Составить алгоритм вычисления НОД двух чисел с помощью рекурсивной функции. 2. Составить алгоритм вычисления значения очередного числа Фибоначчи с помощью рекурсивной функции. 3. Напишите рекурсивную функцию, переворачивающую заданное натуральное число. Задание 2 1. Напишите рекурсивную функцию, которая по заданным натуральным числам m и п выводит все различные представления числа n в виде суммы m натуральных слагаемых. Представления, различающиеся лишь порядком слагаемых, считаются одинаковыми. Напишите рекурсивную функцию, вычисляющую n!!. 2. Напишите рекурсивную функцию, определяющую количество единиц в двоичном представлении натурального числа. 46 3. Написать функцию сложения двух чисел, используя только прибавление единицы. 4. Написать функцию умножения двух чисел, используя только операцию сложения. 5. Проверить, является ли фрагмент строки с i-го по j-й символ палиндромом. 6. Подсчитать количество цифр в заданном числе. Практическая работа № 1.10. Оценка сложности эвристических алгоритмов Цель работы: получение навыков построения алгоритмов с использованием эвристических алгоритмов Теоретический материал Эвристические методы Под эвристическими понимаются такие методы, правильность которых строго не доказывается. Они выглядят правдоподобными; кажется, что в большинстве случаев они должны давать верные решения. На уровне экспертной оценки алгоритма часто не удается придумать контрпример, доказывающий ошибочность или неуниверсальность метода. Это, разумеется, не является строгим обоснованием правильности метода. Тем не менее практика использования эвристических методов дает положительные результаты. Эвристические методы разнообразны, поэтому нельзя описать какую-то общую схему их разработки. Чаще всего они применяются совместно с методами перебора для сокращения числа проверяемых вариантов. Некоторые варианты согласно выбранной эвристике считаются заведомо бесперспективными и не проверяются. Такой подход ускоряет работу алгоритма по сравнению с полным перебором. Платой за это является отсутствие гарантии того, что выбрано правильное или наилучшее из всех возможных решение. Оценка сложности эвристических алгоритмов Традиционно принято оценивать степень сложности алгоритма по объему используемых им основных ресурсов компьютера: процессорного времени и оперативной памяти. В связи с этим вводятся такие понятия, как временная сложность алгоритма и объемная сложность алгоритма. Параметр временной сложности становится особенно важным для задач, предусматривающих интерактивный режим работы программы, или для задач управления в режиме реального времени. Часто программисту, составляющему программу управления каким- нибудь техническим устройством, приходится искать компромисс между точностью вычислений и временем работы программы. Как правило, повышение точности ведет к увеличению времени. Объемная сложность программы становится критической, когда объем обрабатываемых данных оказывается на пределе объема оперативной памяти ЭВМ. На современных компьютерах острота этой проблемы снижается благодаря как росту объема ОЗУ, так и эффективному использованию многоуровневой системы запоминающих устройств. Программе оказывается доступной очень большая, практически неограниченная область памяти (виртуальная память). Недостаток основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Используются приемы, позволяющие минимизировать потери времени при таком обмене. Это использование кэш-памяти и аппаратного просмотра команд программы на требуемое число ходов вперед, что позволяет заблаговременно переносить с диска в основную память нужные значения. Исходя из сказанного можно заключить, что минимизация емкостной сложности не является первоочередной задачей. Поэтому в дальнейшем мы будем интересоваться в основном временной сложностью алгоритмов. Время выполнения программы пропорционально числу исполняемых операций. Разумеется, в размерных единицах времени (секундах) оно зависит еще и от скорости работы процессора (тактовой частоты). Для того чтобы показатель временной сложности алгоритма был инвариантен относительно технических характеристик компьютера, его измеряют в относительных единицах. Обычно временная сложность оценивается числом выполняемых операций. 47 Как правило, временная сложность алгоритма зависит от исходных данных. Это может быть зависимость как от величины исходных данных, так и от их объема. Если обозначить значение параметра временной сложности алгоритма α символом Tα, а буквой V обозначить некоторый числовой параметр, характеризующий исходные данные, то временную сложность можно представить как функцию Tα(V). Выбор параметра V зависит от решаемой задачи или от вида используемого алгоритма для решения данной задачи. Ход работы 1. Оценим временную сложность алгоритма вычисления факториала целого положительного числа. Function Factorial(x:Integer): Integer; Var m,i: Integer; Begin m:=l; For i:=2 To x Do m:=ro*i; Factorial:=m End; 2. Подсчитаем общее число операций, выполняемых программой при данном значении x. Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и присваивание) выполняется х — 1 раз; один раз выполняется присваивание Factorial:=m. Если каждую из операций принять за единицу сложности, то временная сложность всего алгоритма будет 1 + 2 (x — 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует принять значение х. Функция временной сложности получилась следующей: Tα(V)=2V. В этом случае можно сказать, что временная сложность зависит линейно от параметра данных — величины аргумента функции факториал. 3. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk). АВ:=0; For i:=l To k Do AB:=AB+A[i]*B[i]; В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1 + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о линейной зависимости временной сложности от параметра данных. С параметром временной сложности алгоритма обычно связывают две теоретические проблемы. Первая состоит в поиске ответа на вопрос: до какого предела значения временной сложности можно дойти, совершенствуя алгоритм решения задачи? Этот предел зависит от самой задачи и, следовательно, является ее собственной характеристикой. Вторая проблема связана с классификацией алгоритмов по временной сложности. Функция Tα(V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью Тα от V (как это было в рассмотренных нами примерах), с квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых растет быстрее любого полинома. Проблема, которую часто решают теоретики — исследователи алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи полиномиальный алгоритм? Практическая работа № 1.11. Работа с классами Цель работы: получение практических навыков работы с классами и объектами Теоретический материал Описанием объекта является класс, а объект представляет экземпляр этого класса. Можно еще провести следующую аналогию. У нас у всех есть некоторое представление о человеке, у которого есть имя, возраст, какие-то другие характеристики. То есть некоторый шаблон - этот шаблон можно назвать классом. Конкретное воплощение этого шаблона может отличаться, 48 например, одни люди имеют одно имя, другие - другое имя. И реально существующий человек (фактически экземпляр данного класса) будет представлять объект этого класса. По умолчанию проект консольного приложения уже содержит один класс Program, с которого и начинается выполнение программы. По сути класс представляет новый тип, который определяется пользователем. Класс определяется с помощью ключевого слова сlass: class Person { } Где определяется класс? Класс можно определять внутри пространства имен, вне пространства имен, внутри другого класса. Как правило, классы помещаются в отдельные файлы. Но в данном случае поместим новый класс в файле, где располагается класс Program. То есть файл Program.cs будет выглядеть следующим образом: using System; namespace HelloApp { class Person { } class Program { static void Main(string[] args) { } } } Вся функциональность класса представлена его членами - полями (полями называются переменные класса), свойствами, методами, событиями. Например, определим в классе Person поля и метод: using System; namespace HelloApp { class Person { public string name; // имя public int age = 18; // возраст public void GetInfo() { Console.WriteLine($"Имя: {name} Возраст: {age}"); } } class Program { static void Main(string[] args) { Person tom; } } 49 } В данном случае класс Person представляет человека. Поле name хранит имя, а поле age - возраст человека. А метод GetInfo выводит все данные на консоль. Чтобы все данные были доступны вне класса Person переменные и метод определены с модификатором public. Поскольку поля фактически те же переменные, им можно присвоить начальные значения, как в случае выше, поле age инициализировано значением 18. Так как класс представляет собой новый тип, то в программе мы можем определять переменные, которые представляют данный тип. Так, здесь в методе Main определена переменная tom, которая представляет класс Person. Но пока эта переменная не указывает ни на какой объект и по умолчанию она имеет значение null. Поэтому вначале необходимо создать объект класса Person. Конструкторы Кроме обычных методов в классах используются также и специальные методы, которые называются конструкторами. Конструкторы вызываются при создании нового объекта данного класса. Конструкторы выполняют инициализацию объекта. Конструктор по умолчанию Если в классе не определено ни одного конструктора, то для этого класса автоматически создается конструктор по умолчанию. Такой конструктор не имеет параметров и не имеет тела. Выше класс Person не имеет никаких конструкторов. Поэтому для него автоматически создается конструктор по умолчанию. И мы можем использовать этот конструктор. В частности, создадим один объект класса Person: class Person { public string name; // имя public int age; // возраст public void GetInfo() { Console.WriteLine($"Имя: {name} Возраст: {age}"); } } class Program { static void Main(string[] args) { Person tom = new Person(); tom.GetInfo(); // Имя: Возраст: 0 tom.name = "Tom"; tom.age = 34; tom.GetInfo(); // Имя: Tom Возраст: 34 Console.ReadKey(); } } Для создания объекта Person используется выражение new Person(). Оператор new выделяет память для объекта Person. И затем вызывается конструктор по умолчанию, который не принимает никаких параметров. В итоге после выполнения данного выражения в памяти будет выделен участок, где будут храниться все данные объекта Person. А переменная tom получит ссылку на созданный объект. Если конструктор не инициализирует значения переменных объекта, то они получают значения по умолчанию. Для переменных числовых типов это число 0, а для типа string и классов - это значение null (то есть фактически отсутствие значения). После создания объекта мы можем обратиться к переменным объекта Person через переменную tom и установить или получить их значения, например, tom.name = "Tom";. Консольный вывод данной программы: Имя: Возраст: 0 50 Имя: Tom Возраст: 34 Создание конструкторов Выше для инициализации объекта использовался конструктор по умолчанию. Однако мы сами можем определить свои конструкторы: class Person { public string name; public int age; public Person() { name = "Неизвестно"; age = 18; } // 1 конструктор public Person(string n) { name = n; age = 18; } // 2 конструктор public Person(string n, int a) { name = n; age = a; } // 3 конструктор public void GetInfo() { Console.WriteLine($"Имя: {name} Возраст: {age}"); } } Теперь в классе определено три конструктора, каждый из которых принимает различное количество параметров и устанавливает значения полей класса. Используем эти конструкторы: static void Main(string[] args) { Person tom = new Person(); // вызов 1-ого конструктора без параметров Person bob = new Person("Bob"); //вызов 2-ого конструктора с одним параметром Person sam = new Person("Sam", 25); // вызов 3-его конструктора с двумя параметрами bob.GetInfo(); // Имя: Bob Возраст: 18 tom.GetInfo(); // Имя: Неизвестно Возраст: 18 sam.GetInfo(); // Имя: Sam Возраст: 25 } Консольный вывод данной программы: Имя: Неизвестно Возраст: 18 Имя: Bob Возраст: 18 Имя: Sam Возраст: 25 При этом если в классе определены конструкторы, то при создании объекта необходимо использовать один из этих конструкторов. Стоит отметить, что начиная с версии C# 9.0 мы можем сократить вызов конструктора, убрав из него название типа: Person tom = new (); // аналогично new Person(); Person bob = new ("Bob"); // аналогично new Person("Bob"); Person sam = new ("Sam", 25); // аналогично new Person("Sam", 25); Ключевое слово this Ключевое слово this представляет ссылку на текущий экземпляр класса. В каких ситуациях оно нам может пригодиться? В примере выше определены три конструктора. Все три конструктора выполняют однотипные действия - устанавливают значения полей name и age. Но этих повторяющихся действий могло быть больше. И мы можем не дублировать функциональность конструкторов, а просто обращаться из одного конструктора к другому через ключевое слово this, передавая нужные значения для параметров: class Person { public string name; 51 public int age; public Person() : this("Неизвестно") { } public Person(string name) : this(name, 18) { } public Person(string name, int age) { this.name = name; this.age = age; } public void GetInfo() { Console.WriteLine($"Имя: {name} Возраст: {age}"); } } В данном случае первый конструктор вызывает второй, а второй конструктор вызывает третий. По количеству и типу параметров компилятор узнает, какой именно конструктор вызывается. Например, во втором конструкторе: public Person(string name) : this(name, 18) { } идет обращение к третьему конструктору, которому передаются два значения. Причем в начале будет выполняться именно третий конструктор, и только потом код второго конструктора. Также стоит отметить, что в третьем конструкторе параметры называются также, как и поля класса. public Person(string name, int age) { this.name = name; this.age = age; } И чтобы разграничить параметры и поля класса, к полям класса обращение идет через ключевое слово this. Так, в выражении this.name = name; первая часть this.name означает, что name - это поле текущего класса, а не название параметра name. Если бы у нас параметры и поля назывались по-разному, то использовать слово this было бы необязательно. Также через ключевое слово this можно обращаться к любому полю или методу. Инициализаторы объектов Для инициализации объектов классов можно применять инициализаторы. Инициализаторы представляют передачу в фигурных скобках значений доступным полям и свойствам объекта: 1 2 Person tom = new Person { name = "Tom", age=31 }; tom.GetInfo(); // Имя: Tom Возраст: 31 С помощью инициализатора объектов можно присваивать значения всем доступным полям и свойствам объекта в момент создания без явного вызова конструктора. При использовании инициализаторов следует учитывать следующие моменты: С помощью инициализатора мы можем установить значения только доступных из внешнего кода полей и свойств объекта. Например, в примере выше поля name и age имеют модификатор доступа public, поэтому они доступны из любой части программы. Инициализатор выполняется после конструктора, поэтому если и в конструкторе, и в инициализаторе устанавливаются значения одних и тех же полей и свойств, то значения, устанавливаемые в конструкторе, заменяются значениями из инициализатора. 52 Практическая работа № 1.12. Перезагрузка методов Цель работы: изучить метод перезагрузки Теоретический материал Виртуальные и динамические методы могут быть перезагружаемыми. Перезагрузка нужна, чтобы произвести одинаковые или похожие действия с разнотипными данными. Статический метод перекрытия приводит к тому, что потомок «не видит» перекрытый родительский метод и может обращаться к нему только с помощью слова inherited, поэтому в Delphi используется перезагрузка, с помощью которой становятся видны одноименные методы как родителя, так и потомка. Пример: Type TFirst=class i:Extended; procedure SetData(x:Extended); end; TSecond=class(TFirst) j:Integer; procedure SetData(AValue:Integer); end; var T2:TSecond; begin T2.SetData (1.1); (1) T2.SetData (1); (2) В этом примере первый вызов метода SetData из объекта T2 с переменной =1.1 (не целая) вызовет ошибку! А второй вызов не приводит к ошибке, т.к. внутри объекта T2 статический метод с параметром типа Extended перекрыт одноименным методом с параметром типа Integer. Компилятор внутри T2 не признает параметр типа Extended. Для доступа к методу SetData класса TFirst необходимо использовать служебное слово inherited. Например: procedure TSecond.SetData; begin x :=1.1; 53 inherited SetData (x); j:=x; end; Но нам нужно произвести схожие действия (1), (2) с разнотипными данными в строках одной программы. В ходе компиляции при обращении к одному из одноименных методов компилятор проверяет тип и количество параметров обращения и на основе этой проверки выбирает нужный метод. Overload – директива, позволяющая перезагрузить методы: Type TFirst=class i:Extended; procedure SetData(x:Extended); Overload; end; TSecond=class(TFirst) j:Integer; procedure SetData(AValue:Integer); Overload; end; var T2:TSecond; Теперь в программе можно использовать метод как родителя, так и потомка. begin T2.SetData (1.1); T2.SetData (1); Можно перезагрузить и виртуальный, и динамический методы. В этом случае надо добавить директиву reintroduce перед директивой overload. Задача с использованием полиморфизма Полиморфизм – это возможность использовать одинаковые имена для методов, входящих в различные классы. Концепция полиморфизма обеспечивает в случае применения метода к объекту использование именно того метода, который соответствует классу объекта. |