Шестое занятие по C++: функции, vol 2

Медвежьи истории.

Как ты думаешь, почему медведь всю зиму спит? Как ты помнишь, медведь работает на центральном лесном складе, он предоставляет лесным жителям пространство, в котором они могут что-либо хранить. Но каждый раз, когда его просят найти что либо ему приходится оббегать весь склад, читая надписи на каждой коробке — их названия. Причем иногда он находит нужную коробку сразу, а иногда ему приходится оббегать весь склад в поисках нужной маленькой коробки, которая, как оказывается, стояла на самом видном месте на ближней полке. После такой летней беготни он так устает, что потом всю зиму отсыпается. А весной он встает в очень плохом настроении, потому что летом его опять ждет эта титаническая работа. А страдает, в итоге, ни в чем неповинная селедка, которую он весной со злости и голода съедает.

Однажды к медведю на практику приехал студент с факультета логистики НИУ ВШЭ — молоденький лис Федор. Осмотрев склад, Федор сказал, что все цивилизованные склады давно работают совсем по-другому. Он предложил ввести на складе нумерацию всех коробок, то есть помимо названия задать для каждой коробки ее местоположение — число, которое зависит от сектора склада, стеллажа и порядкового номера на полке. Всю информацию о соответствии таких номеров и названий коробок, а также имен их владельцев Федор внес в электронную базу данных. Это позволило находить нужную коробку буквально за секунду. Теперь медведь каждое лето радуется жизни, а зимой успевает съездить к своему брату на север. А у тебя в холодильнике лежит селедка, которая теперь достается тебе, а не медведю. Теперь он питается исключительно черной икрой, ведь теперь он зарабатывает гораздо больше…

По сабжу…

Ты никогда не задумывался о том, как компьютер ищет твою переменную в оперативной памяти? Может быть он обходит все переменные и проверяет их название? А что тогда делать, если у кого то еще переменная с таким же названием?

На самом деле, компьютер оперирует не названиями переменных, а их адресами в памяти. Как и на складе у медведя, у каждой переменной есть свой уникальный номер, который позволяет быстро узнать ее местонахождение. Более подробно мы рассмотрим этот вопрос, когда будем говорить об указателях, а сейчас нам этот факт понадобится, чтобы возвращать из функции более одного значения, а также передавать массивы, как параметры.

Передача параметров по значению.

Передача параметров по значению — непосредственная передача данных в функцию.

Таким способом мы пользовались на предыдущем занятии. Например:

#include <iostream>
using namespace std;

int max(int a, int b)
{
   if (a > b) return a;
   return b;
} 

int main()
{
   int c, d;
   cin >> c >> d;
   cout << max(c, d);
   return 0;
}

Давай разберемся, что здесь на самом деле происходит, когда мы вызываем функцию: при вызове функции max, значения c и d копируются в локальные переменные a и b.

Локальные переменные — переменные существующие только внутри функции.

Изменение a и b никак не повлияет на c и d, т.к. это разные переменные.

Передача параметров по ссылке.

А теперь давай воспользуемся нововведением, которые мы рассмотрели в начале урока. Мы будем передавай в функцию не копии значений переменных, а их адреса в памяти. В этом случае меняя значения аргументов  в функции, мы изменяем их значения в главной программе.

#include <iostream>
using namespace std;

void oldfunc (int a) //передача значения, старый вариант
{
   a = a + 100; //a - локальная переменная, это значение потеряется в конце работы функции
}

void func(int& a) //int& - ссылка на int
{
   a = a + 100; //a - переменная лежащая по адресу, полученному в аргументе. 
            //Значение изменится, т.к. фактически переменная существует в main().
} 

int main()
{
   int c = 20;
   oldfunc(c); //ничего не меняет, на место c подставляется 20
   cout << c; //выведет 20
   func(c); // на место c автоматически подставляется ее адрес
   cout << c; //выведет 120
   return 0;
}

Что нам это дает?

  • Мы можем менять значения переменных из main в других функциях.
  • Мы можем возвращать более одного значения (класть из в переменные, которые передаются по ссылке).
  • Мы можем передавать массивы в функции.

О последнем давай поговорим поподробней.

Передача массива в функцию.

Сейчас я открою тебе величайшую тайну. На самом деле, название массива — это переменная, которая содержит адрес его первого элемента. А операция [] — эквивалент обычного сложения, так как элементы массива лежат в памяти последовательно. То есть mas[5] это тоже самое, что mas+5, но первое удобней. Именно поэтому нумерация элементов массива начинается с нуля. Чуть позже мы поговорим об этом поподробней, а пока для нас важно одно — название массива — это ссылка на первый элемент.

Что это значит? Это означает, что мы можем передать в функцию эту самую ссылку на первый элемент, а также количество элементов массива. Зная адрес первого элемента, а также количество элементов, мы сможем получить доступ ко всем элементам.

Давай напишем программу, в которой будут отдельные функции ввода и вывода массива. Обрати внимание, что простая передача по ссылке и передача массива различаются. Не путай их.

#include <iostream>
using namespace std;

void input(int mas[], int n) {
   for (int i = 0; i < n; i++) 
     cin >> mas[i];
} 

void output(int mas[], int n) {
   for (int i = 0; i < n; i++) 
     cout << mas[i] << ' ';
} 

int main() {
   int mas[5];
   input(mas, 5); //mas - и есть адрес первого элемента
   output(mas, 5);
   return 0;
}

Эта программа просто введет массив с клавиатуры и выведет на экран.

Более подробно об адресах в памяти мы поговорим на одном из следующих занятий, а сейчас надо просто запомнить, как передавать массив в функцию.

Рекурсия.

Как ты думаешь, что произойдет, если собака наступит себе на хвост? А если функция вызовет сама себя?

На самом деле второй случай вполне корректен и часто используется. Это называется рекурсией. Вполне возможно, что ты уже встречался с рекурсивными заданиями некоторых математических функций, скажем и n! = n * (n-1)! (0!=1, что такое факториал, почитай в википедии), а n-ое число Фибоначчи Fn равно Fn-1 + Fn-2.

Давай попробуем описать один из таких математических алгоритмов — вычисление факториала:

#include <iostream>
using namespace std;

int fact(int n)
{
   if (n == 0) return 1; //условие завершение рекурсии
   else return n * fact( n - 1 ); //функция вызывает сама себя в соответствии с математическим алгоритмом
}

Обрати внимание, что рекурсивная функция всегда должна иметь условие завершение, т.е. в одном из случаев возвращать конкретное значение,а не вызывать саму себя , иначе рекурсия никогда не завершится.

Теперь давай рассмотрим более сложную рекурсивную функцию — генерацию всех возможных слов заданной длины (необязательно осмысленных).

#include <iostream>
using namespace std;

const int N=2; //длина слова

//cлово - массив символов, т.е. элементов типа char

void show(char mas[], int n) //вывод массива, т.е одного слова
{
   for (int i = 0; i < n; i++) cout << mas[i];
   cout << " ";
} 

void generate(char mas[], int n, int length) //генерация всех слов заданной длины
{
   //n - изначальная длина слова
   //длина текущего подслова
   //для слова длины n функция фиксирует текущую букву и генерирует все слова длины n-1
   if (length == 0) show(mas, n); //если нужная длина - значит новый вариант готов, печатаем
   else for (char a = 'a'; a <= 'z'; a++ ) //иначе проходим по всем буквам от 'a' до 'z' (они стоят в кодировке последовательно)
   {
       mas[n - length] = a; //ставим букву в массив на нужную позицию
       generate(mas, n, length - 1); //генерируем все подслова длины length - 1
   }
} 

int main() {
   char mas[N];
   generate(mas, N, N); //запускаем
   return 0;
}

Если не понятно как оно работает, посмотри на работу функции в отладчике.

Программа работает следующим образом:

2 1 - параметр lenght
a-
   aa
   ab
   ac
   ..
   az
b-
   ba
   bb
   ..
..

Здесь отступ — это то, что генерируется, когда функция вызывает сама себя.  Для слов длины 3 (просто поменяй константу сверху) будет работать вот так:

 3 2 1 - параметр lenght
a--
   aa-
       aaa
       aab
       ...
       aaz
   ab-
      aba
      ...
   ..
   az-
      ...
...
z--
   ...
      ...

Как ты видишь, рекурсивная реализация этой программы достаточно коротка и относительно проста, а реализацию с циклом придумать гораздо сложнее.

Кстати, а сколько будет слов длины 5 (в латинском алфавите 26 букв)? Это число влезет в int?

Задачи для самостоятельного решения.

4.1.1 Написать функцию swap() которая меняет местами значения двух переменных. (2 балла)

4.1.2. Написать функцию arraySwap() которая меняет местами элементы двух массивов одинаковой длинны (3 балла).

4.2. Написать функцию div() которая принимает 2 числа и возвращает в программу результат целочисленного деления и остаток. Не использовать массивы. (2 балла).

4.3.1 Написать рекурсивную функцию shift(), которая сдвигает все элементы массива на 1 элемент «вправо», то есть  { 0, 1, 2, 3 } -> { 3, 0, 1, 2 }; (5 баллов).

4.3.2. Написать рекурсивную функцию shift() которая сдвигает все элементы массива на N элементов влево (где N — один из аргументов этой функции). (5 баллов)

4.4. Написать рекурсивную сортировку пузырьком. (10 баллов).

4.5. Написать рекурсивную функцию, которая выводит все возможные перестановки символов в строке, которую введет пользователь (15 баллов).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *