Методические рекомендации по выполнению практических работ по междисциплинарному курсу
 Скачать 2.6 Mb.
|
|
Сложность алгоритма n=10 n=10 3 n=10 6 log n 0.2 сек. 0.6 сек. 1.2 сек. n 0.6 сек. 1 мин. 16.6 час. n 2 6 сек. 16.6 час. 1902 года 2 n 1 мин. 10 295 лет 10 300000 лет Когда начинающие программисты тестируют свои программы, то значения параметров, от которых они зависят, обычно невелики. Поэтому даже если при написании программы был применен неэффективный алгоритм, это может остаться незамеченным. Однако, если подобную программу попытаться применить в реальных условиях, то ее практическая непригодность проявится незамедлительно. С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлемое время. Таким образом, увеличивается среднее значение величины , и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма! Практическая работа №3 Оценка сложности рекурсивных алгоритмов Цель работы: Получение практических навыков решения задач с использованием рекурсивных алгоритмов. Методика выполнения работы. Составить программу, которая вычисляет значения заданной функции для заданных значений X – аргумента с заданной точностью и выводит значения аргумента и функции в табличной форме. При программировании вычисления значений функции использовать рекуррентную формулу и рекурсивные функции. Программа должна включать: 1. ввод исходных данных (с клавиатуры и из файла); 2. функцию вычисления очередного члена ряда с использованием рекуррентной формулы; 3. из функции для вычисления очередного члена ряда вызывать другие, в том числе рекурсивные функции, например для вычисления степени X, факториала и пр.; 4. для вычисления суммы ряда использовать 3 разные функции, использующие: оператор While; оператор Repeat – Until; рекурсивное суммирование; 5. вывод результатов выполнения программы (в процессе отладки программы – на экран; после отладки – в файл); 6. для управления работой программой разработать структуру меню для вызова каждой процедуры (формирование меню осуществляется средствами модуля CRT); 7. для тестирования программы сформировать исходные данные таким образом, чтобы проверить каждый вариант альтернативы каждого разветвления алгоритма. Для выполнения работы необходимо знание следующих теоретических вопросов из курса предмета «Основы алгоритмизации и программирования»: строение функции и правила ее вызова; определение рекуррентной формулы; определение рекурсивной функции и ее строение; приемы отладки рекурсивных функций; работа с файлами. Теоретическая часть. Рекурсия - это одна из фундаментальных концепций в математике и программировании и является мощным средством, позволяющим строить элегантные и выразительные алгоритмы. Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной. Но рекурсивная программа не может вызывать себя бесконечно, иначе она никогда не остановится, таким образом в программе (функции) должен присутствовать еще один важный элемент - так называемое терминальное (граничное) условие, то есть условие при котором программа прекращает рекурсивный процесс. Вот типичная конструкция такого рода: procedure proc(i:integer); begin operation1; if logb then proc(i+1); operation2; end; Вызов proc(1) означает, что proc вызывает себя раз за разом с помощью proc(2), proc(3),.. до тех пор, пока условие logb не отменит новый вызов. При каждом вызове выполняется оператор operation1, после чего порядок выполнения операторов прерывается новым вызовом proc(i+1). В Паскале можно пользоваться именами лишь тогда, когда в тексте программы этому предшествует их описание. Рекурсия является единственным исключением из этого правила. Имя proc можно использовать сразу же, не закончив его описания. Рекурсия не должна восприниматься как некий программистский трюк. Это скорее некий принцип, метод. Если в программе нужно выполнить что-то повторно, можно действовать двумя способами: - с помощью последовательного присоединения (или итерации в форме цикла); - с помощью вложения одной операции в другую (а именно, рекурсий). Рассмотрим на примере принципиальное различие между итерацией и рекурсией. Итерации необходим цикл и локальная переменная k как переменная цикла. Рекурсии ничего этого не требуется! program iterativ_zu_rekursion; var n:integer; procedure rekursion (i:integer); begin writeln(i:30); if i < 1 then rekursion(i-1); writeln(i:3); end; (* Рекурсия *) procedure schleife(i:integer); var k:integer; bagin k :=1; while k <= i do begin write(k:3); k :=k+1; end; end; (* Цикл *) begin write(‘Введите n:’); readln(n); writeln(‘Пока:’); scheife(n); writeln; writeln(‘Рекурсия’); rekursion(n); end. Реккурентность - это рекурсивное определение функции. Они широко распространены в математике. Наиболее знакомая из такого рода функций - это факториал. Факториал - это произведение натуральных чисел от единицы до какого - либо данного натурального числа. Он определяется формулой: N!=N((N-1)!, для N>=1 и 0! = 1. Это напрямую соответствует нижеследующей рекурсивной программе: function factorial( N : integer ) : integer; begin if N=0 then factorial := 1 else factorial := N * factorial(N-1); end; Эта программа демонстрирует основные свойства рекурсивных программ: программа вызывает сама себя (с меньшим значением аргумента), и у нее есть граничное условие при котором она прямо вычисляет результат. Необходимо также помнить о том, что это - программа, а не формула: например ни формула, ни программа не работают с отрицательными N, но губительные последствия попытки произвести вычисления для отрицательного числа более заметны для программы, чем для формулы. Вызов factorial(-1) приведет к бесконечному рекурсивному циклу. Поэтому перед вызовом данной программы нужно делать проверку условия неотрицательности. Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека. Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом. Выполнение действий в рекурсивной подпрограмме может быть организовано одним из вариантов: Begin Begin Begin P; операторы; операторы; операторы; P P; End; End; операторы End; Вариант 1 реализует рекурсивный подъём, вариант 2 - рекурсивный спуск и вариант 3 - рекурсивный спуск, и рекурсивный подъём. Здесь Р — рекурсивная подпрограмма. Как видно из примера, действия могут выполняться либо на одном из этапов рекурсивного обращения, либо на обоих сразу. Способ организации действий диктуется логикой разрабатываемого алгоритма. Различие в написании рекурсивных определений в виде функций и процедур рассмотрим на примере вычисления факториала. {Функция} Function Factorial(N:integer):Extended; Begin If N<=1 Then Factorial:=1 Else Factorial:=Factorial(N-1)* N End; {Процедура} Procedure Factorial(N:integer; Var F:Extended); Begin If N<=1 Then F:=1 Else Begin Factorial(N-1, F); F:=F*N End; End; В приведенных выше примерах программ действия выполняются на рекурсивном подъёме. Рассмотрим еще один пример: Вычислить сумму элементов линейного массива. При решении задачи используем следующее соображение: сумма равна нулю, если количество элементов равно нулю, и сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю. Program Rec2; Type LinMas = Array[1..100] Of Integer; Var A : LinMas; I, N : Byte; {Рекурсивная функция} Function Summa(N : Byte; A: LinMas) : Integer; Begin If N = 0 Then Summa := 0 Else Summa := A[N] + Summa(N - 1, A) End; {Основная программа} Begin Write('Количество элементов массива? '); ReadLn(N); Randomize; For I := 1 To N Do Begin A[I] := -10 + Random(21); Write(A[I] : 4) End; WriteLn; WriteLn('Сумма: ', Summa(N, A)) End. Подводя итог, заметим, что использование рекурсии является красивым приёмом программирования. Краткость и выразительность большинства рекурсивных процедур упрощает их чтение и сопровождение. В то же время в большинстве практических задач этот приём неэффективен с точки зрения расходования таких ресурсов ЭВМ, как память и время исполнения программы. Использование рекурсии увеличивает время исполнения программы и зачастую требует значительного объёма памяти для хранения копий подпрограммы на рекурсивном спуске. Поэтому на практике выбор между рекурсивным и итерационным алгоритмами зависит от постановки задачи и определения критериев ее эффективности. Практическая работа №5 Работа с классами. C# является полноценным объектно-ориентированным языком. Это значит, что программу на C# можно представить в виде взаимосвязанных взаимодействующих между собой объектов. Описанием объекта является класс, а объект представляет экземпляр этого класса. Можно еще провести следующую аналогию. У нас у всех есть некоторое представление о человеке, у которого есть имя, возраст, какие-то другие характеристики. То есть некоторый шаблон - этот шаблон можно назвать классом. Конкретное воплощение этого шаблона может отличаться, например, одни люди имеют одно имя, другие - другое имя. И реально существующий человек (фактически экземпляр данного класса) будет представлять объект этого класса. По умолчанию проект консольного приложения уже содержит один класс Program, с которого и начинается выполнение программы. По сути класс представляет новый тип, который определяется пользователем. Класс определяется с помощью ключевого слова сlass: 1 2 3 4 class Person { } Где определяется класс? Класс можно определять внутри пространства имен, вне пространства имен, внутри другого класса. Как правило, классы помещаются в отдельные файлы. Но в данном случае поместим новый класс в файле, где располагается класс Program. То есть файл Program.cs будет выглядеть следующим образом: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 using System; namespace HelloApp { class Person { } class Program { static void Main(string[] args) { } } } Вся функциональность класса представлена его членами - полями (полями называются переменные класса), свойствами, методами, событиями. Например, определим в классе Person поля и метод: 1 2 3 4 5 6 7 8 9 10 using System; namespace HelloApp { class Person { public string name; // имя public int age = 18; // возраст public void GetInfo() 11 12 13 14 15 16 17 18 19 20 21 22 { Console.WriteLine($"Имя: {name} Возраст: {age}"); } } class Program { static void Main(string[] args) { Person tom; } } } В данном случае класс Person представляет человека. Поле name хранит имя, а поле age - возраст человека. А метод GetInfo выводит все данные на консоль. Чтобы все данные были доступны вне класса Person переменные и метод определены с модификатором public. Поскольку поля фактически те же переменные, им можно присвоить начальные значения, как в случае выше, поле age инициализировано значением 18. Так как класс представляет собой новый тип, то в программе мы можем определять переменные, которые представляют данный тип. Так, здесь в методе Main определена переменная tom, которая представляет класс Person. Но пока эта переменная не указывает ни на какой объект и по умолчанию она имеет значение null. Поэтому вначале необходимо создать объект класса Person. Конструкторы Кроме обычных методов в классах используются также и специальные методы, которые называются конструкторами. Конструкторы вызываются при создании нового объекта данного класса. Конструкторы выполняют инициализацию объекта. Конструктор по умолчанию Если в классе не определено ни одного конструктора, то для этого класса автоматически создается конструктор по умолчанию. Такой конструктор не имеет параметров и не имеет тела. Выше класс Person не имеет никаких конструкторов. Поэтому для него автоматически создается конструктор по умолчанию. И мы можем использовать этот конструктор. В частности, создадим один объект класса Person: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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; 20 21 22 23 tom.GetInfo(); // Имя: Tom Возраст: 34 Console.ReadKey(); } } Для создания объекта Person используется выражение new Person(). Оператор new выделяет память для объекта Person. И затем вызывается конструктор по умолчанию, который не принимает никаких параметров. В итоге после выполнения данного выражения в памяти будет выделен участок, где будут храниться все данные объекта Person. А переменная tom получит ссылку на созданный объект. Если конструктор не инициализирует значения переменных объекта, то они получают значения по умолчанию. Для переменных числовых типов это число 0, а для типа string и классов - это значение null (то есть фактически отсутствие значения). После создания объекта мы можем обратиться к переменным объекта Person через переменную tom и установить или получить их значения, например, tom.name = "Tom";. Консольный вывод данной программы: Имя: Возраст: 0 Имя: Tom Возраст: 34 Создание конструкторов Выше для инициализации объекта использовался конструктор по умолчанию. Однако мы сами можем определить свои конструкторы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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}"); } } Теперь в классе определено три конструктора, каждый из которых принимает различное количество параметров и устанавливает значения полей класса. Используем эти конструкторы: 1 2 3 4 5 6 7 8 9 10 11 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 мы можем сократить вызов конструктора, убрав из него название типа: 1 2 3 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, передавая нужные значения для параметров: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Person { public string name; 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}"); } } В данном случае первый конструктор вызывает второй, а второй конструктор вызывает третий. По количеству и типу параметров компилятор узнает, какой именно конструктор вызывается. Например, во втором конструкторе: 1 2 3 public Person(string name) : this(name, 18) { } идет обращение к третьему конструктору, которому передаются два значения. Причем в начале будет выполняться именно третий конструктор, и только потом код второго конструктора. Также стоит отметить, что в третьем конструкторе параметры называются также, как и поля класса. 1 2 public Person(string name, int age) { 3 4 5 this.name = name; this.age = age; } И чтобы разграничить параметры и поля класса, к полям класса обращение идет через ключевое слово this. Так, в выражении this.name = name; первая часть this.name означает, что name - это поле текущего класса, а не название параметра name. Если бы у нас параметры и поля назывались по-разному, то использовать слово this было бы необязательно. Также через ключевое слово this можно обращаться к любому полю или методу. |