Базовый курс Си. Вебинар №7: Область видимости. Указатели. Рекурсия

1.

Вебинар №7
Область видимости.
Указатели. Рекурсия
Базовый курс Си

2.

План курса
Введение в язык Си
Адресная арифметика. Массивы,
строки
Системы счисления
Типы данных. Операторы и
выражения
Структурные типы данных. Файлы
Многомодульные программы
Ветвления и побитовые
операции
Аргументы командной строки.
Препроцессор
Циклы
Буферный ввод-вывод. Функции
Отладка программ. Динамические
структуры данных
Область видимости. Указатели.
Рекурсия
Вещественные числа. Массивы

3.

На этом уроке
Область видимости. Указатели. Рекурсия
Обсудим область видимости переменных в функциях
Что такое указатель
Как передать аргумент по указателю
Узнаем, что такое рекурсия
Какие бывают рекурсии

4.

Статические
переменные

5.

Задачи
По пройденному материалу
#include <stdio.h>
void func(void) {
static int a=5; //статическая память
a++;
printf("a = %d\n",a);
}
int main(void)
{
func();
func();
func();
return 0;
}
a = ?

6.

Решение
По пройденному материалу
#include <stdio.h>
void func(void) {
static int a=5; //статическая память
a++;
printf("a = %d\n",a);
}
int main(void)
{
func();
func();
func();
return 0;
}
a = 6
a = 7
a = 8

7.

Указатель

8.

Указатели в С и С++
Указатель - это переменная, которая хранит адрес
другой переменной
Для работы с указателями используются операции *
и & Это не логическая “И”
Макрос NULL - пустой указатель

9.

Указатель
Указатель - это переменная, значением которой является адрес.
Для указателей определены следующие операции:
& - взятие адреса объекта
* - разыменование. Взятие значения по указанному адресу.
int *p, n; //объявление переменной p - указатель на
целочисленный объект
p = &n; //присвоение адреса n в p
*p = 10; //n = 10 или положить значение по адресу в
переменной p
printf("n = %d\n", n); // n = 10

10.

Пример применения указателей
#include <stdio.h>
int main() {
int x, y, *ptr; // объявляем 3 переменные
ptr = NULL; // инициализируем указатель null, нулевым значением
x = -7;
ptr = &x; // адрес переменной х записываем в переменную ptr
y = *ptr; // Записываем в y значение на которое указывает
указатель ptr
*ptr = 3; // Записываем в ячейку (х) на которую ссылается
указатель ptr число 3
//std::cout << "x = " << x << " y = " << y; // вывод на экран x
= 3 y = -7
printf("x = %d y = %d",x,y);
return 0;
}

11.

Графическое
пояснение
операции
&и*
NULL

12.

Указатель на указатель
//Можно объявлять указатели на указатели:
#include <stdio.h>
int main() {
int a = 77;
int *ptrA = &a;
int** ppA = &ptrA;
*ptrA = 88;
printf("%d\n",a);// << std::endl; // 88
**ppA = 99;
printf("%d\n",a);// << std::endl; // 99
return 0;
}
a
77
1024
ptrA
1024
2340
ppA
2340
4567

13.

Задачи
По пройденному материалу
#include <stdio.h>
void swap(int a, int b) {
int tmp;
tmp = a;
a = b;
b = tmp;
}
int main(void)
{
int n=7, m=5;
swap(n, m); // Передаются значения
printf("n = %d m = %d\n",n,m);
}
n = ?
m = ?

14.

Решение
По пройденному материалу
#include <stdio.h>
void swap(int a, int b) {
int tmp;
tmp = a;
a = b;
b = tmp;
}
int main(void)
{
int n=7, m=5;
swap(n, m); // Передаются значения
printf("n = %d m = %d\n",n,m);
}
n = 7
m = 5
Параметры функции swap
передаются по значению и,
следовательно, поменялись
местами только копии
параметров n и m внутри
функции, при этом никакого
влияния на сами фактические
параметры n и m не
произошло.

15.

Задачи
По пройденному материалу
#include <stdio.h>
void swap(int *pa, int *pb) {
int tmp;
tmp = *pa;
*pa = *pb;
*pb = tmp;
}
int main(void)
{
int n=7, m=5;
swap(&n, &m); // Передается адрес
printf("n = %d m = %d\n",n,m);
}
n = ?
m = ?

16.

Решение
По пройденному материалу
#include <stdio.h>
void swap(int *pa, int *pb) {
int tmp;
tmp = *pa;
*pa = *pb;
*pb = tmp;
}
int main(void)
{
int n=7, m=5;
swap(&n, &m); // Передается адрес
printf("n = %d m = %d\n",n,m);
}
n = 5
m = 7

17.

Рекурсия в функциях

18.

Рекурсия в функциях
Рекурсия - математический механизм, в котором для решения задачи из
функции вызывается та же самая функция
Рекурсивная функция - вызов функции из нее же самой.
Рекурсивная функция всегда должна состоять из:
1. Условие остановки
2. Шаг рекурсии

19.

Схема работы рекурсии
#include <stdio.h>
void rec(int n) {
if(n>0) rec(n-1);
printf("%5d",n);
}
int main(void){
rec(3);
return 0;
}

20.

Вычисление факториала
Факториал можно описать итерационно:
unsigned int factorial(unsigned int n) {
unsigned int i, fact=1;
for(i=2;i<=n;i++)
fact*=i;
return fact;
}

21.

Рекурсивное вычисление факториала
unsigned int factorial(unsigned int n) {
printf("%d\n",n);
if(n<=1) // Условие остановки
return 1;
int _f = n * factorial(n-1);
printf("%d*factorial(%d)=%d\n",n,n-1,_f);
return _f; // Шаг
}
factorial(2) {
factorial(1) {
factorial(3) {
int main() {
factorial(3);
if(2<=1)
if(1<=1)
if(3<=1)
return 0;
return 1;
return 1;
return 1;
}
return 3*factorial(2); return 2*factorial(1); }
}
}

22.

Как это работает?
Стековый кадр — Википедия

23.

Задачи
По пройденному материалу
1
Найти сумму цифр натурального числа

24.

Решение
По пройденному материалу
1
Найти сумму цифр натурального числа
//Нерекурсивный способ:
int sumIter(int num) {
int sum = 0;
while(num > 0) {
sum = sum + num % 10;
num = num / 10;
}
return sum;
}
//Рекурсивный способ:
int sumRec(int num) {
if (num > 0)
return num % 10 +
sumRec(num / 10);
else
return 0;
}

25.

Задачи
Проблемы рекурсии
По пройденному материалу
2
Вычислить рекурсивно число Фибоначчи N.
#include <stdio.h>
int fibonachi(int n) {
if(n<=0)
return 0;
if(n==1)
return 1;
return fibonachi(n-1)+fibonachi(n-2);
}
int main(void){
printf("%d\n",fibonachi(6));
}
?

26.

Решение
По пройденному материалу
2
Вычислить рекурсивно число Фибоначчи N.
#include <stdio.h>
int fibonachi(int n) {
if(n<=0)
return 0;
if(n==1)
return 1;
return fibonachi(n-1)+fibonachi(n-2);
}
int main(void){
printf("%d\n",fibonachi(6));
}
8

27.

Числа Фибоначчи

28.

Код программы
#include <stdio.h>
int fibonachi(int n) {
printf("n=%d\n",n);
if(n<=0)
{
//printf("F(%d)=0\n",n);
printf("return 0\n");
return 0;
}
if(n==1)
{
printf("F(1)=1\n");
//printf("F(%d)=1\n",n);
return 1;
}
int Fib = fibonachi(n1)+fibonachi(n-2);
printf("Fib(%d)=%d\n",n,Fib);
return Fib;
}
int main(void)
{
printf("%d\n",fibonachi(6));
return 0;
}

29.

Проблемы рекурсии
Как видно из картинки, одно и тоже действие будет выполнено несколько раз.
Как можно было бы исправить данную проблему?

30.

Проблемы рекурсии
Как видно из картинки, одно и тоже действие будет выполнено несколько раз.
Как можно было бы исправить данную проблему?
● Сделать итерационную версию
● Кешировать результат, например в глобальном массиве Recursive Caching Based
Fibonacci - Stack Overflow

31.

Хвостовая рекурсия
Если структура рекурсивного алгоритма такова, что
рекурсивный вызов является последней выполняемой
операцией в функции, а его результат непосредственно
возвращается в качестве результата функции, то такую
рекурсию называют хвостовой. Компиляторы
поддерживающие оптимизацию кода могут заменить ее
на цикл.
Хвостовая рекурсия — Википедия

32.

Замена цикла на
рекурсию

33.

Замена цикла на рекурсию
Необходимо реализовать с помощью рекурсии данный цикл:
for(i=1;i<n;i++)
printf("%d ",i);
void recursionFor(int i, int n) {
if(i==n)
return;
printf("%d ", i);
recursionFor(i+1, n);
}

34.

Задачи

35.

Задачи
Проблемы рекурсии
По пройденному материалу
1
На стандартном потоке ввода задан текст
заканчивающийся точкой, точка в текст не входит. На
стандартный поток вывода вывести этот текст в
обратном порядке.

36.

Решение
По пройденному материалу
1
void print_rev (void)
{
char ch;
scanf ("%c", &ch); //ввод очередного символа
if (ch != '.') {
print_rev (); //рекурсивный вызов для обработки
//оставшихся символов
printf ("%c", ch); //вывод символа
}
}

37.

Решение
По пройденному материалу
2
Описать рекурсивную функцию вычисления НОД
int gcd ( int n, int m ){
if(n==m)
return n ;
if (n<m)
return gcd(n,m-n );
return gcd(n-m,m );
}

38.

Решение
По пройденному материалу
3
Написать рекурсивную
функцию перевод
числа в двоичную
систему счисления.
#include <iostream>
void dec_to_bin(int n){
if (n >= 2)
dec_to_bin(n / 2);
std::cout << n % 2;
}
int main(){
int n;
std::cout << "\n\nn -> ";
std::cin >> n;
std::cout << "\n\nBin = ";
dec_to_bin(n);
return 0;
}

39.

Решение
По пройденному материалу
3
Дана
последовательность
натуральных чисел,
завершающаяся
числом 0. Найдите
максимум.
uint32_t max_find(void) {
uint32_t number, max;
scanf("%u", &number);
if(number==0)
return 0;
max = max_find();
if (max<number)
max=number;
return max;
}

40.

Домашнее задание

41.

Домашнее задание
Контест D
Решать рекурсивно!
Выполнено 3 задание - удовлетворительно
Выполнено 4 задания - хорошо
Выполнено 5 - отлично
Формат сдачи
Каждая задача отдельным файлом.
Решенные задачи не считаются
Ссылка на git желательна
Подсказки к задачам группы D Базовый курс Си
Дедлайн: к следующему уроку
Советуем регулярно выполнять ДЗ
(наверстать пропуски тяжело)

42.

Список полезных источников
• Руководство по языку программирования Си
• Онлайн версия «Си для встраиваемых систем» | Класс робототехники