Учебники. Программирование для начинающих.
Programm.ws — это сайт, на котором вы можете почитать литературу по языкам программирования , а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..
Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.
Ассемблер — примеры и задачи
Глава 2. Сложные структуры данных
Множество
Соня закрыла глаза и задремала. Но тут Болванщик
ее ущипнул, она взвизгнула и проснулась.
—. начинается на М, — продолжала она. — Они
рисовали мышеловки, математику, множество.
Ты когда-нибудь видела, как рисуют множество?
— Множество чего? — спросила Алиса.
— Ничего, — отвечала Соня. — Просто множество!
— Не знаю, — начала Алиса, — может.
— А не знаешь — молчи, — оборвал ее Болванщик.
Льюис Кэрролл. «Алиса в стране чудес»
Множество как структура уровня представления является совокупностью различных объектов, которые могут либо сами являться множествами, либо представлять собой неделимые элементы, называемые атомами.
Множество как структура уровня хранения реализуется двумя способами:
ш простым — в виде данных перечислимого типа; в языках высокого уровня этот тип данных реализуют с помощью типа «множество» (в Pascal) или констант перечислимого типа (в С);
ш сложным — в виде вектора или связного списка.
Отличие этих двух способов в том, что данные перечислимого типа ограниченно поддерживают понятие множества, представляя собой совокупность объектов, которым сопоставлены некоторые значения. При реализации множеств с помощью вектора или связного списка становится возможным реализовать именно математическое понятие множества, согласно которому, над множествами определен ряд операций: объединение, пересечение, разность, слияние, вставка (удаление) элемента и т. д. С данными перечислимого типа эти операции невозможны.
В языке ассемблер также есть средства, позволяющие реализовать оба способа представления множеств. Так, описание данных перечислимого типа поддерживаются с помощью директивы enum. Как и в языках высокого уровня, данные перечислимого типа, вводимые этой директивой, являются константами, которым соответствуют уникальные символические имена. Директива enum имеет следующий синтаксис:
символ_имя enum значение[. значение[, значение. ]]
Здесь значение представляет собой конструкцию символ_имя [=число], а символ_ имя — любое символическое имя, не совпадающее с ключевыми словами ассемблера или другими ранее определенными в программе символическими именами. Следующие примеры описания множеств эквивалентны.
week enum Monday.Tuesday,Wednesday,Thursday,Friday,Saturday.Sunday > week enum Monday=0,Tuesday=l. Wednesday^. Thursday=3. Fri day=4.Saturday=5.Sunday=6 week enum Monday=0,Tuesday.Wednesday,Thursday.Fri day.Saturday.Sunday week enum Sunday=6.Monday=0,Tuesday,Wednesday.Thursday,Fri day.Saturday
Перечисление элементов множества может занимать несколько строк в программе.
Транслятор будет отводить под размещение каждого элемента множества столько байтов, сколько требуется для размещения значения самого большого элемента в этом множестве (байт, слово, двойное слово).
Если при описании очередного элемента множества число в некоторой конструкции символ_имя [=число] не задано, то транслятор присвоит этому элементу множества значение, на единицу большее предыдущего. Если ни одного значения не было задано, то первому элементу множества присваивается 0, второму 1 и т. д.
Работа с элементами множества в программе является завуалированной формой использования непосредственного операнда. В этом несложно убедиться, проанализировав листинг трансляции:
5 :задаем множество:
6 =0000 =0001 =0002 + week enum
Monday.Tuesday,Wednesday.Thursday.Fri day.Saturday.Sunday
7 =0003 =0004 =0005 +
8 =0006
20 0005 B8 0006 mov ax,Sunday
Значение символического имени синвол_имя, стоящего слева от директивы enum, равно количеству битов, необходимому для размещения максимального значения элемента справа от директивы enum:
5 ;задаем множество:
6 =0000 =0001 =0002 + week enum
Monday.Tuesday.Wednesday.Thursday,Fri day.Saturday.Sunday
7 =0003 =0004 =0005 +
8 =0006
21 0005 B8 0007 mov ax.week
Перед использованием в программе необходимо определить и инициализировать экземпляр множества:
F_week week Saturday
Размер этой переменной будет соответствовать размеру максимального элемента множества week. Сказанное иллюстрирует фрагмент листинга:
5 :задаем множество:
6 =0000 =0001 =0002 + week enum
Monday.Tuesday,Wednesday.Thursday.Friday.Saturday.Sunday
7 =0003 =0004 =0005 +
8 =0006
9 0000 05 s week Saturday
21 0005 A2 OOOOr movs.al
Хорошо видно, что в данном случае работа с экземпляром множества осуществляется как с байтовой переменной.
Возможности ассемблера для описания множества и работы с ним сложным способом (с помощью векторов и связных списков) будут ясны в ходе дальнейшего изложения.
Множество (тип данных)
Множество — тип и структура данных в информатике, является реализацией математического объекта множество.
Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.
В зависимости от идеологии, разные языки программирования рассматривают множество как простой или сложный тип данных.
Реализации
Множество в Паскале
В языке Паскаль множество — составной тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Мощность этого типа определяет размер множества — 1 бит на элемент. В Turbo Pascal есть ограничение на 256 элементов, в некоторых других реализациях это ограничение ослаблено.
Пример работы с множествами:
type colors = (red,green,blue); smallnumbers = 0..10; colorset = set of colors; numberset = set of smallnumbers; anothernumberset = set of 0..20; var nset1,nset2,nset3:numberset; cset:colorset; begin nset1 := [0,2,4,6,8,10]; cset := [red,blue]; nset2 := [1,3,9,7,5]; nset3 := []; include(nset3,7); exclude(nset3,7); nset1 := [0..5]; nset3 := nset1 + nset2; nset3 := nset1 * nset2; nset3 := nset1 - nset2; if (5 in nset2) or (green in cset) then end.
Типы данных
Множественный тип данных. Множество. Элемент множества. Способы задания множества. Объединение множеств. Разность множеств. Пересечение множеств
Множественный тип данных напоминает перечислимый тип данных. Вместе с тем, множество — набор элементов, не организованных в порядке следования. В математике множество — любая совокупность элементов произвольной природы. Понятие множества в программировании значительно уже математического понятия. Определение. Под множеством в Паскале понимается конечная совокупность элементов, принадлежащих некоторому базовому типу. В качестве базовых типов могут использоваться: перечислимые типы данных, символьный и байтовый типы или диапазонные типы на их основе. Такие ограничения связаны с формой представления множества в языке и объясняются тем, что функция Ord для элементов используемого базового типа должна быть в пределах от 0 до 255. Множество имеет зарезервированное слово set of и вводится следующим описанием
| Type < имя типа >= set of < имя базового типа >; Var < идентификатор. >:< имя типа >; |
Рассмотрите примеры описаний множеств:
| Type SetByte = set of byte; SetChisla = set of 10 .. 20; Symbol = set of char; Month = (January, February, March, April, May, June, July, August, September, October, November, December); Season = set of Month; Var Letter, Digits, Sign : Symbol; Winter, Spring, Summer, Autumn, Vacation, WarmSeason : Season; Index : SetChisla=[12, 15, 17]; Operation : set of (Plus, Minus, Mult, Divid); Param : set of 0..9=[0, 2, 4, 6, 8]; |
Для переменных типа множества в памяти отводится по 1 биту под каждое возможное значение базового типа. Так, под переменные Letter, Digits, Sign будет отведено по 256/8=32 байта. Для переменной Winter, базовый тип которой (Month) имеет 12 элементов, необходимо 2 байта, причем второй используется только наполовину. Если множество содержит какой-то элемент, то связанный с ним бит имеет значение 1, если нет — 0. Для того, чтобы дать переменной множества какое-то значение, используют либо конструктор множества — перечисление элементов множества через запятую в квадратных скобках:
| Sign:=[‘+’, ‘-‘]; Spring:=[March, April, May]; b:=[ ‘k’, ‘l’, ‘d’ ] |
либо определение через диапазон. В этом случае в множество включены все элементы диапазона.
| Digits:=[‘0’..’9′]; WarmSeason := [May .. September]; |
Обратите внимание, что в определении множества Digits использованы символы в таблице ASCII-кодов, а не целые числа. Обе формы конструирования могут сочетаться:
| Vacation:=[January, February, June .. August]; |
В программах множества часто используются как константы, в этом случае их можно определить следующим образом:
| Const YesOrNo = [‘Y’, ‘y’, ‘N’, ‘n’]; Const Const |
Объединение множеств (+)
Определение. Объединением двух множеств называется третье множество, включающее все элементы, которые принадлежат хотя бы одному из множеств-операндов, при этом каждый элемент входит в объединение множеств только один раз. Объединение множеств записывается как операция сложения.
| Type Symbol = set of char; Var SmallLatinLetter, CapitalLatinLetter, LatinLetter : Symbol; Begin . . . . . . SmallLatinLetter :=[‘a’..’z’]; CapitalLatinLetter := [‘A’..’Z’]; LatinLetter := SmallLatinLetter+CapitalLatinLetter; . . . . . . End. |
В операции объединения множеств могут участвовать и отдельные элементы множества. Например, допустима следующая запись, где два элемента и множество объединяются в новое множество:
| WarmSeason := May+Summer+September; |
или другая запись
которую можно применить для организации множества в цикле, если заменить множество [‘c’] переменной Sym того же типа, что и множество B, и считывать с клавиатуры данные в переменную Sym, объединяя ее затем с множеством В.
Разность множеств (-)
Определение. Разностью двух множеств является третье множество, которое содержит все элементы 1-го множества, не входящие во 2-е множество.
Если в вычитаемом множестве есть элементы, отсутствующие в уменьшаемом, они не влияют на результат.
| Summer := WarmSeason-Spring-Autumn; Summer := WarmSeason-May-September; |
Модуль System содержит процедуры для включения элемента в множество
| Include(Var S : set of T; Element : T); |
и исключения из множества
| Exclude(Var S : set of T; Element : T); |
где S — множество элементов типа Т, а Element — включаемый (или исключаемый) элемент. Эти функции отличаются от операций объединения и вычитания множеств только тем, что генерируют более эффективный код.
Пересечение множеств
Определение. Пересечением множеств называется множество, содержащее все элементы, одновременно входящие в оба множества-операнда. Операция обозначается знаком умножения.
| Summer := WarmSeason*Vacation; |
Множества
Множество есть совокупность различных элементов, мыслимая как единое целое (Бертран Рассел). Согласно Википедии множество принимается за одно из исходных понятий, поэтому у него нет определения.
Однако мы должны с вами понимать, что это такое. Примером множества может служить алфавит — множество букв. То есть множество М — это некое количество определённых предметов. Эти предметы называются элементами множества М.
Если хотите знать больше о множествах, то вспоминайте математику. Или хотя бы прочитайте соответствующую статью в Википедии. Как я уже говорил, основы математики я объяснять не буду. И здесь буду рассказывать только о том, как работать с множествами в Паскале.
Может показаться, что множество похоже на массив, однако это не так, потому что принципы работы с множествами отличаются от принципов работы с массивами.
Когда я только изучал программирование, я никак не мог понять, зачем нужны множества в программировании. Вроде бы и без них можно обойтись. Однако со временем понял, что нужны. Так как в некоторых случаях работать с множествами проще и удобнее, чем с другими типами данных.
Итак, в общем случае множество в Паскале объявляется так:
ИмяМножества = set of ТипЭлементов;
Здесь ИмяМножества — это идентификатор переменной, с которой связано данное множество. ТипЭлементов — это тип элементов множества. Тип элементов множества может быть любым порядковым типом данных в диапазоне 0. 255. Множество в Паскале не может содержать более 255 элементов. Пример:
type TMyChar = set of Char; type TSeasons = (Winter, Spring, Summer, Autumn); var Season : set of TSeasons; chm : TMyChar;
нечто подобное вы уже видели, если изучали перечисления.
Множеству можно присваивать значения. Например:
Season := [Winter, Spring, Summer];
После этого действия в переменной Season будет храниться множество из трёх элементов, хотя тип TSeasons позволяет хранить четыре элемента.
Операторы для работы с множествами
Надеюсь, что из школьного курса математики вы помните, какие операции можно выполнять с множествами. Для этих операций в Паскале используются следующие операторы:
Таблица 23.1. Операции с множествами.
| Оператор | Операция |
| + | Объединение множеств |
| — | Разность (дополнение) |
| * | Пересечение |
| > | Симметрическая разность |
| Содержит | |
| include | Включить элемент |
| exclude | Исключить элемент |
| in | Проверить, есть ли элемент в множестве |
А теперь примеры.
type TMyChar = set of Char; type TSeasons = (Winter, Spring, Summer, Autumn); var Season : set of TSeasons; M1, M2 : set of TSeasons; chm : TMyChar; begin M1 := [Winter, Spring]; M2 := [Summer, Autumn]; if Summer in M1 then WriteLn('Лето будет жарким') else WriteLn('Лета не будет'); end.
Этот код выведет на экран строку “Лета не будет”, так как значения Summer нет в множестве М1. То есть выражение
Теперь попробуем объединить множества М1 и М2 и записать результат в М1:
M1 := M1 + M2; //Объединяем множества if Summer in M1 then WriteLn('Лето будет жарким') else WriteLn('Лета не будет');
Теперь будет выведена строка “Лето будет жарким”. Потому что после объединения множеств в переменной М1 содержатся все четыре элемента типа TSeasons (в том числе и Summer).
chm := ['a'..'z']; if 'x' in chm then WriteLn('Символ х есть в множестве') else WriteLn('Символа х нет в множестве'); chm := chm - ['x']; //Удаляем символ х из множества if 'x' in chm then WriteLn('Символ х есть в множестве') else WriteLn('Символа х нет в множестве'); Include(chm, 'x'); //Добавляем символ х в множество if 'x' in chm then WriteLn('Символ х есть в множестве') else WriteLn('Символа х нет в множестве'); Exclude(chm, 'x'); //Удаляем символ х из множества if 'x' in chm then WriteLn('Символ х есть в множестве') else WriteLn('Символа х нет в множестве');
Как видите, удалить элемент из множества можно как минимум двумя способами. Добавить тоже.
Как перебрать все элементы множества
Это приходится делать редко. Однако такая необходимость может возникнуть. Перебрать элементы множества можно в цикле, например, так:
i : TSeasons; for i := Low(Tseasons) to High(TSeasons) do Write(i, ' ');
Пересечение множеств
Пересечение множеств — это набор элементов, общих для двух и более множеств. Например, у нас есть два множества:
M1 = [Winter, Spring, Summer]
M2 := [Summer, Autumn]
У этих множеств есть один общий элемент — Summer. Результатом операции пересечения множеств М1 и М2 будет именно этот элемент. Ниже приведён код программы, который позволяет на практике проверить это утверждение.
M1 := [Winter, Spring, Summer]; M2 := [Summer, Autumn]; M1 := M1 * M2; //M1 = [Summer] for i := Low(Tseasons) to High(TSeasons) do if i in M1 then Write(i, ' ');
Этот код выведет на экран только одно слово — Summer.
Как я уже говорил, множества — это тема довольно сложная для новичков, особенно если вы плохо знаете математику. Так что если вы мало что поняли — не огорчайтесь. Вернётесь к этой теме, когда будет нужно.
Однако не советую откладывать эту тему в долгий ящик. Поверьте на слово, не редко использование множеств существенно упрощает работу программиста.
Остальные операции с множествами рассматривать пока не будем.