Основы программирования. Лабораторная работа №13

Факториал – рекурсивная реализация
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
РЕКУРСИВНЫЙ СПУСК
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
РЕКУРСИВНЫЙ СПУСК
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
РЕКУРСИВНЫЙ СПУСК
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2
--------------------------------------------------
РЕКУРСИВНЫЙ СПУСК
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2
--------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1
--------------------------------------------------
РЕКУРСИВНЫЙ СПУСК
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2
--------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1
--------------------------------------------------
fuct2(0): n = 0
РЕКУРСИВНЫЙ СПУСК
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2
--------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1
--------------------------------------------------
fuct2(0): n = 0
РЕКУРСИВНЫЙ СПУСК РЕКУРСИВНЫЙ ВОЗВРАТ
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2
--------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1
-------------------------------------------------- ----------------------------------------------------
fuct2(0): n = 0 return 1
РЕКУРСИВНЫЙ СПУСК РЕКУРСИВНЫЙ ВОЗВРАТ
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2
-------------------------------------------------- ----------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1 = 1 * 1 = 1 return 1
-------------------------------------------------- ----------------------------------------------------
fuct2(0): n = 0 return 1
РЕКУРСИВНЫЙ СПУСК РЕКУРСИВНЫЙ ВОЗВРАТ
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3
--------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2 = 1 * 2 = 2 return 2
-------------------------------------------------- ----------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1 = 1 * 1 = 1 return 1
-------------------------------------------------- ----------------------------------------------------
fuct2(0): n = 0 return 1
РЕКУРСИВНЫЙ СПУСК РЕКУРСИВНЫЙ ВОЗВРАТ
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4
--------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3 = 2 * 3 = 6 return 6
-------------------------------------------------- ----------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2 = 1 * 2 = 2 return 2
-------------------------------------------------- ----------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1 = 1 * 1 = 1 return 1
-------------------------------------------------- ----------------------------------------------------
fuct2(0): n = 0 return 1
РЕКУРСИВНЫЙ СПУСК РЕКУРСИВНЫЙ ВОЗВРАТ
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4)
--------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4 = 6 * 4 = 24 return 24
-------------------------------------------------- ----------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3 = 2 * 3 = 6 return 6
-------------------------------------------------- ----------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2 = 1 * 2 = 2 return 2
-------------------------------------------------- ----------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1 = 1 * 1 = 1 return 1
-------------------------------------------------- ----------------------------------------------------
fuct2(0): n = 0 return 1
РЕКУРСИВНЫЙ СПУСК РЕКУРСИВНЫЙ ВОЗВРАТ
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Факториал – трассировка
long fuct2(int n) {
if (n == 0) {
return 1;
}
long res = fuct2(n - 1) * n;
return res;
}
main(): f = fuct2(4) = 24 printf("%d! = %ld", 4, 24);
-------------------------------------------------- ----------------------------------------------------
fuct2(4): n = 4
res = fuct2(3)*4 = 6 * 4 = 24 return 24
-------------------------------------------------- ----------------------------------------------------
fuct2(3): n = 3
res = fuct2(2)*3 = 2 * 3 = 6 return 6
-------------------------------------------------- ----------------------------------------------------
fuct2(2): n = 2
res = fuct2(1)*2 = 1 * 2 = 2 return 2
-------------------------------------------------- ----------------------------------------------------
fuct2(1): n = 1
res = fuct2(0)*1 = 1 * 1 = 1 return 1
-------------------------------------------------- ----------------------------------------------------
fuct2(0): n = 0 return 1
РЕКУРСИВНЫЙ СПУСК РЕКУРСИВНЫЙ ВОЗВРАТ
void main() {
int n = 4;
long f = fuct2(n);
printf("%d! = %ld", n, f);
}

Задача 1
Собрать и отладить (т.е. заставить работать) код рекурсивного вычисления факториала.
И выполнить трассировку его для n=5 используя встроенный отладчик VS

Простейшие рекурсивные функции
void rec1(int n) {
printf(" %d", n);
if (n > 1) {
rec1(n - 1);
}
}
void rec2(int n) {
if (n > 1) {
rec2(n - 1);
}
printf(" %d", n);
}
void rec3(int n) {
printf(" %d", n);
if (n > 1) {
rec3(n - 1);
}
printf(" %d", n);
}
void main() {
rec1(3);
printf(" rec1 FINISH\n");
rec2(3);
printf(" rec2 FINISH\n");
rec3(3);
printf(" rec3 FINISH\n");
}

Задача 2
Используя простейшие рекурсивные функции с предыдущего слайда в качестве вдохновения и основы, сделайте собственные рекурсивные функции (f1(), f2(), f3()), которые выводят в консоль последовательность чисел:
Задача 2.1.
Вызов функции: f1(11)
Формируемый вывод: 11 9 7 5 3 1
Задача 2.2.
Вызов функции: f2(11)
Формируемый вывод: 1 3 5 7 9 11
Задача 2.3.
Вызов функции: f3(11)
Формируемый вывод: 11 9 7 5 3 1 3 5 7 9 11

Задача 3
Выполнить трассировку только что созданных функций
Задача 3.1.
Выполнить трассировку для n=7 используя встроенный отладчик VS. Выполнить трассировку по очереди для всех функций f1(), f2(), f3()
Задача 3.2.
Выполнить трассировку для n=7 используя встроенный бумагу и ручку/карандаш. Выполнить трассировку по очереди для всех функций f1(), f2(), f3()

Задача 4* (по мотивам ЕГЭ)
void recEGE1(int n) {
if (n >= 1) {
printf(" %d", n);
recEGE1(n - 1);
recEGE1(n - 1);
}
}
void main() {
recEGE1(3);
}
Нужно выполнить трассировку представленного кода в отладчике VS.
(Задачи, подобные этой, периодически встречаются в ЕГЭ по информатике. )

Задача 5* (по мотивам ЕГЭ)
Нужно выполнить трассировку представленного кода в отладчике VS.
(Крайне желательно) выполнить ручную трассировку – на бумаге!

Задача 6* (по мотивам ЕГЭ)
Нужно выполнить трассировку представленного кода в отладчике VS.
(Крайне желательно) выполнить ручную трассировку – на бумаге!

Задача 7** (по мотивам ЕГЭ)
Нужно выполнить трассировку представленного кода в отладчике VS.
(желательно) выполнить ручную трассировку – на бумаге!

Задача 8*
В игру, реализованную в лаб работах 8, 9 и т.д. добавить «руку Мидаса» - прикосновение к стене превращают всю стену в набор золотых элементов. В золото превращаются ВСЕ ЭЛЕМЕНТЫ связанные друг с другом – в не зависимости от конфигурации стены.

Задача 8* (Код обслуживающий)

Задача 8* (Код превращения стены в золото)

Задача 8.2*
Выполнить трассировку в отладчике VS заливки небольшой стены при помощи добавленной функции
void doMidasHand(int i, int j)

Задача 9**
Реализовать бинарный поиск в отсортированном массиве.
Необходимо реализовать его двумя способами – итерационно и рекурсивно.

Задача 9** (2)

Задача 9** (3)

Задача 9** (4)