Для того, чтобы получить доступ к файлу, находящемуся на жёстком диске системы, необходимо знать его адрес. Адресация пути файла бывает абсолютной и относительной. В случае абсолютной адресации путь к файлу указывается, начиная с корневого каталога и далее вглубь по дереву каталогов до требуемого файла. Например, в ОС Windows абсолютный пусть к файлу apple.doc может выглядеть так: D:\яблоня\ветка\apple.doc. Диск здесь имеет имя `D`, корневой каталог имеет обозначение D:\, имена каталогов разделены знаком «\». При относительной адресации путь к каталогу указывается, начиная с текущего каталога. Например, относительный путь файла apple.doc относительно папки «яблоня» выглядит так: ветка\apple.doc.
Выбирая между абсолютной и относительной адресацией, удобней пользоваться тем адресом, длина которого короче.
В корневом каталоге файловой системы Linux находятся каталоги bin, home и другие. Пусть в каталоге bin находится каталог chess, а в каталоге home находятся каталоги tmp и user. В каталоге user был создан подкаталог pictures и в него помещён файл ivan.jpg. Как выглядит относительный путь из каталога bin к файлу ivan.jpg? Как выглядит абсолютный путь?
Примечание. В системе Linux при перемещении по каталогам используются следующие обозначения: «.» или
« » (пусто) - знак перехода в текущий каталог, «..» - знак перехода в каталог на уровень выше, «/» - знак, обозначающий корневой каталог, а так же разделяющий последовательность каталогов в обозначении пути файла или каталога.
Для удобства изобразим диаграмму дерева каталогов. Следуя обозначениям, применяемым в системе адресации Linux, абсолютный адрес файла в созданном каталоге pictures следующий: /home/user/pictures/ivan.jpg. Относительный адрес из каталога chess таков: ../../home/user/pictures/ivan.jpg
Пользователь ОС Windows, перемещаясь из одного каталога в другой, последовательно посетил каталоги икт, задания, D:\, классы, 10Б. Каково полное имя каталога (абсолютный адрес каталога), из которого начал перемещение пользователь?
Корневым каталогом является каталог D:\. Перемещаясь последовательно по дереву каталогов от корневого каталога в направлении начального каталога, получаем, что начальный каталог: D:\задания\икт.
Первые ФС были одноуровневыми, то есть все файлы хранились в одном каталоге. С увеличением ёмкости носителей и размера информации это стало неудобным, поэтому были разработаны иерархические (многоуровневые) файловые системы. В таких системах каталог, который не является подкаталогом ни одного другого каталога, называется корневым каталогом. Корневой каталог содержит файлы и каталоги первого уровня, каждый из которых может содержать файлы и каталоги второго уровня и так далее. Такая структура называется деревом каталогов.
Заметим, что иногда понятие каталога заменяют понятием папки, что не всегда правильно. Каталог определяется адресом, по которому он находится на носителе информации. Папка же является графическим отображением каталога, созданным операционной системой.
В настоящее время существует несколько основных типов файловых систем: дисковые файловые системы (ReFS, FAT, ExFAT, NTFS, ext`bb2`, ext`bb3`, ext`bb4`, APFS, HFS, HFS+), распределённые (сетевые) и распределённые параллельные файловые системы.
Рассмотрим логическую структуру одной из самых распространённых дисковых файловых систем FAT. Она состоит из загрузочного кластера, таблицы размещения файлов, корневого каталога и файлов. При записи файла всегда занимается целое количество кластеров, при этом файл записывается в произвольные свободные кластеры. Полная информация о кластерах, которые занимают файлы, содержится в таблице размещения файлов FAT, при этом количество ячеек таблицы равно полному количеству кластеров. Значениями ячеек таблицы являются последовательности адресов кластеров, в которых хранятся файлы. Поясним сказанное на примере 2:
Пусть диск с файловой системой FAT состоит из `20` кластеров (см. Табл. 1). На диск записан файл, и он размещён в кластерах под номерами `5`, `6`, `12` и `19`. Тогда цепочка размещения файла будет следующей: в `5`-ой ячейке хранится адрес `6`-ой ячейки, в `6`-ой ячейке – адрес `12`-ой, в `12`-ой ячейке хранится адрес `19`-ой, а в `19`-ой хранится знак конца файла.
|
`1` |
`2` |
`3` |
`4` |
`5` `bb"6"` |
`6` `bb"12"` |
`7` |
`8` |
`9`
|
`10`
|
|
`11` |
`12` `bb"19"` |
`13` |
`14` |
`15` |
`16` |
`17` |
`18` |
`19` К |
`20` |
Табл. 1. Пример размещения файла в файловой таблице FAT.
Для работы распространённых операционных систем (OC) Windows, Linux и Mac OS существуют разнообразные файловые системы, отличающиеся друг от друга размерами кластеров, структурой упорядочивания информации на носителе и системой безопасности данных.
Дисковые ФС, такие как FAT`bb"12"`, FAT`bb"16"`, FAT`bb"32"` предназначаются для OC Windows. Альтернативами файловой системе FAT для ОС Windows являются широко распространенная файловая система NTFS и её современная модификация ReFS. Для работы ОС Linux в настоящее время широко используются файловые системы Ext`bb2`, Ext`bb3` и Ext`bb4`. Для работы ОС Mac OS сегодня используется файловая система APFS, пришедшая на замену системам HFS и HFS+.
Одним из свойств современных файловых систем является журналируемость. Журналируемые системы обеспечивают сохранение списка изменений файловой системы, позволяющего восстановить информацию при сбоях в работе компьютера. Среди перечисленных файловых систем журналируемыми являются NTFS, Ext`4` и HFS+.
В файловой системе FAT`12`, для хранения адреса кластера выделяется `12` бит. Поэтому максимальное количество адресуемых кластеров в системе равно `2`^`12 = 4096`. Размер кластера равен `512` байтам, соответственно максимальный объём информации, хранимой в FAT`12`, равен `2` Мбайтам.
Здесь и в последующем для обозначения крупных единиц измерения информации используются двоичные приставки такие как:
`1` кибибайт (Кбайт) `= 1024` байт;
`1` мебибайт (Мбайт) `= 1024` Кбайт;
`1` гибибайт (Гбайт) `= 1024` Мбайт;
`1` тебибайт (Тбайт) `= 1024` Гбайт;
`1` пебибайт (Пбайт) `= 1024` Тбайт и т. д.
В файловой системе FAT`16` для хранения адреса кластера выделяется `16` бит. Максимальное количество адресуемых кластеров соответственно равно `2`^`16 =65536`. Максимальный размер кластера равен `64` Кбайтам (кибибайтам), поэтому максимальный объём информации, хранимой с помощью FAT`16`, равен `4` Гбайтам (гибибайтам). Файловая система FAT`16` широко используется в картах памяти фотоаппаратов.
В файловой системе FAT`32` под адрес кластера выделяется `32` бита. Максимальный размер кластера равен `4` Кбайтам, поэтому максимальный объём информации, хранимой с помощью FAT`32`, равен `16` Тбайтам (тебибайтам). Это позволяет использовать FAT`32` на жёстких дисках самого большого размера.
Файловая система NTFS способна устанавливать различный объём кластера. В отличие от FAT, как было сказано выше, NTFS является журналируемой файловой системой, что делает её более надёжной.
Помимо дисковых файловых систем существуют файловые системы, предоставляющие доступ к файлам на удалённых компьютерах. Они называются распределёнными или сетевыми файловыми системами. Сетевые файловые системы часто используются на кластерах, применяемых для многопроцессорных вычислений.
это система хранения и структурирования некоторого произвольного множества данных на электронном носителе в форме, удобной для восприятия человека. Файловая система распределяет данные на носителе информации и предоставляет операционной системе доступ к этим данным. В наиболее распространённых файловых системах (FAT и NTFS) минимальным элементом носителя информации является кластер. Размер кластера может различаться в зависимости от типа файловой системы. Минимальный размер кластера равен `512` байтам. Упорядоченная совокупность кластеров, хранящаяся на носителе информации под общим названием, образует файл. Для удобства хранения информации, файлы группируются в файлы, называемые каталогами. Каталог может содержать также данные в виде других каталогов, называемых подкаталогами. Отметим, что каждому файлу выделяется целое число кластеров. Если даже кластер занят частично, остальная часть пространства кластера так же считается занятой.
На жёстком диске с файловой системой FAT`32` размер кластера составляет `4` Кбайта. На диск были записаны три файла размерами `32`, `12027` и `8102` байт. Сколько кластеров необходимо для хранения трёх файлов?
Каждый файл занимает целое количество кластеров. Первый файл занимает `1` кластер, второй – `3`, а третий – `2`. Итого, общее количество кластеров равно `6`. Отметим, что было бы ошибкой найти общий размер файлов, поделив его на размер одного кластера.
Любой файл обладает названием, которое состоит из двух частей: собственно имени файла и так называемого расширения файла.
это часть названия файла, определяющая тип данных, хранящихся в данном файле. Расширение и имя файла разделяются точкой
Как было показано выше в примере 7, электронная таблица позволяет автоматически пересчитывать значения ячеек при изменении исходных данных. Однако табличные процессоры позволяют вычислять значения не только в старых, но и в новых ячейках по формулам, ранее введённым в другие ячейки. Данное свойство табличного процессора напрямую связано с разными видами адресаций ячеек в таблице, о которых пойдёт речь дальше.
Адреса ячеек, использующиеся в формулах ЭТ, могут быть трёх видов – абсолютными, относительными и смешанными. Рассмотрим каждый из них.
 |
В случае относительной адресации адреса ячеек, используемые в формулах, определены относительно места расположения формулы. При копировании формулы в новое положение таблицы адреса используемых в формуле ячеек меняются соответственно новому месту положения формулы. Например, в таблице на рисунке справа формулу в ячейке `"C"1` табличный процессор воспринимает так: умножить значение ячейки, расположенной на две ячейки левее на значение ячейки, расположенной на одну ячейку левее данной формулы. Тогда при копировании формулы в ячейку `"C"2` табличный процессор умножит значение ячейки `"A"2` на значение ячейки `"B"2`. Преимущество относительной адресации состоит в том, что при копировании ячейки в новое положение ссылки в копируемой формуле меняются автоматически. Однако на практике бывает так, что адрес ячейки, используемой в формуле, не должен меняться при копировании. В этом случае используется абсолютная адресация. В абсолютных адресах перед неизменяемым значением адреса ячейки ставится знак `$`, например `$"B"$2` – это абсолютный адрес ячейки `"B"2`. Поясним преимущества относительного адреса и использование абсолютного адреса на следующем примере.
Турфирма «Кругосвет» предоставляет путевки в Грецию, на Мальту и в Италию по ценам, указанным в долларах США. Составьте формулу для расчёта цен путёвок в европейской валюте ЕВРО согласно курсу, указанному в таблице.
Составим формулу расчёта цены путёвки в Грецию в ячейке `"C"4` так, чтобы, скопировав её в ячейки `"C"5` и `"C"6`, можно было автоматически вычислить значения цены на путёвки на Мальту и в Италию. Положение ячейки `"B"1` относительно ячеек `"C"4`, `"C"5` и `"C"6` различное, значит необходимо, чтобы в формуле `"C"4` адрес ячейки `"B"1` был абсолютным. Положение ячеек `"B"4`, `"B"5` и `"B"6` относительно `"C"4`, `"C"5`, `"C"6` одинаковое, а значит, адрес ячейки `"B"4` в формуле должен быть относительным. Тогда выражение `="B"4^(**)$"B"$1` является формулой расчёта цены путёвки в Грецию. Использование относительного адреса `"B"4` и абсолютного адреса `$"B"$1` позволяет скопировать формулу в ячейки `"C"5` и `"C"6` и автоматически вычислить цены путёвок в остальные страны.
В формулах возможно использование смешанной адресации, при которой один из компонентов адреса абсолютный, а другой - относительный. Например, в адресе `"B"$2` компонент по столбцу относительный, а компонент по строке абсолютный.
В ячейке `"B"1` электронной таблицы находится формула `="E"1+`$`"E"2`. Какой вид приобретёт формула после того, как содержимое ячейки `"B"1` скопируют в ячейку `"C"1`?
Так как относительное положение ячейки по строкам не изменилось, и в формуле используется относительная адресация по строкам, то строковая компонента нового адреса остаётся прежней и имеет вид `="X"1+"Y"2`, где адрес по столбцам `"X"` и `"Y"` необходимо определить. Адрес столбца ячейки `"E"1` относительный, и так как ячейка `"B"1` копируется в `"C"1` со смещением в один столбец вправо, то новый адрес столбца ячейки `"E"1` будет `"F"`. Адрес столбца ячейки `$"E"2` абсолютный, значит, он остаётся неизменным и равным `"E"`. Итак, получаем, что формула в новой ячейке принимает вид `="F"1+`$`"E"2`.
В ячейке `"C"2` записана формула `=$"B"$3+"D"2`. Какой вид она приобретёт после того, как содержимое ячейки `"C"2` скопируют в ячейку `"B"1`?
Адрес первой ячейки `$"B"$3` абсолютный, значит, он не изменится. Адрес ячейки `"D"2` относительный по строке и по столбцу. Ячейка `"D"2` располагается в той же строке, что и ячейка `"C"2`, но в другом столбце `"D"` со смещением вправо на один столбец. Значит, адрес столбца ячейки `"D"2` в ячейке `"B"1` станет C, а по строке станет `1`, и полный вид формулы будет выглядеть `=$"B"$3+"C"1`.
В электронных таблицах широко используются логические выражения, такие как IF()/ЕСЛИ(), NOT/НЕ, логическое умножение AND()/И() и логическое сложение OR/ИЛИ. При работе с формулами в электронной таблице возможно использование функций, подобно использованию функций во многих языках программирования. Функция характеризуется названием, предназначением, количеством аргументов, типом аргументов и типом возвращаемого значения. Приведём пример часто используемых функций.
|
Функции и логические выражения |
Англоязычная форма |
Русифицированная форма |
|
Среднее арифметическое |
AVERAGE `("A"1:"A"5)` |
СРЗНАЧ `("A"1:"A"5)` |
|
Сумма |
SUM `("A"1:"A"5)`) |
СУММ `("A"1:"A"5)` |
|
Максимальное значение |
MAX `("A"1:"A"5)` |
МАКС `("A"1:"A"5)` |
|
Минимальное значение |
MIN `("A"1:"A"5)` |
МИН `("A"1:"A"5)` |
|
Остаток от деления |
MOD`("A"1:"A"2)` |
ОСТАТ `("A"1:"A"2)` |
|
Целая часть числа |
INT `("A"1)` |
ЦЕЛОЕ `("A"1)` |
| Табл. 3 | ||
Из функций в таблице выше функция `"MOD"` `("A"1;"A"2)` – это функция, возвращающая остаток от деления числа, хранящегося в ячейке `"A"1`, на делитель, хранящийся в ячейке `"A"2`. При этом результат имеет тот же знак, что и делитель.
Как показано в следующем примере, с помощью функций и диапазонов ячеек можно производить вычисления по формулам для группы ячеек.
В электронной таблице значение формулы `="AVERAGE"` `("A"1:"A"3)` равно `5`. А значение формулы `="SUM"` `("A"1:"A"2)` равно `2`. Чему равно значение ячейки `"A"3`?
Среднее значение `"A"1`, `"A"2`, `"A"3` равно `5`, что значит `"A"1+"A"2+"A"3=15`.
Тогда `"A"3` равно `15-("A"2+"A"1)=15-2=13`.
`"A"3 =13`.
Дмитрий, Мария и Андрей сдавали два теста по биологии. Чтобы сдать их успешно, необходимо было получить за каждый тест не меньше `35` баллов и в сумме не меньше `80`. В таблице ниже приведены результаты тестов. Какую формулу нужно написать для ячейки `"D"2`?
Примечание. В случае условных вычислений часто используется логическое выражение IF(усл; рез_и; рез_л). Русским эквивалентов выражения IF является выражение ЕСЛИ. В логическом выражении IF, как и в других выражениях с более, чем одним аргументом, аргументы разделяются знаком точка с запятой. Первым аргументом функции IF является проверяемое условие. Второй аргумент «рез_и» – это результат логического выражения IF, если проверяемое условие истинно. И третий аргумент «рез_л» – это результат выражения IF, если проверяемое условие ложно.
Алгоритм вычисления значения ячейки `"D"2` может выглядеть так: «если `"B"2>``=35`,
`"C"2>` `=35` и `"B"2+"C"2>``=80`, то записать в ячейку `"D"2` «успешно», если нет – «не успешно». Воспользуемся логическими выражениями IF и AND. Логическое умножение AND() истинно, если все его аргументы истины. Тогда формула в ячейке `"D"2` выглядит:
`="IF"("AND"("B"2>``=35;` `"C"2>``=35;` `("B"2+"C"2)>``=80);` "успешно"; "неуспешно").
Так как адреса в формуле имеют относительный вид, то путём копирования формулы из ячейки `"D"2` мы свободно можем применить формулу для ячеек `"D"3` и `"D"4`.
При работе с упорядоченными массивами данных табличная форма представления информации является одной из наиболее удобных.
это компьютерный эквивалент обычной таблицы, состоящей из строк и столбцов, на пересечении которых располагаются клетки, содержащие числовую информацию, формулы и текст. ЭТ устроeна так, что после создания новых данных, зависящих от уже существующих данных таблицы, изменение исходных данных ведёт к мгновенному изменению новых данных. В последующих примерах мы подробно рассмотрим данное свойство таблицы.
называются прикладные программы, позволяющие пользователю обрабатывать и анализировать электронные таблицы. Существует большое количество различных табличных процессоров: VisiCalc, Microsoft Excel, SuperCalc, Multiplan и другие. Основное назначение табличного процессора состоит в автоматизации расчётов в табличной форме. Любой ТП обладает следующими функциями:
1) редактирование и добавление новой информации в ЭТ;
2) создание данных, зависящих от исходных данных, с целью анализа и обработки исходных данных;
3) графическое представление информации в виде графика или диаграмм.
Табличные процессоры представляют собой удобное средство для проведения статистических, бухгалтерских и инженерных расчётов. В состав ТП входят сотни встроенных математических функций и алгоритмов статистической обработки данных. В данном задании будет рассказано о наиболее важных свойствах электронных таблиц и на примерах будет показано их применение.
Большинство табличных процессоров имеет схожую структуру. Поэтому, изучив один из табличных процессоров, можно легко освоить работу с другими. В данном задании мы рассмотрим ТП Microsoft Excel.
 |
Основными элементами электронной таблицы являются столбцы и строки. Пересечение строки и столбца образует минимальный элемент электронной таблицы, называемый ячейкой. Каждая ячейка обладает адресом (ссылкой), который состоит из названия столбца, состоящего из латинских букв, и номера строки, состоящего из чисел. Столбцы в электронной таблице располагаются в алфавитном порядке, а строки – в порядке возрастания числа, как изображено на рисунке справа. Так, например, ячейка, располагающаяся в столбце «`"B"`» и строке «`2`», имеет адрес `"B"2` соответственно.
 |
В электронной таблице возможна работа с выборочным множеством данных. Для этой цели ячейку с необходимыми данными можно выделить курсором в виде рамки. Выделенная ячейка называются активной. Выделенная область прямоугольной формы, состоящая из нескольких ячеек, называется диапазоном ячеек. Пример двух диапазонов изображён на рисунке справа. Диапазон обозначается с помощью двоеточия, разделяющего адреса ячеек, которые располагаются в противоположных углах прямоугольной области, например `bb"A1":bb"B2"` и `bb"D2":bb"E3"`. Два диапазона, изображённые на рисунке, также могут образовывать один общий диапазон, обозначающийся с помощью точки с запятой `bb"A1":bb"B2"`;`bb"D2":bb"E3"`.
В электронных таблицах Micosoft Excel различаются три основных типа данных: текст, числа и формулы. Формулой в электронной таблице называется выражение, начинающееся со знака равенства и содержащее адреса ячеек таблицы, математические функции, знаки математических операций, логические символы и числа-константы. Прежде чем рассмотреть текстовый и числовой типы данных, отметим, что данные таблицы распознаются табличным процессором согласно заданному в ячейке формату. Форматов ячеек ТП Microsoft Excel существует несколько: общий, текстовый, числовой, денежный, финансовый, формат дат и времени, процентный, дробный, экспоненциальный и специальный.
это формат ячейки для отображения и работы с числовыми значениями в виде последовательности цифр, которые могут быть разделены десятичной запятой и начинаться с цифры, знака числа («`+`» либо «`-`») или десятичной запятой. Например, `237,45` или `-12,1`.
это формат ячейки для отображения и работы с числовыми значениями в экспоненциальном представлении. Числа в экспоненциальном формате представляются в виде `x"E"+-n`, где `x` — целое число или десятичная дробь, `n` — целое число. Пример, `1,2"E"+5` или `1,225"E"+5`.
это формат ячейки для отображения и работы с денежными величинами в заранее заданной пользователем валюте. Например, `342,23`р. или `12,2634`р.
это формат ячейки использующийся для почтовых индексов, номеров телефонов и табельных номеров.
Итак, мы выяснили, что каждому формату ячеек соответствует определённый формат данных.
данных включает в себя следующие форматы данных: числовой, экспоненциальный, дробный, процентный, денежный, финансовый, специальный, формат дат и времени.
И наконец,
это тип данных, не являющихся формулой или числом. В отличие от формул и числовых данных текстовые данные не используются в вычислениях и служат только для отображения информации.
это формат, использующийся по умолчанию такой, что табличный процессор автоматически определяет формат ячейки в зависимости от вида находящихся в ячейке данных.
Числа, даты, время, проценты, финансы, денежные значения, дробные и экспоненциальные числа и специальные данные табличный процессор выравнивает по правому краю ячейки, а текст - по левому. Необходимо помнить, что если формат ячейки текстовый, и в ячейке хранится последовательность цифр, то этот набор цифр ТП Microsoft Excel будет распознавать как текст.
Итак, табличный процессор распознаёт содержимое ячейки в зависимости от выбранного формата ячейки. Пусть, в ячейке содержатся следующие цифры: `230199`. Если в ячейке установлен текстовый формат, цифры будут восприняты как символы `2`, `3`, `0`, `1`, `9`, `9`. Они же могут быть проинтерпретированы табличным процессором как число, если установлен числовой формат. Если же в ячейке установлен общий формат, то цифры будут распознаны как число `230199`.
Как было сказано выше, помимо чисел и текста в электронной таблице используются формулы. Ячейка, содержащая формулу, отображает текущее значение формулы. Поясним работу с формулой на следующем примере.
В ячейку `"A"2` таблицы (см. Ввод формулы ) введена формула `="B"1+"C"3**"B"1`. Какое значение отобразиться в ячейке `"A"2`? Измениться ли значение формулы, если изменить значение ячейки `"B"1` на `4`?
 |
 |
| Табл. 2 | |
Формула обеспечивает сложение числа, хранящегося в ячейке `"B"1`, с числом, хранящимся в ячейке `"C"3`, умноженным на число, хранящееся в ячейке `"B"1`. Таким образом в ячейке `"A"2` появиться число `3+2^(**)3= 9`.
В электронной таблице можно автоматически найти значение формулы для других исходных данных, только лишь изменив исходные данные на новые. Например, изменив значение ячейки `"B"1` на `4`, в ячейке `"A"2` автоматически отобразиться новое значение `4+2^(**)4= 12`.
Для групповых операций с файлами часто используются маски имён файлов. Например, при поиске конкретного файла среди большого количества других файлов, использование маски имён может существенно сократить время поиска. Маска представляет собой последовательность букв, цифр и других символов наряду со специальными символами «?», «*». Символ «?» означает один и только один произвольный символ. Символ «*» означает любую последовательность символов произвольной длины, включая пустую последовательность. Рассмотрим задачу поиска файла по маске среди некоторого множества файлов.
Определите, какие из нижеперечисленных имён файлов удовлетворяют маске: ?a*l*e.txt
1) variable.txt
2) label.txt
3) apple.txt
4) sample.txt
Рассмотрим маску ?a*l*e.txt посимвольно. В маске знак «?» может означать один любой непустой символ. Поэтому, из всех четырёх вариантов 3-ий вариант исключается сразу, так как букве «a» в слове “apple” не предшествует какой-либо символ. За следующим знаком «*» следует буква «l», знак «*» и «e.txt». Вариант 2 исключается, так как label.txt заканчивается символами «l.txt», а не «e.txt». Знак «звёздочка» означает любое количество произвольных символов, включая отсутствие символа (пустой символ). Поэтому данной маске удовлетворяют первый и последний варианты ответов.
В некотором каталоге находятся следующие файлы:
programma_01.cpp, proga_gf.c,pfa_09.com, ptua_09.cx, pasa_pp.cfg.
Каким маскам удовлетворяют все эти файлы?
1) p*a_??.c*
2) p*a_*.c*
3) p?_*.c??
4) p?a_??.c*
Вариант номер 4 исключается из рассмотрения первым потому, что знак «?», следующий после буквы «p», требует наличия только одного символа перед буквой «а». Как минимум один файл programma_01.cpp этой маске не соответствует. Маска под номером 3 не соответствует ни одному файлу потому, что за буквой «p» должен следовать только один символ перед знаком «_». Остальные два варианта масок соответствуют всем файлам.
Для того, чтобы получить доступ к файлу, находящемуся на жёстком диске системы, необходимо знать его адрес. Адресация пути файла бывает абсолютной и относительной. В случае абсолютной адресации путь к файлу указывается, начиная с корневого каталога и далее вглубь по дереву каталогов до требуемого файла. Например, в ОС Windows абсолютный пусть к файлу apple.doc может выглядеть так: D:\яблоня\ветка\apple.doc. Диск здесь имеет имя `D`, корневой каталог имеет обозначение D:\, имена каталогов разделены знаком «\». При относительной адресации путь к каталогу указывается, начиная с текущего каталога. Например, относительный путь файла apple.doc относительно папки «яблоня» выглядит так: ветка\apple.doc.
Выбирая между абсолютной и относительной адресацией, удобней пользоваться тем адресом, длина которого короче.
В корневом каталоге файловой системы Linux находятся каталоги bin, home и другие. Пусть в каталоге bin находится каталог chess, а в каталоге home находятся каталоги tmp и user. В каталоге user был создан подкаталог pictures и в него помещён файл ivan.jpg. Как выглядит относительный путь из каталога bin к файлу ivan.jpg? Как выглядит абсолютный путь?
Примечание. В системе Linux при перемещении по каталогам используются следующие обозначения: «.» или
« » (пусто) - знак перехода в текущий каталог, «..» - знак перехода в каталог на уровень выше, «/» - знак, обозначающий корневой каталог, а так же разделяющий последовательность каталогов в обозначении пути файла или каталога.
Для удобства изобразим диаграмму дерева каталогов. Следуя обозначениям, применяемым в системе адресации Linux, абсолютный адрес файла в созданном каталоге pictures следующий: /home/user/pictures/ivan.jpg. Относительный адрес из каталога chess таков: ../../home/user/pictures/ivan.jpg
Пользователь ОС Windows, перемещаясь из одного каталога в другой, последовательно посетил каталоги икт, задания, D:\, классы, 10Б. Каково полное имя каталога (абсолютный адрес каталога), из которого начал перемещение пользователь?
Корневым каталогом является каталог D:\. Перемещаясь последовательно по дереву каталогов от корневого каталога в направлении начального каталога, получаем, что начальный каталог: D:\задания\икт.
Первые ФС были одноуровневыми, то есть все файлы хранились в одном каталоге. С увеличением ёмкости носителей и размера информации это стало неудобным, поэтому были разработаны иерархические (многоуровневые) файловые системы. В таких системах каталог, который не является подкаталогом ни одного другого каталога, называется корневым каталогом. Корневой каталог содержит файлы и каталоги первого уровня, каждый из которых может содержать файлы и каталоги второго уровня и так далее. Такая структура называется деревом каталогов.
Заметим, что иногда понятие каталога заменяют понятием папки, что не всегда правильно. Каталог определяется адресом, по которому он находится на носителе информации. Папка же является графическим отображением каталога, созданным операционной системой.
В настоящее время существует несколько основных типов файловых систем: дисковые файловые системы (ReFS, FAT, ExFAT, NTFS, ext`bb2`, ext`bb3`, ext`bb4`, APFS, HFS, HFS+), распределённые (сетевые) и распределённые параллельные файловые системы.
Рассмотрим логическую структуру одной из самых распространённых дисковых файловых систем FAT. Она состоит из загрузочного кластера, таблицы размещения файлов, корневого каталога и файлов. При записи файла всегда занимается целое количество кластеров, при этом файл записывается в произвольные свободные кластеры. Полная информация о кластерах, которые занимают файлы, содержится в таблице размещения файлов FAT, при этом количество ячеек таблицы равно полному количеству кластеров. Значениями ячеек таблицы являются последовательности адресов кластеров, в которых хранятся файлы. Поясним сказанное на примере 2:
Пусть диск с файловой системой FAT состоит из `20` кластеров (см. Табл. 1). На диск записан файл, и он размещён в кластерах под номерами `5`, `6`, `12` и `19`. Тогда цепочка размещения файла будет следующей: в `5`-ой ячейке хранится адрес `6`-ой ячейки, в `6`-ой ячейке – адрес `12`-ой, в `12`-ой ячейке хранится адрес `19`-ой, а в `19`-ой хранится знак конца файла.
|
`1` |
`2` |
`3` |
`4` |
`5` `bb"6"` |
`6` `bb"12"` |
`7` |
`8` |
`9`
|
`10`
|
|
`11` |
`12` `bb"19"` |
`13` |
`14` |
`15` |
`16` |
`17` |
`18` |
`19` К |
`20` |
Табл. 1. Пример размещения файла в файловой таблице FAT.
Для работы распространённых операционных систем (OC) Windows, Linux и Mac OS существуют разнообразные файловые системы, отличающиеся друг от друга размерами кластеров, структурой упорядочивания информации на носителе и системой безопасности данных.
Дисковые ФС, такие как FAT`bb"12"`, FAT`bb"16"`, FAT`bb"32"` предназначаются для OC Windows. Альтернативами файловой системе FAT для ОС Windows являются широко распространенная файловая система NTFS и её современная модификация ReFS. Для работы ОС Linux в настоящее время широко используются файловые системы Ext`bb2`, Ext`bb3` и Ext`bb4`. Для работы ОС Mac OS сегодня используется файловая система APFS, пришедшая на замену системам HFS и HFS+.
Одним из свойств современных файловых систем является журналируемость. Журналируемые системы обеспечивают сохранение списка изменений файловой системы, позволяющего восстановить информацию при сбоях в работе компьютера. Среди перечисленных файловых систем журналируемыми являются NTFS, Ext`4` и HFS+.
В файловой системе FAT`12`, для хранения адреса кластера выделяется `12` бит. Поэтому максимальное количество адресуемых кластеров в системе равно `2`^`12 = 4096`. Размер кластера равен `512` байтам, соответственно максимальный объём информации, хранимой в FAT`12`, равен `2` Мбайтам.
Здесь и в последующем для обозначения крупных единиц измерения информации используются двоичные приставки такие как:
`1` кибибайт (Кбайт) `= 1024` байт;
`1` мебибайт (Мбайт) `= 1024` Кбайт;
`1` гибибайт (Гбайт) `= 1024` Мбайт;
`1` тебибайт (Тбайт) `= 1024` Гбайт;
`1` пебибайт (Пбайт) `= 1024` Тбайт и т. д.
В файловой системе FAT`16` для хранения адреса кластера выделяется `16` бит. Максимальное количество адресуемых кластеров соответственно равно `2`^`16 =65536`. Максимальный размер кластера равен `64` Кбайтам (кибибайтам), поэтому максимальный объём информации, хранимой с помощью FAT`16`, равен `4` Гбайтам (гибибайтам). Файловая система FAT`16` широко используется в картах памяти фотоаппаратов.
В файловой системе FAT`32` под адрес кластера выделяется `32` бита. Максимальный размер кластера равен `4` Кбайтам, поэтому максимальный объём информации, хранимой с помощью FAT`32`, равен `16` Тбайтам (тебибайтам). Это позволяет использовать FAT`32` на жёстких дисках самого большого размера.
Файловая система NTFS способна устанавливать различный объём кластера. В отличие от FAT, как было сказано выше, NTFS является журналируемой файловой системой, что делает её более надёжной.
Помимо дисковых файловых систем существуют файловые системы, предоставляющие доступ к файлам на удалённых компьютерах. Они называются распределёнными или сетевыми файловыми системами. Сетевые файловые системы часто используются на кластерах, применяемых для многопроцессорных вычислений.
это система хранения и структурирования некоторого произвольного множества данных на электронном носителе в форме, удобной для восприятия человека. Файловая система распределяет данные на носителе информации и предоставляет операционной системе доступ к этим данным. В наиболее распространённых файловых системах (FAT и NTFS) минимальным элементом носителя информации является кластер. Размер кластера может различаться в зависимости от типа файловой системы. Минимальный размер кластера равен `512` байтам. Упорядоченная совокупность кластеров, хранящаяся на носителе информации под общим названием, образует файл. Для удобства хранения информации, файлы группируются в файлы, называемые каталогами. Каталог может содержать также данные в виде других каталогов, называемых подкаталогами. Отметим, что каждому файлу выделяется целое число кластеров. Если даже кластер занят частично, остальная часть пространства кластера так же считается занятой.
На жёстком диске с файловой системой FAT`32` размер кластера составляет `4` Кбайта. На диск были записаны три файла размерами `32`, `12027` и `8102` байт. Сколько кластеров необходимо для хранения трёх файлов?
Каждый файл занимает целое количество кластеров. Первый файл занимает `1` кластер, второй – `3`, а третий – `2`. Итого, общее количество кластеров равно `6`. Отметим, что было бы ошибкой найти общий размер файлов, поделив его на размер одного кластера.
Любой файл обладает названием, которое состоит из двух частей: собственно имени файла и так называемого расширения файла.
это часть названия файла, определяющая тип данных, хранящихся в данном файле. Расширение и имя файла разделяются точкой
В предыдущих темах мы неоднократно сталкивались с задачами обработки последовательностей (последовательностей чисел в первом задании или символов – во втором). Все подобные задачи решались по единой стратегии: мы считывали очередной элемент последовательности, обрабатывали и забывали о нём. Теперь рассмотрим пример задачи, где подобная стратегия не сработает.
Ввести последовательность из `100` целых чисел, а затем вывести эти числа в порядке возрастания.
РЕШЕНИЕ
Очевидно, что для решения этой задачи нам необходимо сохранить все введённые числа, поэтому описанная выше стратегия здесь неприменима. Так же очевидным является факт, что для хранения всех введённых чисел крайне неудобно использовать сто переменных с уникальными именами. Гораздо удобнее было бы обозначать элементы последовательности так, как это делается в математике, то есть указывать общее имя последовательности и номер элемента (например, ). Для реализации этой идеи нам нужно познакомиться с новым типом переменных – массивом.
Массив – это сложная структура элементов одного типа. Все элементы массива упорядочены по номерам. Порядковый номер элемента в массиве называется индексом элемента. Количество элементов в массиве называется размером массива. Под массив отводится непрерывный участок в оперативной памяти.
Размерность массива – это количество индексов, которое нужно указать для однозначной идентификации элемента массива. Если нужно указывать один индекс, то массив называется одномерным, если два, то двумерным и т. д. В этой главе мы будем работать исключительно с одномерными массивами.
Рассмотрим, каким образом одномерный массив описывается на языке Паскаль.
var <имя массива>: array [тип индекса] of <тип элементов>
В этой конструкции слова ARRAY и OF являются ключевыми словами языка. Задаваемое имя массива должно соответствовать правилам именования объектов в языке Паскаль, то есть, представлять из себя последовательность латинских букв, цифр и символов подчёркивания. начинающуюся с буквы или символа подчёркивания. Тип элементов массива может быть любым (integer, longint, real, boolean, char и т. д.). В качестве типа индекса мы будем использовать диапазоны целых чисел или символов. Диапазон оформляется следующим образом: записывается минимальная граница, затем дважды ставится точка и потом записывается максимальная граница. Обе границы включаются в диапазон.
Пример описания массива:
var massiv: array [1..10] of integer;
В примере описывается массив из `10` целых чисел с индексами от `1` до `10`.
Другой пример:
var massiv2: array [0..9] of integer;
В этом примере также описывается массив из `10` целых чисел, но индексы у них от `0` до `9`.
Для того, чтобы работать с элементом массива, в программе необходимо записывать имя массива и в квадратных скобках индекс интересующего нас элемента. Например, massiv[10]:=2. Этот оператор присваивает в элемент массива massiv с индексом `10` число `2`. Необходимо всегда контролировать выход за границы диапазона значений индекса. Скажем, оператор massiv2[10]:=2 является ошибкой, поскольку у массива с именем massiv2 нет элемента с индексом `10`.
Пусть у нас есть описание массива.
var a: array [1..10] of integer;
Рассмотрим возможные операции с этим объектом. Их можно разделить на две группы: операции с массивом, как с единым объектом, и операции с одним элементом массива.
В первой группе операций совсем немного – всего лишь одна! Это операция копирования массивов.
Пусть есть описание: var a,b: array [1..10] of integer
Тогда допустимыми являются следующие операторы присваивания: a:=b и соответственно b:=a. Первый из этих операторов во все элементы массива `a` запишет значения соответствующих элементов массива `b` (то есть элементов с теми же индексами). А второй оператор во все элементы массива b запишет значения соответствующих элементов массива `a`.
Необходимо помнить, что операция копирования в Паскале применима только к переменным, имеющим одинаковый тип (исключение, в real можно присваивать integer). Описанные выше массивы `a` и `b` имеют одинаковый тип. Если же описать их немного иначе:
var a: array [1..10] of integer;
var b: array [1..10] of integer;
то операция копирования будет неприменима! Несмотря на структурную эквивалентность (и то, и другое – массивы из целых чисел с индексами от `1` до `10`) Паскаль-машина считает, что это разные типы переменных, и поэтому присваивать их один другому нельзя. (Необходимо отметить, что некоторые компиляторы позволяют копирование массивов в случае структурной эквивалентности, но в рамках этого задания мы будем руководствоваться стандартом языка).
Больше с массивами как с едиными объектами нельзя делать ничего. Нельзя даже считывать и выводить их на экран одним оператором (оператор readln(a) или writeln(a) недопустим).
Перейдём к рассмотрению второй группы операций (операции с отдельными элементами массива). С каждым элементом массива можно выполнять все операции, которые применимы к обычной переменной соответствующего типа. Если элемент массива — целое число (как описано выше), то его можно использовать в арифметических выражениях, ему можно присваивать значения арифметических выражений, его можно считывать с клавиатуры и выводить на экран (например, writeln(a[4])). Если элемент массива имеет тип Boolean, то его нельзя вводить с клавиатуры, но можно присвоить ему значение true или false, использовать его в логическом выражении в качестве операнда для логической операции и т. д.
Исходя из всего вышесказанного, уже очевидно, как присвоить значения всем элементам (заполнить массив). Для массива `a` заполнение может выглядеть следующим образом:
a[1]:=1;
a[2]:=4;
a[3]:=-1000;
a[4]:=8950;
a[5]:=0;
a[6]:=78;
a[7]:=6789;
a[8]:=13;
a[9]:=222;
a[10]:=90;
Понятно, что такой способ заполнения, когда мы явным образом прописываем присваивание значения каждому элементу массива, подходит только в случае, когда массив небольшой. То есть, для массива из `20` элементов нужно будет написать `20` операторов присваивания, для массива из `200` элементов – `200` и т. д. При этом, в случае изменения исходных данных, нам нужно будет менять в программе все эти строки! Гораздо выгоднее воспользоваться оператором ввода с клавиатуры и циклом for. Тогда алгоритм заполнения массива записывается в `1` строку независимо от количества элементов в массиве! Для массива `a` алгоритм заполнения будет выглядеть так:
for i:=1 to 10 do readln(a[i]);
Индексы не всегда нужно записывать явным образом. Как показано в примере, на месте индекса можно писать и переменную или выражение соответствующего типа (типа, совпадающего с объявленным типом индекса).
Теперь пришло время познакомиться с ещё одним типом переменных, который активно используется при обработке текстов – это строка (string). Строка представляет собой последовательность символов. Размер строки варьируется от `0` до `255`. В отличие от всех остальных названий типов, слово string является зарезервированным служебным словом и, соответственно, не может использоваться в качестве имени переменных. При описании строки под неё выделяется `256` байт (по одному байту на каждый символ + нулевой байт, в котором хранится текущая длина строки). Если заранее известно, что длина строки не будет превышать какого-то количества символов (например `20`) , то это можно указать при описании переменной: var s :string[20], в квадратных скобках после слова string записывается максимальная длина строки. В этом случае под переменную будет выделен `21` байт (по одному на каждый из `20` символов + нулевой байт для текущей длины строки). Указание длины никак не влияет на совместимость типов.
Переменным типа string можно присваивать константные значения. При этом строковая константа, подобно символу, заключается в апострофы, например s:='cat'. Также их можно выводить на экран, и, что особенно приятно, вводить с клавиатуры одним оператором: (readln(s)).
Так же в задачах иногда бывают ситуации, когда строку нужно набирать постепенно (добавляя в неё по `1` символу). Для этого предусмотрена операция сложения строк (конкатенация). Например, запись s:=s+'c', означает, что к текущему значению переменной `s` справа приписывается символ 'c'. Операция s:=s+'ch' означает, что справа припишется два символа. Также можно записать такое сложение: s:='ch'+'hc'; тогда переменная `s` получит значение 'chhc'. Операция сложения строк не обладает свойством коммутативности, то есть, от перестановки мест слагаемых сумма изменяется. Если в последнем примере поменять местами слагаемые, то получится строка 'hcch'.
Ещё к строкам можно применять операции сравнения, причём все шесть, которые существуют в Паскале. Строки сравниваются посимвольно, то есть сначала первые символы, в случае их равенства вторые и т. д. Если на каком-то шаге (возможно, на первом) символ первой строки оказался больше символа второй, то первая строка считается больше второй. Если у строк совпадают все символы и длины, то строки считаются равными. Если у строк совпали все символы, но первая строка уже кончилась, а вторая – нет (например, «ветер» и «ветерок»), то вторая строка считается больше, чем первая.
Следующая интересная возможность – это работать со строкой, как с символьным массивом (массивом, элементами которого являются символы). При этом индекс имеет целый тип и всегда принадлежит диапазону от единицы до максимально заказанной длины строки (по умолчанию – `255`). К строке применимы все те же операции, что и к символьному массиву, то есть возможность получить доступ к отдельному элементу строки и работать с ним как с отдельным символом.
Теперь рассмотрим стандартные функции и процедуры для обработки строк.
1) length(s) — функция, возвращающая текущую длину строки.
2) сopy(s,i,n) — функция, возвращающая кусок строки `s` длиной `n` символов, начиная с `i`-го. Параметр `s` имеет тип string, `i`, `n` – тип integer.
3) pos(s1,s) — функция, в качестве результата выдающая номер позиции в строке `s`, с которой начинается подстрока `s1`; если подстрока `s1` не входит в строку `s`, то результат равен `0`.
4) delete(s,i,n) — процедура, удаляющая из строки `s` `n` символов, начиная с `i`-го символа. Параметр `s` имеет тип string, `i`, `n` – тип integer.
5) insert(s1,s,i) — процедура, вставляющая в строку `s` подстроку `s1` перед символом с номером `i`;
6) str(a,s) — процедура, переводящая число `a` в его строковое представление `s`. Параметр `s` имеет тип string, `a` – тип integer либо real.
7) val(s,n,i) — процедура, переводящая строку `s` в число (вещественное или целое, согласно типу переменной `n`). Если строка `s` не является изображением числа соответствующего типа по правилам Паскаля, то значение переменной `i`будет равняться номеру первого символа, который не удаётся преобразовать в число, а переменная `n` примет значение – ноль. При удачной конвертации значение переменной `i` станет равным нулю;
Функции для обработки строк, подобно математическим, входят в состав выражений. Процедуры – это новое для нас понятие. В отличие от функции процедура не возвращает какое-то конкретное значение. Результат работы процедуры – изменение одного или нескольких её параметров (например, процедура val в любом случае меняет значения второго и третьего параметра). Изменяемые параметры должны быть переменными. Неизменяемые – могут быть константами, как у функций. Вызов процедуры записывается отдельным оператором. Все функции и процедуры корректно изменяют текущую длину строки (так же как и операция сложения строк или присваивание строке нового значения).
Рассмотрим несколько примеров задач на обработку строк. В каждой задаче под «словом» понимается любая последовательность символов, не содержащая пробелы.
Ввести строку, состоящую из нескольких слов. Между словами `1` или более пробелов. Так же могут быть пробелы в начале и в конце строки. Удалить из строки все лишние пробелы. Длина входной строки не превосходит `255` символов.
Эта задача не просто демонстрирует работу со строками, но ещё и постоянно возникает в качестве подзадачи в более сложных задачах. Решить эту задачу можно разными способами. Самое простое (но не самое эффективное) решение заключается в следующем: Мы будем искать во входной строке подстроку в виде двух пробелов подряд. Если нашли, то один из них удаляем. Процесс повторяется, пока такая подстрока находится. В итоге у нас получится строка, в которой между словами ровно по `1` пробелу, плюс, возможно, есть по `1` пробелу в начале и в конце строки. Если они есть, то мы их удаляем. Приведём полный код программы.
var s : string;
begin
readln(s);
while pos(' ', s)<>0 do delete(s, pos('
',s), 1);
if s[1]= ' ' then delete(s, 1, 1);
if s[length(s)]=' ' then delete(s, length(s), 1);
writeln(s);
readln
end.
На примере этой задачи мы увидели работу функций length и pos, и процедуры delete.
Вводится строка, состоящая из двух слов. Между словами ровно один пробел. Требуется поменять эти два слова местами.
Эта задача демонстрирует работу функции copy и операции сложения строк. Мы заведём ещё одну строку, вырежем из исходной строки второе слово, запишем в результирующую строку, затем припишем справа пробел и, наконец, вырежем из исходной строки первое слово и припишем справа в результирующую строку. Приведём полный код программы.
var s, s1 : string;
begin
readln(s);
s1:=copy(s, pos(' ',s)+1, length(s)-pos(' ', s));
s1:=s1+' '+copy(s,1,pos(' ', s)-1);
writeln(s1);
end.
Постарайтесь внимательно разобраться в параметрах функции copy.
Напоследок, мы рассмотрим сложную комплексную задачу, которая демонстрирует все возможности работы со строками и параллельно содержит несколько базовых алгоритмов, которые пригодятся вам при решении задач для самостоятельной работы.
Волшебник усердно шифрует свои заклинания. Текст заклинания состоит из нескольких слов. Слово – это последовательность заглавных и строчных латинских букв. Длина слова не превосходит `20` символов. Между словами стоит `1` разделитель – любой символ кроме латинской буквы. В начале и конце строки разделителей нет. Общая длина заклинания не превосходит `250` символов. Волшебник сначала подсчитывает количество букв в самом коротком слове (`k`), а потом каждую латинскую букву заменяет на `k`-ую за ней по счёту в алфавите. Алфавит считается циклическим, то есть вторая буква за `Z` – это B. Малые буквы превращаются в малые, заглавные — в заглавные. Ввести зашифрованный текст заклинания, вывести расшифрованный.
Прежде чем читать дальше, прочитайте ещё раз условие задачи и убедитесь, что вам понятны все детали. Особенно, правила записи заклинаний и алгоритм шифрования.
Первая стадия решения – найти количество букв в самом коротком слове. Поскольку количество букв в слове не превосходит `20`, за начальное значение минимума можно принять это самое `20`. Вторая стадия – заменить каждую букву заклинания. Рассмотрим полный код программы.
var s : string; k, dlin,i : integer;
begin
readln(s);
k:=20; dlin:=0;
for i :=1 to length(s) do
if(s[i]>='A')and(s[i]<='Z')or(s[i]>=='a')and(s[i]<='z')
then dlin:=dlin+1
else begin if dlin<k then k:=dlin; dlin:=0 end;
if dlin < k then k:=dlin; {анализ последнего слова}
{Вторая стадия решения. Напомним, что функция ord(c) выдаёт код символа, находящегося в переменной с. В то время как функция chr(x) выдаёт символ по значению кода.}
for i:=1 to length(s) do begin
if (s[i]>='A')and(s[i]<='Z')
then begin s[i]:=chr(ord(s[i])-k);
if s[i]<'A' then s[i]:=chr(ord(s[i])+26)
end;
if (s[i]>='a')and(s[i]<='z')
then begin s[i]:=chr(ord(s[i])-k);
if s[i]<'a' then s[i]:=chr(ord(s[i])+26)
end;
end;
writeln(s);
readln
end.
Обратите внимание, что в качестве аргумента для функции chr(x) может использоваться выражение типа integer.
Пока что будем рассматривать массив a, содержащий `10` элементов типа integer с индексами от `1` до `10`.
Ввести с клавиатуры элементы массива `a`, а потом вывести их в том порядке, в котором они вводились.
Задача решается в `2` строки:
for i:=1 to 10 do read(a[i]);
for i:=1 to 10 do writeln(a[i]);
При вводе чисел: 1 1 1 3 2 2 2 5 66 1 Программа выдаст ответ:
1
1
1
3
2
2
2
5
66
1
Каждое число в ответе располагается на отдельной строке. Это происходит потому, что мы использовали для вывода оператор writeln. Однако, если у нас в массиве, например, `400` элементов, то такой вывод будет неудобным, ибо `400` строк не поместятся на одном экране, и придётся пользоваться прокруткой. Поэтому, более рациональным является использование другого оператора вывода – write.
for i:=1 to 10 do read(a[i]);
for i:=1 to 10 do write(a[i], ' ');
В список вывода добавлен пробел, чтобы числа не сливались в одно.
Ввести с клавиатуры элементы массива `a`, а потом вывести их в обратном порядке.
Есть два способа решения этой задачи. Первый заключается в том, что при выводе мы идём по массиву в обратном порядке (от последнего элемента к первому). Код будет выглядеть так:
for i:=1 to 10 do read(a[i]);
for i:=10 downto 1 do write(a[i], ' ');
Преимущество этого решения – его простота. Недостаток – отсутствие универсальности. Дело в том, что во многих задачах требуется переписывать элементы массива в обратном порядке и затем работать с перевёрнутым массивом. Приведённое же решение так сделать не позволит, поскольку массив, фактически не изменяется. Рассмотрим алгоритм переписывания элементов массива в обратном порядке:
for i:=1 to 10 do read(a[i]);
for i:=1 to 10 div 2 do
begin x:=a[i]; a[i]:=a[10-i+1]; a[10-i+1]:=
= x end;
for i:=1 to 10 do write(a[i], ' ');
Второй цикл переписывает элементы массива в обратном порядке при помощи алгоритма «поменять местами значения двух переменных». Первый элемент меняется местами с последним, второй с предпоследним, и так далее, до середины массива. Обратите внимание, что идти по массиву нужно только до середины, а не до конца. Если пойти до конца, то массив сначала перевернётся (когда мы дойдём до середины), а потом перевернётся обратно, и в итоге получится исходный массив.
Теперь давайте представим, что заказчик, предложивший вам эту задачу, вдруг решил изменить размер массива до `20` элементов. Сколько изменений вам придётся вносить в программу? Очевидно, что нужно будет исправить границу в трёх циклах for (заменить «to 10» на «to 20»), во втором цикле заменить `10` на `20` в формулах, и ещё надо будет заменить `10` на `20` при описании массива. То есть, целых шесть изменений для такой простой задачи. В более сложных задачах количество изменений может достигать сотен. Поэтому, мы познакомимся с так называемой «константой границы», которая позволит при любом размере программы обходиться всего лишь одним изменением кода! Константа границы описывается в разделе описания констант до объявления массива, а затем используется при его объявлении, например:
сonst N=10;
var a : array [1..N] of integer;
Далее в программе при работе с массивом `A` всегда вместо конкретного значения границы указывается константа `N`. Таким образом, если заказчик меняет размер массива, то нам нужно внести в код всего одно изменение – поменять значение константы `N` в разделе const.
Давайте перепишем решение последней задачи с использованием константы границы.
for i:=1 to N do read(a[i]);
for i:=1 to N div 2 do
begin x:=a[i]; a[i]:=a[N-i+1]; a[N-i+1]:=
= x end;
for i:=1 to N do write(a[i], ' ');
Для всех последующих задач мы будем использовать описание массива с константой границы:
сonst N=10;
var a : array [1..N] of integer;
Так же мы будем предполагать, что массив уже заполнен и сконцентрируемся собственно на алгоритмах его обработки.
Вывести сумму элементов массива.
Для решения этой задачи используется стандартный алгоритм накапливания суммы, которым мы уже пользовались при обработке последовательностей.
s:=0;
for i:=1 to N do s:=s+a[i];
writeln(s);
Вывести значение максимального элемента массива.
Изначально предположим, что максимальным является первый элемент массива. Затем пройдём по массиву от второго до последнего элемента, сравнивая каждый элемент с текущим значением максимума и меняя это значение по необходимости
for i:=1 to N do read(a[i]);
max:=a[1];
for i:=2 to N do if a[i]>max then max:=a[i];
writeln(max);
Найти в массиве максимальный и минимальный элементы и поменять их местами.
Эта задача существенно отличается от предыдущей, несмотря на кажущееся сходство. В предыдущей задаче нас интересовало только значение максимального элемента, но не его положение в массиве. Здесь же нам не просто нужно найти значение минимального и максимального элементов, но и их расположение в массиве. Очень часто учащиеся пишут следующее решение:
min:=a[1]; max:=a[1];
for i:=2 to N do
if a[i]>max then max:=a[i]
else if a[i]<min then min:=a[i];
x:= max;
max:=min;
min:=x;
Является ли это решение верным? Разумеется, нет. Здесь меняются местами значения переменных max и min, в то время как массив остаётся без изменений. В правильном решении нам нужно сохранять не сами значения максимального и минимального элементов, а их местоположение в массиве. Правильное решение выглядит следующим образом.
min:=1; max:=1;
for i:=2 to N do
if a[i]>a[max] then max:=i
else if a[i]<a[min] then min:=i;
x:=a[max];
a[max]:=a[min];
a[min]:=x;
Циклически сдвинуть элементы массива на одну позицию влево.
В задаче требуется преобразовать массив следующим образом: все элементы, кроме первого переместить на одну позицию влево, а первый элемент (поскольку сдвиг циклический) поместить в крайнюю правую позицию. То есть из массива `5` `4` `3` `2` должен получиться массив `4` `3` `2` `5`. Решение этой задачи фактически является расширенным алгоритмом обмена значений двух переменных и выглядит так:
x:=a[1];
for i:=1 to N-1 do a[i]:=a[i+1];
a[N]:=x;
Упорядочить элементы массива по возрастанию.
Обратите на эту задачу особенное внимание! Она называется задачей «сортировки массива» и регулярно встречается в качестве подзадачи в сложных задачах, в частности в задачах ЕГЭ. Каждый ученик должен уметь быстро и безошибочно написать алгоритм для решения этой задачи. Существует множество алгоритмов сортировки. Каждый из них имеет свои достоинства и недостатки. Идеального среди них нет. Мы рассмотрим наиболее простой и понятный алгоритм сортировки, который называется «выбор максимума».
Идея алгоритма «выбора максимума» в следующем: мы находим в массиве максимальный элемент и ставим его на предназначенное ему место (последнее) путём обмена (меняем местами максимальный и последний элементы), затем из оставшихся элементов (всех кроме последнего) находим максимальный и меняем его местами с предпоследним и так далее. С каждым шагом область сортировки (несортированная часть массива) будет уменьшаться на один элемент. Алгоритм работает последний раз, когда в области сортировки остаётся два элемента (первый и второй).
Реализуется этот алгоритм следующим образом. У нас будет цикл, который будет отвечать за размер области сортировки. Внутри этого цикла выполняется два действия: поиск максимума и обмен максимального элемента с крайним правым в области сортировки. Приведём код.
for j:=N downto 2 do begin
max:=1;
for i:=2 to j do if a[i]>a[max] then max:=i;
x:=a[j];
a[j]:=a[max];
a[max]:=x;
end;
Даны два целочисленных массива из 30 элементов. Первый заполнен числами от `1` до `30` – это номера дней в июне. Во второй массив метеорологи ввели значения температуры в соответствующий день (то есть в первом элементе – температура первого июня, во втором – второго и так далее до тридцатого). Метеорологи хотят вывести даты июня в порядке от самой холодной до самой жаркой.
Очевидно, что это тоже задача сортировки, которую мы уже умеем решать. Сложность заключается в том, что сортировать надо по одному признаку (температура), а выводить другой (дата). Наша цель – модифицировать алгоритм сортировки таким образом, чтобы не нарушать связь между датой и температурой. Это достигается следующим образом: каждый раз, когда меняются элементы одного массива, надо менять и соответствующие элементы другого массива.
В программе мы будем использовать два массива с говорящими именами: dat и temp. Приведём содержательную часть решения, а именно сортировку.
for j:=N downto 2 do begin
max:=1;
for i:=2 to j do if temp[i]>temp[max] then max:=i;
x:=temp[j];
temp[j]:=temp[max];
temp[max]:=x;
x:=dat[j];
dat[j]:=dat[max];
dat[max]:=x;
end;
Далее необходимо вывести элементы массива dat.
Вводится непустая последовательность символов. Точка – признак конца ввода. Требуется вывести статистику: сколько заглавных латинских букв каждого вида входит в эту последовательность.
Иногда учащимся приходит в голову следующее решение: «А давайте мы сохраним все элементы последовательности в массиве, потом отсортируем его, а потом пройдём по нему, посчитаем, сколько раз встретится каждая заглавная буква, и выведем это число». Основная проблема заключается в том, что по условию задачи нам никто не сказал максимальное количество символов в последовательности, что означает невозможность сохранять их все в массиве (поскольку нужно заранее заказывать размер). К тому же в случае большой последовательности мы потратим ОЧЕНЬ много времени на сортировку. Поэтому, нам нужно завести такой массив, размер которого был бы заранее известен, и при этом в нём хранилась бы вся информация об интересующих нас элементах последовательности. Хорошее решение – создать массив счётчиков, который будет учитывать количество вхождений каждой заглавной буквы в последовательность. Очевидно, что мы можем заранее указать размер этого массива – `26` элементов, поскольку в латинском алфавите – `26` букв. Индексами массива счётчиков должны быть подсчитываемые элементы (то есть заглавные латинские буквы). Внимание! Это первая задача, где тип индекса является не диапазоном целых чисел, а диапазоном символов. Тип элементов в массиве, очевидно, целый. Приведём полный текст решения.
var count : array ['A'..'Z'] of integer;
c : char;
begin
for c:='A' to 'Z' do count[c]:=0;
read(c);
repeat
if (c<='Z') and (c>='A') then count[c]:=
= count[c]+1;
read(c)
until c='.';
for c:='A' to 'Z' do writeln(c, '-',count[c]);
readln
end.
Ввести последовательность символов. Точка – признак конца ввода. Составить из заглавных латинских букв, входящих в последовательность, первый в алфавитном порядке палиндром максимальной длины и вывести его на экран. Гарантируется, что в последовательность входит хотя бы одна заглавная латинская буква.
Палиндром – это строка символов, которая читается одинаково слева направо и справа налево. Например, известная фраза из Буратино «А роза упала на лапу Азора» становится палиндромом, если удалить из неё пробелы и не различать заглавные и строчные буквы (что происходит автоматически при восприятии этой фразы на слух).
В нашей задаче нам нужно найти палиндром максимальной длины, первый в алфавитном порядке. Мы подсчитаем количество вхождений каждой заглавной латинской буквы в последовательность, а потом будем выводить половину вхождений каждой буквы в порядке от `A` до `Z`. Таким образом, мы выведем половину искомого палиндрома. Далее, найдём первую букву в алфавитном порядке, которая встречается нечётное количество раз, и поставим её в середину палиндрома. Во фразе из Буратино средней буквой является «н». Если же окажется, что все буквы встретились в последовательности чётное количество раз, то, соответственно, палиндром будет чётной длины без серединной буквы, и, значит, на этой стадии ничего не произойдёт. Наконец, последним этапом мы выведем половину вхождений каждой буквы, но уже в обратном порядке – от `Z` до `A`. Рассмотрим полный код решения.
var count : array ['A'..'Z'] of integer;
c,d : char; i : integer;
begin
for c:='A' to 'Z' do count[c]:= 0;
read(c);
repeat
if (c<='Z')and (c>='A')then count[c]:=
=count[c]+1;
read(c)
until c='.';
for c:='A' to 'Z' do
for i:=1 to count[c] div 2 do write(c);
d:='0';
for c:='A' to 'Z' do
if count[c] mod 2 <> 0 then begin
d:=c; break end;
{оператор break прерывает выполнение цикла и передаёт управление на следующий за ним оператор программы}
if d<>'0' then write(d);
for c:='Z' downto 'A' do
for i:=1 to count[c] div 2 do write(c);
readln
end.
В предыдущих темах мы неоднократно сталкивались с задачами обработки последовательностей (последовательностей чисел в первом задании или символов – во втором). Все подобные задачи решались по единой стратегии: мы считывали очередной элемент последовательности, обрабатывали и забывали о нём. Теперь рассмотрим пример задачи, где подобная стратегия не сработает.
Ввести последовательность из `100` целых чисел, а затем вывести эти числа в порядке возрастания.
РЕШЕНИЕ
Очевидно, что для решения этой задачи нам необходимо сохранить все введённые числа, поэтому описанная выше стратегия здесь неприменима. Так же очевидным является факт, что для хранения всех введённых чисел крайне неудобно использовать сто переменных с уникальными именами. Гораздо удобнее было бы обозначать элементы последовательности так, как это делается в математике, то есть указывать общее имя последовательности и номер элемента (например, ). Для реализации этой идеи нам нужно познакомиться с новым типом переменных – массивом.
Массив – это сложная структура элементов одного типа. Все элементы массива упорядочены по номерам. Порядковый номер элемента в массиве называется индексом элемента. Количество элементов в массиве называется размером массива. Под массив отводится непрерывный участок в оперативной памяти.
Размерность массива – это количество индексов, которое нужно указать для однозначной идентификации элемента массива. Если нужно указывать один индекс, то массив называется одномерным, если два, то двумерным и т. д. В этой главе мы будем работать исключительно с одномерными массивами.
Рассмотрим, каким образом одномерный массив описывается на языке Паскаль.
var <имя массива>: array [тип индекса] of <тип элементов>
В этой конструкции слова ARRAY и OF являются ключевыми словами языка. Задаваемое имя массива должно соответствовать правилам именования объектов в языке Паскаль, то есть, представлять из себя последовательность латинских букв, цифр и символов подчёркивания. начинающуюся с буквы или символа подчёркивания. Тип элементов массива может быть любым (integer, longint, real, boolean, char и т. д.). В качестве типа индекса мы будем использовать диапазоны целых чисел или символов. Диапазон оформляется следующим образом: записывается минимальная граница, затем дважды ставится точка и потом записывается максимальная граница. Обе границы включаются в диапазон.
Пример описания массива:
var massiv: array [1..10] of integer;
В примере описывается массив из `10` целых чисел с индексами от `1` до `10`.
Другой пример:
var massiv2: array [0..9] of integer;
В этом примере также описывается массив из `10` целых чисел, но индексы у них от `0` до `9`.
Для того, чтобы работать с элементом массива, в программе необходимо записывать имя массива и в квадратных скобках индекс интересующего нас элемента. Например, massiv[10]:=2. Этот оператор присваивает в элемент массива massiv с индексом `10` число `2`. Необходимо всегда контролировать выход за границы диапазона значений индекса. Скажем, оператор massiv2[10]:=2 является ошибкой, поскольку у массива с именем massiv2 нет элемента с индексом `10`.
Пусть у нас есть описание массива.
var a: array [1..10] of integer;
Рассмотрим возможные операции с этим объектом. Их можно разделить на две группы: операции с массивом, как с единым объектом, и операции с одним элементом массива.
В первой группе операций совсем немного – всего лишь одна! Это операция копирования массивов.
Пусть есть описание: var a,b: array [1..10] of integer
Тогда допустимыми являются следующие операторы присваивания: a:=b и соответственно b:=a. Первый из этих операторов во все элементы массива `a` запишет значения соответствующих элементов массива `b` (то есть элементов с теми же индексами). А второй оператор во все элементы массива b запишет значения соответствующих элементов массива `a`.
Необходимо помнить, что операция копирования в Паскале применима только к переменным, имеющим одинаковый тип (исключение, в real можно присваивать integer). Описанные выше массивы `a` и `b` имеют одинаковый тип. Если же описать их немного иначе:
var a: array [1..10] of integer;
var b: array [1..10] of integer;
то операция копирования будет неприменима! Несмотря на структурную эквивалентность (и то, и другое – массивы из целых чисел с индексами от `1` до `10`) Паскаль-машина считает, что это разные типы переменных, и поэтому присваивать их один другому нельзя. (Необходимо отметить, что некоторые компиляторы позволяют копирование массивов в случае структурной эквивалентности, но в рамках этого задания мы будем руководствоваться стандартом языка).
Больше с массивами как с едиными объектами нельзя делать ничего. Нельзя даже считывать и выводить их на экран одним оператором (оператор readln(a) или writeln(a) недопустим).
Перейдём к рассмотрению второй группы операций (операции с отдельными элементами массива). С каждым элементом массива можно выполнять все операции, которые применимы к обычной переменной соответствующего типа. Если элемент массива — целое число (как описано выше), то его можно использовать в арифметических выражениях, ему можно присваивать значения арифметических выражений, его можно считывать с клавиатуры и выводить на экран (например, writeln(a[4])). Если элемент массива имеет тип Boolean, то его нельзя вводить с клавиатуры, но можно присвоить ему значение true или false, использовать его в логическом выражении в качестве операнда для логической операции и т. д.
Исходя из всего вышесказанного, уже очевидно, как присвоить значения всем элементам (заполнить массив). Для массива `a` заполнение может выглядеть следующим образом:
a[1]:=1;
a[2]:=4;
a[3]:=-1000;
a[4]:=8950;
a[5]:=0;
a[6]:=78;
a[7]:=6789;
a[8]:=13;
a[9]:=222;
a[10]:=90;
Понятно, что такой способ заполнения, когда мы явным образом прописываем присваивание значения каждому элементу массива, подходит только в случае, когда массив небольшой. То есть, для массива из `20` элементов нужно будет написать `20` операторов присваивания, для массива из `200` элементов – `200` и т. д. При этом, в случае изменения исходных данных, нам нужно будет менять в программе все эти строки! Гораздо выгоднее воспользоваться оператором ввода с клавиатуры и циклом for. Тогда алгоритм заполнения массива записывается в `1` строку независимо от количества элементов в массиве! Для массива `a` алгоритм заполнения будет выглядеть так:
for i:=1 to 10 do readln(a[i]);
Индексы не всегда нужно записывать явным образом. Как показано в примере, на месте индекса можно писать и переменную или выражение соответствующего типа (типа, совпадающего с объявленным типом индекса).
Теперь пришло время познакомиться с ещё одним типом переменных, который активно используется при обработке текстов – это строка (string). Строка представляет собой последовательность символов. Размер строки варьируется от `0` до `255`. В отличие от всех остальных названий типов, слово string является зарезервированным служебным словом и, соответственно, не может использоваться в качестве имени переменных. При описании строки под неё выделяется `256` байт (по одному байту на каждый символ + нулевой байт, в котором хранится текущая длина строки). Если заранее известно, что длина строки не будет превышать какого-то количества символов (например `20`) , то это можно указать при описании переменной: var s :string[20], в квадратных скобках после слова string записывается максимальная длина строки. В этом случае под переменную будет выделен `21` байт (по одному на каждый из `20` символов + нулевой байт для текущей длины строки). Указание длины никак не влияет на совместимость типов.
Переменным типа string можно присваивать константные значения. При этом строковая константа, подобно символу, заключается в апострофы, например s:='cat'. Также их можно выводить на экран, и, что особенно приятно, вводить с клавиатуры одним оператором: (readln(s)).
Так же в задачах иногда бывают ситуации, когда строку нужно набирать постепенно (добавляя в неё по `1` символу). Для этого предусмотрена операция сложения строк (конкатенация). Например, запись s:=s+'c', означает, что к текущему значению переменной `s` справа приписывается символ 'c'. Операция s:=s+'ch' означает, что справа припишется два символа. Также можно записать такое сложение: s:='ch'+'hc'; тогда переменная `s` получит значение 'chhc'. Операция сложения строк не обладает свойством коммутативности, то есть, от перестановки мест слагаемых сумма изменяется. Если в последнем примере поменять местами слагаемые, то получится строка 'hcch'.
Ещё к строкам можно применять операции сравнения, причём все шесть, которые существуют в Паскале. Строки сравниваются посимвольно, то есть сначала первые символы, в случае их равенства вторые и т. д. Если на каком-то шаге (возможно, на первом) символ первой строки оказался больше символа второй, то первая строка считается больше второй. Если у строк совпадают все символы и длины, то строки считаются равными. Если у строк совпали все символы, но первая строка уже кончилась, а вторая – нет (например, «ветер» и «ветерок»), то вторая строка считается больше, чем первая.
Следующая интересная возможность – это работать со строкой, как с символьным массивом (массивом, элементами которого являются символы). При этом индекс имеет целый тип и всегда принадлежит диапазону от единицы до максимально заказанной длины строки (по умолчанию – `255`). К строке применимы все те же операции, что и к символьному массиву, то есть возможность получить доступ к отдельному элементу строки и работать с ним как с отдельным символом.
Теперь рассмотрим стандартные функции и процедуры для обработки строк.
1) length(s) — функция, возвращающая текущую длину строки.
2) сopy(s,i,n) — функция, возвращающая кусок строки `s` длиной `n` символов, начиная с `i`-го. Параметр `s` имеет тип string, `i`, `n` – тип integer.
3) pos(s1,s) — функция, в качестве результата выдающая номер позиции в строке `s`, с которой начинается подстрока `s1`; если подстрока `s1` не входит в строку `s`, то результат равен `0`.
4) delete(s,i,n) — процедура, удаляющая из строки `s` `n` символов, начиная с `i`-го символа. Параметр `s` имеет тип string, `i`, `n` – тип integer.
5) insert(s1,s,i) — процедура, вставляющая в строку `s` подстроку `s1` перед символом с номером `i`;
6) str(a,s) — процедура, переводящая число `a` в его строковое представление `s`. Параметр `s` имеет тип string, `a` – тип integer либо real.
7) val(s,n,i) — процедура, переводящая строку `s` в число (вещественное или целое, согласно типу переменной `n`). Если строка `s` не является изображением числа соответствующего типа по правилам Паскаля, то значение переменной `i`будет равняться номеру первого символа, который не удаётся преобразовать в число, а переменная `n` примет значение – ноль. При удачной конвертации значение переменной `i` станет равным нулю;
Функции для обработки строк, подобно математическим, входят в состав выражений. Процедуры – это новое для нас понятие. В отличие от функции процедура не возвращает какое-то конкретное значение. Результат работы процедуры – изменение одного или нескольких её параметров (например, процедура val в любом случае меняет значения второго и третьего параметра). Изменяемые параметры должны быть переменными. Неизменяемые – могут быть константами, как у функций. Вызов процедуры записывается отдельным оператором. Все функции и процедуры корректно изменяют текущую длину строки (так же как и операция сложения строк или присваивание строке нового значения).
Рассмотрим несколько примеров задач на обработку строк. В каждой задаче под «словом» понимается любая последовательность символов, не содержащая пробелы.
Ввести строку, состоящую из нескольких слов. Между словами `1` или более пробелов. Так же могут быть пробелы в начале и в конце строки. Удалить из строки все лишние пробелы. Длина входной строки не превосходит `255` символов.
Эта задача не просто демонстрирует работу со строками, но ещё и постоянно возникает в качестве подзадачи в более сложных задачах. Решить эту задачу можно разными способами. Самое простое (но не самое эффективное) решение заключается в следующем: Мы будем искать во входной строке подстроку в виде двух пробелов подряд. Если нашли, то один из них удаляем. Процесс повторяется, пока такая подстрока находится. В итоге у нас получится строка, в которой между словами ровно по `1` пробелу, плюс, возможно, есть по `1` пробелу в начале и в конце строки. Если они есть, то мы их удаляем. Приведём полный код программы.
var s : string;
begin
readln(s);
while pos(' ', s)<>0 do delete(s, pos('
',s), 1);
if s[1]= ' ' then delete(s, 1, 1);
if s[length(s)]=' ' then delete(s, length(s), 1);
writeln(s);
readln
end.
На примере этой задачи мы увидели работу функций length и pos, и процедуры delete.
Вводится строка, состоящая из двух слов. Между словами ровно один пробел. Требуется поменять эти два слова местами.
Эта задача демонстрирует работу функции copy и операции сложения строк. Мы заведём ещё одну строку, вырежем из исходной строки второе слово, запишем в результирующую строку, затем припишем справа пробел и, наконец, вырежем из исходной строки первое слово и припишем справа в результирующую строку. Приведём полный код программы.
var s, s1 : string;
begin
readln(s);
s1:=copy(s, pos(' ',s)+1, length(s)-pos(' ', s));
s1:=s1+' '+copy(s,1,pos(' ', s)-1);
writeln(s1);
end.
Постарайтесь внимательно разобраться в параметрах функции copy.
Напоследок, мы рассмотрим сложную комплексную задачу, которая демонстрирует все возможности работы со строками и параллельно содержит несколько базовых алгоритмов, которые пригодятся вам при решении задач для самостоятельной работы.
Волшебник усердно шифрует свои заклинания. Текст заклинания состоит из нескольких слов. Слово – это последовательность заглавных и строчных латинских букв. Длина слова не превосходит `20` символов. Между словами стоит `1` разделитель – любой символ кроме латинской буквы. В начале и конце строки разделителей нет. Общая длина заклинания не превосходит `250` символов. Волшебник сначала подсчитывает количество букв в самом коротком слове (`k`), а потом каждую латинскую букву заменяет на `k`-ую за ней по счёту в алфавите. Алфавит считается циклическим, то есть вторая буква за `Z` – это B. Малые буквы превращаются в малые, заглавные — в заглавные. Ввести зашифрованный текст заклинания, вывести расшифрованный.
Прежде чем читать дальше, прочитайте ещё раз условие задачи и убедитесь, что вам понятны все детали. Особенно, правила записи заклинаний и алгоритм шифрования.
Первая стадия решения – найти количество букв в самом коротком слове. Поскольку количество букв в слове не превосходит `20`, за начальное значение минимума можно принять это самое `20`. Вторая стадия – заменить каждую букву заклинания. Рассмотрим полный код программы.
var s : string; k, dlin,i : integer;
begin
readln(s);
k:=20; dlin:=0;
for i :=1 to length(s) do
if(s[i]>='A')and(s[i]<='Z')or(s[i]>=='a')and(s[i]<='z')
then dlin:=dlin+1
else begin if dlin<k then k:=dlin; dlin:=0 end;
if dlin < k then k:=dlin; {анализ последнего слова}
{Вторая стадия решения. Напомним, что функция ord(c) выдаёт код символа, находящегося в переменной с. В то время как функция chr(x) выдаёт символ по значению кода.}
for i:=1 to length(s) do begin
if (s[i]>='A')and(s[i]<='Z')
then begin s[i]:=chr(ord(s[i])-k);
if s[i]<'A' then s[i]:=chr(ord(s[i])+26)
end;
if (s[i]>='a')and(s[i]<='z')
then begin s[i]:=chr(ord(s[i])-k);
if s[i]<'a' then s[i]:=chr(ord(s[i])+26)
end;
end;
writeln(s);
readln
end.
Обратите внимание, что в качестве аргумента для функции chr(x) может использоваться выражение типа integer.
Пока что будем рассматривать массив a, содержащий `10` элементов типа integer с индексами от `1` до `10`.
Ввести с клавиатуры элементы массива `a`, а потом вывести их в том порядке, в котором они вводились.
Задача решается в `2` строки:
for i:=1 to 10 do read(a[i]);
for i:=1 to 10 do writeln(a[i]);
При вводе чисел: 1 1 1 3 2 2 2 5 66 1 Программа выдаст ответ:
1
1
1
3
2
2
2
5
66
1
Каждое число в ответе располагается на отдельной строке. Это происходит потому, что мы использовали для вывода оператор writeln. Однако, если у нас в массиве, например, `400` элементов, то такой вывод будет неудобным, ибо `400` строк не поместятся на одном экране, и придётся пользоваться прокруткой. Поэтому, более рациональным является использование другого оператора вывода – write.
for i:=1 to 10 do read(a[i]);
for i:=1 to 10 do write(a[i], ' ');
В список вывода добавлен пробел, чтобы числа не сливались в одно.
Ввести с клавиатуры элементы массива `a`, а потом вывести их в обратном порядке.
Есть два способа решения этой задачи. Первый заключается в том, что при выводе мы идём по массиву в обратном порядке (от последнего элемента к первому). Код будет выглядеть так:
for i:=1 to 10 do read(a[i]);
for i:=10 downto 1 do write(a[i], ' ');
Преимущество этого решения – его простота. Недостаток – отсутствие универсальности. Дело в том, что во многих задачах требуется переписывать элементы массива в обратном порядке и затем работать с перевёрнутым массивом. Приведённое же решение так сделать не позволит, поскольку массив, фактически не изменяется. Рассмотрим алгоритм переписывания элементов массива в обратном порядке:
for i:=1 to 10 do read(a[i]);
for i:=1 to 10 div 2 do
begin x:=a[i]; a[i]:=a[10-i+1]; a[10-i+1]:=
= x end;
for i:=1 to 10 do write(a[i], ' ');
Второй цикл переписывает элементы массива в обратном порядке при помощи алгоритма «поменять местами значения двух переменных». Первый элемент меняется местами с последним, второй с предпоследним, и так далее, до середины массива. Обратите внимание, что идти по массиву нужно только до середины, а не до конца. Если пойти до конца, то массив сначала перевернётся (когда мы дойдём до середины), а потом перевернётся обратно, и в итоге получится исходный массив.
Теперь давайте представим, что заказчик, предложивший вам эту задачу, вдруг решил изменить размер массива до `20` элементов. Сколько изменений вам придётся вносить в программу? Очевидно, что нужно будет исправить границу в трёх циклах for (заменить «to 10» на «to 20»), во втором цикле заменить `10` на `20` в формулах, и ещё надо будет заменить `10` на `20` при описании массива. То есть, целых шесть изменений для такой простой задачи. В более сложных задачах количество изменений может достигать сотен. Поэтому, мы познакомимся с так называемой «константой границы», которая позволит при любом размере программы обходиться всего лишь одним изменением кода! Константа границы описывается в разделе описания констант до объявления массива, а затем используется при его объявлении, например:
сonst N=10;
var a : array [1..N] of integer;
Далее в программе при работе с массивом `A` всегда вместо конкретного значения границы указывается константа `N`. Таким образом, если заказчик меняет размер массива, то нам нужно внести в код всего одно изменение – поменять значение константы `N` в разделе const.
Давайте перепишем решение последней задачи с использованием константы границы.
for i:=1 to N do read(a[i]);
for i:=1 to N div 2 do
begin x:=a[i]; a[i]:=a[N-i+1]; a[N-i+1]:=
= x end;
for i:=1 to N do write(a[i], ' ');
Для всех последующих задач мы будем использовать описание массива с константой границы:
сonst N=10;
var a : array [1..N] of integer;
Так же мы будем предполагать, что массив уже заполнен и сконцентрируемся собственно на алгоритмах его обработки.
Вывести сумму элементов массива.
Для решения этой задачи используется стандартный алгоритм накапливания суммы, которым мы уже пользовались при обработке последовательностей.
s:=0;
for i:=1 to N do s:=s+a[i];
writeln(s);
Вывести значение максимального элемента массива.
Изначально предположим, что максимальным является первый элемент массива. Затем пройдём по массиву от второго до последнего элемента, сравнивая каждый элемент с текущим значением максимума и меняя это значение по необходимости
for i:=1 to N do read(a[i]);
max:=a[1];
for i:=2 to N do if a[i]>max then max:=a[i];
writeln(max);
Найти в массиве максимальный и минимальный элементы и поменять их местами.
Эта задача существенно отличается от предыдущей, несмотря на кажущееся сходство. В предыдущей задаче нас интересовало только значение максимального элемента, но не его положение в массиве. Здесь же нам не просто нужно найти значение минимального и максимального элементов, но и их расположение в массиве. Очень часто учащиеся пишут следующее решение:
min:=a[1]; max:=a[1];
for i:=2 to N do
if a[i]>max then max:=a[i]
else if a[i]<min then min:=a[i];
x:= max;
max:=min;
min:=x;
Является ли это решение верным? Разумеется, нет. Здесь меняются местами значения переменных max и min, в то время как массив остаётся без изменений. В правильном решении нам нужно сохранять не сами значения максимального и минимального элементов, а их местоположение в массиве. Правильное решение выглядит следующим образом.
min:=1; max:=1;
for i:=2 to N do
if a[i]>a[max] then max:=i
else if a[i]<a[min] then min:=i;
x:=a[max];
a[max]:=a[min];
a[min]:=x;
Циклически сдвинуть элементы массива на одну позицию влево.
В задаче требуется преобразовать массив следующим образом: все элементы, кроме первого переместить на одну позицию влево, а первый элемент (поскольку сдвиг циклический) поместить в крайнюю правую позицию. То есть из массива `5` `4` `3` `2` должен получиться массив `4` `3` `2` `5`. Решение этой задачи фактически является расширенным алгоритмом обмена значений двух переменных и выглядит так:
x:=a[1];
for i:=1 to N-1 do a[i]:=a[i+1];
a[N]:=x;
Упорядочить элементы массива по возрастанию.
Обратите на эту задачу особенное внимание! Она называется задачей «сортировки массива» и регулярно встречается в качестве подзадачи в сложных задачах, в частности в задачах ЕГЭ. Каждый ученик должен уметь быстро и безошибочно написать алгоритм для решения этой задачи. Существует множество алгоритмов сортировки. Каждый из них имеет свои достоинства и недостатки. Идеального среди них нет. Мы рассмотрим наиболее простой и понятный алгоритм сортировки, который называется «выбор максимума».
Идея алгоритма «выбора максимума» в следующем: мы находим в массиве максимальный элемент и ставим его на предназначенное ему место (последнее) путём обмена (меняем местами максимальный и последний элементы), затем из оставшихся элементов (всех кроме последнего) находим максимальный и меняем его местами с предпоследним и так далее. С каждым шагом область сортировки (несортированная часть массива) будет уменьшаться на один элемент. Алгоритм работает последний раз, когда в области сортировки остаётся два элемента (первый и второй).
Реализуется этот алгоритм следующим образом. У нас будет цикл, который будет отвечать за размер области сортировки. Внутри этого цикла выполняется два действия: поиск максимума и обмен максимального элемента с крайним правым в области сортировки. Приведём код.
for j:=N downto 2 do begin
max:=1;
for i:=2 to j do if a[i]>a[max] then max:=i;
x:=a[j];
a[j]:=a[max];
a[max]:=x;
end;
Даны два целочисленных массива из 30 элементов. Первый заполнен числами от `1` до `30` – это номера дней в июне. Во второй массив метеорологи ввели значения температуры в соответствующий день (то есть в первом элементе – температура первого июня, во втором – второго и так далее до тридцатого). Метеорологи хотят вывести даты июня в порядке от самой холодной до самой жаркой.
Очевидно, что это тоже задача сортировки, которую мы уже умеем решать. Сложность заключается в том, что сортировать надо по одному признаку (температура), а выводить другой (дата). Наша цель – модифицировать алгоритм сортировки таким образом, чтобы не нарушать связь между датой и температурой. Это достигается следующим образом: каждый раз, когда меняются элементы одного массива, надо менять и соответствующие элементы другого массива.
В программе мы будем использовать два массива с говорящими именами: dat и temp. Приведём содержательную часть решения, а именно сортировку.
for j:=N downto 2 do begin
max:=1;
for i:=2 to j do if temp[i]>temp[max] then max:=i;
x:=temp[j];
temp[j]:=temp[max];
temp[max]:=x;
x:=dat[j];
dat[j]:=dat[max];
dat[max]:=x;
end;
Далее необходимо вывести элементы массива dat.
Вводится непустая последовательность символов. Точка – признак конца ввода. Требуется вывести статистику: сколько заглавных латинских букв каждого вида входит в эту последовательность.
Иногда учащимся приходит в голову следующее решение: «А давайте мы сохраним все элементы последовательности в массиве, потом отсортируем его, а потом пройдём по нему, посчитаем, сколько раз встретится каждая заглавная буква, и выведем это число». Основная проблема заключается в том, что по условию задачи нам никто не сказал максимальное количество символов в последовательности, что означает невозможность сохранять их все в массиве (поскольку нужно заранее заказывать размер). К тому же в случае большой последовательности мы потратим ОЧЕНЬ много времени на сортировку. Поэтому, нам нужно завести такой массив, размер которого был бы заранее известен, и при этом в нём хранилась бы вся информация об интересующих нас элементах последовательности. Хорошее решение – создать массив счётчиков, который будет учитывать количество вхождений каждой заглавной буквы в последовательность. Очевидно, что мы можем заранее указать размер этого массива – `26` элементов, поскольку в латинском алфавите – `26` букв. Индексами массива счётчиков должны быть подсчитываемые элементы (то есть заглавные латинские буквы). Внимание! Это первая задача, где тип индекса является не диапазоном целых чисел, а диапазоном символов. Тип элементов в массиве, очевидно, целый. Приведём полный текст решения.
var count : array ['A'..'Z'] of integer;
c : char;
begin
for c:='A' to 'Z' do count[c]:=0;
read(c);
repeat
if (c<='Z') and (c>='A') then count[c]:=
= count[c]+1;
read(c)
until c='.';
for c:='A' to 'Z' do writeln(c, '-',count[c]);
readln
end.
Ввести последовательность символов. Точка – признак конца ввода. Составить из заглавных латинских букв, входящих в последовательность, первый в алфавитном порядке палиндром максимальной длины и вывести его на экран. Гарантируется, что в последовательность входит хотя бы одна заглавная латинская буква.
Палиндром – это строка символов, которая читается одинаково слева направо и справа налево. Например, известная фраза из Буратино «А роза упала на лапу Азора» становится палиндромом, если удалить из неё пробелы и не различать заглавные и строчные буквы (что происходит автоматически при восприятии этой фразы на слух).
В нашей задаче нам нужно найти палиндром максимальной длины, первый в алфавитном порядке. Мы подсчитаем количество вхождений каждой заглавной латинской буквы в последовательность, а потом будем выводить половину вхождений каждой буквы в порядке от `A` до `Z`. Таким образом, мы выведем половину искомого палиндрома. Далее, найдём первую букву в алфавитном порядке, которая встречается нечётное количество раз, и поставим её в середину палиндрома. Во фразе из Буратино средней буквой является «н». Если же окажется, что все буквы встретились в последовательности чётное количество раз, то, соответственно, палиндром будет чётной длины без серединной буквы, и, значит, на этой стадии ничего не произойдёт. Наконец, последним этапом мы выведем половину вхождений каждой буквы, но уже в обратном порядке – от `Z` до `A`. Рассмотрим полный код решения.
var count : array ['A'..'Z'] of integer;
c,d : char; i : integer;
begin
for c:='A' to 'Z' do count[c]:= 0;
read(c);
repeat
if (c<='Z')and (c>='A')then count[c]:=
=count[c]+1;
read(c)
until c='.';
for c:='A' to 'Z' do
for i:=1 to count[c] div 2 do write(c);
d:='0';
for c:='A' to 'Z' do
if count[c] mod 2 <> 0 then begin
d:=c; break end;
{оператор break прерывает выполнение цикла и передаёт управление на следующий за ним оператор программы}
if d<>'0' then write(d);
for c:='Z' downto 'A' do
for i:=1 to count[c] div 2 do write(c);
readln
end.
