Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков

^ Билет № 7 1. Типы данных. Структуры данных. Обработка массивов. Итеративные и рекурсивные методы обработки массивов. Многомерные массивы
Обсуждая билет № 5, мы уже гласили о типах данных, их роли в методе, также о том, что дает Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков компу “познание” типа определенной величины. Мы также гласили, что есть обыкновенные и сложные типы данных. Обыкновенные типы в большинстве случаев употребляются для хранения рабочих величин, но могут быть также аргументами либо плодами Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков в легких методах. Все же для представления данных в реальных задачках способностей обычных данных обычно недостаточно. По правде, в обычном случае о человеке нужно хранить фамилию, имя и отчество (текстовые данные), год рождения (число Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков), пол и семейное положение (одно из значений, избираемых из фиксированного набора), факты наличия либо отсутствия определенных признаков, к примеру, обладания недвижимостью (логические данные) и т.д. В итоге для объединения совокупы всех Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков относящихся к одному реальному объекту данных (компонент) требуется возможность сотворения из их единой сложной структуры.

Примечание. Необходимо отметить, что если к сложному набору данных, состоящему из отдельных компонент (полей), добавить способы их обработки Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков, то получится автономная конструкция еще больше высочайшего уровня — объект (см. билет № 6).

Необходимость в обработке на компьютере сложных видов данных также конкретно вытекает из цикличности большинства используемых на практике алгоритмов. Свойство массовости (см Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков. билет № 4) просит, чтоб метод реализовывался для обработки очень огромного количества данных, а не для какого-то 1-го определенного значения1. Как следует, компьютер в подавляющем большинстве случаев производит неоднократную обработку огромного количества Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков данных по одному и тому же методу (к примеру, просматривает информацию о каждом человеке, отбирая по определенному признаку только тех, кто нужен согласно запросу).
В итоге в языке программирования нужно Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков предугадать средства, которые позволяют компактно представлять программки такового рода обработки: обрисовать деяния над одним из обычных данных, а потом циклически неоднократно повторять эти деяния. Несложно осознать, что над формальной совокупой обычных данных (набором обычных Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков переменных с различными обозначениями) такую функцию выстроить тяжело — для этого лучше подойдет одна величина, спецефическим образом организованная (к примеру, массив).

Как неявно следует из предстоящей формулировки вопроса, в данном билете требуется говорить Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков конкретно о сложных типах данных (в неких языках, схожих Си, подобные конструкции данных принято именовать структурами).

Современные языки программирования позволяют создавать очень различные сложные структуры данных, при этом для этого можно соединять Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков воединыжды как несколько обычных, так и другие сложные данные. Самым всераспространенным сложным типом является массив, соединяющий внутри себя набор данных 1-го типа, к примеру, массив из целых чисел либо массив из логических Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков величин. Кстати, конструкция “массив из массивов” также является полностью допустимой, о чем мы будем гласить несколько позднее.

Для сложного типа в неотклонимом порядке требуется за ранее обрисовать его состав. Это Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков логически понятно, так как для определенной структуры данных составляющие выбирает юзер, и компьютер в принципе не в состоянии предвидеть их набор; как следует, никакое самое дружеское программное обеспечение не в состоянии заавтоматизировать данную операцию. В Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков то же время сложные структуры данных требуют огромных объемов памяти, так что и с этой точки зрения компу требуется заблаговременно знать состав компонент структуры (для рассредотачивания памяти под каждый Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков ее компонент).

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

Массив — это единая структура, составляющие которой Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков имеют один и тот же тип. Воззвание к отдельным элементам массива делается методом указания общего имени массива и определенной инфы, характеризующей позицию требуемого элемента снутри массива. Последняя имеет смысл некой координаты (либо Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков, может быть, нескольких координат) и именуется индексом (индексами). Отсюда видно, что массивы естественным образом делятся по количеству индексов на одномерные (с одним индексом), двумерные и, что допускается в большинстве языков Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков, многомерные массивы (с боRльшим числом индексов). Для удобства изложения начнем рассмотрение с одномерных массивов.

Описание одномерного массива в разных языках программирования смотрится несколько по-разному, но всегда содержит информацию об устройстве индекса Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков и типе частей. К примеру:

m1: array [1..10] of real; — Паскаль

float m2[10]; — Си, Java и ряд других языков программирования

dim m3(9) as variant; — VBA (Visual Basic for Applications)

Во всех приведенных примерах в той либо другой Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков форме находится информация об индексах массива2 и типе его компонент3. Видно, что, невзирая на различную форму записи, ее смысл во всех языках программирования приблизительно один и тот же, что Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков просто разъясняется общностью целей описаний массивов.

Подчеркнем, что хотя в одних языках (Basic, Си) индексы, определяющие положение элемента массива, всегда числовые, в других (Паскаль, Ада) допускаются и другие “счетные” типы (более точно Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков их именовать порядковыми). Неплохим примером порядковых данных может служить символьный тип CHAR, упорядоченный в согласовании с принятым в компьютере алфавитом (см. билет № 21).

Следует верно различать значения частей массива и значения их индексов, обеспечивающие доступ к Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков этим элементам. Можно провести очень глубокую аналогию, сопоставив эту пару понятий с человеком и его почтовым адресом, который позволяет доставить нужную информацию подходящему лицу.

При решении задач на обработку массивов очень принципиально Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков повсевременно держать под контролем правильность значений индексов. В особенности животрепещущей эта неувязка становится в этом случае, если значения индекса задаются не в очевидном виде, а рассчитываются тем либо другим методом Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков. Разглядим в качестве примера последующий кусок программки. Пусть в описании сказано, что массив Q состоит из частей с номерами от 1 до 5. Пусть дальше в неком месте программки находится оператор присваивания Q[t Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков+2] := 0. Тогда в случае t > 3 нулевое значение будет сохранено вне массива, поточнее говоря, в то место памяти, где находился бы элемент под номером t+2, если б он существовал. Так что в итоге выполнения данного неправильного Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков присвоения в наилучшем случае будет “испорчено” значение какой-нибудь другой переменной, а в худшем — сама исполняемая программка. В любом случае отыскать такую ошибку очень трудно: для этого будет нужно Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков огромное внимание и глубочайшее осознание логики работы программки.

Примечание. Может быть, у неких читателей появился вопрос: неуж-то компьютер не в состоянии проконтролировать “попадание” значения индекса в “разрешенный” спектр? Очевидно, в состоянии, вот Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков только контроль этот наращивает длину программки и замедляет ее работу. Вот поэтому в почти всех компиляторах контроль индексов является отключаемым, при этом ради эффективности итоговой программки по дефлоту контроль как раз бывает Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков выключен (конкретно так работает система программирования Turbo Pascal конторы Borland).

Введение сложного типа “массив” позволяет компактно обрисовывать решение широкого круга принципиальных для практики задач. К типовым задачкам обработки массива относятся:

· наполнение его Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков частей по определенному закону;

· нахождение некого соответствующего элемента (к примеру, наибольшего либо первого нулевого) и, может быть, его положения;

· поиск частей, удовлетворяющих определенному условию (либо подсчет их количества);

· определение неких черт массива (сумма, среднее Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков значение, наличие упорядоченности либо симметрии);

· сортировка массива;

· перенос данных из 1-го массива в другой, разделение массива на части, объединение массивов

— и некие другие. Подчеркнем, что к этим, казалось бы, очень абстрактным упражнениям Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков сводится большущее огромное количество практических задач: от обслуживания каталогов дисков до обработки результатов соревнований.

В качестве примера разглядим задачку поиска в массиве положения наибольшего элемента, которое определяется числовым значением его индекса. Программка Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков решения этой стандартной для массивов задачки на языке Паскаль может быть реализована последующим образом.

PROGRAM ind_max(INPUT, OUTPUT);

CONST n = 10;

m: ARRAY [1..n] OF INTEGER =

(8,10,9,4,7,2,5,6,3,1);

VAR k,im: INTEGER Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков;

BEGIN im := 1;

FOR k := 2 TO n DO

IF m[k] > m[im] THEN im := k;

WRITELN('max=',im)

END.

Программка так ординарна и традиционна, что не просит особенных комментариев. Отметим только, что для Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков простоты отладки4 элементы массива не вводятся с клавиатуры, а инициализируются входящими в текст программки значениями при помощи механизма так именуемых типизированных констант. Очевидно, заместо этого для ввода может быть написан и стандартный Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков цикл FOR k := 1 TO n DO READLN(m[k]).

Существует огромное количество методов организации обработки массивов. Кроме рассмотренной выше классической реализации, можно дополнительно выделить итерационный и рекурсивный способы. Опишем подробнее нареченные Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков технологии обработки массивов на примере традиционной задачки сортировки массива.

Примечание. В том, что таковой трудности задание соответствует уровню проведения выпускного экзамена, свидетельствуют задачки под номером 3, предлагаемые в качестве образцов в билетах
№ 12 базисного Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков и № 17 профильного уровня (см. [1] либо [2]).

^ Пример итеративной обработки массива

Разглядим итерационный метод сортировки частей одномерного числового массива в порядке возрастания, сущность которого заключается в последующем. Просматривая массив, будем поменять местами его примыкающие элементы Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков в тех случаях, когда они нарушают требуемый порядок, другими словами, больший элемент оказывается в положении с наименьшим индексом. Разумеется, что любая такая перестановка “соседей” с позиций сортировки улучшает ситуацию в массиве, но 1-го “прохода Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков повдоль массива” вероятнее всего будет недостаточно. Наибольшее число просмотров приравнивается количеству частей массива без единицы, что достигается при более неудачной исходной расстановке (когда самое малеханькое число стоит последним). Все Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков же полностью вероятны ситуации, когда требуемый порядок по обозначенному методу получится получить за наименьшее число проходов; а именно, в предельном случае, когда массив уже упорядочен, в этом можно убедиться единичным просмотром.

Каждый Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков просмотр массива, приближающий к решению намеченной цели (при этом итог обработки всегда служит исходным состоянием для нового просмотра), в компьютерной литературе именуют итерацией. В словаре [3], к примеру, дается такое определение данного термина: итерация — это Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков “повторение пошагового процесса, когда итог предшествующего шага (шагов) употребляется для получения результата последующего шага”.

Вообщем говоря, хоть какой цикл обработки массивов есть итерация. Правда, обычно, итерационными методами в большинстве случаев именуют Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков такие, в каких количество повторений заблаговременно непонятно. Наш метод сортировки является конкретно таким.

Механизм сортировки описанным способом так обширно известен, что тут мы приведем только вероятное решение на Паскале и совершенно Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков короткие пояснения к нему.

PROGRAM sort_iter(INPUT, OUTPUT);

CONST n = 10;

m:ARRAY [1..n] OF INTEGER =

(10,9,8,7,6,5,4,3,2,1);

VAR i,p: INTEGER; c: BOOLEAN;

BEGIN REPEAT c := FALSE;

FOR i := 1 TO n - 1 DO

IF m[i Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков] > m[i + 1] THEN

BEGIN p := m[i]; m[i] := m[i + 1];

m[i + 1] := p;

c := TRUE

END;

FOR i := 1 TO n DO

WRITE(m[i],' '); WRITELN;

UNTIL NOT c;

END.

В программке в виде Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков типизированной константы задан массив, который исходя из убеждений сортировки по возрастанию представляет самую большую трудность. Итерационный процесс сортировки регулируется переменной c, которая имеет смысл наличия сделанных во время итерации перестановок: когда c после Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков выполнения очередной итерации неверно, перестановок не было и сортировку можно закончить. 1-ый из циклов FOR обеспечивает проход по массиву и обмен “некорректно стоящих” примыкающих частей местами, а 2-ой — служит для Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков контрольного вывода на экран результатов каждой итерации сортировки.

Заметим, что в билете № 5 в связи с рассмотрением физической задачки о расчете рассредотачивания температуры в стержне также был тщательно описан пример итерационного метода обработки одномерного массива Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков.

^ Примеры рекурсивной обработки массива

Рекурсия — это метод решения задачки, при котором делается последовательное ее сведение к аналогичной, но более обычный. К рекурсии в принципе можно свести хоть какой повторяющийся метод, но Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков не напротив: известным примером может служить метод закраски на дисплее случайной области, который тривиально реализуется рекурсивным методом, зато решение этой задачки в виде циклов очень проблемно.

Таким макаром, неважно какая задачка по обработке Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков массива может быть решена при помощи рекурсии. Мы возьмем в качестве примера ту же самую задачку сортировки массива, которая рассматривалась выше для итерационного способа. Попутно окажется, что нам будет нужно написать нахождение максимума Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков, что также можно сделать рекурсивно5. Как следует, в конечном итоге у нас будет сходу два примера рекурсивных алгоритмов.

Разглядим вероятную реализацию программки.

PROGRAM sort_rekurs(INPUT, OUTPUT);

CONST n = 10;

m: ARRAY [1..n Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков] OF INTEGER =

(10,9,8,7,6,5,4,3,2,1);

FUNCTION ind_max(k: INTEGER): INTEGER;

VAR w: INTEGER;

BEGIN IF k > 1 THEN BEGIN w := ind_max(k - 1);

IF m[k] < m[w] THEN ind_max := w

ELSE ind_max := k

END

ELSE Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков ind_max := 1

END;

PROCEDURE sort2(p: INTEGER);

VAR im,c: INTEGER;

BEGIN im := ind_max(p);

c := m[im]; m[im] := m[p]; m[p] := c;

FOR c := 1 TO n Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков DO WRITE(m[c],' '); WRITELN;

IF p > 2 THEN sort2(p - 1)

END;

BEGIN sort2(n)

END.

Описание начнем с рассмотрения рекурсивной функции ind_max для нахождения индекса наибольшего элемента. Ее рекурсивная логика может Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков быть сформулирована последующим образом. Решение задачки для массива из n частей очень трудоемко, потому его равномерно сводим к более обычному: для n – 1, n – 2
и т.д. частей (см. вызов ind_max(k-1), который Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков и является рекурсивным вызовом функцией самой себя). Так поступаем до того времени, пока ответ не станет элементарным: в массиве из 1-го элемента индекс максимума равен индексу этого единственного элемента (в нашем случае Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков 1). Дальше делается “оборотный ход” — зная текущее значение ind_max, соответственное ему значение максимума сравниваем с текущим элементом массива, после этого индекс большего из сравниваемых частей запоминаем. Таким макаром, отрабатывается поочередная цепочка рекурсивных Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков вызовов и без всякого цикла организуется полный перебор всех частей массива.

Примечание. Осознание механизма вызова процедур6 делает возможность реализации их “самовызова” полностью тривиальной; даже просто зная о факте разрешения вызова из одной Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков процедуры другой, можно предсказать существование рекурсивности. Основная же неувязка рекурсии состоит в том, чтоб организованный рассматриваемым методом процесс каким-то образом завершался.

Сейчас, рассматривая функцию ind_max как единое целое и Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков не обращая внимания на ее внутреннюю логику, обсудим 2-ой рекурсивный метод — сортировку массива, описанную в рекурсивной процедуре sort2. Ее логика работы такая. В массиве размерности n находится наибольший элемент, и он изменяется местами с Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков последним. В итоге самый последний элемент массива займет свое окончательное место и остается рассортировать массив уже наименьшего размера, т.е. n – 1. Аналогичным образом задачка поочередно решается для все наименьшего и наименьшего массива Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков, пока не остается массив из 1-го элемента, в каком, естественно, сортировка уже не требуется: условие p > 2 предутверждает вызов sort2(1) и процесс рекурсии благополучно заканчивается.

Примечание. Имеющийся в sort2 цикл вывода массива Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков на экран играет вспомогательную роль. Читатели при желании могут без усилий без помощи других оформить его в виде рекурсивной процедуры (печатаем 1-ый элемент, а потом вызываем функцию вывода оставшегося массива!), реализовав Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков тем чисто рекурсивную программку без одного цикла.

Основная программка состоит из единственной строчки sort2(n), которая запускает процесс сортировки, начиная с полного массива.

^ Примечание для учителей. Полностью может быть, что приведенное решение задачки для неких Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков школ покажется очень сложным. В данном случае полностью можно ограничиться рекурсивным решением ее части — нахождением положения максимума в массиве. Вообщем сам факт наличия вопроса о рекурсии7 в тексте официальных “министерских” билетов Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков для выпускных экзаменов в пору, когда слово “программирование” для многих методистов стало чуть ли не бранным, очень наглядно показывает тот идеологический разброд, который занесла в содержание курса информатики энергичная борьба за Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков заполнение школьного курса прикладными офисными технологиями!

Все обсуждавшиеся выше примеры рассматривали одномерные массивы данных. Они являются более ординарными и, не считая того, естественным образом согласуются с принципами организации памяти компьютера: согласно традиционным Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков идеям фоннеймановской архитектуры, память — это линейный массив пронумерованных ячеек. Как следует, остается только получить формулу пересчета значений индексов в адреса ОЗУ и с элементами такового массива можно просто работать.

В арифметике, физике и неких Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков других науках все же обширно употребляются и многомерные массивы. Потому такие структуры не могли не показаться в языках программирования. Практически есть два метода определения многомерных массивов: конкретный и создание сложной Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков структуры. Мы ограничимся обсуждением двумерных массивов; обобщение для большей размерности делается аналогично. На языке Паскаль, к примеру, эти два метода описания массивов смотрятся так:

m1: ARRAY [1..3, 1..5] OF REAL;

m2: ARRAY [1..3] OF ARRAY Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков [1..5] OF REAL;

Примечание. Воззвание к элементам массивов m1 и m2 отличаются: они записываются как m1[i,j] и m2[i][j] соответственно.

В неких обычных языках программирования типа Basic употребляется только обычная математическая Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков (“матричная”) форма представления массивов, а в языках с более развитыми средствами сотворения данных, а именно Паскале, допустимы обе формы.

Подчеркнем, что если в языке программирования для индексов допустимы не только Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков лишь целочисленные типы (в Паскале в том числе), то индексы многомерных массивов не непременно имеют однообразный тип: к примеру, один индекс может быть целочисленным, а другой являться эмблемой.

С математической точки зрения для роста размерности Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков массива довольно формально приписать очередной индекс. Но для реализации таковой структуры в памяти компьютера будет нужно как-то приспособить многомерную структуру данных к хранению в одномерной памяти. “Кроме языка Fortran, все языки Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков хранят двумерные массивы как последовательности строк… Такое размещение полностью естественно, так как сохраняет идентичность двумерного массива и массива массивов”. [4] Приведенный набросок объясняет идею формирования двумерного массива данных в “линейном” ОЗУ Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков компьютера.



Беря во внимание, что все элементы массива однородны (имеют один и тот же тип и, как следует, занимают однообразное место в памяти), получить формулу пересчета индексов в требуемый адресок ОЗУ является легкой Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков задачей. И хотя школьных познаний для этого полностью довольно, мы не будем на данный момент этим заниматься. Заметим только, что в 32-разрядных микропроцессорах Intel специально предусмотрены аппаратные способы адресации, в которые заложены Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков такие формулы для данных стандартной длины (1, 2, 4 и даже 8 б), что значительно упрощает для программера (либо для компилятора) доступ к элементам массивов. Заинтересовавшиеся читатели могут познакомиться с формулами для масштабированной базово-индексной Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков адресации (одномерные массивы) и для аналогичного способа со смещением (двумерные), к примеру, по книжке [5].

Литература

1. Примеры задач к билетам. Информатика, 2006, № 6, с. 3–16.

2. Примеры задач к билетам. Информатика и образование, 2006, № 3, с. 24–30.

3. Фридланд А.Я. Информатика и компьютерные Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков технологии: Главные определения: Толковый словарь / А.Я. Фридланд, Л.С. Ханамирова, И.А. Фридланд. М.: ООО “Издательство Астрель”: ООО “Издательство АСТ”, 2003, 272 с.

4. Бен-Ари М. Языки программирования. Практический сравнительный анализ Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков. М.: Мир, 2000, 366 с.

5. Гук М. Микропроцессоры Intel: от 8086 до Pentium II. СПб.: Питер, 1997, 224 с.
2. Изображение на картонном носителе состоит из нескольких частей. Отсканировать части изображения и соединить их в одно растровое изображение Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков. Отретушировать получившееся изображение и сохранить его в файле.
Решение данной задачки (после сканирования частей изображения) может быть выполнено в любом растровом графическом редакторе (а именно, в редакторе Paint). Для получения высококачественного Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков итогового изображения рекомендуется пользоваться редактором Adobe Photoshop.

Не будем тут приводить детализированного описания решения задачки.
3. Найти информационный объем переданного сообщения за определенный период времени при данной пропускной возможности канала.
Пример. Модем передает сообщения Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков со скоростью 14 400 бит за секунду. Изображение какого размера (в формате без сжатия) может передать модем за три минутки неизменной работы, если употребляется гамма из 65 тыщ цветов?

Решение. Представим для определенности, что гамма составляет Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков 65536 = 216 цветов. Тогда для кодировки инфы об одной точке требуется
2 б. 14 400 бит/с = 1800 б/с. За 3 мин. = 180 с будет передано 180 х 1800 = 324 000 б (316,4 Кб) изображения либо информация о 162 000 точек изображения.

^ Варианты заданий

1. Информация по Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков электрической почте через модем передается со скоростью 9600 бит/с. Сколько времени пригодится, чтоб передать по электрической почте субботний выпуск газеты “Комсомольская правда”, если ее объем 3 условных печатных листа (1 условный печатный лист газеты с Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков иллюстрациями 512 Кб)?

2. В течение урока 12 учеников пишут диктант в 10 000 знаков. Оцените, сколько минут пригодится, чтоб переслать попеременно работы всех учеников на ПК учителя при скорости пересылки в 9600 бит/с?



1 Вправду Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков, для однократного вычисления по единственной не очень сложной формуле обычно пользуются калькулятором, а не пишут программку.

2 В Паскале указаны граничные значения индекса (поточнее говоря, тип данных ограничение, личным случаем которого как раз является спектр целых Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков чисел), в Си — количество частей, в VBA — наибольшее значение индекса (малое, обычно, равно 0, что упрощает расчеты с индексами, но есть оператор его установки в 1).

3 real, float и variant соответственно.

4 У создателя Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков, как у практика, огромное сострадание вызывает предлагаемая ученикам в образчиках к билетам задачка “написать и отладить программку ввода и сортировки… массива из 20 частей”.

5 Создатели советуют провести сопоставление рекурсивного поиска положения Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков максимума с написанной обычным методом программкой ind_max, приведенной выше.

6 Многие методисты охотно включают в программку школьного курса информатики исследование стека и других динамических структур данных; при всем этом ни какой-то из них Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков не упоминает, что конкретно этот самый стек, аппаратным образом организованный, лежит в базе механизма реализации вложенных процедур (и даже передачи им характеристик!).

7 Рекурсию можно считать понятием третьего(!) уровня трудности в программировании: алгоритмические Билет № 7 - Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков структуры — автономные процедуры и функции — особенности их “самовызова”.


bioelektricheskie-yavleniya-v-vozbudimih-tkanyah.html
bioenergeticheskij-analiz.html
bioenergetika-i-boevie-iskusstva-vostoka.html