Описание алгоритма: Будем наращивать длину последовательности от 0 знаков до N. Пусть после какого-то количества шагов у нас выписаны все последовательности длины А и мы хотим узнать количество подходящих последовательностей длины А+1. Распределим все последовательности на три группы(так как предыдущие символы нас не волнуют, то любые последовательности одной группы для нас равнозначны): 1) Заканчиваются на 0. 2) Ровно на одну единицу 3) Ровно на две единицы. Из каждой последовательности группы 1 приписыванием нуля или единицы мы можем получить одну последовательность группы 1 и одну - группы 2. Неважно, какие именно, но они не перекрываются, т.к. предыдущие символы различны, хоть мы их и не учитываем. Точно так же из второй группы мы получаем одну последовательность группы 3 и одну группы 1, а из группы 3 - только группу 1. Таким образом, если количества последовательностей длины А по группам были (x, y, z), то для длины А+1 такое распределение будет (x+y+z, x, y). Если взять для длины 0 тройку (0, 0, 1) и просчитать тройки от 1 до N, получится искомое количество. Для N=1 и N=2 также работает правильно. Программа на Pascal:
var num00,num01,num11,mem00:integer; n,i:byte; begin readln(n); num00:=1; for i:=1 to n do begin mem00:=num11; num11:=num01; num01:=num00; num00:=num01+num11+mem00; end; writeln(num11+num01+num00); end.
Переменные в программе дают возможность обращаться к областям в памяти компьютера с удобных имен - это упрощает написание, отладку и модификацию программы. Получив описание переменной, современный транслятор (непринципиально, будет это компилятор или интерпретирующая программа) должен отвести под эту переменную область памяти, достаточную для размещения в ней данных и впоследствии учитывать тип переменной, делая, при необходимости, неявные преобразования типа. Ранние языки программирования не допускали неявных преобразований, т.е. преобразований, которые выполняются без участия программиста. Пример таких языков - Fortran II. В этом языке нельзя было смешивать в одном операторе переменные разных типов. Кстати, о типе переменных. Существуют разные классификации, но для понимания самой концепции типов непринципиально, какой классификацией пользоваться. Если говорить упрощенно, можно различать числовые и нечисловые данные. С числовыми можно совершать математические операции, а нечисловые можно только вводить в компьютер (например, с клавиатуры) и выводить из компьютера во внешнюю среду (например, отображать на мониторе). И вот тут самое интересное. Перед тем, как компьютер получит числовое данное, оно должно быть введено в форме нечислового. Тут-то и возникает неявное преобразование типов. Когда мы, к примеру, вводим число 25, то нажимаем клавиши "2" и "5", посылая компьютеру определенные коды. Компьютер преобразует их и получает последовательность символов "25". Это то же, что число 25? Если мы пишем 25 на бумаге, то для нас оно хоть число, хоть текст, изображающий число. А для компьютера это не так. Его система команд обрабатывает символы отдельно, числа отдельно. И хранит компьютер число 25 и символы "25" совсем по-разному. Вот поэтому мы должны описывая переменные, сообщать не только их имена, но и тип - чтобы транслятор "понял", как эти данные ему обрабатывать. Даже числовые данные неоднородны - компьютер может хранить их с разным представлением (целые, с фиксированной точкой, с плавающей точкой) и с разной разрядностью (максимальным числом цифр). И, встретив в операции два числа разного типа, транслятор должен привести их к одному - это тоже случай неявного приведения типов. Например, оно возникнет при вычислении выражения 2.5+1, потому что первое значение дробное, а второе - целое. Транслятор приведет его к 2.5+1.0.
Описание переменной должно быть сделано до её первого использования в программе. Обычно стараются вынести все описания в начало программы - при изучении текста чужой программы так легче найти нужное описание. Это характерно для "классических" языков программирования типа Pascal. Описание переменных в этом языке делается в разделе, который начинается ключевым словом var (от английского слова variable - переменная). Альтернативой является описание в месте, непосредственно предшествующем первому использованию переменной - это облегчает первичное написание программы, когда заранее сложно сказать, какие переменные понадобятся - особенно этим любят пользоваться программисты на языках С/С++, хотя и в этом языке есть возможность описать переменные в начале программы.
Примеры описания одних и тех же переменных: a) Pascal var a:integer; b1, b134, delta: real; weight: array[1..n] of integer;
б) С/С++ int a; single b1, b134, delta; int weight[n+1];
в) BASIC DIM a AS INTEGER DIM b1 AS REAL, b134 AS REAL, delta AS REAL DIM weight(1 To N) AS INTEGER
Будем наращивать длину последовательности от 0 знаков до N. Пусть после какого-то количества шагов у нас выписаны все последовательности длины А и мы хотим узнать количество подходящих последовательностей длины А+1. Распределим все последовательности на три группы(так как предыдущие символы нас не волнуют, то любые последовательности одной группы для нас равнозначны):
1) Заканчиваются на 0.
2) Ровно на одну единицу
3) Ровно на две единицы.
Из каждой последовательности группы 1 приписыванием нуля или единицы мы можем получить одну последовательность группы 1 и одну - группы 2. Неважно, какие именно, но они не перекрываются, т.к. предыдущие символы различны, хоть мы их и не учитываем. Точно так же из второй группы мы получаем одну последовательность группы 3 и одну группы 1, а из группы 3 - только группу 1. Таким образом, если количества последовательностей длины А по группам были (x, y, z), то для длины А+1 такое распределение будет (x+y+z, x, y). Если взять для длины 0 тройку (0, 0, 1) и просчитать тройки от 1 до N, получится искомое количество. Для N=1 и N=2 также работает правильно.
Программа на Pascal:
var num00,num01,num11,mem00:integer;
n,i:byte;
begin
readln(n);
num00:=1;
for i:=1 to n do begin
mem00:=num11;
num11:=num01;
num01:=num00;
num00:=num01+num11+mem00;
end;
writeln(num11+num01+num00);
end.
Кстати, о типе переменных. Существуют разные классификации, но для понимания самой концепции типов непринципиально, какой классификацией пользоваться.
Если говорить упрощенно, можно различать числовые и нечисловые данные. С числовыми можно совершать математические операции, а нечисловые можно только вводить в компьютер (например, с клавиатуры) и выводить из компьютера во внешнюю среду (например, отображать на мониторе). И вот тут самое интересное. Перед тем, как компьютер получит числовое данное, оно должно быть введено в форме нечислового. Тут-то и возникает неявное преобразование типов. Когда мы, к примеру, вводим число 25, то нажимаем клавиши "2" и "5", посылая компьютеру определенные коды. Компьютер преобразует их и получает последовательность символов "25". Это то же, что число 25? Если мы пишем 25 на бумаге, то для нас оно хоть число, хоть текст, изображающий число. А для компьютера это не так. Его система команд обрабатывает символы отдельно, числа отдельно. И хранит компьютер число 25 и символы "25" совсем по-разному. Вот поэтому мы должны описывая переменные, сообщать не только их имена, но и тип - чтобы транслятор "понял", как эти данные ему обрабатывать. Даже числовые данные неоднородны - компьютер может хранить их с разным представлением (целые, с фиксированной точкой, с плавающей точкой) и с разной разрядностью (максимальным числом цифр). И, встретив в операции два числа разного типа, транслятор должен привести их к одному - это тоже случай неявного приведения типов. Например, оно возникнет при вычислении выражения 2.5+1, потому что первое значение дробное, а второе - целое. Транслятор приведет его к 2.5+1.0.
Описание переменной должно быть сделано до её первого использования в программе. Обычно стараются вынести все описания в начало программы - при изучении текста чужой программы так легче найти нужное описание. Это характерно для "классических" языков программирования типа Pascal.
Описание переменных в этом языке делается в разделе, который начинается ключевым словом var (от английского слова variable - переменная).
Альтернативой является описание в месте, непосредственно предшествующем первому использованию переменной - это облегчает первичное написание программы, когда заранее сложно сказать, какие переменные понадобятся - особенно этим любят пользоваться программисты на языках С/С++, хотя и в этом языке есть возможность описать переменные в начале программы.
Примеры описания одних и тех же переменных:
a) Pascal
var
a:integer;
b1, b134, delta: real;
weight: array[1..n] of integer;
б) С/С++
int a;
single b1, b134, delta;
int weight[n+1];
в) BASIC
DIM a AS INTEGER
DIM b1 AS REAL, b134 AS REAL, delta AS REAL
DIM weight(1 To N) AS INTEGER