Слайд 2
Контрольные вопросы
Что такое ООП?
Чему соответствуют понятия Класс и
Объект в функциональном программировании?
Где объявляются новые классы в C#?
Что
означает слово Public в ООП?
Что такое Метод?
Где может располагаться в программе определение метода?
Что такое формальные параметры? Для чего они служат?
Что такое фактические параметры? Для чего они служат?
Слайд 3
План лекции
Поля данных и свойства
Рекурсия
Понятие рекурсии
Пример для задачи
“Ханойские башни”
Вопросы для повторения
Слайд 4
Поля данных
Класс гистограммы.
public class Histogram { // Левая и
правая граница
public double LeftEdge;
public double RightEdge;
public int [] Data;
// Массив
public Histogram(double leftEdge, double rightEdge, int N)
{
…
}
…
}
LeftEdge, RightEdge и Data – поля данных
Слайд 5
Недостатки полей данных
Если поле данных объекта можно читать
(оно доступно), то его можно и изменить.
Программно защитить
или контролировать изменение поля нельзя!
Как следствие, полям можно придать недопустимые значения, например, для гистограммы можно указать левую границу больше правой.
Слайд 6
Свойства
Этих недостатков лишены Свойства.
public class Histogram {
double _leftEdge;
double
_rightEdge;
int [] Data;
public double LeftEdge
{
get {return _leftEdge;}
set {_leftEdge
= value;}
}
…
}
Слайд 7
Свойства
Используются свойства так же как и поля данных.
Histogram
h = new Histogram();
h.LeftEdge = 0;
h.RightEdge = 100;
Console.WhriteLine(“{0} –
{1}”, h.LeftEdge, h.RightEdge);
Их можно задавать (присваивать) и считывать.
Слайд 8
Свойства
Варианты свойств. Только для чтения.
public class Histogram {
double
_leftEdge;
double _rightEdge;
int [] Data;
public double LeftEdge
{
get {return _leftEdge;}
//set
{_leftEdge = value;}
}
…
}
Слайд 9
Свойства
Варианты свойств. Проверка при присваивании.
public class Histogram {
double
_leftEdge;
double _rightEdge;
int [] Data;
public double LeftEdge
{
get {return _leftEdge;}
set
{if(value > 0) _leftEdge = value;}
}
…
}
В set проверяем значение value и, если оно допустимо, выполняем присваивание.
Слайд 10
Свойства
C# облегчает использование свойств ! Можно не задавать
поля данных.
public class Histogram {
public double LeftEdge {get; set;};
public
double RightEdge {get; set;};
int [] Data;
//public double LeftEdge
//{
// get {return _leftEdge;}
// set {if(value > 0) _leftEdge = value;}
//}
…
}
Слайд 11
Свойства.
Заключительные замечания
Последнее упрощение позволяет требовать применения свойств
вместо полей данных без исключений.
Мы не смогли заменить массив
на свойства, но C# это позволяет!
Обратите внимание на элемент нотации (системы имен):
Свойства как public начинаются с большой буквы, а поля, как private с маленькой, да еще со знаком подчеркивания.
Слайд 12
Рекурсия
Рекурсия – ссылка на себя
Вычисление факториала в цикле:
Double
F(int N)
{
f = 1;
for(int i = 1; i
N; i++)
f *= i;
return f;
}
Слайд 13
Рекурсия
Рекурсия – ссылка на себя
Вычисление факториала рекурсивно:
Double F(int
N)
{
if(N == 0) return 1;
return N * F(N-1);
}
Слайд 14
Рекурсия
Структура
Всегда имеются простейшие случаи, которые вычисляются явно!
if(N
== 0) return 1;
Более сложные случаи вычисляются со
ссылкой на более простые.
return N * F(N-1);
Слайд 15
Рекурсия.
Как происходит вычисление
Алгоритм вызывает сам себя, но
с более простыми значениями параметров.
Это позволяют сделать методы!
Без методов рекурсия теряет свои преимущества.
Почему?
Когда наступает простой случай, начинается последовательный возврат значений и он завершается решением исходной задачи.
Слайд 16
Рекурсия. “Ханойские башни”
Рекурсия помогает решать задачи.
Слайд 17
Рекурсия. “Ханойские башни”
Рекурсия помогает решать задачи.
Задача. Переместить N
дисков с пирамиды i на пирамиду k.
Если N =
1, то задача тривиальна.
Допустим, мы умеем перемещать N-1 дисков с любой пирамиды на любую.
Слайд 18
Рекурсия. “Ханойские башни”
Если N = 1, то переместить
с i на k
Иначе:
Переметить N-1 дисков с i на
пирамиду j
Переместить последний диск с i на k
Переместить N-1 дисков с j на пирамиду k
Имеются все элементы рекурсии!
Слайд 19
“Ханойские башни”. Реализация.
Как представить пирамиды и диски?
int N
= 12; //Высота пирамид
int [,] p = new int[3,
N];
Номера пирамид : 0, 1 и 2.
Диаметр диска задаем числом в массиве!
for(int i = 0; i < N; i++)
p[0, i] = 2*(N – i) + 1;
//Что за формула 2*(N – i) + 1?
//Где низ, а где верх?
Слайд 20
“Ханойские башни”. Реализация.
///
/// Перемещает M дисков
с пирамиды i на пирамиду j для системы башен
p
///
///
Ханойские башни
///
Исходная пирамида
///
Пирамида назначения
///
Количество дисков для перемещения
void Move (int[,] p, int i, int j, int M)
{
}
Слайд 21
“Ханойские башни”. Реализация.
void Move (int[,] p, int i,
int j, int M)
{
if(M == 1) Переместить 1 с
i на j
else
{
Переместить M-1 с i на k
Переместить 1 с i на j
Переместить M-1 с k на j
}
}
Как найти k, если известно i и j?
Как узнать сколько дисков на пирамидке?
Слайд 22
“Ханойские башни”. Реализация.
///
/// Вычисляет высоту пирамиды i
для системы башен p
///
/// Ханойские башни
///
name="i">Пирамида для котороой вычисляется высота
/// Высоту приамиды i
int Height (int[,] p, int i)
{
int N = p.GetLength(1);
int j = N;
for( ; j > 0; j--)
if(p[i, j-1] > 0) return j;
return 0;
}
Находим положение первого сверху диска.
Слайд 23
“Ханойские башни”. Реализация.
///
/// Перемещает 1 диск
с пирамиды i на пирамиду j для системы башен
p
///
///
Ханойские башни
///
Исходная пирамида
///
Пирамида назначения
void Move1 (int[,] p, int i, int j)
{
int hi = Height(p, i);
int hj = Height(p, j);
p[j, hj] = p[i, hi-1];
p[i, hi-1] = 0;
}
Слайд 24
“Ханойские башни”. Реализация.
void Move (int[,] p, int i,
int j, int M)
{
if(M == 1) Move1(p, i, j);
else
{
Move(p,
i, 3-i-j, M-1);
Move1(p, i, j);
Move(p, 3-i-j, j, M-1);
}
}
Слайд 25
Заключительные замечания
Рекурсия – полезный инструмент. Существенно упрощает некоторые
задачи.
Декомпозиция – хорошая методика решения задач.
Нам пришлось:
Продумать как будут
представлены в программе пирамидки
Как организовать рекурсию
Как определить “высоту” пирамиды
Каждая задача оказалась простой, а в целом, мы решили довольно сложную задачу.
Слайд 26
Рекурсия
Заключительные замечания
Факториал можно вычислить рекурсивно или в цикле.
Любую рекурсию можно заменить циклическим вычислением!
Алгоритм замены рекурсии циклическим
вычислением может оказаться довольно сложным.
Рекурсия медленнее чем цикл! Злоупотреблять не следует!
Слайд 27
Контрольные вопросы и упражнения
Почему в ООП рекомендуется использовать
свойства, а не поля данных?
Что такое рекурсия?
Реализуйте метод поиска
решения уравнения на отрезке с использованием рекурсии.
![СвойстваЭтих недостатков лишены Свойства.public class Histogram { double _leftEdge; double _rightEdge; int [] Data; public](/img/tmb/15/1418264/1f032c7361c08df5d5037c123404a72a-720x.jpg "ПЯВУ. Лекция 13. Элементы ООП. Рекурсия")
![СвойстваВарианты свойств. Только для чтения.public class Histogram { double _leftEdge; double _rightEdge; int [] Data;](/img/tmb/15/1418264/9366788e26f3a30b7ff0115fcede30cd-720x.jpg "ПЯВУ. Лекция 13. Элементы ООП. Рекурсия")
![СвойстваВарианты свойств. Проверка при присваивании.public class Histogram { double _leftEdge; double _rightEdge; int [] Data;](/img/tmb/15/1418264/1b4dc148db15fea15c3ebac0f9ac3e12-720x.jpg "ПЯВУ. Лекция 13. Элементы ООП. Рекурсия")
![“Ханойские башни”. Реализация.void Move (int[,] p, int i, int j, int M){ if(M](/img/tmb/15/1418264/9b1c2f36f11e2affc86da50a194167d0-720x.jpg "ПЯВУ. Лекция 13. Элементы ООП. Рекурсия")
![“Ханойские башни”. Реализация.void Move (int[,] p, int i, int j, int M){ if(M](/img/tmb/15/1418264/88c80e5f2b54021e09dd1a0aed46cac6-720x.jpg "ПЯВУ. Лекция 13. Элементы ООП. Рекурсия")
