СВЯЗЬ МАССИВОВ И ЦИКЛОВ
======================= Вследствие этого массивы приходится копировать (и инициализировать) поэлементно, в цикле перебирая все (или часть) ячейки массива.
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 (и
|