ПЯВУ. Лекция 13. Элементы ООП. Рекурсия

1. ПЯВУ. Лекция 13.

Элементы ООП. Рекурсия.
А.М. Задорожный

2. Контрольные вопросы

1. Что такое ООП?
2. Чему соответствуют понятия Класс и Объект в
функциональном программировании?
3. Где объявляются новые классы в C#?
4. Что означает слово Public в ООП?
5. Что такое Метод?
6. Где может располагаться в программе определение
метода?
7. Что такое формальные параметры? Для чего они
служат?
8. Что такое фактические параметры? Для чего они
служат?

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. Свойства. Заключительные замечания

1. Последнее упрощение позволяет требовать
применения свойств вместо полей данных без
исключений.
2. Мы не смогли заменить массив на свойства, но C#
это позволяет!
3. Обратите внимание на элемент нотации (системы
имен):
Свойства как 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. Рекурсия Структура

1. Всегда имеются простейшие случаи,
которые вычисляются явно!
if(N == 0) return 1;
2. Более сложные случаи вычисляются со
ссылкой на более простые.
return N * F(N-1);

15. Рекурсия. Как происходит вычисление

Алгоритм вызывает сам себя, но с более
простыми значениями параметров.
Это позволяют сделать методы! Без методов
рекурсия теряет свои преимущества.
Почему?
Когда наступает простой случай, начинается
последовательный возврат значений и он
завершается решением исходной задачи.

16. Рекурсия. “Ханойские башни”

Рекурсия помогает решать задачи.

17. Рекурсия. “Ханойские башни”

Рекурсия помогает решать задачи.
Задача. Переместить N дисков с пирамиды i
на пирамиду k.
Если N = 1, то задача тривиальна.
Допустим, мы умеем перемещать N-1 дисков
с любой пирамиды на любую.

18. Рекурсия. “Ханойские башни”

1. Если N = 1, то переместить с i на k
Иначе:
2. Переметить N-1 дисков с i на пирамиду j
3. Переместить последний диск с i на k
4. Переместить 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. “Ханойские башни”. Реализация.

/// <summary>
/// Перемещает M дисков с пирамиды i на пирамиду j для системы башен p
/// </summary>
/// <param name="p">Ханойские башни</param>
/// <param name="i">Исходная пирамида</param>
/// <param name="j">Пирамида назначения</param>
/// <param name="M">Количество дисков для перемещения</param>
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
}
}
1.
2.
Как найти k, если известно i и j?
Как узнать сколько дисков на пирамидке?

22. “Ханойские башни”. Реализация.

/// <summary>
/// Вычисляет высоту пирамиды i для системы башен p
/// </summary>
/// <param name="p">Ханойские башни</param>
/// <param name="i">Пирамида для котороой вычисляется высота</param>
/// <returns>Высоту приамиды i</returns>
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. “Ханойские башни”. Реализация.

/// <summary>
/// Перемещает 1 диск с пирамиды i на пирамиду j для системы башен p
/// </summary>
/// <param name="p">Ханойские башни</param>
/// <param name="i">Исходная пирамида</param>
/// <param name="j">Пирамида назначения</param>
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. Заключительные замечания

1. Рекурсия – полезный инструмент. Существенно
упрощает некоторые задачи.
2. Декомпозиция – хорошая методика решения задач.
3. Нам пришлось:
1.
2.
3.
Продумать как будут представлены в программе
пирамидки
Как организовать рекурсию
Как определить “высоту” пирамиды
Каждая задача оказалась простой, а в целом, мы решили
довольно сложную задачу.

26. Рекурсия Заключительные замечания

Факториал можно вычислить рекурсивно или в цикле.
Любую рекурсию можно заменить циклическим
вычислением!
Алгоритм замены рекурсии циклическим
вычислением может оказаться довольно сложным.
Рекурсия медленнее чем цикл! Злоупотреблять не
следует!

27. Контрольные вопросы и упражнения

1. Почему в ООП рекомендуется
использовать свойства, а не поля данных?
2. Что такое рекурсия?
3. Реализуйте метод поиска решения
уравнения на отрезке с использованием
рекурсии.

28. Вопросы для повторения

1. Объясните синтаксис оператора for
2. Какова область видимости счетчика,
объявленного в for?
3. Что такое оператор цикла с
предусловием/постусловием?
Классифицируйте каждый из операторов
цикла в C#.
4. Какие дополнительные операторы позволяют
управлять исполнением циклов?