shpory
.pdfs1 |
: str4; |
{ строка типа str4, описанного выше } |
s2 |
: string [n]; { описание типа задано при описании переменной } |
|
Инициализация строк, как и переменных других типов, выполняется в разделе описания констант: const s3 : string [15] = 'shooshpanchik' ;О перации Строки можно присваивать друг другу. Если максимальная длина результирующей строки меньше длины исходной, лишние символы справа отбрасываются: s2 := 'shooshpanchik'; s1 := s2; { в s1 будут помещены символы "shoo" } Строки можно склеивать между собой с помощью операции конкатенации, которая обозначается знаком +, например: s1 := 'ком'; s2 := s1 + 'пот'; { результат - "компот" } Строки можно сравнивать друг с другом с помощью операций отношения. При сравнении строки рассматриваются посимвольно слева направо, при этом сравниваются коды соответствующих пар символов. Строки равны, если они имеют одинаковую длину и посимвольно эквивалентны: abc' > 'ab' abc' = 'abc' abc' < 'abc ' Имя строки может использоваться в процедурах ввода-вывода: readln (s1, s2); write (s1); При вводе в строку считывается из входного потока количество символов, равное длине строки или меньшее, если символ перевода строки (Enter) встретится раньше. При выводе под строку отводится количество позиций, равное ее фактической длине.К отдельному символу строки можно обращаться как к элементу массива символов, например, s1[4]. Символ строки совместим с типом char, их можно использовать в выражениях одновременно, например: s1[4] := 'x'; writeln (s2[3] + s2[5] + 'r'); Процедуры и функции для работы со строками Функция Concat(s1, s2, ..., sn) возвращает строку, являющуюся слиянием строк s1, s2, ..., sn. Ее действие аналогично операции конкатенации. Функция Copy(s, start, len) возвращает подстроку длиной len, начинающуюся с позиции start строки s. Параметры len иstart должны быть целого типа. Процедура Delete(s, start, len) удаляет из строки s, начиная с
позиции start, подстроку длиной len. Процедура Insert(subs, s, start) вставляет |
в строку s подстроку subs, начиная с позиции start. Функция Length(s) возвращает фактическую длину |
строки s, результат |
имеет тип byte. Функция Pos(subs, s) ищет вхождение |
подстроки subs в строку s и возвращает номер первого символа subs в s или 0, |
еслиsubs не содержится в s. Процедура Str(x, s) преобразует числовое значение x в строку s, при этом |
для x может быть |
задан формат, как в процедурах вывода write и writeln, |
например, Str(x:6:2, s). Процедура Val(s, x, errcode) преобразует строку s в значение числовой переменной x, при этом строка s должна содержать символьное изображение числа. В случае успешного преобразования переменная errcode равна нулю. Если же обнаружена ошибка, то errcode будет содержать номер позиции первого ошибочного символа, а значение не x определено.
21. Классификация программного обеспечения.Языки программирования и их классификация. Метаязыки. Парадигмы и технологии программирования. Трансляторы и их виды.
Программное обеспечение-это совокупность программ, выполненных вычислительной системой. К программному обеспечению (ПО) относится также вся область деятельности по проектированию и разработке (ПО): технология проектирования программ (нисходящее проектирование, структурное программирование и др.); методы тестирования программ; методы доказательства правильности программ; анализ качества работы программ и др.
Программное обеспечение - неотъемлемая часть ЭВМ. Оно является логическим продолжением технических средств ЭВМ, расширяющие их возможности и сферу использования. |
|
Классификация программного обеспечения: -системное програмное обеспечение; -прикладное програмное обеспечение;-инструментарий программирования. |
Существует три категории: 1) |
Прикладные программы, непосредственно обеспечивающие выполнение необходимых пользователям работ.2) Системные программы: управление ресурсами ЭВМ;создание копий используемой информации; проверку работоспособности устройств компьютера;выдачу справочной информации о компьютере и др.. 3) Инструментальные программные системы, облегчающие процесс создания новых программ для компьютера.
Более или менее определенно сложились следующие группы программного обеспечения: операционные системы. системы программирования, инструментальные системы, интегрированные пакеты,динамические электронные таблицы,системы машинной графики,системы управления базами данных (СУБД),прикладное программное обеспечение.
Языки программирования и их классификация
По наиболее распространенной классификации все языки программирования, в соответствии с тем, в каких терминах необходимо описать задачу, делят на языки низкого и высокого уровня.Если язык близок к естественному языку программирования, то он называется языком высокого уровня, если ближе к машинным командам, – языком низкого уровня.В группу языков низкого уровня входят машинные языки и языки символического кодирования: Автокод, Ассемблер. Операторы этого языка – это те же машинные команды, но записанные мнемоническими кодами, а в качестве операндов используются не конкретные адреса, а символические имена. Все языки низкого уровня ориентированы на определенный тип компьютера, т. е. являются машинно–зависимыми.Машинно–ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.).К языкам программирования высокого уровня относят Фортран (переводчик формул
Алгол, Кобол (коммерческий язык – используется, в первую очередь, для программирования экономических задач), Паскаль, Бейсик (был разработан профессорами Дармутского колледжа Джоном Кемени и Томасом
Курцом.), Си (Деннис Ритч – 1972 году), Пролог (в основе языка лежит аппарат математической логики) и т.д.Программу, написанную на языке программирования высокого уровня, ЭВМ не понимает, поскольку ей доступен только машинный язык. Языки программирования также можно разделять на поколения:– языки первого поколения: машинно–ориентированные с ручным управлением памяти на компьютерах первого поколения.– языки второго поколения: с мнемоническим представлением команд, так называемые автокоды.– языки третьего поколения: общего назначения, используемые для создания прикладных программ любого типа. Например, Бейсик, Кобол, Си и Паскаль.– языки четвертого поколения: усовершенствованные, разработанные для создания специальных прикладных программ, для управления базами данных.- языки программирования пятого поколения: языки декларативные, объектно–ориентированные и визуальные. Например, Пролог, ЛИСП (используется для построения программ с использованием методов искусственного интеллекта), Си++, Visual Basic, Delphi. Языки программирования также можно классифицировать на процедурные и непроцедурные.В процедурных языках программа явно описывает действия, которые
необходимо выполнить, а результат задается только способом получения его при помощи некоторой процедуры, которая представляет собой определенную последовательность действий. Среди процедурных языков выделяют в свою очередь структурные и операционные языки. В структурных языках одним оператором записываются целые алгоритмические структуры: ветвления, циклы и т.д. В операционных языках для этого используются несколько операций. Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1. Среди операционных известны Фортран, Бейсик, Фокал. Непроцедурное (декларативное) программирование появилось в начале 70-х годов 20 века, К непроцедурному программированию относятся функциональные и логические языки. В функциональных языках программа описывает вычисление некоторой функции. Обычно эта функция задается как композиция других, более простых, те в свою очередь делятся на еще более простые задачи и т.д. Один из основных элементов функциональных языков – рекурсия. Оператора присваивания и циклов в классических функциональных языках нет. В логических языках программа вообще не описывает действий. Она задает данные и соотношения между ними. После этого системе можно задавать вопросы. Машина перебирает известные и заданные в программе данные и находит ответ на вопрос. Парадигмы
программирования Парадигма программирования — это система идей и понятий, определяющих стиль написания компьютерных программ, а также образ мышления программиста. Парадигма программирования в
современной индустрии программирования очень часто определяется набором инструментов программиста (язык программирования и операционная система).Парадигма программирования представляет (и определяет) то, как программист видит выполнение программы. Например, в объектно-ориентированном программировании программист рассматривает программу как набор взаимодействующих объектов, тогда как в функциональном программировании программа представляется в виде цепочки вычисления функций.Приверженность определённого человека какой-то одной парадигме иногда носит настолько сильный характер, что споры о преимуществах и недостатках различных парадигм относятся в околокомпьютерных кругах к разряду так называемых «религиозных» войн.История термина. Термин «парадигма программирования» впервые применил Роберт Флойд в своей лекции лауреата премии Тьюринга.Флойд отмечает, что в программировании можно наблюдать явление, подобное парадигмам Куна, но, в отличие от них, парадигмы программирования не являются взаимоисключающими: Если прогресс искусства программирования в целом требует постоянного изобретения и усовершенствования парадигм, то совершенствование искусства отдельного программиста требует, чтобы он расширял свой репертуар парадигм. Таким образом, по мнению Роберта Флойда, в отличие от парадигм в научном мире, описанных Куном, парадигмы программирования могут сочетаться, обогащая инструментарий программиста.
Основные модели программирования :Императивное программирование, Функциональное программирование, Логическое программирование,Объектно-ориентированное программирование.Подходы и приёмы: Структурное программирование, Процедурное программирование,Декларативное программирование, Обобщённое программирование,Порождающее программирование,Аспектно-ориентированное программирование,Рекурсия,Автоматное программирование,Событийно-ориентированное программирование,Компонентно-ориентированное программирование Императивное программирование — это парадигма
программирования, которая, в отличие от декларативного программирования, описывает процесс вычисления в виде инструкций, изменяющих состояние программы.
Императивная программа очень похожа на приказы, выражаемые повелительным наклонением в естественных языках, то есть это последовательность команд, которые должен выполнить компьютер. Функциональное программирование — раздел дискретной математики и парадигм программирования, в которой процесс вычисления трактуется как вычисление
значений функций в математическом понимании последних.Трансляторы и их виды. для перевода программы с языка программирования на язык машинных кодов используют специальные программы – трансляторы. Существует три вида транслятора: интерпретаторы (это транслятор, который производит пооператорную обработку и выполнение исходного кода программы), компиляторы (преобразует всю программу в
модуль на машинном языке, после чего программа записывается в память компьютера и лишь потом исполняется) и ассемблеры (переводят программу, записанную на языке ассемблера, в программу на машинном языке).
39. Инициализация графического режима. Множество графических процедур и функций среды программирования Pascal собраны в модуле Graph . Для подключения библиотеки графических функций и процедур необходимо подключить модуль к вашей программе строкой Uses graph ; Взаимодействие программы и видеосистемы в графических режимах обеспечивают драйверы. Драйверы собраны в файлах, имеющих расширение BGI : CGA . BGI , EGAVGA . BGI , HERC . BGI , IBM 8514. BGI , ATT . BGI , PC 3270. BGI и др. Драйвер – это специальная программа, осуществляющая управление тем или иным техническим средством ПК. Графический драйвер управляет графическим адаптером в графическом режиме. Графические возможности конкретного адаптера определяются разрешением экрана, т.е. общим количеством пикселей, а также количеством цветов. Кроме того, многие адаптеры могут работать с несколькими графическими страницами. Для инициализации графического режима используется процедура: InitGraph(var Driver, Mode: integer; Path:string); Где Driver – переменная типа integer , определяющая тип графического драйвера; Mode – переменная того же типа, задающая режим работы графического адаптера; Path – выражение типа string , содержащее путь доступа к файлу драйвера. Установка цвета. Драйвер EGAVGA . BGI позволяет использовать 16 цветов. Каждому цвету присвоен код – целое число, которое используется процедурами и функциями.
Black 0, Blue 1 ,Green 2 , Cyan 3 , Red 4 ,Magenta 5 ,Brown 6 ,LightGray7 , DarkGray 8 ,LightBlue 9
,LightGreen 10 ,LightCyan 11, LightRed12, LightMagenta 13 , Yellow 14, White 15
Цвет выводимых в графическом режиме на экран линий и символов можно задать процедурой SetColor( color : word ); аргумент которой – целое число от 0 до 15 или имя одной из приведенных выше констант. Установка цвета действует на те линии и тексты, которые выводятся после ее вызова, но не меняет цвет линий и символов, выведенных на экран ранее. Таким образом, процедуру SetColor следует вызывать каждый раз перед выбором нового цвета. Если цвет не установлен, то используется белый цвет. Установка цвета фона. Чтобы установить цвет фона для всего экрана, используется процедура: SetBkColor( color : word ); Если процедура установки цвета фона не вызвана, экран будет черным. Установка указателя вывода Процедура MoveTo ( x, y: integer) перемещает указатель в точку с координатами x, y Процедура MoveRel ( dx, dy: integer) перемещает указатель на dx, dy пикселей относительно последнего положения. Функции GetX и GetY возвращают координаты x, y указателя вывода. Установка точки Процедура PutPixel ( x, y: integer; color: word) устанавливает точку с координатами ( x, y) и закрашивает ее указанным цветом color. Функция GetPixel ( x, y: integer): word возвращает значение цвета, в который окрашена точка с координатами ( x, y). Рисование линий Процедура Line ( x1, y1, x2, y2: integer) вычерчивает линию между двумя точками экрана с координатами ( x1, y1) и ( x2, y2). Процедура LineTo ( x, y: integer) вычерчивает линию от последнего положения указателя до точки с координатами ( x, y). Окружность, эллипс, дуга, сектор Процедура Circle ( x, y: integer; r: word) вычерчивает окружность радиуса r с центром в точке с координатами ( x, y). Процедура Arc ( x, y, ugol_ begin, ugol_ end, r: integer) вычерчивает дугу окружности радиуса r с центром в точке с координатами ( x, y). Параметры ugol_ begin и ugol_ end задают угловые координаты начала и конца дуги. Отсчет углов ведется против часовой стрелки. Значения угловых координат задается в градусах. Процедура Ellips ( x, y: integer; ugol_ begin, ugol_ end, rx, ry: word) вычерчивает эллипс или дугу эллипса с центром в точке с координатами ( x, y). Параметры ugol_ begin и ugol_ end задают угловые координаты начала и конца дуги. Параметры rx и ry определяют горизонтальный и вертикальный радиусы эллипса. Процедура PieSlice ( x, y: integer; ugol_ begin, ugol_ end, r: word) вычерчивает сектор окружности радиуса r с центром в точке с координатами ( x, y). Параметры ugol_ begin и ugol_ end задают угловые координаты начала и конца сектора. Сектор может быть закрашен в соответствии со стилем, заданным процедурой SetFillStyle (о ней чуть позже). Процедура Sector ( x, y: integer; ugol_ begin, ugol_ end, rx, ry: word) вычерчивает сектор эллипса с центром в точке с координатами ( x, y) и горизонтальным радиусом rx, вертикальным - ry. Параметры ugol_ begin и ugol_ end задают угловые координаты начала и конца сектора. Сектор может быть закрашен в соответствии со стилем, заданным процедурой SetFillStyle. Прямоугольник; закрашенный прямоугольник; параллелепипед Процедура Rectangle ( x1, y1, x2, y2: integer) вычерчивает контур прямоугольника. Параметры x1, y1 задают положение левого верхнего угла, x2, y2 – правого нижнего. Процедура Bar ( x1, y1, x2, y2: integer) вычерчивает закрашенный прямоугольник. Параметры x1, y1 задают положение левого верхнего угла, x2, y2 – правого нижнего. Стиль и цвет заливки определяется процедурой SetFillStyle. Процедура Bar3 D ( x1, y1, x2, y2: integer; глубина: word; граница: boolean) вычерчивает параллелепипед. Параметры x1, y1 задают положение левого верхнего угла, x2, y2 – правого нижнего угла ближней грани. Параметр глубина задает расстояние между передней и задней гранями в пикселях. Параметр граница определяет, нужно ли вычерчивать верхнюю границу задней грани параллелепипеда. Стиль и цвет заливки ближней грани определяется процедурой SetFillStyle. Вывод текста в графическом режиме. Процедура OutText ( text: string) выводит строку символов text от текущей позиции указателя вывода и перемещает указатель в точку, расположенную за последним выведенным символом. Процедура OutTextXY ( x, y: integer; text: string) выводит строку символов text, начиная с точки с координатами ( x, y), при этом указатель своего положения не меняет, т.е. остается в точке ( x, y).
16. Перечислимый и ограниченный типы данных.
Этот тип данных получил название перечисляемого, потому что он задаётся в виде перечисления некоторых значений. Эти значения образуют упорядоченное множество и являются константами этого типа. Для объявления переменной список возможных значений, разделённых запятой, указывается в круглых скобках. Например,
Var month: (january, february, marth, april, may, june, jule, august, september, october, november, december);
Упорядоченность элементов перечисляемого типа определяется порядком их следования. Самый левый имеет минимальное значение (значение функции ord для него равно 0), а наиболее правый - максимальное.
Ограниченный тип данных представляет собой интервал значений порядкового типа, называемого базовым типом. Описание типа задаёт наименьшее и наибольшее значения, входящие в этот интервал.
Например,Var a: 1..25; ch: 'a' ..'z';
Здесь переменные а и ch могут принимать значения только из указанного интервала; базовым типом для переменой а является целый тип, а для переменной ch – символьный .Переменная ограниченного типа сохраняет все свойства переменных базового типа.Для чего вводится ограниченный тип данных? Использование ограниченного типа делает программу наиболее понятной и наглядной. Например, если в программе переменная b может принимать только значения 3, 4, 5, 6, 7, 8, то лучше описать её следующим образом: Var b: 3..8;, чем Var b: Integer; так как в случае выхода значения b за диапазон 3..8 в первом случае будет выдано диагностическое сообщение, которое поможет найти ошибку. Во втором случае будет получен неправильный результат, что затруднит поиск ошибки. Таким образом, второй вариант описания переменной следует использовать в тех случаях, когда диапазон значений заранее неизвестен либо занимает весь допустимый интервал значений для рассматриваемого типа.
Основные (стандартные) типы данных часто называют арифметическими, поскольку их можно использовать в арифметических операциях. Для описания основных типов определены следующие ключевые слова: int (целый);
char (символьный);
wchar_t (расширенный символьный); bool (логический);
float (вещественный);
double (вещественный с двойной точностью).
Первые четыре типа называют целочисленными (целыми), последние два – типами с плавающей точкой. Код, который формирует компилятор для обработки целых величин, отличается от кода для величин с плавающей точкой. Существует четыре спецификатора типа, уточняющих внутреннее представление и диапазон значений стандартных типов:
short (короткий); long (длинный); signed (знаковый);
unsigned (беззнаковый).
8)«Основные (базовые) типы данных»
Понятие типа данных
Напомним о понятии «переменная».В алгоритмических языках под переменной понимают область памяти, где хранятся обрабатываемые данные. (Исходные, промежуточные и итоговые.). Название происходит от того, что при работе ЭВМ данные могут менять свои значения.Область памяти характеризуется размером и адресом начала.
Чтобы разные переменные человеку легче было отличать друг от друга, им даются имена (идентификаторы). (Компьютер отличает переменные друг от друга по их началу в памяти.)
Информацию, хранящуюся в переменной в момент обращения к этой переменной называют ЗНАЧЕНИЕМ переменной.
адрес начала и размер в памяти
|| |
+--+- память -+----------+ |
|
||
| |
| |
| |
|
| |
ПЕРЕМЕННАЯ |
| |
|
| |
/ \ |
| |
|
+- имя |
значение – тип |
||
|
|
(возможный диапазон значений) |
|
В переменных хранятся разные данные, разные по размеру и назначению. Компьютер работает и с числами, и с буквами, и с картинками. Выполняемые над разными объектами действия должны быть различны.
Для обеспечения принципа детерминированности (компьютер должен знать, что можно делать с разными данными), все данные разбиты на группы, с данными одной группы можно выполнять определенный набор действий. Заодно, договорились, что и размер места в памяти данных одного типа одинаков. Описанные группы данных называют данными одного типа. Типы данных так же имеют имена.
Будем изучать все типы данных по одной схеме:
1)имя типа
2)размер в памяти (кодирование)
3)набор операций
4)связь с данными других типов
Кпростейшим (базовым) типам данных относят такие, для которых достаточно только имени, чтобы компьютер понял, сколько места выделить в памяти для их хранения и какие операции с ними можно выполнять.
*** Классификация типов данных
* Сложные (структурные) типы данных. Данные этих типов, как и данные
базовых типов, занимают в памяти фиксированную область.
Фактически, являются совокупностью данных базового или самого
структурного (кроме файлов) типа.
Идентификатор заложен в транслятор (массив, запись, множество, файл).
Кодирование требует уточнений.
Набор внутритиповых операций связан с обращением к данным.
Набор операций связи с данными других типов связан с кодированием.
* Динамические типы данных. Область памяти, где хранятся данные этих
типов, может изменять со временем свои размеры.
В современных языках программирования специальных средств не имеют.
Идентификатор определяется программистом.
Кодирование определяется программистом.
Набор внутритиповых операций определяется программистом.
Набор операций связи с данными других типов определяется программистом.
***** БАЗОВЫЕ ТИПЫ ДАННЫХ
1 Базовые (простые) типы данных (базовые способы хранения информации).
Для работы с данными этих типов не требуется никаких уточнений,
достаточно только указать тип.
Идентификатор, кодирование и набор операций заложены в транслятор.
Есть возможность увеличения набора операций (функции пользователя).
3 Получение информации базовых типов происходит специальным оператором
присваивания, из константы или чтением с клавиатуры (или из файла).
Вывод данных базовых типов организуется единой стандартной командой.
10)Базовый тип данных - целое число.
(Имена типов приводятся согласно ЯП Паскаль)
Компьютер предназначен прежде всего, для работы с числами. Выделяют несколько типов целых чисел.
Целые натуральные (без знака) и целые со знаком. Кроме того, целые числа занимают разное количество байт.
Для числа без знака используется двоичная запись в выделенное место памяти. Поскольку счет идет с 0, то:
для одного байта диапазон [0..255] (byte) {=2^8-1}; для двух байт - [0..65535] (unsign) {=2^16-1}; для четырех байт - [0..4294967295] {=2^32-1}
Для числа со знаком самый старший бит выделен для знака 0 - число положительное, 1 - отрицательное.
В целом, отрицательное число образуется из положительного за два шага: 1) в двоичной записи числа обратим цифры "1" в цифры "0" и наоборот, 2) к полученному числу добавим 1 (действие выполняем в двоичной системе счисления).Очевидно появление цифры "1" на первом месте, если там был "0".
Такое кодирование решает три задачи:
1)образование положительного числа из отрицательного выполняется теми же двумя операциями (убедитесь сами!)
2)числа "+0" и "-0" представляются одинаково.
3)кодирование самообратимо { k(k(x))=x }
00000101 - число 5 в 1 байте
00000101 - исходное
11111010 - после инверсии
11111011 - после добавления 1
11111011 - число -5 в 1 байте
11111011 - исходное
00000100 - после инверсии
00000101 - после добавления 1 Описанный способ представления отрицательных чисел называется «дополнительное кодирование». Дополнение до 1, которая при сложении числа А с числом –А уйдет за пределы выделенной области, останется 0.
Прежде встречались:- прямое кодирование – просто у отрицательных чисел вписывалась 1 в старший бит. Тое есть число 0 можно было писать 00000000 и 10000000 (+0 и -0!!!)
- обратное кодирование – у числа 0 менялись на 1, а 1 на 0. Тоже в наличии значения +0 и -0 соответственно 00000000 и 11111111
Взависимости от выделяемой памяти имеются:
для одного байта диапазон [-128..+127] (shortint)
для двух байт - [-32768..+32767] (integer)
для четырех байт - [-2147483648..+2147483647] (longint)
Вязыке PASCAL
имя типа |
диапазон значений |
||||
byte |
1 байт, без знака, |
0..255 |
|||
word |
1 байт, без знака, |
0..65535 |
|||
shortint |
1 байт, со знаком, |
-128..+127 |
|||
integer |
2 байт, со знаком, |
-32768..+32767 |
|||
longint |
4 байт, со знаком, |
-2147483648..+2147483647 |
|||
Способ кодирования – двоичное представление и дополнительный код для отрицательных чисел.
Основные операции. |
BASIC PASCAL |
|
сложение a и b |
a+b |
a+b |
вычитание a и b |
a-b |
a-b |
умножение a на b a*b |
a*b |
|
Делить целые числа нельзя! – Результат – не целое число.
деление нацело a на b a\b a div b
остаток от деления a на b a mod b a mod b
взятие модуля a |
abs(a) |
abs(a) |
логические И от a и b |
a and b a and b |
|
ИЛИ от a и b |
a or b |
a or b |
отрицание a |
not a |
not a |
Связь с данными других типов.
Вязыке pascal различают 5 типов целочисленных данных, связь между ними автоматическая, то есть аргументы операций приводятся к одному типу, выполняется операция. Попытка сохранения результата в другом типе, например word как integer, может привести к ошибкам. Числа, большие чем 32767, будут показаны как отрицательные.Пока другие типы не изучались, связь целочисленных типов с ними рассматривать не будем.
Вязыке basic программу можно написать не обращая внимания на типы. Имеющийся целочисленный тип соответствует паскалевскому типу integer, обозначается наличием знака % в конце имени переменной.
3) Способы записи алгоритмов
Алгоритм – точная конечная последовательность команд, приводящая от исходных данных к искомому результату за конечное число шагов
Способы (формы) записи алгоритмов
Словесно-пошаговый, алгоритмический язык , блок-схема, структурограмма.
Словесно-пошаговый способ записи алгоритмов Описывает алгоритм на естественном языке, задавая шаги в виде последовательных пунктов. Не смотря на простоту этого способа, он имеет множество недостатков: отсутствие строгой формализации, толкование шагов не всегда однозначно, описание чрезмерно многословно. Классическим примером словесно-пошагового алгоритма являются рецепты приготовления блюд.
Графический способ описания алгоритмов :Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Достоинство блок схем – наглядность и простота записи алгоритма. Каждому действию алгоритма соответствует геометрическая фигура
В линейном алгоритме команды выполняются последовательно,блок-схема будет иметь вид:
Т.к. в разветвляющемся алгоритме порядок следования команд может быть разный,блок-схема примет вид:
В циклическом алгоритме некоторые действия повторяются несколько раз и для него блок-схема примет вид:
Структурограммы : дают полное визуальное представление деталей логических операций над группами операторов программы. Структурограмма (схема Насси–Шнейдермана) – это схема, иллюстрирующая структуру передачи управления внутри модуля с помощью вложенных друг в друга блоков. Каждый блок имеет форму прямоугольника и может быть вписан в любой внутренний прямоугольник любого другого блока. Запись внутри блока производится на естественном языке или с помощью математических обозначений. Символ «Обработка» содержит описание действий, выполняемых оператором или группой операторов. В подобном символе можно помещать операторы присваивания, ввода/вывода и т. д. Управление передается в прямоугольник сверху, а выходит из него снизу. Символ «Cледование» объединяет ряд следующих друг за другом процессов обработки. В отдельные прямоугольники записываются логически завершенные шаги программы. Управление начинает свой путь на внешней стороне верхнего прямоугольника, проходит через каждый прямоугольник и завершает путь на внешней стороне нижнего прямоугольника. Символ «Решение» применяется для обозначения конструкций IF-THEN-ELSE. Условие (вопрос) располагается в верхнем треугольнике, варианты ответов – по его сторонам, а процессы обработки обозначаются прямоугольниками. В результате принятия решения управление передается в один из нижних прямоугольников: Для усеченной конструкции разветвления IF-THEN прямоугольник, соответствующий ветви невыполнения условия – НЕТ, следует оставить пустым. Символ CASE представляет расширение блока решение. Условие, называемое селектором выбора, записывается в верхнем треугольнике. Варианты выхода из треугольника, соответствующие точно определенным значениям селектора, размещаются в маленьких треугольниках по его
левой стороне. Каждому варианту соответствует свой символ обработки. По правой стороне треугольника размещается выход по несовпадению условий и соответствующий ему альтернативный символ обработки. Символ «Цикл» служит для обозначения конструкций WHILE-DO и REPEAT-UNTIL. Изображенный внутренним прямоугольником процесс повторяется некоторое число раз либо пока выполняется некоторое условие (WHILE), либо до тex пор пока не выполнится некоторое условие (UNTIL). Затем управление выходит из нижней стороны внешнего прямоугольника. Условие окончания цикла размещается в верхней полосе внешнего прямоугольника для цикла WHILE-DO и в нижней полосе – для цикла REPEAT-UNTIL. Горизонтальная линия внутри символа показывает место проверки условия завершения цикла – в его начале для цикла WHILE-DO и в его конце для цикла REPEAT-UNTIL.ПОНЯТИЕ АЛГОРИТМИЧЕСКОГО ЯЗЫКАДостаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Под исполнителем в алгоритмическом языке может подразумеваться не только компьютер, но и устройство для работы «в обстановке». Программа, записанная на алгоритмическом языке, не обязательно предназначена компьютеру. Как и каждый язык, алгоритмический язык имеет свой словарь. Основу этого словаря составляют слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алгоритма. Такие команды называют простыми командами. В алгоритмическом языке используют слова, смысл и способ употребления которых задан раз и навсегда. Эти слова называют служебными. Использование служебных слов делает запись алгоритма более наглядной, а форму представления различных алгоритмов - единообразной.При построении новых алгоритмов могут использоваться алгоритмы, составленные ранее. Алгоритмы, целиком используемые в составе других алгоритмов, называют вспомогательными алгоритмами. Вспомогательным может оказаться любой алгоритм из числа ранее составленных. Не исключается также, что вспомогательным в определенной ситуации может оказаться алгоритм, сам содержащий ссылку на вспомогательные алгоритмы.Очень часто при составлении алгоритмов возникает необходимость использования в качестве вспомогательного одного и того же алгоритма, который к тому же может быть весьма сложным и громоздким. Было бы нерационально, начиная работу, каждый раз заново составлять и запоминать такой алгоритм для его последующего использования. Поэтому в практике широко используют, так называемые, встроенные (или стандартные) вспомогательные алгоритмы, т.е. такие алгоритмы, которые постоянно имеются в распоряжении исполнителя. Обращение к таким алгоритмам осуществляется так же, как и к «обычным» вспомогательным алгоритмам. У исполнителя-робота встроенным вспомогательным алгоритмом может быть перемещение в склад из любой точки рабочего поля; у исполнителя-язык программирования Бейсик это, например, встроенный алгоритм «SIN».Алгоритм может содержать обращение к самому себе как вспомогательному и в этом случае его называют рекурсивным. Если команда обращения алгоритма к самому себе находится в самом алгоритме, то такую рекурсию называют прямой. Возможны случаи, когда рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение. Такая рекурсия называется косвеннойАлгоритмы, при исполнении которых порядок следования команд определяется в зависимости от результатов проверки некоторых условий, называют разветвляющимися. Для их описания в алгоритмическом языке используют специальную составную команду - команда ветвления. Она соответствует блок-схеме «альтернатива» и также может иметь полную или сокращенную формуАлгоритмы, при исполнении которых отдельные команды или серии команд выполняются неоднократно, называют циклическими. Для организации циклических алгоритмов в алгоритмическом языке используют специальную составную команду цикла.
14. *** Работа с файлами.
1 Определение.
Файл - информация, подготовленная для хранения во внешней
памяти или к использованию на внешних устройствах (ВУ).
Частным случаем файла является ТЕКСТ (TEXT)
Текст - файлы последовательного доступа (чтение и запись данных
начинаются всегда от начала файла)
В файлах могут храниться как данные, так и команды (программы)
Различают файлы программы:
- хранящие текст программы на языке высокого уровня
-хранящие исполняемый код для прцессора
файлы данных:
-последовательного доступа (чтение и запись данных начинаются
всегда от начала файла)
-прямого доступа (чтение и запись данных возможны для любого места)
2 Способы представления (хранения).
Для различия между собой, файлы имеют имена. Имена имеют и ВУ:
CON, KBD, CRT, PRN, LPT1,...LPT3, COM1, COM2 (ДОС);
GRP (MSX-basic); SCRN, KYBD (GWbasic)
Стандартными внешними устройствами являются клавиатура и дисплей.
Используя при передаче файловой информации вместо имен файлов имена
устройств, получают ввод информации с указаных устройств или вывод информации
на нестандартные устройства. Поэтому имена устройств нельзя давать файлам.
Полное имя файла состоит из трех частей:
адресная - <имя устройства памяти>:[/<имена подкаталогов через />]
именная - <имя файла до 8 знаков>
расширение имени файла - <три знака>
При написании, между именем файла и расширением ставится точка.
При работе с текущим устройством адресная часть полного имени файла может
быть пропущена (берется "по умолчанию"), важными являются
только имя и расширение, которые обычно называют именем файла.
ТЕКСТ - набор данных, имеющий вид упакованных строк, закачивается
специальным знаком "конец файла" <26>.
Файлы - программы, доступные процессору, т.е. могут сразу исполнены,
имеют расширения .COM или .EXE . Имена таких файлов служат командами
исполнения содержимого для операционной системы. Операционная система
(ОС) - специальная программа, автоматически запускаемая при включении
компьютера, основным назначением которой является поиск и исполнение
файлов-программ.
Файлы - программы на языке "Pascal" - содержат текст программы,
являются строками. Могут быть созданы с помощью любого текстового
редактора. С помощью программы-транслятора могут быть преобразованы
в файлы, исполняемые процессором.
Обычно специальный редактор объединяют с транслятором, куда
добавляются средства контроля программ и систему подсказок (Help) -
получается система программирования. Результат работы такой системы,
записанный в виде .COM или .EXE - файла, в дальнейшем, присутствия
системы программирования не требует.
По стандарту языка "BASIC", для выполнения программ обязательно
требуется присутствие BASIC-системы. При работе которой оператор
находится в среде специального редактора. Набираемые команды
могут быть выполнены немедленно, или, если имеют метку - номер,
запомнены в оперативной памяти. Команды оперативной памяти
могут быть просмотрены командой "LIST" или исполнены командой "RUN"
Из оперативной памяти программа может быть перенесена во внешнюю
командой SAVE"<ИМЯ ФАЙЛА>"[,A]
Запись присходит в более коротком кодированном варианте или
(при наличии флажка - буквы "A" в команде) в полном варианте,
пригодном для просмотра и печати средствами ДОС.
Командой восстановления программы в оперативную память из файла
является LOAD"<ИМЯ ФАЙЛА>"[,R]
Флаг 'R' служит для немедленного запуска программы после "загрузки".
Загрузить в оперативную память и сразу исполнить программу можно
командой RUN"<ИМЯ ФАЙЛА>"
Обычно, файл - программа на языке "BASIC" имеет расширение .BAS .
Запись/загрузка подпрограмм в кодах проводится командами
BSAVE"<имя>" BLOAD"<имя>"
При работе с кассетным магнитофоном в качестве ВУ, используют
команды CSAVE"<имя>" CLOAD"<имя>"
Есть возможность объединения двух текстов - программ в один.
Для этого один текст должен быть в оперативной памяти, а
другой, заранее подготовленный, должен быть записан в файл в
полном варианте. Команда MERGE"<имя подготовленного файла>"
создаст в оперативной памяти совместный текст обеих программ.
Если в склеиваемых текстах были строки с одинаковами номерами,
то останется только строка подготовленного файла.
Итак, на примере работы с файлами-программами на языке "BASIC",
имеем три вида работы с файлами - создание (SAVE), чтение (LOAD)
и добавление (MERGE).
Для работы с файлами данных в языке BASIC, в начале программы
должно быть указано число одновременно открытых файлов
MAXFILES=<N>, по умолчанию, это число =1. Каналы связи программы
с файлом нумеруются, номера используются в командах. В файлах
могут быть только данные базовых типов.
В языке PASCAL вместо номеров каналов связи вводятся переменные
файлового типа, которые описываются как
:file of <тип элементов>; или :text;
Элементы файлов могут быть любых типов, кроме файлового.
Слово "text" указывает на файл строк произвольной длины.
*Способ образования (хранения). <цифры приведены для ЭВМ "Yamaha">
В памяти компьютера, для каждого файла, выделяется буфер <256 байт>
При создании файла последовательного доступа, заполняется не файл,
а буфер. По заполнении буфера, все его содержимое копируется во
внешне устройство (файл), буфер очищается и готов заполняться снова.
При чтении, часть содержимого файла, копируется в буфер, откуда
читается программой. По мере необходимости, в буфер считываются
очередные порции информации.
При работе файлов прямого доступа, команды смены содержимого
буфера приходится программировать.
Для работы буфера используются служебная информация - блок
управления файлом (File Control Blok - FCB) <9 байт>
*Для работы с текстами обычно используют специальный редактор.
Для работы с файлами данных в языке BASIC, в начале программы
должно быть указано число одновременно открытых файлов
MAXFILES=<N>, по умолчанию, это число =1. Каналы связи программы
с файлом нумеруются, номера используются в командах.
В языке PASCAL вместо номеров каналов связи вводятся переменные
файлового типа, которые описываются как :text;
3 Основные операции.
С файлами проделывают две операции: открывают с какой-то целью
и закрывают. (file - папка (англ)). Существуют три цели открытия
файла - для занасения в него данных (заново)
-для добавления в него данных (в конец)
-для извлечения из него информации.
BASIC |
PASCAL |
открыть |
|
open "<имя>" for output as#1 |
rewrite(f) |
для записи |
|
open "<имя>" for input as#1 |
reset(f) для чтения |
||
open "<имя>" for append as#1 |
append(f) |
для добавления |
|
close(#1) |
close(f) |
закрыть |
|
После открытия файла стандартные команды получения и вывода информации,при наличии указания на номер или имя канала связи, работают с файлом:
PRINT #1, A;B |
WRITE(f,A,B); WRITELN(f,A,B); |
INPUT #1, X,Y |
READ(f,X,Y); READLN(f,X,Y); |
В языке PASCAL файловая переменная перед использованием связывается
с именим файла - строкой знаков специальной командой ASSIGN(f,<имя>);
4 Связь с данными других типов.
Элементом текста является строка.
Возможны файлы данных любого вообразимого типа. В файле могут быть несколько данных одного типа.Файлы программ считаются двоичными. В них хранятся байты кодов команд процессора (в двоичной форме).
18) Линейные списки (основные операции)
Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (NIL).Чтобы список существовал, надо определить указатель на его начало. Опишем переменные:
Var и, х: EXS;
Создадим первый элемент:
New(u); {выделим место в памяти для переменной типа S}
u^.next:=nil; |
{указатель пуст} и^.data:=3; {информационное поле первого элемента} |
Продолжим формирование списка, для этого нужно добавить элемент в конец списка.
х:=и; {Введем вспомогательную переменную указательного типа, которая будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом.}
New(x^.Next)•,{выделим область памяти для следующего элемента списка}
x:=x^.Next; {переменная х принимает значение адреса выделенной области памяти}
x^.Data:=5; {определим значение этого элемента списка} x^.Next.=Nil:
Оформим создание списка в виде процедуры, в которой его элементы вводятся с клавиатуры.
Procedure Init(Var u: Exs); {создание списка}
Var х, у: Exs; Digit: Integer; {значение информационной части элемента списка} Begin
Writeln('Введите список '); u:=Nil; {список пуст} WriteLn('Bводите элементы списка. Конец ввода 0); Read(Digit);
While Digit<>0 Do Begin
New(y); {формирование элемента списка} y^.Nexf:=Nil; y^.Data:=Digit; If u=nil Then u:=y {вставляем первый элемент списка}
Else x^.Next:=y; {вставляем элемент в конец списка}
х:=у; {переносим значение указателя на последний элемент списка} Read(Digit);
End;
Writein;
End;
Итак, мы построили список добавлением элементов в конец списка. Вставим элемент со значением 7 в начало списка.
Удаление элемента из начала списка
Напишем фрагмент программы:
х:=и; {запомним адрес первого элемента списка} u:=u^.next; {теперь и указывает на второй элемент списка} Dispose(x); {освободим память, занятую переменной х^}
Удаление элемента из середины списка
Для этого нужно знать адреса удаляемого элемента и элемента, находящегося в списке перед ним. х:=и; {переменная х для хранения адреса удаляемого элемента}
{найдем адреса нужных элементов списка }
While (x<>Nil) And (x^.Data<>Digit) Do Begin dx:=x; x:=x^.Next End;
dx^.Next:=x^.Next; Dispose(x);
Удаление элемента из конца списка
Оно производится, когда указатель ах показывает на предпоследний элемент списка, а х — на последний.
{найдем предпоследний элемент} х:=и; ах:=и;
While x^.Next<>NIL Do Begin dx:=x; x:=x^.Next; End;
{удаляем элемент х^ из списка и освобождаем занимаемую им память} dx^.Next:= Nil; Dispose(x);
Стек
Стек — упорядоченный набор элементов, в котором добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
В любой момент времени доступен лишь один элемент стека — верхний. Из определения следует, что извлекать элементы из стека можно только в порядке, обратном порядку их добавления в стек (первый пришел, последний ушел).Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.Стеки довольно часто встречаются в практической жизни. Процесс сборки и разборки ее подобен процессу функционирования стека.
Основные операции со стеками
Как было сказано выше, стек является динамической структурой, размеры которой изменяются по мере добавления и удаления элементов. Поэтому удобнее всего применить для реализации стека динамическую структуру данных, а именно список.
Дадим новое определение стека. Стек — это список, в котором добавление новых элементов и извлечение имеющихся происходит с начала (или конца) списка.
Значением указателя, представляющего стек, является ссылка на вершину стека, каждый элемент стека содержит поле ссылки.
Таким образом, описать стек можно следующим образом:
Type EXST=^ST;
ST=Record Data: Integer; Next: EXST; End;
Var Stack: EXST; |
{текущая переменная} |
Тогда, если стек пуст, то значением указателя равно NIL.
Занесение в стек
Процедура занесения элемента в стек должна содержать два параметра — первый задает нужный стек, второй — заносимое в него значение. Обозначим их соответственно х1 и с.
Занесение в стек производится аналогично вставке нового элемента в начало списка:
Procedure WriteStack (Var ir.EXST; digit: Integer); {запись в стек} Var x:.EXST;
Begin
New(x); {создание нового элемента стека} x^.Data:=diglt; х^.Nехt:=u {созданный элемент определить как вершину стека} u:=х;
End;
Основная программа формирования стека будет иметь вид:
Var Stack: EXST; {текущая переменная} digit: Integer;
Begin
Stack:=Nil;
WriteLn(1'Введите элементы стека. Окончание ввода — О'); Read(Digit); While Digit<>O Do Begin WriteStack(Stack, digit); Read(digit); End
End.
Извлечение элемента из стека.
В результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека и изменено значение указателя на начало списка.
Procedure ReadStack(Var u-.EXST; Var i-.Integer); Var x: EXST;
Begin
i:u^.Data; x:=u; u:=u^.Next; Dlspose(x);
End;
Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию проверки пустоты обрабатываемого стека. function Free(u:EXST):Boolean;
Очереди
Очередь — это упорядоченный набор элементов, в котором извлечение элементов происходит с одного его конца, а добавление новых элементов — с другого.
Очередь является динамической структурой — с течением времени изменяется и ее длина, и набор составляющих ее элементов. Поэтому удобно представить ее в виде списка.
Описание очереди на языке программирования:
Type ЕХО=^О; O=Record Data: Integer; Next: EXO; End;
Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.
В очереди, в силу ее определения, доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы. Поэтому для работы с очередью необходимо описать две переменные:
Var xl, х2: EXO;
где xl — соответствует началу очереди и будет использоваться для вывода элемента из очереди, х2 — соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.
Поскольку очередь представлена списком, занесение элемента в очередь соответствует занесению элемента в конец списка.
Procedure WriteO (Var xl,x2: EXO; с: Integer); Varи: EXO;
Begin
New(u); u^.data:=c; u^.nexf:=^NIL;
If xl=NIL Then xl:=u {если очередь пуста}
Else x2^.next:=u; {заносим элемент в конец списка} х2:=u;
End;
Основная программа, создающая очередь, может быть такой:
Begin
xl:=NIL; x2:=NIL;
Write Ln('Введите элементы очереди. Конец ввода — О'); Read(Digit);
While Digit<>O Do Begin WriteO(xl,x2,Digit); Read(Digit); End
End.
Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка.
Поскольку извлечение элемента из пустой очереди осуществить нельзя, опишем логическую функцию, проверяющую, есть ли элементы в очереди.
Procedure Reado(Var xl,x2:EXO; Var c:Integer); Var u:ЕХО;
Function Nul (xl: ЕХО): Boolean; Begin Nul:=(xl=Nil); End;
Begin
If Nul(xl) Then Writeln(‘0чepeдь пуста') Else
Begin c:=xl^.Data; u:=xl; xl:=xl^.Next; Dispose(u); End;
End;
Деревья
Введение основных понятий
Граф — это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.
Если на каждом ребре задать направление, то граф будет ориентированный.
Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем. Замкнутый путь, состоящий из различных ребер, называется циклом.Граф называется связным, если любые две его вершины соединены путём. Связный граф без циклов называется деревом. На рис. 54 изображено дерево, в узлах которого располагаются символы.
Примечание. С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.
Для дальнейшей работы с деревьями необходимо определить ряд понятий.
•Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.
•Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.
•Количество непосредственных потомков внутренней вершины называется ее степенью.
•Степенью дерева называется максимальная степень всех вершин. Например:
•вершины F, D, Е являются непосредственными потомками вершины В;
•вершины F, D, Е являются листьями;
• вершины С, G, Н — внутренние;
•степень вершины В — 3, а вершины Н — 1;
•степень дерева равна 3.
Двоичное дерево — это дерево, в котором из каждой вершины исходит не более двух ребер.
6.2. Представление деревьев
Дерево — это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.
Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой — сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два - левое и правое.
Type TreeLink =^Tree;
Tree=Record
Data: <mun данных>;
Left, Right: TreeLink;
End;
Корень дерева опишем в разделе описания переменных:
Var kd: TreeLink;
6.3.Основные операции над деревом
Косновным операциям над деревьями относятся:
• занесение элемента в дерево;
• обход дерева;
• удаление элемента из дерева. Рассмотрим вставку и обход дерева на примере следующей задачи.
6.5.Удаление из дерева
Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной (рис. 55) или из нее выходит только одно ребро (рис. 56). Для этого нужно изменить соответствующую ссылку у предшествующей вершины.
Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины (рис. 57).Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая:
•удаляемая вершина имеет два поддерева (В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка);
•удаляемая вершина имеет не более одного поддерева (0 или 1);
•удаляемой вершины в дереве нет. Ниже приведена рекурсивная процедура deltree, решающая поставленную задачу. Она отыскивает элемент с заданным ключом и удаляет его.
В процедуре deltree описана вспомогательная процедура dl, которая работает только в первом из трех перечисленных случаев.Вспомогательная процедура dl "движется" по правой ветви левого поддерева исключаемого элемента q^ и заменяет значение ключа в q^ на соответствующее значение из самого правого элемента r^ левого поддерева.
1. Базис, алфавит, основание.
Система счисления - способ записи (изображения) чисел.
Символы, при помощи которых записывается число, называются цифрами.
Системы счисления, в которых количественный эквивалент каждой цифры зависит от ее положения (позиции) в коде(записи) числа, называются позиционными. Основанием позиционной системы счисления называется количество знаков или символов, используемых для изображения числа в данной системе счисления. Базисом позиционной системы счисления называется последовательность чисел, каждое из которых задает количественное значение или "вес" каждого разряда.
Например: Базисы некоторых позиционных систем счисления.
Десятичная система: 100, 101, 102, 103, 104, ..., 10n, ...
Двоичная система: 20, 21, 22, 23, 24, ..., 2n, ...
Восьмеричная система: 80, 81, 82, 83, 84, ..., 8n, ...
Совокупность различных цифр, используемых в позиционной системе счисления для записи чисел, называется алфавитом системы счисления. Количество цифр в алфавите равно основанию системы счисления.
Уравновешенные системы счисления
---===---
Двоичная СС с большим успехом используется в компьютерной технике до сих пор. Однако выявились и существенные недостатки использования
двоичной СС, влияющие на скорость работы процессора и надежность передачи информации.
Одним из этих недостатков является так называемая проблема представления отрицательных чисел. Попытка преодолеть этот и другие недостатки двоичной системы счисления стимулировала использование в компьютерах других систем счисления и развитие собственно теории систем счисления.
Выбирая систему кодирования информации в компьютере, разработчики в первую очередь думают о быстродействии процессора, т.е. о скорости обработки закодированной информации.
///
Что привычно и хорошо для человека, выполняющего вычисления на бумаге, не всегда хорошо для компьютера. Для того чтобы сложить два целых числа
с разными знаками, и человек, и компьютер, вообще говоря, должны выполнить следующие действия:
1)взять модули слагаемых;
2)сравнить эти модули;
3)запомнить знак большего по модулю слагаемого;
4)получившийся результат з
5)из большего модуля вычесть меньший модуль;
6)записать со знаком из п. 3.
Многовато будет для простой и часто используемой операции!
\\\
В десятичной системе счисления для представления отрицательных чисел человек использует знак числа. То, есть для записи отрицательных чисел имеющихся 10 знаков недостаточно. Используется еще один знак - '-'.
То есть для записи отрицательных десятичных чисел потребоваломь 11 знаков! Аналогично, для записи отрицательных двоичных чисел требуется 3 знака,
но в нашем распоряжении их два - 0 и 1. Для решения проблемы вначале века использовалось прямое кодирование: в старший бит регистра числа явно вписывался знак '0' для положительных и знак '1' для отрицательных чисел. При определении значения числа этот бит игнорировался. Вроде бы все нормально, но процессор не может работать с отдельными битами регистра. Для определения знака числа, число загружалось в процессор, применение маски (числа 10 или 1000) оставляло в регистре только бит знака, весь регистр проверялся (ноль или нет). Для выделения значения числа снова использовалась маска (7F или 7FFF), после чего определялось число -