Числа Фибоначчи. Класс string. 

Михаил Медведев

[к списку лекций]

1. Числа Фибоначчи. Рекурсивный и циклический методы вычисления. Рекурсивный метод вычисления с запоминанием. Формула Бине. Свойства чисел Фибоначчи.

2. Класс string. Обработка строк с помощью класса string: инициализация, конкатенация, ввод-вывод, вставка, удаление, поиск. Обработка подстрок. Потоковое чтение из строки.

3. Задачи

http://acm.uva.es/problemset: 495 (Замораживание Фибоначчи), 900 (Кирпичная стена), 10450 (Шум мирового кубка), 11000 (Пчела).

http://www.topcoder.com/tc: SRM 178 (Простой калькулятор), SRM 210 (Заглавная строка), SRM 246 (Склеивание), SRM 257 (Код замены), SRM 305 (Мультичтение).

1. ЧИСЛА ФИБОНАЧЧИ

В XIII веке итальянский математик Леонардо Фибоначчи исследовал решение следующей задачи:

Фермер выращивает кроликов. Когда кролик становится взрослым (ему исполняется два месяца), то каждый месяц он дает потомство в одного кролика. Сколько кроликов будет у фермера через n месяцев, если сначала у него был только один (считается, что кролики не умирают и дают потомство по выше описанной схеме)?

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

Количество кроликов в n - ый месяц будет равно количеству кроликов, которое было в n – 1 месяце, плюс количество родившихся. Последних будет столько, сколько кроликов дают потомство (которым уже исполнилось 2 месяца). Их число равно количеству кроликов в n – 2 месяц.

Если через F_n обозначить количество кроликов после n - го месяца, то имеет местоследующее рекуррентное соотношение:

F_n =  F_n-1 + F_n-2, F₁ = F₂ = 1

Положим F₀ = 0, при этом соотношение при n = 2 останется истиным. Таким образом образовалась последовательность

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... ,

которая называеться последовательностью Фибоначчи.

Рассмотрим несколько функций f(n) вычисляения n - го числа Фибоначчи. Для нахождения f(n) с линейной сложностью без запоминания значений f(1), f(2), …, f(n – 1) можно использовать циклический вариант:

int f(int n)

{

  int i,temp,a=0,b=1;

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

    temp=a,a=b,b=temp+a;

  return a;

}

Максимальным числом Фибоначчи, которое помещается в тип int, является F₄₆ = 1836311903. В 64-битовый целочисленный тип long long (__int64) помещается максимум F₉₂. Если в задаче требуется находить значения f(n) для n > 92, то следует воспользоваться длинной арифметикой.

В случае необходимости запоминания всех чисел Фибоначчи f(1), f(2), …, f(n), заведем массив m, в котором положим m[i] = f(i), 0 £ i £ n. Реализация может быть как циклическая, так и рекурсивная с запоминанием:

При вычислении чисел Фибоначчи F_n для больших аргументов (n > 92) следует воспользоваться классом BigInteger:

BigInteger f(int n)

{

  BigInteger a(0),b(1),temp(0);

  for(int i=0;i<n;i++)

    temp = a,a = b,b = temp + a;

  return a;

}

Формула Бине выражает в явном виде значение F_n как функцию от n:

F_n =  = ,

где j =  – золотое сечение. При этом j и  (-j)^-1 = 1 – j являются корнями квадратного уравнения x² – x – 1 = 0.

Следствие. Для всех n ³ 0 имеет место равенство: F_n = .

Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть

НОД(F_n, F_m) = F_НОД(n,m)

Следствие 1. F_m делится на F_n тогда и только тогда, когда m делится на n (за исключением n = 2).

Следствие 2. F_n может быть простым только для простых n (за исключением n = 4).

Упражнение 1.1. Свойства чисел Фибоначчи. Доказать следующие свойства:

а) F₀ + F₁ + F₂ + F₃ + … +  F_n = F_n+2 – 1;

б) F₁ + F₃ + F₅ + … +  F_2n-1 = F_2n;

в) F₀ - F₁ + F₂ - F₃ + … - F_2n-1 +  F_2n = F_2n-1 – 1;

г) F₀² + F₁² + F₂² + F₃² + … +  F_n² = F_n * F_n+1;

д) F_n+1F_n-1 – F_n² = (-1)ⁿ (Равенство Ж. Д. Кассини);

е) F_n+m = F_m F_n+1 + F_m-1 F_n;

Упражнение 1.2. Лестница. Необходимо пройти по лестнице, состоящей из n ступенек. Из очередной ступеньки можно перейти или на следующую ступеньку, или перешагнуть через одну. Сколько существует вариантов прохождения лестницы?

Упражнение 1.3. Кирпичная стена [Вальядолид, 900]. Высота кирпича равна 2, ширина – 1. Необходимо построить стену высоты 2 и длиной n. Сколькими способами можно это сделать в зависимости от значения n?

Упражнение 1.4. Путь пчелы. Пчела начинает свой путь с клетки 1 или 2 и направляется в клетку с номером n. Двигаться пчеле можно только по соседним клеткам от меньшего номера к большему. Сколькими разными путями пчела может попасть в клетку с номером n?

Упражнение 1.5. Новости по телефону. n друзей проживают в разных городах и разговаривают между собой только по телефону. Один телефонный звонок всегда длится одну минуту. Один из друзей желает поделиться новостью со всеми друзьями за наименьшее время. Найти наименьшее время, за которое все друзья будут знать новость, если каждый может совершить не более 2 звонков.

Упражнение 1.6. Резисторы. n одинаковых резисторов, с сопротивлением 1 Ом каждый, соединили как показано на рисунке (к первому резистору подсоединены резисторы с нечетными номерами последовательно, а с четными – параллельно). Найти сопротивленние всей системы из n резисторов.

                                                  n = 1    n = 2      n = 3      n = 4      n = 5      n = 6

Упражнение 1.7. Замораживание Фибоначчи [Вальядолид, 495]. Последовательность чисел Фибоначчи (0, 1, 1, 2, 3, 5, 8, 13, 21, ....) определяется рекуррентным соотношением:

f₀ = 0, f₁ = 1,

f_i = f_i-1 + f_i-2, i ³ 2

Следует написать программу, которая вычисляет числа Фибоначчи.

Вход. Каждая строка содержит целое неотрицательное число n (n £ 5000).

Выход. Для каждого входного n вывести n - ое число Фибоначчи в соответствии с ниже приведенным форматом.

Упражнение 1.8. Шум мирового кубка  [Вальядолид, 10450]. По заданному числу n вычислить количество последовательностей из 0 и 1 длины n, в которых две единицы не стоят рядом.

Вход. Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит число n (0 < n < 51).

Выход. Для каждого теста вывести его номер и количество последовательностей из 0 и 1 длины n, в которых две единицы не стоят рядом.

Упражнение 1.9. Пчела [Вальядолид, 11000]. В Африке живет специальный вид пчел. Каждый год самка производит на свет одого самца, а самец – самца и самку, после чего родители погибают. Ученые изобрели магическую самку пчелу, которая плодится как обыкновенная самка, но при этом является бессмертной. Необходимо вычислить число самцов и общее количество пчел в семействе, если изначально была лишь одна магическая самка пчела.

Вход. Каждая строка содержит целое n (n ³ 0).Последний тест содержит n = -1 и не обрабатывается.

Выход. Для каждого значения n вывести число самцов и общее количество пчел в семействе через n лет. Выводимые числа не более 2³².

Упражнение 1.10. Флаги [Тимус 1225]. Флаг состоит из n вертикальных полос белого, красного и синего цвета. Соседние полосы не могут иметь одинаковый цвет, а синяя полоса всегда должна находиться между красной и белой. Сколькими способами можно покрасить флаг из n полос?

Вход. Число полос n (1 £ n £ 45) на флаге.

Выход. Количество способов, которыми можно покрасить флаг из n полос.

2. ОБРАБОТКА СТРОК С ПОМОЩЬЮ КЛАССА STRING

Строкой называется последовательность символов, оканчивающаяся нуль-байтом. Для работы со строками (типом string) следует подключить библиотеку <string>:

#include <string>

using namespace std;

Конструкторы. Создание строки производится одним из следующих конструкторов:

string a;          // Создание пустой строки

string b("Hello"); // Создание строки с инициализацией данными

string c(10,'a');  // Создание строки, состоящей из 10 букв ‘a’

string d = b;            // Создается строка d и в нее копируется одержимое строки b

string e(b,1,2);   // В создавемую строку e копируются 2 символа строки b,

                   //  начиная с позиции 1. Значение созданой строки e равно “el”

Конкатенация. Опрерация ‘+’ используется для объединения (конкатенации) строк:

string a(“This”); string b(“cat”);

string c = a+b;   // Значение c равно “Thiscat”

Итераторы. Итератор string::begin() указывает на начало, a string::end() на конец строки.

string a("ABCDEFGH");

string b(a.begin()+1,a.end()-1); // b = “BCDEFG”

Ввод-вывод. При использовании функций библиотеки <cstdio> для ввода-вывода строк следует непосредственно перед операцией переводить их в массив символов. Это совершается функцией c_str(). Вывод строки символов:

string a("Hello");

printf("%s\n",a.c_str());

Ввод строки при помощи функции scanf следует совершать в символьный массив. Далее массив символов можно преобразовать в тип string при помощи конструктора

char s[100];

string a;

scanf("%s",s); a = string(s);

printf("%s\n",a.c_str());

Форматированный ввод из строки осуществляется функцией sscanf. Чтение чисел со строки и вычисление их суммы:

int x,y;

string a("23+4");

sscanf(a.c_str(),"%d+%d",&x,&y);

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

Нумерация индексов элементов строк начинается с нуля. i - ый символ строки a можно получить операцией индексирования a[i] или выполнением функции at(i):

string a("This is a hat");

printf("Second letter is %c or %c\n",a[1],a.at(1));

Размер строки a равен a.size(). Посимвольный вывод строки a:

string a("This is a hat");

for(i=0;i<a.size();i++) printf("%c",a[i]);

Подстроки. Если a – переменная типа string, то a.substr(pos, l) является подстрокой, начинающейся с позиции pos и имеющей длину l. Если второй аргумент отсутствует, то выделяется подстрока с позиции pos до коца строки.

string a("This is a hat");

string b = a.substr(2,4);                  // b = “is i”

string c = a.substr(3);                    // c = “s is a hat”

printf("%s\n%s\n",b.c_str(),c.c_str());

Функция is_prefix возвращает 1, если строка a является префиксом строки b.

int is_prefix(string a, string b)

{

  return b.substr(0,a.size()) == a;

}

Поиск. Если a и b – переменные типа string, то то a.find(b) возвращает первую позицию вхождения строки b в строку a. Если b не является подстрокой a, то метод find возвращает -1.

string a = "qwertwqy";

string b = "qw";

int pos = a.find(b);                 // pos = 0

Используя метод find, функцию is_prefix можно переписать так:

int is_prefix(string a, string b)

{

  return (b.find(a) == 0);

}

Поиск в строке s подстроки b, начинающейся не раньше i - ой позиции, следует при помощи метода find(b, i) класса string:

string s = "abcdabcabc";

int pos = s.find("ab",1);            // pos = 4

Удаление подстрок. Если t является подстрокой s, то находим позицию i, с которой она начинается и удаляем при помощи метода erase.

string s = "Hello thisis world";

string t = "this";

int i = s.find(t);

s.erase(i,t.size());                 // s = "Hello is world"

Удаление всех вхождений строк t в качестве подстрок в строку s можно совершить в цикле:

string s = "thisHello thisis world this isthis";

string t = "this";

while((i = s.find(t)) >= 0)

  s.erase(i,t.size());               // s = "Hello is world  is"

Разбиение. Разбиение строки s на несколько подстрок при помощи разделителя c совершается при помощи функции split. Разделитель c может встречаться в строке в любом месте и в любом количестве.

vector<string> split(string s,char c)

{

  vector<string> res;

  int i=0,j = s.find(c);

  while(j >= 0)

  {

    if (s[i] != c) res.push_back(s.substr(i,j-i));

    i = ++j;

    j = s.find(c,j);

  }

  res.push_back(s.substr(i));

  return res;

}

Вызов функции и вывод результата:

string s = "  g  this     is a test    9";

vector<string> v = split(s,' ');

for(i=0;i<v.size();i++) printf("%s ",v[i].c_str());

Замена. Пример замены всех вхождений пробелов в строке v на точку:

string s = "This is a text";

replace(s.begin(),s.end(),' ','.');  // s = "This.is.a.text"

Обращение. Обращение строки можно совершить при помощи функции reverse, объявленной в <algorithm>:

s = "This";

reverse(s.begin(),s.end());         // s = “sihT”

Потоковое чтение из строки. Занесение чисел, содержащихся в строке s, в массив m, можно совершить при помощи потокового вывода:

#include <cstdio>

#include <cstring>

#include <sstream>

using namespace std;

void main(void)

{

  string s = "2   34  55 9 111";

  int m[10],ptr=0,i,a;

  stringstream in(s);

  while (in >> a) m[ptr++] = a;

  for(i=0;i<ptr;i++) printf("%d ",m[i]); printf("\n");

}

Упражнение 2.1. Простой калькулятор [Топкодер, раунд 178, дивизион 2, уровень 1]. Калькулятор умеет вычислять четыре арифметических действия и имеет один из следующих входных форматов: <num> + <num>, <num> – <num>, <num> * <num> или  <num> / <num>, где <num> – натуральное число, которое может содержать ведущие нули. Операция деления является целочисленной. В задаче требуется найти значение заданного арифметического выражения.

Класс: SimpleCalculator

Метод: int calculate(string input)

Ограничения: 1 £ <num> £ 1000.

Вход. Строка input, содержащая одно из арифметических выражений.

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

Пример входа

Пример выхода

1

45

-9999

35

Упражнение 2.2. Заглавная строка [Топкодер, раунд 210, дивизион 2, уровень 1]. В заданной строке необходимо заменить все первые буквы слов на заглавные. Слова в строке разделены пробелами.

Класс: TitleString

Метод: string toFirstUpperCase(string title)

Ограничения: строка title содержит от 0 до 50 символов, строка title содержит символы ‘a’ – ‘z’ и пробелы.

Вход. Строка title.

Выход. Строка title, в которой все первые буквы слов заменены на заглавные.

Пример входа

Пример выхода

Introduction To Algorithms

More Than  One   Space    Between     Words

The King And I

Упражнение 2.3. Склеивание [Топкодер, раунд 246, дивизион 2, уровень 1]. Задана строка conglutination, состоящая из цифр, и целое число expectation. Можно ли строку разбить на два числа A и B так, чтобы A + B = expectation?

Класс: Conglutination

Метод: String split(String conglutination, int expectation)

Ограничения: conglutination содержит от 2 до 20 цифр, первая цифра не 0, 1 £ expectation £ 1000000000.

Вход. Строка цифр conglutination и ожидаемое значение суммы expectation.

Выход. Если строку conglutination невозможно разбить на части, сумма чисел в которых равна expectation, то вывести пустую строку. Иначе вывести строку в виде “A+B”.

Пример входа

Пример выхода

“2+2”

“5+36”

“1234560+00789”

“”

Упражнение 2.4. Код замены [Топкодер, раунд 257, дивизион 2, уровень 1]. В задаче следует декодировать строку символов code. Каждая цифра закодирована буквой. Ключом является строка key из 10 букв. Цифра ‘1’ соответствует первой букве ключа key, цифра ‘2’ – второй букве и так далее. Цифра ‘0’ соответствует последней букве. Буквы закодированной строки code, которые не встречаются в ключе key, игнорируются.

Класс: SubstitutionCode

Метод: int getValue(String key, String code)

Ограничения: code содержит от 1 до 9 символов ‘A’ – ‘Z’, key содержит в точности 10 разных символов, code содержит хотя бы один символ, содержащийся в key.

Вход. Две строки символов key и code.

Выход. Декодированная строка.

Пример входа

Пример выхода

709

0

6

Упражнение 2.5. Мультичтение [Топкодер, раунд 305, дивизион 2, уровень 1]. В компьютерных системах несколько процессов могут одновременно читать данные, но только один процесс может выполнять операцию записи в течении одного такта времени. Строка trace содержит историю работы системы и состоит из символов ‘R’ (чтение) и ‘W’ (запись). Вычислить минимальное время, за которое могут быть произведены все операции procs процессами.

Класс: MultiRead

Метод: int minCycles(string trace, int procs)

Ограничения: trace содержит от 1 до 50 символов ‘R’ и ‘W’, 1 £ procs £ 10.

Вход. Строка trace и число procs.

Выход. Количество тактов времени, за которое может быть выполнена последовательность операций чтения/записи, заданная строкой trace, procs процессами.

Пример входа

Пример выхода

4

5

3

УКАЗАНИЯ К РЕШЕНИЮ УПРАЖНЕНИЙ

Упражнение 1.1. Свойства чисел Фибоначчи.

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

а) База. n = 0. F₀ = F₂ – 1, что верно.

    Шаг. F₁ + F₂ + F₃ + … +  F_n =  (F₁ + F₂ + F₃ + … +  F_n-1) + F_n =

                           F_n+1 – 1 + F_n = F_n+2 – 1.

б) База. n = 1. F₁ = F₂, что верно.

    Шаг. F₁ + F₃ + F₅ + … +  F_2n+1 = (F₁ + F₃ + F₅ + … +  F_2n-1) + F_2n+1 =

 F_2n + F_2n+1 = F_2n+2.

в) База. n = 1. F₀ – F₁ + F₂ = 0 – 1 + 1 = 0, F₁ – 1  = 1 – 1 = 0.

    Шаг. (F₀ – F₁ + F₂ – F₃ + … – F_2n-1 +  F_2n) – F_2n+1 +  F_2n+2 =

F_2n-1 – 1 – F_2n+1 +  F_2n+2 = F_2n-1 - 1 – F_2n+1 +  F_2n + F_2n+1 =

F_2n-1 +  F_2n – 1 = F_2n+1 – 1.

г) База. n = 0. F₀² = F₀ * F₁, что верно.

    Шаг. F₀² + F₁² +  … +  F_n+1² =  (F₀² + F₁² +  … +  F_n²) +  F_n+1² =

 F_n * F_n+1 + F_n+1² = F_n+1 * (F_n + F_n+1) = F_n+1 * F_n+2.

д) Равенство получается из матричного тождества  =  после вычисления определителей.

е) Индукция по m. База. m = 1. F_n+1 = F₁F_n+1 + F₀F_n =   1 * F_n+1 + 0 * F_n = F_n+1, что верно.

    Шаг. F_n+m+1 = F_n+m +  F_n+m-1 = F_m F_n+1 + F_m-1F_n + F_m-1 F_n+1 + F_m-2F_n =

 (F_m + F_m-1) F_n+1 + (F_m-1 + F_m-2) F_n = F_m+1 F_n+1 + F_m F_n.

Упражнение 1.2. Лестница. Пусть f(n) – количество вариантов, которыми можно пройти по n ступенькам. С n - ой ступеньки можно перейти или на (n – 1) - ую, или на (n – 2) - ую. Количество вариантов пройти n ступенек равно количеству вариантов пройти n – 1 ступенек плюс количество вариантов пройти n – 2 ступеньки, тоесть f(n) = f(n – 1) + f(n – 2). Очевидно, что f(1) = 1 и f(2) = 2. Таким образом f(n) является (n + 1) - ым числом Фибоначчи.

Упражнение 1.3. Кирпичная стена [Вальядолид, 900]. Обозначим через f(n) количество способов, которыми можно построить кирпичную стену высоты 2 и длины n. Тогда можно положить один кирпич вертикально и далее строить стену длины n – 1 f(n – 1) способом, или положить два кирпича горизонтально и строить стену длины n – 2 f(n – 2) способами. То есть f(n) = f(n – 1) + f(n – 2). Также имеем: f(1) = 1 (один вертикальный кирпич), f(2) = 2 (два вертикальных или два горизонтальных кирпича). То есть f(n) является (n + 1) - ым числом Фибоначчи.

Упражнение 1.4. Путь пчелы.  Из клетки с номером n пчела может попасть или в клетку с номером n + 1, или с номером n + 2. Задача сводится к движению по ступенькам лестницы. Количество разных путей до клетки с номером n равно F_n.

Упражнение 1.5. Новости по телефону.  Звонки между друзьями следует организовать как показано на рисунке. Тогда на i - ой минуте о новости узнают еще F_i друзей. Наименьшее число минут, за которое новость распространится среди всех друзей, равно такому наименьшему значению k, для которого F₁ + F₂ + … + F_k ³ n (или то же самое что F_k+2 – 1 ³ n), где F₁ = 1 (личность, которая распространяет новость) и F₂ = 1 (друг, которому сделан первый звонок).

                  личность, распространяющая новость

                                    /------------^----\

  первая минута           A                     \   

                                /----^----\                \  

  вторая минута       C           \               B

                             /--^--\          \           /--^--\ 

третья минута    D       \         E        F         \     

                         /--^-\      \     /--^--\   /--^--\     \

                     ...   ...    ... ...    ... ...    ...   ...

Упражнение 1.6. Резисторы. Обозначим через f(n) сопротивление системы из n резисторов. Очевидно, что f(1) = 1, f(2) = 2. Докажем по индукции, что

f(n) =   при четном n  и  f(n) =   при нечетном n.

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

 =  =  =

В случае нечетного количество резисторов соединение со следующим резистором происходит последовательно и результирующее сопротивление равно

 + 1 =  =

Упражнение 1.7. Замораживание Фибоначчи [Вальядолид, 495]. Поскольку n £ 5000, то для нахождения f_n следует воспользоваться классом BigInteger. Найдем и запомним в массиве m все значения f_n (0 £ n £ 5000) и для каждого входного n будем выводить m[n] = f_n.

Реализация. Вычислим все значения f_n (0 £ i £ 5000) и занесем их в массив m[5001]. Поскольку f₅₀₀₀ содержит не более 1100 десятичных знаков, то установим MAXLENGTH = 1100.

#include <stdio.h>

#include <memory.h>

#define MAXLENGTH 1100

class BigInteger{ . . .};

BigInteger m[5001];

void main(void)

{

  int i,n;

Положим m[1] = 1 и воспользуемся рекуррентной формулой m[i] = m[i -1] + m[i - 2].

  m[1] = BigInteger(1);

  for(i=2;i<5001;i++) m[i] = m[i-1] + m[i-2];

Для каждого входного значения n выводим f_n = m[n] в соответствии с требуемым форматом.

  while(scanf("%d",&n) == 1)

  printf("The Fibonacci number for %d is ",n),m[n].print();

}

Упражнение 1.8. Шум мирового кубка  [Вальядолид, 10450]. Обозначим через f(n) количество искомых последовательностей из 0 и 1 длины n. Если на первом месте последовательности будет находиться 0, то начиная со второго места можно построить f(n – 1) последовательностей. Если на первом месте стоит 1, то на втором месте обязательно должен стоять 0, а на последующих n - 2 свободных местах можно построить f(n – 2) последовательностей.

При этом f(1) = 2 (имеем две последовательности длины 2: 0 и 1), f(2) = 3 (последовательности 00, 01, 10). Значения f(n) образуют числа Фибоначчи . Известно, что f₀ = 0, f₁ = 1, f₂ = 1, f_i = f_i-1 + f_i-2. Учитывая начальные условия, получим: f(n) = f_n+2.

Пример. Рассмотрим второй тест. Всего существует 5 последовательностей из 0 и 1 длины 3, в которых две единицы не стоят рядом: 000, 001, 010, 100, 101.

Реализация. В массиве fib вычислим значения f(n): f(n) = fib[n]. Для n > 44 значения f(n) будут выходить за границы типа int, поэтому воспользуемся 64 - битовым целочисленным типом long long (в среде Microsoft Visual Studio C++ – тип __int64).

#include <stdio.h>

int tests,i,n;

long long fib[51];

void main(void)

{

Нахождение значений f(n) совершим в цикле:

  fib[1] = 2; fib[2] = 3;

  for(i=3;i<51;i++) fib[i] = fib[i-1] + fib[i-2];

Читаем количество тестов и для каждого входного n выводим значение fib[n].

  scanf("%d",&tests);

  for(i=1;i<=tests;i++)

  {

    scanf("%d",&n);

    printf("Scenario #%d:\n",i);

    printf("%lld\n\n",fib[n]);

  }

}

Упражнение 1.9. Пчела [Вальядолид, 11000]. Обозначим n - ое число Фибоначчи через f(n). Тогда через n лет число самцов в пчелином семействе будет равно f(n) – 1, а общее число пчел f(n + 1) – 1. Через n = 0 лет семейство состоит из единственной пчелы самки, то есть имеется 0 самцов и 1 пчела. Положим f(0) = 1, f(1) = 2. Далее по индукции докажем справедливость приведенного утверждения. После n + 1 года число самцов равно суммарному числу самок и самцов после n - го года, то есть f(n + 1) – 1. Число самок после n + 1 года равно числу самцов после n - го года плюс одна бессмертная самка, то есть f(n) – 1 + 1 = f(n). Таким образом общее число пчел после n + 1 года равно f(n + 1) – 1 + f(n) = f(n + 2) – 1.

Реализация. Искомые числа Фибоначчи не превосходят 2³². Вычислим их первые 50 значений и занесем в массив f типа long long.

#include <stdio.h>

long long f[50];

void main(void)

{

  int i,n;

Заполним массив f числами Фибоначчи.

  f[0] = 1; f[1] = 2;

  for(i=2;i<50;i++) f[i] = f[i-1] + f[i-2];

Для каждого входного n выведем результат.

  while(scanf("%d",&n),n >= 0)

    printf("%lld %lld\n",f[n]-1,f[n+1]-1);

}

Упражнение 1.10. Флаги [Тимус 1225]. Обозначим через f_red(n) и f_white(n) количество способов раскраски флага из n полос при условии, что первой полосой будет соответственно красная или белая. Тогда

f_red(n) = f_white(n – 1) + f_white(n – 2), f_red(1) = 1, f_red(2) = 1;

f_white(n) = f_red(n – 1) + f_red(n – 2), f_white(1) = 1, f_white(2) = 1.

Если f(n) – искомое общее количество способов раскраски, то

f(n) = f_red(n) + f_white(n)

Поскольку f_red(1) = f_white(1) = 1, f_red(2) = f_white(2) = 1, а f_red(n) и f_white(n) одинаковыми формулами выражаются друг через друга, то f_red(n) = f_white(n) = f_n, где f_n – n-ое число Фибоначчи. Таким образом f(n) = 2 * f_n.

Реализация. В массиве fib вычислим значения f_red(n): f_red(n) = fib[n]. Для n > 44 значения f_red(n) будут выходить за границы типа int, поэтому воспользуемся 64 - битовым целочисленным типом __int64.

__int64 fib[46];

Читаем входное значение n. Нахождение значения fib[n] совершим в цикле:

scanf("%d",&n);

fib[1] = 1; fib[2] = 1;

for(i=3;i<=n;i++) fib[i] = fib[i-1] + fib[i-2];

Выводим результат f(n) = 2* f_red(n) = 2 * fib[n]:

printf("%I64d\n",2*fib[n]);

Упражнение 2.1. Простой калькулятор [Топкодер, раунд 178, дивизион 2, уровень 1]. Следует воспользоваться форматированным чтением данных при помощи функции scanf.

#include <cstdio>

#include <string>

using namespace std;

class SimpleCalculator

{

public:

  int calculate(string input)

  {

    int a,b,res;

    char c;

    sscanf(input.c_str(),"%d%c%d",&a,&c,&b);

    if (c == '+') res = a + b; else

    if (c == '-') res = a - b; else

    if (c == '*') res = a * b; else

    if (c == '/') res = a / b;

    return res;

  }

};

Упражнение 2.2. Заглавная строка [Топкодер, раунд 210, дивизион 2, уровень 1]. Проходим по строке, каждую первую букву слова заменяем на заглавную при помощи функции toupper, объявленной в библиотеке <ctype.h>. Буква title[i] является первой буквой слова, если title[i – 1] = ' ' и title[i] является буквой. При этом следует отдельно обработать случай i = 0.

#include <cstdio>

#include <cctype>

#include <string>

using namespace std;

class TitleString

{

public:

  string toFirstUpperCase(string title)

  {

    for(int i=0;i<title.size();i++)

      if ((!i || title[i-1] == ' ') && isalpha(title[i]))

        title[i] = toupper(title[i]);

    return title;

  }

};

Упражнение 2.3. Склеивание [Топкодер, раунд 246, дивизион 2, уровень 1]. Задача решается полным перебором вариантов разбиения строки на две части. Если размер входной строки равен len = conglutination.size(), то следует перебрать len – 1 разбиений: левая часть строки содержит i цифр, правая len – i  цифр, 1 £ i £ len – 1.

Если a – переменная типа string, то a.substr(pos, l) является подстрокой, начинающейся с позиции pos и имеющей длину l. Если второй аргумент отсутствует, то выделяется подстрока с позиции pos до коца строки.

Функция a.c_str() преобразовывает строку a в массив символов, с которым работают функции ввода-вывода библиотеки <stdio.h>. Чтение форматированных данных из строки совершается функцией sscanf.

Требуемое разбиение строки на два числа не будет найдено, если по окончанию цикла переменная i будет содержать значение len.

#include <cstdio>

#include <string>

using namespace std;

class Conglutination

{

public:

  string split(string conglutination, int expectation)

  {

    string a,b,res="";

    int x,y;

    for(int i = 1; i < conglutination.size(); i++)

    {

      a = conglutination.substr(0,i);

      b = conglutination.substr(i);

      sscanf(a.c_str(),"%d",&x);

      sscanf(b.c_str(),"%d",&y);

      if (x + y == expectation) break;

    }

    if (i < conglutination.size()) res = a + '+' + b;

    return res;

  }

};

Упражнение 2.4. Код замены [Топкодер, раунд 257, дивизион 2, уровень 1]. Для каждой  i - ой буквы из кода code следует найти ее позицию pos в ключе key при помощи метода find класса string. Если буква не найдена, метод возвратит -1. Если соответствующая буква найдена в ключе, то припишем к результату res цифру (pos + 1) % 10.

#include <cstdio>

#include <string>

using namespace std;

class SubstitutionCode

{

public:

  int getValue(string key, string code)

  {

    int i,pos,res=0;

    for(i=0;i<code.size();i++)

    {

      pos = key.find(code[i]);

      if (pos >= 0) res = res*10+(pos+1)%10;

    }

    return res;

  }

};

Упражнение 2.5. Мультичтение [Топкодер, раунд 305, дивизион 2, уровень 1]. Просматриваем строку trace. При встрече операции записи увеличиваем искомое число тактов времени res на 1. Длину каждой группы из операций чтения заносим в переменную с. с операций чтения можно выполнить procs процессами за временных тактов. Заметим, что

 = (c + procs – 1) / procs,

где деление является целочисленным. Добавим это число к переменной res.

#include <cstdio>

#include <string>

using namespace std;

class MultiRead{

public:

  int minCycles(string trace, int procs)

  {

    int res,i,c;

    for(res=i=0;i<trace.size();i++)

      if (trace[i] == 'W') res++; else

      {

        c=0;while((trace[i] == 'R') && (i < trace.size())) {c++;i++;} i--;

        res += (c + procs - 1)/procs;

      }

    return res;

  }

};

[к списку лекций]