textarchive.ru

Главная > Документ


G := Nod(Abs(E), F);

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

При решении задач целесообразно проанализировать условие, записать решение в крупных блоках (не являющихся операторами Pascal), детализировать каждый из блоков (записав в виде блоков, возможно, по-прежнему не операторов Pascal) и т.д., продолжать до тех пор, пока каждый из блоков не будет реализован с помощью операторов языка.

Пример 2. Дано натуральное число n. Переставить местами первую и последнюю цифры этого числа.

Program Integ;

Var N : Integer;

Begin

Write('Введите натуральное число: ');

ReadLn(N);

If Impossible(N)

Then WriteLn('Невозможно переставить

цифры, возникнет переполнение')

Else Begin

Change(N);

WriteLn('Ответ: ', N)

End;

End.

Можно заметить, что необходимо детализировать логическую функцию Impossible, которая диагностирует, возможна ли перестановка, и процедуру Change, которая эту перестановку (в случае, если она возможна) выполняет.

Function Impossible(N : Integer) : Boolean;

Begin

If Number(N) < 10000

Then Impossible := False

Else Impossible := (N Mod 10 > 3) Or

N Mod 10 = 3) And

(N Mod 10000 Div 10 * 10 + N Div 10000 >

MaxInt Mod 10000)

End;

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

Function Number(N : Integer) : Integer;

Var Vsp : Integer;

Begin

Vsp := 1;

While N > 10 Do Begin

Vsp := Vsp * 10; N := N Div 10

End;

Number := Vsp

End;

Наконец, последняя процедура.

Procedure Change(Var N : Integer);

Var Kol, P, S, R : Integer;

Begin

Kol := Number(N);

P := N Mod 10; {последняя цифра}

If Kol > 1 Then

S := N Div Kol

Else S := 0; {первая цифра}

R := N Mod Kol div 10;

N := P * Kol + R * 10 + S

End;

Возможны также подпрограммы, которые вызывают сами себя. Они называются рекурсивными. Создание таких подпрограмм является красивым приемом программирования, но не всегда целесообразно из-за чрезмерного расхода памяти ЭВМ.

Пример 3. Найти максимальную цифру в записи данного натурального числа.

Program MaxDigit;

Type NaturLong = 1..MaxLongInt;

Digit = 0..9;

Var A : NaturLong;

Function Maximum(N : NaturLong) : Digit;

Begin

If N < 10 Then Maximum := N

Else If N Mod 10 > Maximum(N Div 10)

Then Maximum := N mod 10

Else Maximum := Maximum(N Div 10)

End;

Begin

Write('Введите натуральное число: ');

ReadLn(A);

WriteLn('Максимальная цифра равна ',

Maximum(A))

End.

При создании функции Maximum было использовано следующее соображение: если число состоит из одной цифры, то она является максимальной, иначе если последняя цифра не является максимальной, то ее следует искать среди других цифр числа. При написании рекурсивного алгоритма следует позаботиться о граничном условии, когда цепочка рекурсивных вызовов обрывается и начинается ее обратное “раскручивание”. В нашем примере это условие N < 10.

В структурном языке программирования любой программный объект (константа, переменная, тип и др.) должен быть описан перед использованием в программе. Иначе говоря, описание объекта должно предшествовать его первому появлению в других фрагментах программы. Это правило относится и к подпрограммам.

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

Любая подпрограмма может использоваться лишь в пределах области действия ее описания (а описанные в ней объекты — лишь внутри этой подпрограммы). Например, область действия подпрограмм А и В — основная программа. Поэтому из основной программы можно обратиться к подпрограммам А и В. В свою очередь, в подпрограмме В могут быть обращения к подпрограмме А; а из А нельзя обратиться к В, поскольку описание А предшествует описанию В. Подпрограммы А1 и А2 локализованы в подпрограмме А и могут использоваться только в ней; из А2 можно обратиться к А1, но нельзя наоборот.

Из подпрограммы В1 можно обратиться к А, поскольку ее описание является глобальным по отношению к В1, но нельзя обратиться к А1, поскольку область действия описания А1 не распространяется на блок подпрограммы В.

Из подпрограммы В22 можно обратиться только к В21, В1, B2, А.

Таким образом, можно заметить, что все внешние описания по отношению к той или иной подпрограмме носят глобальный характер. Все, что объявляется внутри подпрограммы, локализовано. Понятие “локальный-глобальный” является относительным, поскольку одно и то же описание по отношению к разным подпрограммам (основной программе) может являться и локальным, и глобальным.

Использованные источники информации

1. Семакин И., Залогова Л., Русаков С., Шестакова Л. Информатика: учебник по базовому курсу. М.: Лаборатория Базовых Знаний, 1998. (Глава 12. Введение в программирование, с. 323–371.)

2. Угринович Н. Информатика и информационные технологии. Учебное пособие для общеобразовательных учреждений. М.: БИНОМ, 2001, 464 с.

3. Информатика. 7–8-е классы / Под ред. Н.В. Макаровой. СПб.: ПитерКом, 1999, 368 с.

4. Шафрин Ю.А. Информационные технологии. М.: Лаборатория Базовых Знаний, 1998, 704 с. (п. 1.6. Понятие об алгоритмах, п. 1.7. Понятие о программировании, с. 53–72).

5. Информатика. Задачник-практикум в 2 т. / Под ред. И.Г. Семакина, Е.К. Хеннера: Т. 1. М.: Лаборатория Базовых Знаний, 1999, 304 с.

6. Основы информатики и вычислительной техники. Пробное учебное пособие для средних учебных заведений / Под ред. А.П. Ершова, В.М. Монахова. М.: Просвещение, 1985. Ч. I, II.

7. Шауцукова Л.З. Информатика: Учебник для
10–11-х классов. М.: Просвещение, 2000 (Глава 7. Алгоритмы. Алгоритмизация. Алгоритмические языки).

8. /didakt_i.html — дидактические и методические материалы по программированию и информатике.

9. Семакин И.Г., Шестаков А.П. Основы программирования (учебник) — допущен Министерством образования Российской Федерации в качестве учебника для студентов образовательных учреждений среднего профессионального образования, обучающихся по специальностям 2202 “Автоматизированные системы обработки информации и управления (по отраслям)”, 2203 “Программное обеспечение вычислительной техники и автоматизированных систем”. М.: Мастерство, НМЦ СПО; Высшая школа, 2001, 432 с.

10. Гладков В.П., Шестаков А.П. Вопросы, задания и контрольные работы для начинающих программистов. // Информатика № 20, 33, 34, 35, 37, 38, 40, 47, 48/2001.

11. Иванова Г.С. Технология программирования: Учебник для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002, 320 с.

2. Средствами почтовой программы создать фильтр для автоматического распределения входящих писем по почтовым папкам в зависимости от темы письма

Рассмотрим решение поставленной задачи в двух разных почтовых клиентах.

Outlook Express

Для того чтобы такое распределение было возможно, необходимо существование тех папок, по которым предполагается “раскладывать” письма (или нужно создать такие папки в процессе формирования правила сортировки почты).

Необходимо выбрать меню Сообщение > Создать правило из сообщения…

Далее в диалоговом окне Создать правило для почты (см. рисунок) указать, что сортировка почты осуществляется по полю Тема, в качестве действия указать Переместить в заданную папку, далее — описать правило.

Описание правила включает:

1) ввод ключевых слов

2) выбор папки, куда будут помещаться указанные сообщения

Последнее — задание названия для правила (либо можно согласиться с предлагаемым по умолчанию).

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

Служба

В персональных настройках можно установить фильтры.

Выбрать Добавить фильтр в список фильтров. Настроить фильтр.

3. Задание на подсчет полного набора символов (мощности алфавита), используемого при кодировании информации

Пример. Перед въездом в город стоят пять флагштоков. На флагштоках можно поднимать флаги желтого, зеленого и красного цветов. Какое количество различных сигналов можно подать при помощи этих флагштоков при условии, что не обязательно поднимать флаг на каждом из флагштоков?

Решение. При условии, что не обязательно поднимать флаг на каждом из флагштоков, для каждого флагштока есть 4 возможности: нет флага, желтый флаг, зеленый флаг, красный флаг. Тогда общее количество комбинаций получается следующим:
4 · 4 · 4 · 4 · 4 = 1024.

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

В качестве задач в этом разделе можно предлагать любые простейшие задачи из комбинаторики.

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

2. Сколькими способами можно рассадить аллею, если у нас есть яблоня, береза, липа, сосна, елка и рябина? Притом сосну нельзя сажать первой, а яблоню нельзя сажать рядом с рябиной.

3. Сколько можно составить пятизначных телефонных номеров из цифр от 0 до 7?

4. На полке стоит 5 напитков. Сколько разных коктейлей из них можно составить?

5. Номер машины состоит из 3 цифр. Сколько неправильных вариантов можно получить, угадывая номер?

Билет № 7

1. Типы данных. Структуры данных. Обработка массивов. Итеративные и рекурсивные алгоритмы обработки массивов. Многомерные массивы

Обсуждая билет № 5, мы уже говорили о типах данных, их роли в алгоритме, а также о том, что дает компьютеру “знание” типа конкретной величины. Мы также говорили, что существуют простые и сложные типы данных. Простые типы чаще всего используются для хранения рабочих величин, но могут быть также аргументами или результатами в несложных алгоритмах. Тем не менее для представления данных в реальных задачах возможностей простых данных обычно недостаточно. В самом деле, в типичном случае о человеке необходимо хранить фамилию, имя и отчество (текстовые данные), год рождения (число), пол и семейное положение (одно из значений, выбираемых из фиксированного набора), факты наличия или отсутствия определенных признаков, например, обладания недвижимостью (логические данные) и т.д. В результате для объединения совокупности всех относящихся к одному реальному объекту данных (компонентов) требуется возможность создания из них единой сложной структуры.

Примечание. Стоит отметить, что если к сложному набору данных, состоящему из отдельных компонентов (полей), добавить методы их обработки, то получится автономная конструкция еще более высокого уровня — объект (см. билет № 6).

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

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

Современные языки программирования позволяют создавать весьма разнообразные сложные структуры данных, причем для этого можно объединять как несколько простых, так и другие сложные данные. Самым распространенным сложным типом является массив, соединяющий в себе набор данных одного типа, например, массив из целых чисел или массив из логических величин. Кстати, конструкция “массив из массивов” также является вполне допустимой, о чем мы будем говорить несколько позже.

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

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

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

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

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

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

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

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

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

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

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

Примечание. Возможно, у некоторых читателей возник вопрос: неужели компьютер не в состоянии проконтролировать “попадание” значения индекса в “разрешенный” диапазон? Разумеется, в состоянии, вот только контроль этот увеличивает длину программы и замедляет ее работу. Именно поэтому во многих компиляторах контроль индексов является отключаемым, причем ради эффективности итоговой программы по умолчанию контроль как раз бывает выключен (именно так работает система программирования Turbo Pascal фирмы Borland).

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

· заполнение его элементов по определенному закону;

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

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

· определение некоторых характеристик массива (сумма, среднее значение, наличие упорядоченности или симметрии);

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

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

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

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

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;

BEGIN im := 1;

FOR k := 2 TO n DO

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

WRITELN('max=',im)

END.

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

Существует большое количество способов организации обработки массивов. Помимо рассмотренной выше традиционной реализации, можно дополнительно выделить итерационный и рекурсивный методы. Опишем подробнее названные технологии обработки массивов на примере классической задачи сортировки массива.

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

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

Рассмотрим итерационный способ сортировки элементов одномерного числового массива в порядке возрастания, суть которого заключается в следующем. Просматривая массив, будем менять местами его соседние элементы в тех случаях, когда они нарушают требуемый порядок, иными словами, больший элемент оказывается в положении с меньшим индексом. Очевидно, что каждая такая перестановка “соседей” с позиций сортировки улучшает ситуацию в массиве, но одного “прохода вдоль массива” скорее всего будет недостаточно. Максимальное число просмотров равняется количеству элементов массива без единицы, что достигается при наиболее неудачной начальной расстановке (когда самое маленькое число стоит последним). Тем не менее вполне возможны ситуации, когда требуемый порядок по указанному алгоритму удастся получить за меньшее число проходов; в частности, в предельном случае, когда массив уже упорядочен, в этом можно убедиться единичным просмотром.

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

Вообще говоря, любой цикл обработки массивов есть итерация. Правда, как правило, итерационными алгоритмами чаще всего называют такие, в которых количество повторений заранее неизвестно. Наш алгоритм сортировки является именно таким.

Механизм сортировки описанным методом настолько широко известен, что здесь мы приведем только возможное решение на Паскале и совсем краткие пояснения к нему.

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] > 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.

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

Заметим, что в билете № 5 в связи с рассмотрением физической задачи о расчете распределения температуры в стержне также был подробно описан пример итерационного алгоритма обработки одномерного массива.



Скачать документ

Похожие документы:

  1. Примерные ответы на профильные билеты

    Документ
    Примерныеответынапрофильныебилеты Е.А. Еремин, А.П. Шестаков От авторов Уважаемые ... . М.: Энергия, 1973, 144 с. 5. Еремин Е.А., Шестаков А.П. Примерныеответынапримерныебилеты // Информатика, 2002, № 13 (350), с. 9–13 ...
  2. Профильное обучение

    Сценарий
    ... (Методическая консультация. Профильная школа). Профильное обучение: вопросы и ответы : [ответына некоторые актуальные вопросы] ... . Анализ существующего положения дел. Еремин Е. А. Примерныеответынапрофильныебилеты / Е. А. Еремин, А. П. Шестаков. ...
  3. Ответы на экзаменационные билеты по литературе 11 класс

    Экзаменационные билеты
    ... билетов полностью соответствует примерным экзаменационным билетам по литературе для образовательных учреждений, осуществивших переход напрофильное ...
  4. Примерные ответы на теоретические вопросы билетов профильный уровень билет № 1 понятие информации виды информации ее свойства классификации по различным основаниям проблема определения выбор способа представления информации в соответствии

    Документ
    Примерныеответына теоретические вопросы билетов. Профильный уровень Билет № 1 Понятие информации. Виды ... так, чтобы на них можно было ответить «да» или ... в Америке и мангустов — на острове Ямайка. Билет № 11 Информационные основы управления ...
  5. Примерные билеты по физике для сдачи экзамена по выбору выпускниками xi (xii) классов общеобразовательных учреждений российской федерации пояснительная записка

    Документ
    ... изучавших физику на базовом и напрофильном уровнях. Содержание билетов учитывает требования ... 2) плакаты и таблицы для ответовна теоретические вопросы, 3) непрограммируемый калькулятор ... именно статистические исследования? Примерныебилеты по физике для ...

Другие похожие документы..