СВЯЗЬ МАССИВОВ И ЦИКЛОВ

=======================

Вследствие этого массивы приходится копировать (и инициализировать)

поэлементно, в цикле перебирая все (или часть) ячейки массива.

 

int i;

 

for(i=0; i < 5; i++)

a[i] = b[i];

 

В данном случае индекс цикла служит также и индексом в массиве.

 

Индексы в массиве идут с НУЛЯ.

 

Пример инициализации:

 

int index, array[5];

 

for(index=0; index < 5; index++)

array[index] = index * 2 + 1;

 

или

 

int index, array[5];

 

index = 0;

while(index < 5){

array[index] = index * 2 + 1;

index++;

}

 

/* В массиве будет: { 1, 3, 5, 7, 9 } */

 

ИНДЕКС

для массивов -

номер "ящика/ячейки" в массиве.

 

для циклов -

номер повторения цикла, счетчик.

Мы должны изменять его САМИ.

 

Обычно массивы и циклы совмещаются так:

индекс цикла есть индекс в массиве;

то есть индекс цикла используется для перебора всех

элементов массива:

 

int a[N], i;

 

for(i=0; i < N; i++)

...a[i]...

---------------------------------------------------------------------------

 

Примеры:

 

int a[5];

 

a[0] = 17;

a[0] += 4;

a[0]++;

---------------------------------------------------------------------------

 

Пример: числа Фибоначчи.

Задаются математическими формулами:

 

f[1] = 1

f[2] = 1

f[n+2] = f[n+1] + f[n]

 

Вот программа:

---------------------------------------------------------------------------

 

#include /* магическая строка */

#define N 20 /* сколько первых чисел посчитать */

 

void main(){

int fibs[N], index;

 

fibs[0] = 1; /* индексы отсчитываются с нуля!!! */

fibs[1] = 1;

 

/* Тут показано, что индекс элемента массива может вычисляться */

 

for(index=2; index < N; index++)

fibs[index] = fibs[index-1] + fibs[index-2];

 

/* Распечатка в обратном порядке */

for(index = N-1; index >= 0; index--)

printf("%d-ое число Фибоначчи есть %d\n",

index+1, fibs[index]);

}

 

Здесь мы видим новый для нас оператор #define

Он задает текстуальную ЗАМЕНУ слова N на слово 20,

в данном случае просто являясь эквивалентом

 

const int N = 20;

 

К несчастью размер массива не может быть задан при помощи переменной,

а вот при помощи имени, определенного в #define - может.

 

СТРОКИ

 

Строки есть массивы БУКВ - типа char,

оканчивающиеся спецсимволом \0

 

char string[20];

 

string[0] = 'П';

string[1] = 'р';

string[2] = 'и';

string[3] = 'в';

string[4] = 'е';

string[5] = 'т';

string[6] = '\0';

 

printf("%s\n", string);

 

%s - формат для печати СТРОК.

Никакие другие массивы не могут быть напечатаны

целиком одним оператором.

 

char string[20];

 

string[0] = 'П';

string[1] = 'р';

string[2] = 'и';

string[3] = 'в';

string[4] = 'е';

string[5] = 'т';

string[6] = '\n'; /* Перевод строки - тоже буква */

string[7] = '\0';

 

printf("%s", string);

 

или даже просто

 

printf(string);

 

Такие массивы можно записать в виде строки букв в ""

 

char string[20] = "Привет\n";

 

Оставшиеся неиспользованными символы массива от string[8] до string[19]

содержат МУСОР.

 

ПОЧЕМУ ДЛЯ СТРОК ИЗОБРЕЛИ СИМВОЛ "ПРИЗНАК КОНЦА"?

=================================================

Строка - это ЧАСТЬ массива букв.

В разное время число букв в строке может быть различным,

лишь бы не превышало размер массива (тогда случится сбой программы).

Значит, следует где-то хранить текущую длину строки (число использованных

символов). Есть три решения:

(1) В отдельной переменной. Ее следует передавать во все

функции обработки данной строки (причем она может изменяться).

 

char str[32]; /* массив для строки */

int slen; /* брать первые slen букв в этом массиве */

...

func(str, &slen); /* ДВА аргумента для передачи ОДНОЙ строки */

...

 

Этот подход работоспособен, но строка разбивается на два

объекта: сам массив и переменную для его длины. Неудобно.

 

(2) Хранить текущую длину в элементе str[0],

а буквы - в str[1]... итд.

Плохо тем, что в str[0] можно хранить лишь числа от 0 до 255,

и если строка длиннее - то такой подход неприменим.

 

(3) Не хранить длину НИГДЕ, а ввести символ-признак конца строки.

Теперь в

 

func(str); /* ОДИН аргумент - сам массив */

 

передается только сам массив, а его текущая длина может быть

при нужде вычислена при помощи некоей функции, вроде такой:

 

int strlen(char s[]){ /* функция от массива букв */

int counter = 0; /* счетчик и одновременно индекс */

 

while(s[counter]!= '\0') /* пока не встретился признак конца текста */

counter++; /* посчитать символ */

return counter; /* сколько символов, отличных от '\0' */

}

 

Тут никаких ограничений нет. Именно этот подход и был избран

в языке Си, хотя в принципе можно самому пользоваться и другими.

На самом деле в языке есть такая СТАНДАРТНАЯ функция strlen(s)

(вам не надо писать ее самому, ее уже написали за вас).

---------------------------------------------------------------------------

 

ИНИЦИАЛИЗАЦИЯ ГЛОБАЛЬНОГО МАССИВА

=================================

Массив, заданный вне каких-либо функций, можно проинициализировать

константными начальными значениями:

 

int array[5] = { 12, 23, 34, 45, 56 };

 

char string[7] = { 'П', 'р', 'и', 'в', 'е', 'т', '\0' };

 

Если размер массива указан БОЛЬШЕ, чем мы перечислим элементов,

то остальные элементы заполнятся нулями (для int) или '\0' для char.

 

int array[5] = { 12, 23, 34 };

 

Если мы перечислим больше элементов, чем позволяет размер массива -

это будет ошибкой.

 

int a[5] = { 177, 255, 133 };

 

Операция индексации массива a[] дает:

 

при n значение выражения a[n] есть

---------------------------------------------------------------------------

 

-1 не определено (ошибка: "индекс за границей массива")

0 177

1 255

2 133

3 0

4 0

5 не определено (ошибка)

* 13_FUNCS.txt *

 

КАК ПРОИСХОДИТ ВЫЗОВ ФУНКЦИИ

============================

 

Пусть у нас описана функция, возвращающая целое значение.

 

/* ОПРЕДЕЛЕНИЕ ФУНКЦИИ func(). */

/* Где func - ее имя. Назвать мы ее можем как нам угодно. */

 

int func(int a, int b, int c){

int x, y;

 

...

x = a + 7;

...

b = b + 4;

...

 

return(некое_значение);

}

 

Здесь

a, b, c - аргументы функции (параметры)

x, y - локальные переменные

 

Точка вызова - находится внутри какой-то другой

функции, например функции main()

 

main(){

 

int zz, var;

...

var = 17;

zz = func(33, 77, var + 3) + 44;

...

}

 

Когда выполнение программы доходит до строки

 

zz = func(33, 77, var + 3) + 44;

 

1) Происходит ВЫЗОВ ФУНКЦИИ func()

 

(a) Этот пункт мы увидим ниже.

 

(b) Создаются переменные с именами a, b, c, x, y;

 

(c) Переменным-аргументам присваиваются начальные значения,

которые берутся из точки вызова.

В точке вызова перечислен список (через запятую) выражений (формул):

 

func(выражение1, выражение2, выражение3)

 

Вычисленные значения этих выражений соответственно будут присвоены

1-ому, 2-ому и 3-ему аргументам (параметрам) из определения функции:

 

int func(a, b, c){ /* a = номер 1, b = 2, c = 3 */

 

Первый параметр:

 

a = 33;

 

Второй параметр:

 

b = 77;

 

Третий параметр:

 

c = var + 3;

 

то есть, вычисляя,

 

c = 20;

 

Локальные переменные x и y содержат неопределенные значения,

то есть мусор (мы не можем предсказать их значения,

пока не присвоим им явным образом какое-либо значение сами).

 

2) Выполняется ТЕЛО функции, то есть вычисления, записанные внутри {... }

в определении функции. Например:

 

x = a + 7;

 

И параметры, и локальные переменные - это ПЕРЕМЕННЫЕ,

то есть их можно изменять.

 

b = b + 4;

 

При этом никакие переменные ВНЕ этой функции не изменяются.

(Об этом еще раз позже).

 

3) Производится ВОЗВРАТ из функции.

 

...

return(некое_значение);

}

 

Например, это может быть

 

...

return(a + 2 * x);

}

 

Рассмотрим, что при этом происходит в точке вызова:

 

zz = func(33, 77, var + 3) + 44;

 

(1) Вычеркиваем func(.....)

 

zz = XXXXXXX + 44;

 

(2) Вычисляем значение "некое_значение" в операторе return,

и берем КОПИЮ этого значения.

Пусть при вычислении там получилось 128.

 

(3) Подставляем это значение на место вычеркнутого func(.....)

У нас получается

 

zz = 128 + 44;

 

(4) АВТОМАТИЧЕСКИ УНИЧТОЖАЮТСЯ локальные переменные и аргументы функции:

 

a - убито

b - убито

c - убито

x - убито

y - убито

 

Таких переменных (и их значений) больше нет в природе.

 

(5) Пункт, который мы обсудим позже.

 

(6) Продолжаем вычисление:

 

zz = 128 + 44;

 

Вычисляется в

 

zz = 172; /* оператор присваивания */

 

---------------------------------------------------------------------------

 

int func1(int x){

printf("func1: x=%d\n", x); /* 1 */

x = 77;

printf("func1: x=%d\n", x); /* 2 */

return x;

}

 

void main(){

int var, y;

 

var = 111;

y = func1(var); /* @ */

 

printf("main: var=%d\n", var); /* 3 */

}

 

В данном случае в точке @ мы передаем в функцию func1()

ЗНАЧЕНИЕ переменной var, равное 111.

Это значит, что при вызове функции будет создана переменная x

и ей будет присвоено начальное значение 111

 

x = 111;

 

Поэтому первый оператор printf() напечатает 111.

 

Затем мы изменяем значение переменной x на 77.

Мы меняем переменную x, но не переменную var!!!

Использовав ЗНАЧЕНИЕ (его копию) из переменной var для x,

мы о переменной var забыли - она нас не касается (а мы - ее).

 

Поэтому второй оператор printf() напечатает 77.

В переменной же var осталось значение 111,

что и подтвердит нам третий оператор printf,

который напечатает 111.

 

---------------------------------------------------------------------------

 

ВРЕМЕННОЕ СОКРЫТИЕ ПЕРЕМЕННЫХ

=============================

 

int func1(int x){ /* f.1 */

printf("func1: x=%d\n", x); /* f.2 */

x = 77; /* f.3 */

printf("func1: x=%d\n", x); /* f.4 */

return x; /* f.5 */

}

 

void main(){

int x, y; /* 1 */

 

x = 111; /* 2 */

y = func1(x); /* 3 */

 

printf("main: x=%d y=%d\n", x, y); /* 4 */

}

 

А теперь мы и переменную внутри main(), и аргумент функции

func1() назвали одним и тем же именем. Что будет?

 

Будет то же самое, что в предыдущем примере.

 

В момент вызова функции func1() будет создана НОВАЯ переменная

с именем x, а старая (прежняя) переменная и ее значение будут

ВРЕМЕННО СПРЯТАНЫ (скрыты).

 

Можно было бы уточнить эти переменные именами функций,

в которых они определены:

 

main::x

 

и

 

func1::x

 

(но это уже конструкции из языка Си++, а не Си).

 

Выполним программу по операторам:

 

|/* 1 */ Отводятся переменные main::x и main::y для целых чисел;

|/* 2 */ main::x = 111;

|/* 3 */ Вызывается func1(111);

|

+-------+

. |/* f.1 */ Отводится переменная func1::x со значением 111;

. |/* f.2 */ Печатается 111 из переменной func1::x;

. |

. |/* f.3 */ func1::x = 77; (это не main::x, а другая переменная,

. | ЛОКАЛЬНАЯ для функции func1.

. | Переменную main::x мы сейчас не видим -

. | она "заслонена" именем нашей локальной

. | переменной.

. | Поэтому мы не можем ее изменить).

. |

. |/* f.4 */ Печатает 77 из func1::x;

. |/* f.5 */ Возвращает значение func1::x, то есть 77.

. | Переменная func1::x уничтожается.

. |

. | Теперь мы снова возвращаемся в функцию main(),

. | где имя x обозначает переменную main::x

 

+-------+

|

|/* 3 */ y = 77;

|/* 4 */ Печатает значения main::x и main::y, то есть

| 111 и 77.

 

Этот механизм сокрытия имен позволяет писать функции main() и func1()

разным программистам, позволяя им НЕ ЗАБОТИТЬСЯ о том, чтобы имена

локальных переменных в функциях НЕ СОВПАДАЛИ. Пусть совпадают - хуже не

будет, механизм упрятывания имен разрешит конфликт.

Зато программист может использовать любое понравившееся ему имя

в любой функции - хотя бы и x, или i.

 

---------------------------------------------------------------------------

 

То же самое происходит с локальными переменными,

а не с аргументами функции.

 

int func1(int arg){ /* локальная переменная-параметр func1::arg */

int x; /* локальная переменная func1::x */

 

x = arg;

printf("func1: x=%d\n", x);

x = 77;

printf("func1: x=%d\n", x);

return x;

}

 

void main(){

int x, y; /* переменные main::x и main::y */

 

x = 111;

y = func1(x);

 

printf("main: x=%d y=%d\n", x, y);

}

 

Действует тот же самый механизм временного сокрытия имени x.

Вообще же, аргументы функции и ее локальные переменные

отличаются только одним:

аргументам автоматически присваиваются

начальные значения, равные значениям соответствующих выражений

в списке

 

имя_функции(...,...,....)

арг1 арг2 арг3

 

в месте вызова функции.

 

То есть

 

ОПИСАНИЕ ФУНКЦИИ:

 

int f(int арг1, int арг2, int арг3){

int перем1, перем2;

...

/* продолжение */

}

 

ВЫЗОВ:

 

.... f(выражение1, выражение2, выражение3)...

 

ТО В ТЕЛЕ ФУНКЦИИ ВЫПОЛНИТСЯ (в момент ее вызова):

 

арг1 = выражение1;

арг2 = выражение2;

арг3 = выражение3;

 

перем1 = МУСОР;

перем2 = МУСОР;

 

...

/* продолжение */

 

---------------------------------------------------------------------------

 

ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

=====================

 

Наконец, существуют переменные, которые объявляются ВНЕ ВСЕХ ФУНКЦИЙ,

и существующие все время выполнения программы

(а не только то время, когда активна функция, в которой они созданы).

 

Локальные переменные и аргументы УНИЧТОЖАЮТСЯ при выходе

из функции. Глобальные переменные - нет.

 

int x = 12; /*::x - ей можно заранее присвоить константу */

int globvar; /*::globvar */

 

int f1(){

int x; /* f1::x */

 

x = 77;

printf("x=%d\n", x); /* 4 */

return x;

}

 

int f2(){

printf("x=%d\n", x); /* 5 */

return 0;

}

 

void main(){

int x, y; /* main::x */

 

x = 111; /* 1 */

printf("x=%d\n", x); /* 2 */

printf("glob=%d\n", globvar); /* 3 */

 

y = f1();

y = f2();

}

 

В данном примере мы видим:

- во-первых мы видим ФУНКЦИИ БЕЗ ПАРАМЕТРОВ. Это нормальная ситуация.

- во-вторых тут используются ТРИ переменные с именем "x".

 

Как выполняется программа?

 

/* 1 */ main::x = 111;

Это локальный x, а не глобальный.

Глобальный x попрежнему содержит 12.

 

/* 2 */ Напечатает значение переменной main::x, то есть 111.

Внутри функции main глобальная переменная::x

заслонена своей собственной переменной x.

В данном случае НЕТ СПОСОБА добраться из main к глобальной

переменной x, это возможно только в языке Си++ по имени::x

 

К переменной же globvar у нас доступ есть.

 

/* 3 */ Печатает::globvar. Мы обнаруживаем, что ее значение 0.

В отличие от глобальных переменных,

которые изначально содержат МУСОР,

глобальные переменные изначально содержат значение 0.

 

В рамочку, подчеркнуть.

 

/* 4 */ При вызове f1()

переменная f1::x

заслоняет собой как

main::x

так и

::x

 

В данном случае напечатается 77,

но ни::x ни main::x не будут изменены оператором x = 77.

Это изменялась f1::x

 

/* 5 */ При вызове f2() история интереснее.

Тут нет своей собственной переменной x.

Но какая переменная печатается тут -

::x или

main::x?

 

Ответ:::x

то есть 12.

 

Переменные названы локальными еще и потому,

что они НЕВИДИМЫ В ВЫЗЫВАЕМЫХ ФУНКЦИЯХ.

 

Это ОПРЕДЕЛЕНИЕ локальных переменных.

(Поэтому не спрашивайте "почему?" По определению)

 

То есть, если мы имеем

 

funca(){

int vara;

...

...funcb();... /* вызов */

...

}

 

то из функции funcb() мы НЕ ИМЕЕМ ДОСТУПА К ПЕРЕМЕННОЙ vara.

 

funcb(){

int z;

 

z = vara + 1; /* ошибка,

vara неизвестна внутри funcb() */

}

 

Если, в свою очередь, funcb() вызывает funcc(),

то и из funcc() переменная vara невидима.

 

Остановитесь и осознайте.

Это правило служит все той же цели - разные функции

могут быть написаны разными программистами, которые могут

использовать одни и те же имена для РАЗНЫХ переменных,

не боясь их взаимопересечения.

Множества имен, использованных в разных функциях, независимы

друг от друга. Имена из одной функции НИКАК не относятся

к переменным с теми же именами ИЗ ДРУГОЙ функции.

 

Вернемся к параграфу КАК ПРОИСХОДИТ ВЫЗОВ ФУНКЦИИ

и рассмотрим пункт (a). Теперь он может быть описан как

 

(a) Локальные переменные и аргументы вызывающей функции делаются невидимыми.

~~~~~~~~~~

А при возврате из функции:

 

(5) Локальные переменные и аргументы вызывающей функции снова делаются видимыми.

 

ОДНАКО глобальные переменные видимы из ЛЮБОЙ функции,

исключая случай, когда глобальная переменная заслонена

одноименной локальной переменной данной функции.

 

---------------------------------------------------------------------------

 

ПРОЦЕДУРЫ

=========

Бывают функции, которые не возвращают никакого значения.

Такие функции обозначаются void ("пустышка").

Такие функции называют еще ПРОЦЕДУРАМИ.

 

void func(){

printf("Приветик!\n");

return; /* вернуться в вызывающую функцию */

}

 

Такие функции вызываются ради "побочных эффектов",

например печати строчки на экран или изменения глобальных (и только)

переменных.

 

int glob;

 

void func(int a){

glob += a;

}

 

Оператор return тут необязателен, он автоматически выполняется

перед последней скобкой }

 

Вызов таких функций не может быть использован

в операторе присваивания:

 

main(){

int z;

 

z = func(7); /* ошибка, а что мы присваиваем??? */

}

 

Корректный вызов таков:

 

main(){

func(7);

}

 

Просто вызов и все.

 

ЗАЧЕМ ФУНКЦИИ?

 

Чтобы вызывать их с разными аргументами!

 

int res1, res2;

...

 

res1 = func(12 * x * x + 177, 865, 'x');

res2 = func(432 * y + x, 123 * y - 12, 'z');

 

Кстати, вы заметили, что список фактических параметров

следует через запятую;

и выражений ровно столько, сколько параметров у функции?

 

Функция описывает ПОСЛЕДОВАТЕЬНОСТЬ ДЕЙСТВИЙ,

которую можно выполнить много раз,

но с разными исходными данными (аргументами).

В зависимости от данных она будет выдавать разные результаты,

но выполняя одни и те же действия.

 

В том то и состоит ее прелесть:

мы не дублируем один кусок программы много раз,

а просто "вызываем" его.

 

Функция - абстракция АЛГОРИТМА, то есть последовательности действий.

Ее конкретизация - вызов функции с уже определенными параметрами.

---------------------------------------------------------------------------

 

Оператор return может находиться не только в конце функции,

но и в ее середине.

Он вызывает немедленное прекращение тела функции и возврат значения

в точку вызова.

 

int f(int x){

int y;

 

y = x + 4;

if(y > 10) return (x - 1);

y *= 2;

return (x + y);

}

 

РЕКУРСИВНЫЕ ФУНКЦИИ. СТЕК

 

Рекурсивной называется функция, вызывающая сама себя.

 

int factorial(int arg){

if(arg == 1)

return 1; /* a */

else

return arg * factorial(arg - 1); /* b */

}

 

Эта функция при вызове factorial(n) вычислит произведение

 

n * (n-1) *... * 3 * 2 * 1

 

называемое "факториал числа n".

В данной функции переменная arg будет отведена (а после и уничтожена) МНОГО РАЗ.

 

Так что переменная factorial::arg должна получить еще и НОМЕР вызова функции:

 

factorial::arg[уровень_вызова]

 

И на каждом новом уровне новая переменная скрывает все предыдущие.

Так для factorial(4) будет

 

+----------------------------------------+

| | factorial::arg[ 0_ой_раз ] есть 4 |

| | factorial::arg[ 1_ый_раз ] есть 3 |

| | factorial::arg[ 2_ой_раз ] есть 2 |

| | factorial::arg[ 3_ий_раз ] есть 1 |

V --------+ +---------

 

Затем пойдут возвраты из функций:

 

+----------------------------------------+

A | /* b */ return 4 * 6 = 24 |

| | /* b */ return 3 * 2 = 6 |

| | /* b */ return 2 * 1 = 2 |

| | /* a */ return 1; |

| --------+ +---------

 

Такая конструкция называется СТЕК (stack).

 

--------+ +------------

| | пустой стек

+---------------+

 

Положим в стек значение a

|

--------+ | +------------

| V |

+---------------+

| a | <--- вершина стека

+---------------+

 

Положим в стек значение b

 

--------+ +------------

| |

+---------------+

| b | <--- вершина стека

+---------------+

| a |

+---------------+

 

Положим в стек значение c

 

--------+ +------------

| |

+---------------+

| c | <--- вершина стека

+---------------+

| b |

+---------------+

| a |

+---------------+

 

Аналогично, значения "снимаются со стека" в обратном порядке: c, b, a.

 

В каждый момент времени у стека доступно для чтения (копирования) или

выбрасывания только данное, находящееся на ВЕРШИНЕ стека.

 

Так и в нашей рекурсивной функции переменная factorial::arg

ведет себя именно как стек (этот ящик-стек имеет имя arg) -

она имеет ОДНО имя, но разные значения в разных случаях.

Переменные, которые АВТОМАТИЧЕСКИ ведут себя как стек,

встречаются только в (рекурсивных) функциях.

 

Стек - это часто встречающаяся в программировании конструкция.

Если подобное поведение нужно программисту, он должен промоделировать

стек при помощи массива:

 

int stack[10];

int in_stack = 0; /* сколько элементов в стеке */

 

/* Занесение значения в стек */

void push(int x){

stack[in_stack] = x;

in_stack++;

}

 

/* Снять значение со стека */

int pop(){

if(in_stack == 0){

printf("Стек пуст, ошибка.\n");

return (-1);

}

in_stack--;

return stack[in_stack];

}

 

Обратите в нимание, что нет нужды СТИРАТЬ (например обнулять)

значения элементов массива, выкинутых с вершины стека.

Они просто больше не используются, либо затираются новым значением при

помещении на стек нового значения.

 

void main(){

push(1);

push(2);

push(3);

 

while(in_stack > 0){

printf("top=%d\n", pop());

}

}

 

СТЕК И ФУНКЦИИ

 

Будем рассматривать каждый ВЫЗОВ функции как помещение в специальный стек

большого "блока информации", включающего в частности

АРГУМЕНТЫ И ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ вызываемой функции.

 

Оператор return из вызванной функции выталкивает со стека ВЕСЬ такой блок.

 

В качестве примера рассмотрим такую программу:

 

int x = 7; /* глобальная */

int v = 333; /* глобальная */

 

int factorial(int n){

int w; /* лишняя переменная, только для демонстрационных целей */

 

w = n;

 

if(n == 1) return 1; /* #a */

else return n * factorial(n-1); /* #b */

}

void func(){

int x; /* func::x */

 

x = 777; /* #c */

printf("Вызвана функция func()\n");

}

void main(){

int y = 12; /* main::y */

int z;

 

/* A */

z = factorial(3); /* B */

printf("z=%d\n", z);

 

func(); /* C */

}

---------------------------------------------------------------------------

 

Выполнение программы начнется с вызова функции main().

В точке /* A */

 

| в з г л я д |

V V

 

--------+ +--------

|=======================|

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

В каждый данный момент видимы переменные, которые находятся

a) на вершине (и только) стека вызовов функций.

b) и незаслоненные ими глобальные переменные.

В данном случае мы смотрим "сверху" и видим:

 

main::z, main::y,::x,::v

 

---------------------------------------------------------------------------

 

В точке /* B */ мы вызываем factorial(3).

 

--------+ +--------

|=======================|

| w = мусор |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

При новом взгляде видимы:

factorial(3)::w, factorial(3)::n,::x,::v

 

Стали невидимы:

main::z, main::y

 

Строка "текущий оператор..." указывает место, с которого надо возобновить

выполнение функции, когда мы вернемся в нее.

---------------------------------------------------------------------------

 

Когда выполнение программы в функции factorial(3) дойдет до точки

/* #b */ будет выполняться return 3 * factorial(2).

В итоге будет вызвана функция factorial(2).

 

--------+ +--------

|=======================|

| w = мусор |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

---------------------------------------------------------------------------

 

Когда выполнение программы в функции factorial(2) дойдет до точки

/* #b */ будет выполняться return 2 * factorial(1).

В итоге будет вызвана функция factorial(1).

 

--------+ +--------

|=======================|

| w = мусор |

| n = 1 |

|factorial(1) |

|=======================|

| +-|---> текущий оператор return 2 * factorial(1);

| w = 2 |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

---------------------------------------------------------------------------

 

Затем в factorial(1) выполнение программы дойдет до точки /* #a */

и будет производиться return 1.

 

При return вычеркивается ОДИН блок информации со стека вызовов функций,

и возобновляется выполнение "текущего оператора" в функции,

ставшей НОВОЙ вершиной стека вызовов.

Заметьте, что в данной ситуации вызванные функции factorial(m) еще не завершились.

В них еще ЕСТЬ что сделать: вычислить выражение в return,

и собственно выполнить сам return. Вычисления будут продолжены.

 

--------+ +--------

|=======================|

| +-|---> текущий оператор return 1;

| w = 1 |

| n = 1 |

|factorial(1) |

|=======================|

| +-|---> текущий оператор return 2 * factorial(1);

| w = 2 |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

---------------------------------------------------------------------------

 

Начинается выталкивание функций со стека и выполнение операторов return;

 

--------+ +--------

|=======================|

| +-|---> текущий оператор return 2 * 1;

| w = 2 |

| n = 2 |

|factorial(2) |

|=======================|

| +-|---> текущий оператор return 3 * factorial(2);

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

--------+ +--------

|=======================|

| +-|---> текущий оператор return 3 * 2;

| w = 3 |

| n = 3 |

|factorial(3) |

|=======================|

| +-|---> текущий оператор z = factorial(3);

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

--------+ +--------

|=======================|

| +-|---> текущий оператор z = 6;

| z = мусор |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

--------+ +--------

|=======================|

| z = 6 |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

---------------------------------------------------------------------------

 

Наконец, в точке /* C */ будет вызвана функция func().

Рассмотрим точку /* #c */ в ней.

 

--------+ +--------

|=======================|

| x = 777; |

|func(); |

|=======================|

| +-|---> текущий оператор func();

| z = 6 |

| y = 12 | +------+---------+

|main() | |x = 7 | v = 333 |

+-----------------------+-----------+------+---------+-----

СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ

 

В данном месте нас интересует - какие переменные видимы?

Видимы:

func::x = 777

::v = 333

 

И все.

::x заслонен локальной переменной.

main::y, main::z невидимы, так как находятся

не на вершине стека вызовов функций

---------------------------------------------------------------------------

 

Многие функции более естественно выражаются через рекурсию.

Хотя, часто это приводит к излишним вычислениям по сравнению с итерациями

(то есть циклами). Вот пример - числа Фибоначчи.

 

int fibonacci(int n){

if(n==1 || n==2) return 1;

 

/* else */

 

return fibonacci(n-1) + fibonacci(n-2);

}

void main(){

printf("20ое число Фибоначчи равно %d\n", fibonacci(20));

}

 

Поскольку тут отсутствует массив для запоминания промежуточных

результатов, то этот массив на самом деле неявно моделируется

в виде локальных переменных внутри стека вызовов функций.

Однако этот способ плох - в нем слишком много повторяющихся

действий. Добавим оператор печати - и посчитаем, сколько раз

была вызвана fibonacci(1)?

 

int called = 0;

 

int fibonacci(int n){

if(n==1){

called++;

return 1;

 

} else if(n==2)

return 1;

 

return fibonacci(n-1) + fibonacci(n-2);

}

void main(){

printf("20ое число Фибоначчи равно %d\n", fibonacci(20));

printf("fibonacci(1) была вызвана %d раз\n", called);

}

 

Она была вызвана... 2584 раза!

14.c

 

/* Рисуем хитрую геометрическую фигуру */

#include

 

const int LINES = 15;

 

void draw(int nspaces, int nstars, char symbol){

int i;

 

for(i=0; i < nspaces; i++)

putchar(' ');

for(i=0; i < nstars; i++)

putchar(symbol);

}

 

void main(){

int nline, nsym;

char symbols[3]; /* Массив из трех букв */

 

symbols[0] = '\\';

symbols[1] = 'o';

symbols[2] = '*';

 

for(nline=0; nline < LINES; nline++){

for(nsym = 0; nsym < 3; nsym++)

draw(nline, nline, symbols[nsym]);

 

/* Переход на новую строку вынесен

из функции в главный цикл */

putchar('\n');

}

}

15.c

 

/* Задача:

нарисовать таблицу вида

 

кот кот кот кошка кошка кот

кот кот кошка кошка кот...

 

Где идет последовательность

кот, кот, кот, кошка, кошка...

повторяющаяся много раз и располагаемая по 6 зверей в строку.

*/

 

#include /* магическая строка */

 

/* Объявление глобальных переменных.

В данном случае - констант.

*/

 

int TOMCATS = 3; /* три кота */

int CATS = 2; /* две кошки */

int ANIMALS_PER_LINE = 6; /* шесть зверей в каждой строке */

int LINES = 25; /* число выводимых строк */

 

/* и нам понадобится еще одна переменная - общее число зверей.

Ее мы вычислим через уже заданные, поэтому тут мы ее объявим...

но вычислить что-либо можно только внутри функции.

В нашем случае - в функции main().

*/

int ANIMALS; /* общее число зверей */

 

int nth_in_line = 0; /* номер зверя в текущей строке */

/* Эта переменная не может быть локальной в функции, так как

* тогда она уничтожится при выходе из функции. Нам же необходимо,

* чтобы ее значение сохранялось. Поэтому переменная - глобальная.

*/

 

/* Функция, которая считает число зверей в одной строке

и либо переводит строку, либо переводит печать в

следующую колонку (табуляцией).

*/

void checkIfWeHaveToBreakLine(){

nth_in_line++; /* текущий номер зверя в строке (с единицы) */

 

if(nth_in_line == ANIMALS_PER_LINE){

/* Если строка заполнена зверьми... */

putchar('\n'); /* новая строка */

nth_in_line = 0; /* в новой строке нет зверей */

} else {

putchar('\t'); /* в следующую колонку */

}

}

 

void main(){

int nanimal; /* номер зверя */

int i; /* счетчик */

 

ANIMALS = ANIMALS_PER_LINE * LINES;

nanimal = 0;

 

while(nanimal < ANIMALS){

 

for(i=0; i < TOMCATS; i++){

/* Оператор printf() выводит СТРОКУ СИМВОЛОВ.

СТРОКА заключается в двойные кавычки

(не путать с одиночными для putchar().

*/

printf("кот");

nanimal++; /* посчитать еще одного зверя */

 

/* и проверить - не надо ли перейти на новую строку? */

checkIfWeHaveToBreakLine();

}

for(i=0; i < CATS; i++){

printf("кошка");

nanimal++; /* посчитать еще одного зверя */

 

/* и проверить - не надо ли перейти на новую строку? */

checkIfWeHaveToBreakLine();

}

}

/* putchar('\n'); */

}

16.c

 

/*

Та же задача, но еще надо печатать номер каждого зверя.

Ограничимся пятью строками.

*/

 

#include /* магическая строка */

 

int TOMCATS = 3; /* три кота */

int CATS = 2; /* две кошки */

int ANIMALS_PER_LINE = 6; /* шесть зверей в каждой строке */

int LINES = 5; /* число выводимых строк */

int ANIMALS; /* общее число зверей */

 

int nth_in_line = 0; /* номер зверя в текущей строке */

 

void checkIfWeHaveToBreakLine(){

nth_in_line++;

 

if(nth_in_line == ANIMALS_PER_LINE){

putchar('\n');

nth_in_line = 0;

} else

printf("\t\t"); /* @ */

 

/* Одинокий оператор может обойтись без {...} вокруг него */

}

 

void main(){

int nanimal;

int i;

 

ANIMALS = ANIMALS_PER_LINE * LINES;

nanimal = 0;

 

while(nanimal < ANIMALS){

 

for(i=0; i < TOMCATS; i++){

/* Формат %d выводит значение переменной типа int

в виде текстовой строки.

Сама переменная должна быть в списке после формата

(список - это перечисление переменных через запятую).

Переменных ИЛИ выражений (формул).

 

Давайте выводить по ДВЕ табуляции --

это место отмечено в функции checkIfWeHaveToBreakLine()

как @.

 

Еще раз внимание - один символ мы выводим как

putchar('a');

Несколько символов - как

printf("abcdef");

 

Одиночные кавычки - для одной буквы.

Двойные кавычки - для нескольких.

*/

 

printf("кот%d", nanimal);

nanimal++;

 

checkIfWeHaveToBreakLine();

}

for(i=0; i < CATS; i++){

printf("кошка%d", nanimal);

nanimal++;

 

checkIfWeHaveToBreakLine();

}

}

}

17.c

 

/* Задача: напечатать корни из чисел от 1 до 100.

 

Новая информация:

Нам понадобится новый тип данных - ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА.

Это числа, имеющие дробную часть (после точки).

Как мы уже знаем, целые - это int.

буква - это char.

действительное число - это double.

(есть еще слово float, но им пользоваться не рекомендуется).

 

Для вычисления корня используется итерационный алгоритм Герона.

 

q = корень из x;

 

q[0]:= x;

q[n+1]:= 1/2 * (q[n] + x/q[n]);

 

Главное тут не впасть в ошибку, не клюнуть на q[n] и не

завести массив. Нам не нужны результаты каждой итерации,

нам нужен только конечный ответ. Поэтому нам будет вполне

достаточно ОДНОЙ, но изменяющейся в цикле, ячейки q.

*/

 

#include

 

/* Еще одно новое ключевое слово - const. Обозначает константы.

В отличие от переменных, такие имена нельзя изменять.

То есть, если где-то потом попробовать написать epsilon =...;

то это будет ошибкой.

*/

const double epsilon = 0.0000001; /* точность вычислений */

 

/* Функция вычисления модуля числа */

double doubleabs(double x){

if(x < 0) return -x;

else return x;

}

 

/* Функция вычисления квадратного корня */

double sqrt(double x){

 

double sq = x;

 

/* Такая конструкция есть просто склейка двух строк:

double sq;

sq = x;

Называется это "объявление переменной с инициализацией".

*/

 

while(doubleabs(sq*sq - x) >= epsilon){

sq = 0.5 * (sq + x/sq);

}

return sq;

}

 

void main() {

int n;

 

for(n=1; n <= 100; n++)

printf("sqrt(%d)=%lf\n",

n, sqrt((double) n)

);

 

}

 

/*

Здесь в операторе printf() мы печатаем ДВА выражения.

ФОРМАТ ЗНАЧЕНИЕ

------ --------

%d -- n

%lf -- sqrt((double) n)

 

По формату %d печатаются значения типа int.

По формату %c печатаются значения типа char.

По формату %lf (и