Задача 2. Строки (цепочки символов латинских букв) создаются по следующему правилу

Строки (цепочки символов латинских букв) создаются по следующему правилу.

Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка.

Вот первые 4 строки, созданные по этому правилу:

(1) A

(2) BAA

(3) CBAABAA

(4) DCBAABAACBAABAA

Латинский алфавит (для справки):

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).

Решение.

Рассмотрим, какую длину имеют строки с 1 по 7.

1 – 1, 2 – 3, 3 – 7, 4 – 15, 5 – 31, 6 – 63, 7 – 127.

Можно заметить, что это числа на единицу меньше соответствующей степени двойки. Структура восьмой строки такова: новый символ (H), затем 127 символов седьмой строки, затем они же еще раз. Значит, 126-й символ 8-й строки – это 125-й символ 7-й строки, т.е. третий с конца. Все строки заканчиваются одинаково: BAA. Символы со 129 по 132 – это 4 первых символа седьмой строки, т.е. GFED.

Ответ: BAAGFED

Массивы

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

Представьте себе, что мы переехали в новую квартиру. Там нет никакой мебели, а вот вещи мы привезли. Это нужные, полезные вещи. Их много. Очень много! Мы все свалили по углам. А теперь представьте, что нам понадобилась какая-то вещь. Во-первых, мы не знаем, есть ли она среди вещей или, может быть, ее не привезли. Пусть нам сказали, что она где-то здесь. Не так просто ее найти. Вот мы ее нашли! Но теперь надо до нее добраться и вытащить из-под груды других, не менее нужных вещей.

Ситуация меняется, когда все вещи в доме мы правильно структурируем. Для этого нам нужны хранилища, причем разные для разного типа вещей. Шкаф – для одежды, сервант – для посуды, полки – для книг, портфель – для бумаг, кошелек – для денег. Хранилища разные и по назначению, и по размерам, но в каждом из них вещи только одного типа. Теперь можно быстро найти нужную вещь, получить к ней доступ, воспользоваться. Причем важным является и появившаяся способность оперировать с группами вещей. Гораздо удобнее и надежнее пользоваться кошельком, чем рассовывать деньги по карманам.

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

Массив – это именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом. Доступ к элементам массива осуществляется по номеру элемента в массиве. Его называют индексом.

Массивы обеспечивают:

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

быстрый доступ к элементам, поскольку при необходимости, например, обратиться к 10-му элементу массива компьютеру нет необходимости просматривать предыдущие 9 элементов. Происходит просто смещение по памяти на заданное число байт, которое вычисляется по типу элементов массива. С этой точки зрения массивы – это устройства прямого доступа. Это аналогично быстрому перемещению к нужному фрагменту на компакт-диске, в отличие от перемотки пленки на кассете, где наблюдается последовательный доступ.

возможность совершения массовых операций с данными.

В различных языках программирования индекс начального элемента массива может быть разным. В Бейсике массив начинается с первого элемента, в Си – с нулевого, а в Паскале начальный элемент массива может иметь любой номер. При записи на алгоритмическом языке обычно используют либо нумерацию с нуля, либо с единицы. Это поясняется в постановке задачи или становится понятно из контекста.

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

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