Задачи по темам Системы счисления, алгоритмы и метаязыки (1106281)
Текст из файла
А. А. ВылитокЗадачи по темам«Системы счисления, алгоритмы и метаязыки»1.Дать «интуитивное» определение алгоритма.2.Перевод числа из десятичной системы счисления в q-ичную систему. Числа:0, 1, 8, 16, 25.75, 891, 255;q = 2, 3, 4, 5, 6, 7, 8, 16.3.Перевод числа из q-ичной в десятичную систему счисления. Числа:1112, 11015, 22101.0123, 654328, AFF716.4.Арифметические операции в позиционных системах счисления:а) 11112 +1102,б) 178 + 68,в) 11112 + 1112 + 112,г) 178 + 78 + 38,д) 10001101.12 + 111011.112,е) 215.48 + 73.68,ж) 8D.816 + 3B.C16;з) 11001001.01 − 111011.112,и) 311.28 − 73.68,к) С9.416 − 3B.C16;л) 58 • 68,м) 1012 • 1102,н) 11100112 • 1100112,о) 1638 • 638;п) 1816 : 316,р) 10011101.12 : 1002.5.Быстрый перевод из q-ичной системы счисления в систему с основанием qn иобратно.
Двоичные числа 1001, 111, 101010101.01011, 11101 перевести вчетверичную, восьмеричную и шестнадцатеричную системы счисления. Числа32134, 75.128, 10FA.816 перевести в двоичную систему.6.Сформулируйте необходимое и достаточное условие делимости:а) на три для числа, записанного в троичной системе счисления;б) на пять для числа, записанного в шестнадцатеричной системе счисления;в) на два для числа, записанного в семеричной системе счисления.7.Построить структурированную блок-схему для решения следующей задачи. Данонатуральное число n.
Поменять порядок цифр числа n на обратный.1А. А. Вылиток8.Построить структурированную блок-схему для решения следующей задачи. Данынатуральные числа n, q1, q2, … , qn. Найти те члены qi последовательности q1, q2, … ,qn , которые при делении на 7 дают остаток 1, 2 или 5.9.Построить НАМ в алфавите букв кириллицы, который к слову приписываетприставку «сам». Пример: Д ⇒ самД10. Построить НАМ над алфавитом букв кириллицы, который к слову приписываетсуффикс «ок».
Примеры: лес ⇒ лесок, дуб ⇒ дубок, брус ⇒ брусок.11. Построить алгоритм (НАМ и МТ) над алфавитом {0, 1}, заменяющий первые триединицы на нули. Примеры: 00 ⇒ 00, 010 ⇒ 000, 010110111 ⇒ 000000111.12. Построить алгоритм (НАМ и МТ), переводящий число, записанное в десятичнойсистеме, в следующее по порядку. Примеры: 11 ⇒ 12, 99 ⇒ 100, 0 ⇒ 1.13. Построить алгоритм (НАМ и МТ) над алфавитом {a, b, с}, который каждое второевхождение a заменяет на b или на с в зависимости от того, в четной или нечетнойпозиции находится данное вхождение а. Позиции нумеруются слева направо,начиная с единицы.
Пример: aababcaa ⇒ abbabcca.14. Построить алгоритм (НАМ и МТ) над алфавитом { | }, переводящий число в«первобытной» системе счисления в пустое слово, если заданное число являетсястепенью тройки, иначе — в какое-нибудь непустое слово.15. Построить алгоритм (НАМ и МТ) над алфавитом {a, b}, который удаляет в словекаждое третье вхождение b.16. Построить алгоритм (НАМ и МТ), переводящий число в четверичной системесчисления в «первобытную». Пример: 134 ⇒ | | | | | | | .17. Построить пример алгоритма (НАМ или МТ) в алфавите {a}, которыйнесамоприменим и неприменим к любому слову в алфавите {a}.18.
Построить пример алгоритма (НАМ или МТ) в алфавите {a}, которыйсамоприменим и применим к любому слову в алфавите {a}.19. Построить пример алгоритма (НАМ или МТ) над алфавитом {a}, которыйсамоприменим и неприменим к любому слову в алфавите {a}.20. Построить пример алгоритма (НАМ или МТ) над алфавитом {a}, которыйнесамоприменим и применим к любому слову в алфавите {a}.21. Сформулировать условие задачи, которую решает НАМ над алфавитом {a, b},заданный следующей схемой:⎧ **→ #*⎪⎪ #*→ #⎪ #a→a#⎪⎪ #b →b #⎪⎪ # a⎨⎪*a a→a*a⎪ *a b →b*a⎪⎪ *b b →b *b⎪ *b a → a *b⎪⎪⎩ → *2А. А.
Вылиток22. Сформулировать условие задачи, которую решает НАМ над алфавитом { | , # } вприменении к словам вида x # y, где x и y — натуральные числа в «первобытной»системе счисления. НАМ задается следующей схемой:⎧ |a →a|⎪ | #| → a #⎪⎪ |#→ #b⎪⎨ b →|⎪ a→c⎪⎪ c →|⎪# a⎩23. Сформулировать условие задачи, которую решает НАМ над алфавитом { | , # } вприменении к словам вида x # y, где x и y — неотрицательные целые числа в«первобытной» системе счисления.
НАМ задается следующей схемой:⎧ b |→ | b⎪ a | →|b a⎪⎪ a→⎪⎨ |#→ #a⎪ #|→ #⎪⎪ #→⎪ b →|⎩24. Построить НАМ над алфавитом {a, b}, эквивалентный алгоритму из задачи 21,используя не более десяти правил и не более одного вспомогательного символа (*).25.
Построить формальную грамматику, порождающую те и только те цепочки валфавите {a, b}, к которым применим НАМ, задаваемый схемой:⎧ ab→⎪⎨a→a⎪b →b⎩26. Построить грамматику скобочных систем, удовлетворяющих ограничениям1:а) 2 ≤ протяжение системы ≤ 4;б) глубина системы ≤ 2;в) ширина системы ≤ 2;г) глубина ≤ 2 и ширина ≤ 2;д) глубина ≤ 2 , а ширина ≥ 2.27. Построить грамматику, порождающую цепочки в алфавите {a,b}, в которыхколичество букв b четно.1Скобочную систему будем называть неделимой, если ее нельзя представить в виде конкатенации(соединения) двух непустых скобочных систем, т. е.
в такой системе первая открывающая скобкапарна последней закрывающей. Протяжение скобочной системы — это число неделимых скобочныхсистем, конкатенация которых дает данную систему. (Протяжение пустой с. с. равно нулю).Ширина — максимальное протяжение среди всех подсистем данной скобочной системы, глубина —максимальный уровень вложенности скобок.3А. А. Вылиток28.
Построить грамматику, порождающую цепочки в алфавите {a, b}, которые неоканчиваются на abb.29. Построить грамматику, порождающую язык {ambn | 0 ≤ m < n}.30. Построить грамматику, порождающую цепочки в алфавите {a, b}, в которыхколичество букв a не равно количеству букв b. Примеры: a, abb, abbab, bbb, aab.31. Построить грамматику «товарных поездов» в виде БНФ и СД. Поезд состоит изтяги, за которой следуют вагоны.
Тяга — это один или несколько тепловозов.Вагоны бывают двух типов: цистерны и рефрижераторы. На каждый рефрижераторв поезде приходится по меньшей мере две цистерны.32. Построить грамматику арифметических выражений (в виде БНФ) в алфавите { +, –,*, / , ^, a, (, ) }, где a символизирует операнд, ^ — операцию возведения в степень.Грамматика должна отражать естественный приоритет операций, правуюассоциативность операции возведения в степень и левую ассоциативностьостальных операций.33. Грамматика обезьяньего языка выглядит так:〈фраза〉 ::= 〈слово〉 @ 〈фраза〉 | 〈слово〉〈слово〉 ::= 〈ш〉 〈слог〉 | 〈слово〉 〈слог〉〈слог〉::= 〈слог〉 ba | 〈слог〉 bb 〈слог〉 | aКто из перечисленных ниже ораторов является шпионом, замаскированным подобезьяну?Бабуин: ababbaa@abaabba@aaШимпанзе: ababa@abba@abbaaaaГорилла: abaa@abbaaa@aabbaa34.
Язык «пляшущих человечков» задается грамматикой:S→A|A→S|AКакие из приведенных ниже писем на языке «пляшущих человечков» фальшивые?а)б)в)4.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
