Гипермаркет знаний>>Информатика>>Информатика 9 класс>>Информатика: Информатика 9 класс. Дополнение к главе 6

Дополнение к главе 6

6.1. Поиск наибольшего и наименьшего элементов массива

Основные темы параграфа:

♦ поиск максимума и минимума в электронной таблице;
♦ блок-схемы алгоритмов поиска максимума и минимума в массиве;
♦ программа на Паскале поиска максимума и минимума в массиве.

Поиск максимума и минимума в электронной таблице

Одной из типовых задач обработки массивов является поиск наибольшего или наименьшего значения среди значений его элементов. Построим алгоритм решения этой задачи и составим программу на Паскале. Для примера возьмем итоговые данные чемпионата России по футболу в премьер-лиге за 2003 год.

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

Для определения максимального значения в электронной таблице существует функция МАКС( ), а для нахождения минимального значения — функция МИН( ). В ячейке В17 записана формула МАКС(В1:В16), а в ячейке В18 — формула МИН(В1:В16). Результаты вы видите в таблице. Отсюда делаем вывод: чемпионом России стала команда ЦСКА, а на последнем месте — Черноморец.

Блок-схемы алгоритмов поиска максимума и минимума

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

Начнем с поиска максимума. Опишем алгоритм на Алгоритмическом языке.

Пусть в целочисленный массив В[1:16] заносятся очки команд в том порядке, в каком они расположены в таблице на рис. 6.12. Максимальное количество очков получим в переменной МахВ. Кроме того, найдем еще и номер команды, занявшей первое место. Для этого будет использоваться переменная Nmax.

Рассмотрим алгоритм решения задачи. Ниже приведен полный алгоритм на Алгоритмическом языке, а на рис. 6.13 — фрагмент блок-схемы, относящийся только к выбору максимального элемента (без ввода и вывода).

Идея алгоритма состоит в следующем. В переменную МахВ заносится значение первого элемента массива, в переменную Nmax — единица, т. е. номер первого элемента. Затем в цикле последовательно с МахВ сравниваются все остальные элементы массива В. Если очередной элемент оказывается больше текущего значения МахВ, то его значение заносится в МахВ, а его номер — в Nmах. Когда закончится цикл, в МахВ останется наибольшее число из всего массива, а в Nmах — его номер.

Теперь нетрудно догадаться, как искать минимальное значение в массиве и его номер. Если для этого использовать в программе переменные МinВ и Nmin и в условии ветвления заменить знак отношения «больше» на «меньше», то получим нужный алгоритм. Он показан блок-схемой на рис. 6.14.

Если в алгоритме нужно одновременно искать максимальное и минимальное значения, то соответствующие ветвления можно объединить в одном цикле. Именно так сделано в приведенной ниже программе на Паскале.

Программа на Паскале поиска максимума и минимума в массиве

Составим программу на Паскале. Но в эту программу мы внесем еще некоторые новые детали. Хотелось бы в итоге работы программы получить не номера, а названия команды-победителя и команды, занявшей последнее место. Но для этого названия всех команд чемпионата должны быть организованы в массив и введены как исходные данные. В программе такой массив назван Теаm[1. . 16] и тип его элементов объявлен как string.

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

Обратите внимание на то, как определяется название команды-победителя и команды, занявшей последнее место. Это делается по значениям индексов максимального и минимального элементов массива В: Nmах и Nmin. В переменной Теаm[Nmах] находится название чемпиона, а в переменной Теаm[Nmin] — название последней команды в чемпионате.

При выполнении программы на экране будет отражено следующее:

Коротко о главном

Алгоритм выбора максимального (минимального) значения в массиве имеет структуру цикла с вложенным неполным ветвлением.

Для обработки последовательностей символов в Паскале имеется строковый тип данных: string.

Вопросы и задания

1. Придумайте собственные примеры данных, которые можно было бы представить в виде строкового массива.
2. Представьте себе, что две команды набрали 59 очков. Например, ЦСКА и ЗЕНИТ. Номер какой команды был бы выведен в качестве результата?
3. При условии предыдущего задания определите, какие будут выведены результаты, если в операторе ветвления, где отбирается максимальное значение, заменить знак отношения «>» на «>=»?
4. Введите в компьютер программу Рremier-liga. Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.
5. По условиям чемпионата 2003 года из премьер-лиги выбывают две последние в турнирной таблице команды. Составьте программу, определяющую обе команды, выбывающие из премьер-лиги.

6.2. Сортировка массива

Основные темы параграфа:

♦ алгоритм сортировки методом пузырька;
♦ программа на Паскале сортировки методом пузырька.

Известно, что данные в электронной таблице можно сортировать по возрастанию или убыванию значений в столбцах. Для задачи с таблицей футбольного чемпионата естественным действием была бы сортировка по убыванию значений набранных очков. Тогда вверху таблицы останется победитель чемпионата, а в нижней строчке — команда, занявшая последнее место. На рис. 6.15 показана такая отсортированная таблица. Из нее мы получаем исчерпывающую информацию об итогах чемпионата: кто какое место занял.

Алгоритм сортировки методом пузырька

Рассмотрим, как программируется сортировка массива. Для решения этой задачи существует целый класс алгоритмов. Мы рассмотрим здесь только один из них, известный под названием «метод пузырька». Откуда такое название, станет ясно немного позже.

Проиллюстрируем идею метода пузырька на маленьком массиве из пяти чисел. Пусть это будет массив В[1:5], исходные значения в котором распределены случайным образом (рис. 6.16). Требуется отсортировать числа по убыванию.

Первый этап (первый проход). Последовательно сравниваются пары соседних чисел и упорядочиваются по убыванию. Сначала сравниваются B[1] и В[2]. Поскольку на втором месте должно стоять меньшее число, то числа меняются местами. B[1] становится равным 3, В[2] — равным 1. Затем упорядочиваются B[2] и B[3]. Их значения тоже переставляются: В[2]=2, В[3]=1. Затем упорядочиваются B[3] и B[4]. И наконец, B[4] и B[5]. В результате первого прохода минимальное число попадает на свое место: В[5]=1.

Алгоритм первого прохода можно описать так:

Обмен значениями В[I] и В[I+1] происходит через третью переменную X. Вот теперь можно понять смысл образа пузырька! В результате прохода минимальное значение «всплывает» в конец массива, как воздушный пузырек в воде всплывает на поверхность, подталкиваемый архимедовой силой.

Далее нужно повторять такие проходы еще три раза. После второго прохода на своем месте окажется B[4], после третьего прохода — В[3]. После четвертого упорядочатся В[2] и В[1]. Нетрудно понять, что при втором проходе не надо трогать В[5], т.е. цикл должен повторяться для I от 1 до 3. При третьем проходе — от 1 до 2. И наконец, на четвертом проходе — от 1 до 1, т. е. всего 1 раз.

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

Вот полный алгоритм сортировки массива В[1:16]:

Здесь переменная К играет роль номера прохода. Для массива длиной 16 такие проходы требуется повторить 15 раз. Длина каждого К-го прохода равна 16—К.

Программа на Паскале сортировки методом пузырька

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

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

Вывод результатов на экран организован так, чтобы на экране номера мест, занятых командами, названия команд и набранные очки выводились в три ровных столбца. Названия разных команд имеют разную длину. Самое длинное название у команды ТОРПЕДО-МЕТАЛЛУРГ состоит из 17 символов. Для выравнивания длин строк каждое название дополняется пробелами до 18 символов. Число добавляемых пробелов вычисляется так:

18-length(Теат[I])

Здесь length( ) — это стандартная функция, вычисляющая длину строки (число символов), указанной в скобках. Например, для ЦСКА длина строки равна 4, а для ТОРПЕДО-МЕТАЛЛУРГ длина равна 17. Значит к ЦСКА добавится 14 пробелов, а к ТОРПЕДО-МЕТАЛЛУРГ — 1 пробел.

В операторе Теаm[I]:=Теаm[I]+;используется операция присоединения символов «+». В данном случае присоединяется пробел. К строке Теam[I] добавится столько пробелов, сколько раз повторится присоединение. После этого по команде

Writeln (I:2,' ',Теаm[I]:18, В[I]:2) 

в ровные колонки выведутся места, названия команд и очки. Результаты будут иметь на экране следующий вид:
1  ЦСКА                                      59
2  ЗЕНИТ                                    56
3  РУБИН                                    53
…………..

14 ТОРПЕДО-МЕТАЛЛУРГ         29
15 УРАЛАН                                  28
16 ЧЕРНОМОРЕЦ                       24

Коротко о главном

Метод пузырька — алгоритм сортировки числового маcсива.

Структура алгоритма метода пузырька — два вложенных цикла с переменной длиной внутреннего цикла.

length() — функция определения длины строковой переменной.

В Паскале существует операция присоединения строк. Ее знак — «+».

Вопросы и задания

1. Как пояснить название метода сортировки массива - «метод пузырька»?
2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?
3. Введите в компьютер программу Ргemier-liga-2. Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.
4. Внесите изменения в программу для того, чтобы получить список в обратном порядке (по возрастанию очков). Выполните программу.
5. Возможно, что массив окажется отсортированным до завершения всех проходов. В таком случае число повторений внешнего цикла можно сократить, и программа будет выполняться быстрее. Попробуйте усовершенствовать приведенную программу с учетом этого факта. Проверьте результат на тестах.
6. Если несколько команд набрали одинаковое количество очков, то места между ними распределяются по разнице забитых и пропущенных мячей: чем разница больше, тем место выше. Попробуйте усовершенствовать программу, учитывая это правило. Для этого в программу надо добавить массив с разницами мячей. Придумайте тест, на котором можно проверить работу программы.
7. Условие то же, что и в предыдущем задании. Но в качестве исходных данных вводится еще два массива: с числом забитых мячей и с числом пропущенных мячей каждой командой.'


6.3. О языках программирования и трансляторах

Основные темы параграфа:

♦ системы программирования;
♦ уровни языков программирования;
♦ трансляция и трансляторы;
♦ о двух способах трансляции;
♦ работа компилятора;
♦ работа интерпретатора.

Системы программирования

«Родным» языком ЭВМ является язык машинных команд (ЯМК). Самые первые ламповые ЭВМ понимали только этот язык. В программах на ЯМК данные обозначаются их адресами в памяти машины, выполняемые операции — числовыми кодами. Программист сам должен заботиться о расположении в памяти ЭВМ команд программы и данных.

Современные программисты так не работают. Для программирования на современных компьютерах применяются системы программирования (СП). В учебнике 8 класса (глава 2) говорилось о том, что программное обеспечение компьютера делится на три части:

• системное ПО;
• прикладное ПО;
• системы программирования.

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

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

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

Уровни языков программирования

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

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

Автокод — это машинно-ориентированный язык символического программирования.

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

Начиная с машин третьего поколения, языки такого типа стали называть ассемблерами. В наше время на ассемблере программируют довольно редко. Это, как правило, делают системные программисты.

Сокращение ЯПВУ расшифровывается так: языки программирования высокого уровня. Сегодня большинство программистов работают именно на этих языках. Примеры языков высокого уровня: Паскаль, Бейсик, СИ, Фортран.

Вот пример записи одной и той же команды сложения двух чисел на трех языках разного уровня: ЯМК, автокоде и Паскале:

С:=А+В                   Паскаль
АDD А, В, С            автокод
01 24 28 2С           ЯМК

Видно, как с повышением уровня языка повышается «понятность» команды (по-английски слово «АDD» означает «сложить»). Однако, чем понятнее язык для человека, тем непонятнее для процессора компьютера. Процессор понимает только ЯМК, это его «родной» язык. Человеку же легче писать программы на языках более высокого уровня. Как же быть?

Трансляция и трансляторы

Как сделать так, чтобы человек мог писать программы на автокоде или Паскале, а компьютер мог исполнять эти программы? Ответ на поставленный вопрос такой же, как на вопрос «Как мне общаться с японцем, если я не знаю японского языка?». Нужен переводчик! По-английски «переводчик» — «translator».

Программы-переводчики с автокода, Паскаля, Фортрана и других языков на язык машинных команд называются трансляторами.

Таким образом, компьютер сам производит перевод под управлением программы-транслятора. Процесс перевода программы на язык машинных команд называется трансляцией. Прежде чем выполнить, например, программу на Паскале, ее нужно оттранслировать. Трансляцию можно представить как спуск с верхней ступеньки языка на самую первую ступеньку — ЯМК (рис. 6.18).

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

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

Язык программирования, с которым работает СП, называется ее входным языком. Системы программирования именуются по названию своего входного языка. Например: «Система Бейсик», «Система Паскаль», «Система Фортран». Иногда в название систем включаются префиксы, обозначающие, например, ее фирменное происхождение. Очень популярны системы с приставкой «Турбо»: Турбо Паскаль, Турбо С и др. Это системы программирования, разработанные фирмой Borland.

О двух способах трансляции

Реализовать тот или иной язык программирования на компьютере — это значит создать транслятор с этого языка для данного компьютера. Существуют два принципиально различных метода трансляции. Они называются «компиляция» и «интерпретация».

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

1) полный предварительный перевод: лектор заранее передает текст выступления переводчику, тот записывает перевод, размножает его и раздает слушателям (после этого лектор может уже и не выступать);
2) синхронный перевод: лектор читает доклад, переводчик одновременно с ним, слово за словом, переводит выступление.

Компиляция является аналогом полного предварительного перевода; интерпретация — аналог синхронного перевода. Транслятор, работающий по принципу компиляции, называется компилятором. Транслятор, работающий методом интерпретации, называется интерпретатором.

Работа компилятора

При компиляции в память компьютера загружается программа-компилятор. Она воспринимает текст программы на ЯПВУ как исходную информацию. Компилятор производит синтаксический контроль программы и при обнаружении ошибок выводит диагностические сообщения. Если ошибок нет, то результатом компиляции является программа на языке машинных команд.

Затем компилятор удаляется из оперативной памяти. В памяти остается только программа на ЯМК, которая выполняется для получения результатов.

На рис. 6.19 схематически показан процесс выполнения программы на ЯПВУ с использованием компиляции. Прямоугольниками изображены программы в машинных кодах, овалами — обрабатываемая и конечная информация.

Конечно, компиляция с автокода-ассемблера много проще, чем с языков высокого уровня. Для этой процедуры часто применяют специальный термин — ассемблирование. А под словом «ассемблер» понимается не только язык программирования, но и транслятор с него.

Работа интерпретатора

Интерпретатор в течение всего времени работы программы находится во внутренней памяти (иногда для этого используется ПЗУ). В ОЗУ помещается программа на ЯПВУ. Интерпретатор «читает» ее первый оператор, переводит его в машинные команды и тут же организует выполнение этих команд. Затем переходит к переводу и выполнению следующего оператора и так до конца программы. При этом результаты предыдущих переводов в памяти не сохраняются. При повторном выполнении одного и того же оператора в цикле он снова будет транслироваться. Перед трансляцией каждого оператора происходит его синтаксический анализ.

На рис. 6.20 схематически показан процесс выполнения программы на ЯПВУ с использованием интерпретатора.

Таким образом, при компиляции трансляция и исполнение программы идут последовательно друг за другом. При интерпретации — параллельно.

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

Из-за указанных причин использование компиляторов удобнее для больших программ, требующих быстрого счета и большого объема памяти. Программы на Паскале, Си, Фортране всегда компилируются. Язык Бейсик часто реализуется через интерпретатор.

Коротко о главном

Для разработки программ управления компьютером программисты используют системы программирования (СП),

Язык программирования, с которым позволяет работать данная СП, называется ее входным языком.

Язык процессора компьютера — это язык машинных команд — ЯМК.

Уровень языка программирования определяется степенью его удаленности от ЯМК (чем дальше, тем выше уровень).

Автокод (ассемблер) — это машинно-ориентированный язык символического программирования.

Наиболее удобным средством программирования являются языки высокого уровня (ЯПВУ). Сегодня с ними работает большинство программистов.

Трансляция — это процесс перевода текста программы на язык машинных команд. Программа-переводчик называется транслятором.

Существуют два способа трансляции: компиляция и интерпретация. При компиляции сначала весь текст программы переводится на ЯМК, затем производится ее исполнение. При интерпретации перевод и исполнение происходят параллельно.

Вопросы и задания

1. Что такое язык программирования?
2. Что обозначает понятие «уровень языка программирования»?
3. К какому уровню относятся языки типа «автокод-ассемблер»?
4. Почему языки программирования высокого уровня называют машинно-независимыми языками?
5. Какие из языков программирования высокого уровня вы знаете?
6. Что такое трансляция? Что такое транслятор?
7. В чем различие между компиляцией и интерпретацией?'

И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Информатика, 9 класс
Отослано читателями из интернет-сайтов

_{Планы уроков информатики, скачать тесты бесплатно, всё для учителя и школьника в подготовке к уроку по информатике 9 класс, домашние задания, вопросы и ответы}

Содержание урока
 конспект урока                       
 опорный каркас  
 презентация урока
 акселеративные методы 
 интерактивные технологии 

Практика
 задачи и упражнения 
 самопроверка
 практикумы, тренинги, кейсы, квесты
 домашние задания
 дискуссионные вопросы
 риторические вопросы от учеников

Иллюстрации
 аудио-, видеоклипы и мультимедиа 
 фотографии, картинки 
 графики, таблицы, схемы
 юмор, анекдоты, приколы, комиксы
 притчи, поговорки, кроссворды, цитаты

Дополнения
 рефераты
 статьи 
 фишки для любознательных 
 шпаргалки 
 учебники основные и дополнительные
 словарь терминов                          
 прочие 

Совершенствование учебников и уроков
 исправление ошибок в учебнике
 обновление фрагмента в учебнике 
 элементы новаторства на уроке 
 замена устаревших знаний новыми 

Только для учителей
 идеальные уроки 
 календарный план на год  
 методические рекомендации  
 программы
 обсуждения


Интегрированные уроки

Если у вас есть исправления или предложения к данному уроку, напишите нам.

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