Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

МУ Теория алгоритмов - БИ-1.docx

Скачиваний:

110

Добавлен:

30.05.2015

Размер:

4.19 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 / 1615 16 > Следующая >>>

Библиографический список

Акулов, О. А.Информатика: базовый курс [Текст]: учебник/ О.А. Акулов, Н. В. Медведев. – 6-е изд. – М.: Омега-Л, 2009. – 574 с.
Каймин, В. А.Информатика [Текст]: учебник / В. А. Каймин. – М.: ИНФРА-М, 2010. – 284 с.
Лабораторный практикум. Основы программирования на языке PASCAL: методические указания [Текст] / [Сост. Э.С.Саитова, Т.М. Шамсутдинова]; Башкирский государственный аграрный университет. – Уфа: БГАУ, 2012. – 92 с.
Шамсутдинова Т.М. Программирование на языке PASCAL. Методические указания для самостоятельной работы /Башкирский государственный аграрный университет: Уфа, 2012. –12 с.
Игошин В.И. Математическая логика и теория алгоритмов: Учеб. пособие для студ. высш. учеб. заведений/ В.И. Игошин. – М.: Академия, 2004.
Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач, М.: ВМК МГУ, 2006. – 47 с.
Культин Н.Б. Основы программирования в Delphi7. – СПб.: БХВ-Петербург, 2007. – 608 с.

Основные функциональные элементы блок-схем алгоритмов в соответствии с ГОСТ 19002-89 ЕСПД (Единая система программной документации)

Название символа	Обозначение и пример заполнения	Пояснение
Процесс		Вычислительное действие или последовательность действий
Решение		Проверка условий
Модификация		Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод		Ввод-вывод в общем виде
Пуск-останов		Начало, конец алгоритма, вход и выход в подпрограмму
Документ		Вывод результатов на печать

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

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

Блок модификация используется для организации циклических конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.

Блок предопределенный процесс используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам

Контрольные вопросы для подготовки к зачету

Зачем в математике потребовалось формализовать понятие алгоритма?
Какие подходы к уточнению понятия алгоритма существуют?
Какие функции называют вычислимыми? Какие функции называют частичными?
Какие функции называют частично-рекурсивными?
Какой набор простейших функций и элементарных операций используется в теории рекурсивных функций?
Какова формулировка тезиса Черча? Что он означает?
Каково устройство абстрактной машины Поста? Каковы выполняемые ею команды?
Каково устройство абстрактной машины Тьюринга? Каковы выполняемые ею действия?
Как описывается машина Тьюринга? Приведите примеры схем машин Тьюринга.
Что называется композицией машин Тьюринга?
В чем состоит содержание теоремы Тьюринга?
Приведите примеры дедуктивных цепочек.
Как определяются нормальные алгоритмы Маркова?
В чем состоит задача универсального алгоритма?
Алгоритм. Свойства алгоритма. Возможность автоматизации деятельности человека. Пример.
Формальный исполнитель алгоритмов.
Алгоритмическая структура “ветвление”. Команда ветвления. Пример.
Способы записи алгоритмов.
Алгоритмическая структура “Цикл”. Команда повторения. Пример.
Исполнитель команд (робот, автомат, человек, компьютер). Компьютер как формальный исполнитель алгоритмов (программ).
Алгоритмическое программирование. Основные способы организации действий в алгоритмах.
Основные алгоритмические структуры.
Разработка программы для решения задачи, алгоритм решения которой содержит команду ветвления.
Описание алгоритма с помощью естественного языка.
Виды исполнителей алгоритмов.
Описание алгоритма с помощью блок-схемы.
Словесно-формульное описание алгоритма. Примеры
Как изображается на блок-схеме блок обработки информации? (параллелограмм, прямоугольник, ромб, овал).
Линейная алгоритмическая конструкция. Команда присваивания. Примеры.
Разработка программы для решения задачи, алгоритм решения которой содержит команду повторения (цикла).
Какой из документов является алгоритмом? (правила техники безопасности, инструкция по получению денег в банкомате, расписание уроков, список классов.)
Понятие алгоритмического языка.
Какую смысловую нагрузку несет блок “параллелограмм"? (блок ввода-вывода, блок обработки, блок начала алгоритма, логический блок.)
Алгоритмическая конструкция какого типа изображена на блок-схеме?

Задачи для самостоятельного решения по теме «Алгоритмы линейной и разветвляющейся структуры»

1. Вычислить длину окружности, площадь круга и объём шара одного и того же заданного радиуса.

2. Вычислить периметр и площадь прямоугольного треугольника по длинам двух его катетов.

3. По координатам трёх вершин некоторого треугольника найти его площадь и периметр.

4. Вычислить дробную часть среднего геометрического трёх заданных вещественных чисел.

5. Определить, является ли заданное целое число А нечётным двузначным числом.

6. Определить, имеется ли среди заданных целых чиселA, B, C хотя бы одно чётное.

7. Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [ e, f ].

8. Определить число, полученное выписыванием в обратном порядке цифр заданного целого трёхзначного числа.

9 Вычислить площадь кольца, ширина которого равна Н, а отношение радиуса большей окружности к радиусу меньшей окружности равно D.

10 Определить, есть ли среди цифр заданного целого трёхзначного числа одинаковые.

11 Заданы площади круга и квадрата. Определить, поместится ли квадрат в круге.

12 Для задачи 6.12 определить, поместится ли круг в квадрате.

13 Заданы координаты двух точек. Определить, лежат ли они на одной окружности с центром в начале координат.

14 Определить, лежит ли заданная точка на одной из сторон треугольника, заданного координатами своих вершин.

15 Проверить, можно ли построить треугольник из отрезков с длинами x, y, z и, если можно, то какой – остроугольный, прямоугольный или тупоугольный.

16 Проверить, можно ли построить параллелограмм из отрезков с длинами x, y, v, w.

17 Даны координаты (как целые от 1 до 8) двух полей шахматной доски. Определить, может ли конь за один ход перейти с одного из этих полей на другое.

18 Треугольник задан величинами своих углов (град.) и радиусом описанной окружности. Вычислить стороны треугольника.

19 Смешали v₁ литров воды с температурой t₁ градусов Цельсия с v₂ литрами воды с температурой t₂ градусов Цельсия. Вычислить объём и температуру образовавшейся смеси.

20 Выбрать наибольшее из трёх заданных чисел.

21 Два прямоугольника заданы длинами сторон. Определить, можно ли первый прямоугольник целиком разместить во втором.

22 Значения заданных переменных a, b и c перераспределить таким образом, что a, b, c станут, соответственно, наименьшим, средним и наибольшим значениями.

24 Решить линейное уравнение ax = b.

24 Решить биквадратное уравнение ax⁴ + bx² + c = 0.

25 Определить номер квадранта, в котором находится точка с заданными координатами (x, y).

26 Записать заданное смешанное число в виде неправильной дроби.

27 Определить, пройдет ли кирпич с рёбрами a, b, c в прямоугольное отверстие со сторонами x и y. Просовывать кирпич в отверстие разрешается только так, чтобы каждое из его рёбер было параллельно или перпендикулярно каждой из сторон отверстия.

28 Идет k-ая секунда суток. Определить, сколько полных часов и полных минут прошло к этому моменту.

29 Найти центр и радиус окружности, проходящей через три заданные точки на плоскости.

30 Даны четыре точки на плоскости. Определить, можно ли построить треугольник с вершинами в этих точках такой, что оставшаяся точка окажется внутри треугольника.

31 Составить программу случайного выбора трех дисциплин, по которым придется сдавать экзамены, из предлагаемых на выбор четырех (всего возможно 4 варианта выбора);

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

33 Составить программу выбора дежурного в группе из списка 10 студентов с вероятностью 1/15, в остальных случаях дежурит староста.

34 Вывести на экран сообщение в зависимости от полученного значения оценки (по десятибальной системе), например: 1..2: плохо; 3..5: удовлетворительно и т.д., иначе – неправильный ввод данных.

35 Вывести на экран сообщение в зависимости от значения температуры воздуха на улице (от –50 до +50^оС), например: -50..-20: очень холодно; -19..-10 : холодно и т.д., иначе – неправильный ввод данных.

Задачи для самостоятельного решения по теме «Алгоритмы циклической структуры»

1 Даны действительные числа х, а, натуральное число n. Вычислить

((… ((х+а)²+…а)²+а)²+а

ncкобок

2 Дано действительное число х. Вычислить:

3 Даны натуральное n, действительное х. Вычислить:

4 Даны натуральное n, действительное х. Вычислить:

5 Даны натуральное n, действительное х. Вычислить:

6Вычислить:

7 Вычислить:

8 Вычислить:

9Вычислить:

10 Дано натуральное n. Вычислить:

Дано натуральное n. Вычислить:

12 Дано натуральное n. Вычислить:

13 Дано натуральное n. Вычислить:

14 Дано натуральное n. Вычислить:

15 Дано натуральное n. Вычислить:

16 Дано натуральное n. Вычислить:

17 Дано натуральное n, действительное число х. Вычислить:

18 Дано натуральное n, действительное число х. Вычислить:

19 Дано натуральное n, действительное число х. Вычислить:

20 Дано натуральное n, действительное число х. Вычислить:

sin x+sin² x+…+sin xⁿ

21 Дано натуральное n, действительное число х. Вычислить:

sin x+sin x²+…+sin xⁿ

22 Вычислить сумму Z = 1 + 2 + 3 + ... . Вычисления прекратить, когда значение Z превысит заданное значение A.

23. Известен начальный вклад клиента в банк и процент годового дохода. Определить, через сколько лет вклад превысит заданный размер и каков при этом будет размер вклада.

24. Торговая фирма в первый день работы реализовала товаров на P тыс. руб., а затем ежедневно увеличивала выручку на 3%. Какой будет выручка фирмы в тот день, когда она впервые превысит заданное значение Q? Сколько дней придется торговать фирме для достижения этого результата?

25. Малое предприятие в первый день работы выпустило P единиц товарной продукции. Каждый последующий день оно выпускало продукции на Q единиц больше, чем в предыдущий. Сколько дней потребуется предприятию, чтобы общее количество выпущенной продукции за все время работы впервые превысило запланированный объем?

Задачи для самостоятельного решения по теме «Алгоритмы обработки массивов»

Проверить, есть ли в заданной целочисленной последовательности a₁ , a₂ , ..., a_N элементы, равные нулю. Если есть, найти номер первого из них, если нет – выдать соответствующий текст.
Для заданного числа x вычислить первое из чисел последовательности sin x, sin sin x, sin sin sin x, ..., меньшее по модулю 10^–2.
Выяснить, имеются ли в заданном векторе A(N) два подряд идущих нулевых элемента.
Выяснить, имеются ли в заданном целочисленном векторе A(N) три подряд идущих элемента одного знака.
Множество точек в пространстве задано своими целочисленными координатами. Определить, совпадает ли хотя бы одна из точек с началом координат.
Если у заданного вектора A(N) есть хотя бы один элемент, меньший, чем –5, то все отрицательные элементы заменить их квадратами, оставив остальные элементы без изменения; в противном случае вектор умножить на 0,1.
Имеется последовательность чисел a₁, a₂ , ..., a_N . Найти сумму первых из них (считая слева направо), произведение которых не превышает заданного числа М.
Все элементы заданного вектора A(N), начиная с первого по порядку положительного элемента, уменьшить на единицу.
Числа Фибоначчи (F_i) определяются по формулам F₀ = F₁= 1; F_i = F_i–1+ F_i–2 при i = 2, 3, ... Найти первое из чисел Фибоначчи, которое превосходит заданное число M (M>0).
Выяснить, имеется ли среди чисел i3 – 17• i• n2 + n3, i=1, ..., n, хотя бы одно число, которое кратно заданному числу А и не кратно числу В
(A<>B). При существовании такого числа требуется вычислить сумму всех тех элементов, которые предшествовали ему.
Определить, имеются ли среди элементов побочной диагонали заданной целочисленной матрицы A(N,N) числа, равные нулю.
Если в заданном целочисленном векторе A(N) есть элементы со значением, равным заданному числу B, то переменной С присвоить значение, равное сумме всех элементов, предшествующих первому по порядку такому элементу; в противном случае вывести соответствующий текст.
Определить, имеется ли в заданном массиве A(N) хотя бы одна пара соседних чисел, являющихся взаимнообратными.
Определить, выполняются ли для заданного вектора A(2N) условия: а1=а2N , a2= a2N–1 , ..., aN= aN+1, т.е. является ли он симметричным относительно своей середины.
Имеется монотонно убывающая последовательность чисел a1 , a2 , ..., aN . Определить квадрат суммы положительных членов этой последовательности.
Если в заданном целочисленном векторе A(N) есть элементы со значением, равным заданному числу B, то переменной С присвоить значение, равное произведению всех элементов, следующих за первым по порядку таким элементом; в противном случае вывести соответствующий текст.
Определить, имеется ли в заданном целочисленном массиве X(N) число, кратное заданным числам А и В, и не кратное числу С.
Дано натуральное N. Выяснить, сколько цифр оно содержит.
Найти сумму цифр заданного натурального числа.
Цифры заданного натурального числа записать в обратном порядке.
Проверить, все ли элементы заданного массива A(N) положительны.
Найти наименьший делитель заданного натурального числа A (не считая единицы).
Определить по прейскуранту, можно ли подобрать в спортивном магазине велосипед, стоимость которого не превышает имеющуюся у покупателя сумму.
Дана матрица A(N,N). Переменной В присвоить значение, равное количеству строк матрицы А, содержащих хотя бы одну нулевую компоненту.
Дана матрица B(N,N). Получить вектор A(N) , компоненты которого находятся по правилу: Ai равно первому по порядку положительному элементу в i-ой строке матрицы (если таких элементов в строке нет, то принять Ai = –1).
Среди строк заданной целочисленной матрицы, содержащих только нечётные элементы, найти строку с максимальной суммой модулей элементов.
Среди столбцов заданной целочисленной матрицы, содержащих только такие элементы, которые по модулю не больше 10, найти столбец с минимальным произведением элементов.
Задано два множества точек на плоскости. В первом множестве найти хотя бы одну точку, сумма расстояний от которой до точек второго множества превышала бы заданную величину.
В заданной матрице A(N,M) найти количество строк, не содержащих отрицательных чисел.
Дана целочисленная матрица А(N,N). Сформировать результирующий вектор B, элементами которого являются суммы элементов только тех строк матрицы А, которые начинаются с К положительных чисел подряд.
Подсчитать количество столбцов заданной целочисленной матрицы A(N,N), в которых имеются взаимно противоположные соседние числа.
Дана матрица A(N,M). Построить вектор B(N), элементы Bi которого равны единице, если элементы i-ой строки образуют упорядоченную по убыванию или по возрастанию последовательность, и нулю во всех остальных случаях.
Определить, сколько строк заданной матрицы A(N,M) содержат хотя бы один элемент из заданного числового диапазона.
Найти номера строк заданной целочисленной матрицы A(N, M), в которых:

на всех нечётных позициях стоят нули;
на нечетных позициях встречаются нули.

Найти номера столбцов заданной целочисленной матрицы A(N, M), которые составлены из попарно различных чисел, и подсчитать количество таких столбцов.
Даны сведения о количестве забитых голов каждого футболиста команды в каждом из матчей чемпионата. Проверить, сколько в команде есть футболистов:

забивших хотя бы два гола;
забивавших голы в каждом матче;
не забивших ни одного гола.

Используя сведения о ежемесячных выплатах зарплаты сотрудникам фирмы, выяснить, не оказалась ли годовая зарплата кого-либо из сотрудников ниже годового минимума, оговоренного в его контракте.
Используя сведения о результатах сдачи n вступительных экзаменов m абитуриентами, определить, сколько абитуриентов сдали все экзамены на "отлично".

Задачи для самостоятельного решения по теме «Машина Поста»

На ленте машины Поста расположен массив в N отмеченных секциях. Необходимо справа от данного массива через одну пустую секцию разместить массив вдвое больший (он должен состоять из 2N меток). При этом исходный массив может быть стерт.
На ленте машины Поста расположен массив из N меток (метки расположены через пробел). Надо сжать массив так, чтобы все N меток занимали N расположенных подряд секций.
На информационной ленте машины Поста расположено N массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определите число массивов.
Игра Баше. В игре участвуют двое (человек и машина Поста). Напишите программу, по которой всегда будет выигрывать машина Поста. Суть игры заключается в следующем: имеется 21 предмет. Первым ходит человек. Каждый из играющих может брать 1, 2, 3 или 4 предмета. Проигрывает тот, кто берет последний предмет.
Число к представляется на ленте машины Поста к + 1 идущими подряд метками. Одна метка соответствует нулю. Составьте программу прибавления 1 к произвольному числу к. Каретка расположена над одной из меток, принадлежащих заданному числу к.
Составьте программу сложения двух целых неотрицательных чисел а и Ь, расположенных на ленте машины Поста. Каретка расположена над одной из меток, принадлежащих числу а. Число b находится правее числа а через несколько пустых секций.
Составьте программу сложения произвольного количества целых неотрицательных чисел, записанных на ленте машины Поста на расстоянии одной пустой секции друг от друга. Каретка находится над крайней левой меткой левого числа.
На ленте машины Поста расположен массив из N меток. Составьте программу, действуя по которой машина выяснит, делится ли число на 3. Если да, то после массива через одну пустую секцию поставьте метку V
Число к представлено на ленте машины Поста к + 1 идущими подряд метками. Найдите остаток от деления целого неотрицательного числа к на 3, если известно, что каретка находится справа от заданного числа.
Составьте программу нахождения разности двух неотрицательных целых чисел а и Ь, находящихся на ленте машины Поста. Каретка находится над левой меткой левого числа. Неизвестно, какое число больше: а или Ь.
На ленте машины Поста расположен массив из 2N отмеченных секций. Составьте программу, по которой машина Поста раздвинет на расстояние в одну секцию две половины данного массива.
На ленте машины Поста расположен массив из 27V—1 меток. Составьте программу отыскания средней метки массива и стирания ее.
На ленте машины Поста расположены два массива. Составьте программу стирания того из массивов, который имеет большее количество меток.
На информационной ленте машины Поста находятся два массива в М и N меток. Составьте программу выяснения, одинаковы ли массивы по длине.
Задача В. А. Успенского. На информационной ленте либо вправо, либо влево от секции, над которой расположена каретка, находится массив меток. Расстояние до массива выражается произвольным числом. Необходимо составить программу, работая по которой машина Поста найдет этот массив и установит каретку на начало этого массива.
Составьте программу умножения двух чисел а и Ь.
На ленте машины Поста находится п массивов меток, после последнего массива на расстоянии более трех пустых секций находится одна метка. Массивы разделены тремя пустыми ячейками. Количество меток в массивах не может быть меньше двух. Произвести обработку массивов следующим образом: если количество меток в массиве кратно трем, то стереть метки в данном массиве через одну, иначе – массив стереть полностью. Каретка находится над крайней левой меткой первого массива.
На ленте изображено п массивов меток, отделенных друг от друга одной свободной ячейкой. Каретка находится над первой меткой первого массива. Определите количество массивов.
На ленту машины Поста нанесены два массива меток на некотором расстоянии друг от друга. Соедините эти два массива в один. Каретка находится над крайней левой меткой левого массива.
На ленте машины Поста отмечен массив и меток. Найдите число 2п + 1 и проверьте, делится ли оно на 3. Если да, то после числа через одну пустую секцию, поставьте две метки, если нет – поставьте три метки. Каретка находится над крайней левой отмеченной секцией.
Дан массив меток. Каретка обозревает первую пустую секцию перед началом массива. Раздвиньте массив так, чтобы после каждой метки была пустая секция.
Составьте программу сложения произвольного количества чисел, записанных на ленте машины Поста через одну пустую секцию. Каретка обозревает крайнюю левую секцию левого числа.
Найти НОД двух чисел, находящихся на ленте машины Поста. Между этими числами находится произвольное количество пустых секций. Каретка находится над левой меткой левого числа.
На ленте машины Поста находятся п массивов меток. Каретка находится где-то над первым массивом. Удалите все массивы с четными номерами (соседние массивы разделены тремя пустыми секциями).
На информационной ленте машины Поста находится массив меток. Каретка находится где-то над массивом (но не над крайней меткой). Сотрите все метки, кроме крайних, таким образом, чтобы положение каретки при этом не изменилось.

Задачи для самостоятельного решения по теме «Машина Тьюринга»

На информационной ленте машины Тьюринга содержится массив символов +. Необходимо разработать функциональную схему машины Тьюринга, которая каждый второй символ + заменит на —. Каретка в начальном состоянии находится где- то над указанным массивом.
Дано число п в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число п на 1.
Дана десятичная запись натурального числа п > 1. Разработайте машину Тьюринга, которая уменьшала бы заданное число и на 1. При этом запись числа п – 1 не должна содержать левый нуль, например, 100 – 1 = 99, а не 099. Начальное положение головки – правое.
Дан массив из открывающихся и закрывающихся скобок. Постройте машину Тьюринга, которая удаляла бы пары взаимных скобок. Например, дано: «)(()(()», надо получить: «)...((.».
Дана строка из букв а и Ь. Разработайте машину Тьюринга, которая переместит все буквы а в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки.
Даны два целых положительных числа в десятичной системе счисления. Сконструируйте машину Тьюринга, которая будет находить разность этих чисел, если известно, что первое число больше второго, а между ними стоит знак «минус». Каретка находится над левой крайней цифрой левого числа.
Даны два целых положительных числа в различных системах счисления; одно – в троичной системе, другое – в десятичной. Разработайте машину Тьюринга, которая будет находить сумму этих чисел в десятичной системе счисления.
Сконструируйте машину Тьюринга, которая выступит в качестве двоично-восьмеричного дешифратора. Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток.
На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три различные буквы: А, В и С. Каретка в начальном состоянии обозревает букву, расположенную справа. Необходимо составить функциональную схему машины Тьюринга, которая сумеет поменять местами крайние буквы.
Даны два натуральных числа /лил, представленных в унарной системе счисления. Соответствующие наборы символов « | » разделены « – » , вслед за последним символом набора л стоит знак «=». Разработайте машину Тьюринга, которая будет находить разность чисел тип. При этом результат должен быть записан следующим образом: если т > л, то справа от «=» должны стоять знак «+» и набор символов « | » в количестве т – п\ если т – л, то справа от знака «=» должна стоять пустая клетка; если т <л, то справа от «=» должны стоять знак «—» и набор символов « | » в количестве л – т.
Даны два натуральных числа л и т, заданных в унарной системе счисления. Числа ли/л представлены наборами символов « | » , разделенных « \ ». В конце набора стоит «=». Разработайте машину Тьюринга, которая будет производить деление нацело двух натуральных чисел л и т и находить остаток от деления. При этом результат должен быть записан следующим образом: после «=» должен находиться набор символов « | » частного (он может быть и пустым), после чего ставится знак «(», за которым следует набор символов « | » остатка от деления л на т.
На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножьте это число на 2, если каретка находится над крайней левой цифрой числа.
На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на число 11. Каретка обозревает крайнюю правую цифру числа.
На ленте машины Тьюринга находится слово, состоящее из букв латинского алфавита {а, Ь, с, d). Подсчитайте число букв «а» в данном слове и полученное значение запишите на ленту левее исходного слова через пробел. Каретка обозревает крайнюю левую букву.
На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово «да», если нет – «нет». Каретка находится где-то над числом.
На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.
На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.
На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и В. Сожмите массив, удалив из него все элементы В.
На ленте машины Тьюринга находится массив 2N меток. Уменьшите этот массив в 2 раза.
Даны два натуральных числа пит, представленные в унарной системе счисления. Между этими числами стоит знак «?». Выясните отношение тип, т.е. знак «?* замените на один из подходящих знаков «>», «<», « = ».
Найдите произведение двух натуральных чисел тип, заданных в унарной системе счисления. Соответствующие наборы символов «|» разделены знаком « * », а справа от последнего символа правого члена стоит знак « = ». Поместите результат умножения этих чисел вслед за знаком « = ».
На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три цифры: 1, 2, 3. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины Тьюринга, которая расположит эти цифры в порядке возрастания.
На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово «да», если нет – «нет». Каретка находится где-то над числом.
На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.
На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.
На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и В. Сожмите массив, удалив из него все элементы В.

Задачи для самостоятельного решения по теме «Знакомство со средой программирования Delphi»¹¹

Расчет по формуле. Линейные алгоритмы.

Составить программу, которая бы выводила на экран компьютера на светло-сером фоне фиолетовыми буквами в пять строк следующий текст:

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

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

Составить программу, которая выводила бы на экран компьютера треугольник зеленого цвета, составленный из символов «». Вершину треугольника должна составлять одна звездочка, на следующей строке должно быть три символа «», на третьей – пять и так далее вплоть до основания треугольника, составленного из пятнадцати звездочек.
Составить программу, которая определяла бы разницу между двумя моментами времени, выраженными в часах и минутах. Первый момент времени предшествует второму. Сама разница также должна быть выражена в часах и минутах. Величина, как первого, так и второго моментов времени должна быть введена в компьютер с клавиатуры.
Составить программу, которая по известному радиусу окружности вычисляла бы длину окружности и площадь круга. Величина радиуса вводится в компьютер с клавиатуры.
Покупатель приобрел на рынке а килограммов картофеля, b килограммов огурцов и с килограммов помидоров. Составить программу, которая позволила бы подсчитать общую сумму покупки. Цена 1 килограмма каждого из приобретенных овощей (в рублях и копейках) и приобретенное их количество (в килограммах) для каждого вида овощей вводится в компьютер с клавиатуры.

Условные операторы и безусловного перехода.

Составить программу, которая определяет, делится ли введенное с клавиатуры целое число на 5.
Составить программу, которая проверяет, является ли введенное с клавиатуры число одновременно положительным и четным.
Стоимость проезда на пригородном поезде составляет 3 рубля за одну зону. Нумерация зон ведется, начиная с городского вокзала (1 зона). Составить программу, которая бы определяла стоимость проезда в один конец между станциями, расположенными в разных зонах. Номера зоны, в которой находится станция отправления и той зоны, в которой расположена конечная станция, вводятся в компьютер с клавиатуры. При составлении программы следует учесть, что пассажир может отправляться как из пригорода в город (из зоны с большим номером в зону с меньшим номером), так и из города в пригород (то есть из зоны с меньшим номером в зону с большим номером).
Усовершенствовать программу, вычисляющую стоимость проезда на пригородном поезде таким образом, чтобы она в начале своей работы выводила на экран компьютера меню, предлагающее пользователю следующие варианты:

– вычисление стоимости поездки в один конец;
– вычисление стоимости поездки в оба конца (стоимость такого билета равна удвоенной стоимости билета в один конец);
– вычисление стоимости месячного билета (эта стоимость равна стоимости поездки в один конец, умноженной на 15), а затем вычисляла бы соответствующую стоимость.

Операторы цикла.

В университете формируется баскетбольная команда, членами которой могут стать студенты, рост которых составляет не менее 175 сантиметров. Составить программу, которая позволила бы тренеру команды определить, сколько потенциальных кандидатов в команду имеется в студенческой группе, насчитывающей 25 человек. Данные о росте каждого из студентов группы вводятся в компьютер с клавиатуры.
Клиент положил в банк сроком на 5 лет некоторую денежную сумму под определенный процент. Составить программу, которая бы определяла, какую величину составит сумма вклада по истечении срока хранения данного вклада в банке, если по условиям договора о вкладе, заключенного между клиентом и банком, в течение всего срока хранения вклада банковский процент не должен изменяться. Сумма вклада и процент вводятся в компьютер с клавиатуры.
Известна легенда о том, как одному могущественному индийскому радже некий мудрец оказал важную услугу. В награду за услугу раджа был готов выполнить любое желание мудреца. Мудрец попросил положить перед ним шахматную доску и на первую клетку доски положить одно зерно риса, на вторую клетку два зерна, на третью клетку четыре зерна и так далее, то есть на каждую следующую клетку должно было быть положено вдвое больше зерен, чем на предыдущую, и таким образом должны были быть заполнены все 64 клетки шахматной доски.
Как оказалось при подсчете, для выполнения просьбы мудреца не хватило бы не только всех запасов риса во владениях раджи, но и всего урожая риса на всем земном шаре. Составить программу, которая определила бы на какой по счету клетке шахматной доски количество зерен риса должно было превысить один миллион, в случае, если просьба мудреца была бы выполнена.
Определить, исходя из условий, поставленных в предыдущем задании, сколько клеток шахматной доски нужно было бы заполнить для того, чтобы суммарное число зерен на них превысило бы один миллиард.

Работа с символами и строками.

Составить программу, которая проверяет, является ли введенная с клавиатуры последовательность символов целым числом, записанным в двоичной системе счисления. При этом известно, что в данной системе счисления для записи числа используются только две цифры – нуль и единица.
Составить программу, которая подсчитывает число слов во введенной в компьютер с клавиатуры строке. Условимся считать словом любую последовательность символов, которая отделена от других пробелом. Например, в предложении «персональный компьютер фирмы Apple» имеются 4 слова, отделенные друг от друга тремя пробелами. Как видно из приведенного примера, количество слов в строке можно определить как сумму имеющихся в строке пробелов плюс единица.
Изменить предыдущую программу таким образом, чтобы она подсчитывала среднюю длину слова во введенной с клавиатуры строке.
Составить программу, которая зашифровывает введенный с клавиатуры в компьютер текст. Процесс шифровки производится следующим образом: из десятичного кода каждого введенного с клавиатуры символа вычитается какое-либо число (например, 10). Получившаяся в результате вычитания величина интерпретируется как десятичный код некоторого другого символа, который и выводится на экран компьютера. Таким образом, получается внешне бессмысленный набор символов, который можно расшифровать, только зная вышеупомянутый принцип шифрования исходного сообщения.

Массивы.

Составить программу, заполняющую массив, состоящий из n элементов, (где n не больше 20) введенными с клавиатуры целыми числами. В этом массиве требуется определить число содержащихся в нем положительных элементов.
Составить программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Вывести на экран компьютера созданный массив и найти количество тех элементов, значения которых находятся в диапазоне от а до b. Число элементов массива и значения а и b вводятся с клавиатуры.
Составить программу, заполняющую массив, состоящий из n элементов (где n не больше 20), введенными с клавиатуры целыми числами. Требуется вывести массив на экран компьютера и найти индекс последнего по счету в массиве отрицательного элемента.
Составить программу, которая определяет, какие символы встречаются во вводимой с клавиатуры текстовой строке, а также сколько раз встречается во введенном тексте тот или иной символ. Признаком окончания ввода текстовой строки является ввод нуля, который сам в числе символов не учитывается. При этом в статистику символов должны быть включены наряду с буквами, цифрами и знаками препинания также и пробелы.

Функции и процедуры.

Составьте программу, которая определяет площадь треугольника по формуле Герона. Данная формула выглядит следующим образом:
где а, b и с – длины сторон треугольника, а р – половина периметра треугольника. Для извлечения квадратного корня используйте стандартную функцию sqrt.
Составьте программу, которая по выбору пользователя возводит в введенное с клавиатуры целое число в квадрат, определяет его абсолютную величину или извлекает квадратный корень числа. В программе следует предусмотреть вывод сообщения об ошибке, если пользователь попытается извлечь квадратный корень из отрицательного числа. Используйте в программе стандартные функции abs, sqr и sqrt.
Дополните предыдущую программу функцией, которая определяет, действительно ли введенное с клавиатуры число является целым (целое число может содержать только цифры от 0 до 9). Результат функции должен быть логического типа, то есть либо true, либо false. В зависимости от значения функции программа должна предложить пользователю либо произвести на выбор один из вышеуказанных вариантов вычислений, либо вывести сообщение об ошибке и вернуть пользователя к вводу исходных данных.
Составьте программу, которая заполняет одномерный массив из 20 элементов случайными целыми числами от 1 до 99, а затем определяет, сколько в массиве имеется простых чисел (простым числом называется такое, которое делится только на единицу или само на себя). Процесс определения того, является ли число простым, оформить в виде отдельной процедуры.
Составьте программу, которая определяет в интервале от 1 до 10000 все совершенные числа. Совершенным числом называется число, которое равно сумме всех своих делителей, включая единицу. Процесс определения того, является ли данное число совершенным, оформите в виде отдельной процедуры.

Работа с файлами.

Составьте программу, которая создает на дискете текстовый файл, записывает в него построчно информацию (количество строк заранее неизвестно, а признаком окончания ввода является ввод в конце очередной строки символа *) и подсчитывает количество строк, которое содержится в этом файле.
Дополните предыдущую программу таким образом, чтобы она в конец текстового файла дописывала информацию об имеющемся в файле количестве строк (включая последнюю строку с данными о количестве строк).
Составьте программу, которая создает на дискете типизированный файл, содержащий п целочисленных элементов (количество элементов пользователь вводит с клавиатуры), записывает в файл п чисел, введенных пользователем, и подсчитывает сумму элементов, содержащихся в этом файле, а затем добавляет в файл еще один элемент – подсчитанную сумму. Для контроля правильности ввода данных предусмотреть в программе вывод всех данных из файла на экран компьютера.
Составьте программу, которая создает на дискете не типизированный файл, содержащий следующую введенную пользователем информацию о прочитанной им книге: номера глав и названия этих глав, причем номера должны записываться в файл как целочисленные элементы, а названия – как строковые. Количество глав в прочитанной книге пользователь вводит с клавиатуры. Для контроля правильности вводимых данных следует вывести содержимое файла на экран компьютера, причем номер и название каждой главы должны выводиться в отдельной строке.

Работа с данными нестандартных типов.

Составить программу, которая по названию месяца определяет текущее время года. Для описания переменной-селектора в условном операторе использовать перечисляемый тип. В программе предусмотреть защиту от неправильного ввода данных.
Составить программу, которая по номеру года определяет, является ли он високосным или нет. Год является високосным в том случае, если его номер делится на 4 (например, високосными являются 1996 или 2004). Исключение составляют годы, номера которых делятся на 100. Эти годы являются високосными в том случае, если их номера делятся также на 400 (например, 1600 и 2000 годы являются високосными, а 1800 и 1900 нет). Переменную, которой присваивается значение номера года, описать как переменную ограниченного типа (значение данной переменной должно изменяться в диапазоне от 1600 до 2100). Предусмотреть в программе защиту от неверного ввода данных (вне зависимости от настроек системы Турбо Паскаль).
Составить программу, которая создает типизированный файл и вводит в него данные о результатах сдачи экзаменов классом из п школьников. Данные по успеваемости каждого из школьников должны быть оформлены в виде записи. Каждая запись должна содержать следующие данные: фамилию и имя школьника, его имя и оценки по следующим предметам: математика, физика, литература, история. Количество учеников, сдающих экзамен, заранее неизвестно, поэтому после ввода очередной записи программа должна запрашивать пользователя о том, будет ли он вводить следующую запись. После завершения ввода данных на экран должно быть выведено сообщение о количестве записей, имеющихся в файле, а затем должна быть выведена экзаменационная ведомость.
Составить программу, которая должна определять, является ли введенный с клавиатуры символ цифрой, прописной буквой английского алфавита, прописной буквой русского алфавита, строчной буквой английского алфавита, строчной буквой русского алфавита или каким-либо другим символом. При решении задачи использовать множественный тип данных.

Основы работы в графическом режиме.

Составить программу, которая по введенной пользователем длине стороны квадрата строит этот квадрат на экране компьютера, а также изображает диагонали квадрата и окружность, в которую вписан данный квадрат. Квадрат и его диагонали должны быть зеленого цвета, а окружность – красного. Ввод данных производится в текстовом режиме, а построение соответствующих фигур – в графическом.
Составить программу, которая заполняет экран компьютера красными и голубыми квадратами, расположенными в шахматном порядке. Размер каждого квадрата составляет 20 на 20 пикселов.
Составить программу, которая по введенному пользователем радиусу окружности строит данную окружность и разбивает ее на 6 секторов, каждый из которых закрашен своим цветом: белым, красным, зеленым, желтым, бирюзовым и фиолетовым. Ввод данных производится в текстовом режиме, а построение соответствующих фигур – в графическом.
Составить программу, которая запрашивает пользователя о результатах сдачи экзамена группой студентов и затем изображает эти результаты в виде гистограммы (столбчатой диаграммы). Всего данная гистограмма должна включать в себя четыре столбца, высота каждого из которых должна соответствовать количеству студентов, сдавших экзамены на следующие оценки: неудовлетворительно, удовлетворительно, хорошо и отлично. Слева от диаграммы следует изобразить координатную ось, которая показывает масштаб изображения. Справа от гистограммы следует поместить легенду, то есть информацию об используемых в диаграмме условных обозначениях. Ввод данных производится в текстовом режиме, а построение самой диаграммы – в графическом. Пример, показывающий, как должна выглядеть гистограмма, приведен на рис. 25.

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

Составить программу, которая использует такие же исходные данные, что и предыдущая, но результаты отображает не в виде гистограммы, а виде круговой диаграммы, в которой угловая величина каждого сектора соответствует проценту студентов группы, получивших ту или иную оценку. На каждом из секторов круговой диаграммы должна быть выведена надпись, показывающая процент соответствующей категории студентов (двоечников, троечников, хорошистов или отличников) по отношению к их общему количеству. Справа от диаграммы следует поместить легенду. Ввод данных производится в текстовом режиме, а построение самой диаграммы – в графическом. Пример, показывающий, как должна выглядеть круговая диаграмма, приведен на рис. 26.

Результаты работы программы построения круговой диаграммы успеваемости группы студентов по итогам сессии

Составить программу, которая по введенной пользователем длине стороны квадрата строит этот квадрат на экране компьютера, а также изображает диагонали квадрата и окружность, в которую вписан данный квадрат. Квадрат и его диагонали должны быть зеленого цвета, а окружность – красного. Ввод данных производится в текстовом режиме, а построение соответствующих фигур – в графическом.
Составить программу, которая заполняет экран компьютера красными и голубыми квадратами, расположенными в шахматном порядке. Размер каждого квадрата составляет 20 на 20 пикселов.
Составить программу, которая по введенному пользователем радиусу окружности строит данную окружность и разбивает ее на 6 секторов, каждый из которых закрашен своим цветом: белым, красным, зеленым, желтым, бирюзовым и фиолетовым. Ввод данных производится в текстовом режиме, а построение соответствующих фигур – в графическом.
Составить программу, которая строит график функции . Для обеспечения наглядности графика следует при его построении использовать разный горизонтальный и вертикальный масштабы. Пример, показывающий, как должен выглядеть экран в результате работы данной программы, приведен на рис. 27.

Результат работы программы, строящей график функции

Составить программу, которая строит гистограмму, отражающую результаты сдачи сессии студенческой группой (см. задание № 41), но столбцы гистограммы должны быть не плоскими, а объемными. Пример, показывающий, как может выглядеть такая диаграмма, приведен на рис. 28.
Составить программу, которая изображает Солнце с вращающимися вокруг него планетами – Землей и Марсом на фоне звездного неба. Угловые скорости вращения планет должные быть различными (так как Марс затрачивает на один оборот вокруг Солнца почти в два раза больше времени, чем Земля).

Результаты работы программы построения трехмерной гистограммы успеваемости группы студентов по итогам сессии

Составить программу, которая изображает приземление НЛО. «Летающая тарелка» должна появляться в верхней части экрана на фоне звездного неба с изображенной на нем луной, и опускаться вертикально вниз. После приземления НЛО в нижней части экрана долж-но появляться сообщение: «Приветствуем братьев по разуму». Примертого, как может выглядеть экран в результате выполнения данной программы, приведен на рис. 29.

Результат работы программы «Приземление НЛО»

Составить программу «Компьютерное пианино», в которой нажатие определенной клавиши на клавиатуре компьютера вызывает звучание определенной ноты. Нотам от «до» до «си» должно соответствовать нажатие клавиш от «1» до «7». На экране должен быть изображен нотный стан, причем при нажатии клавиши соответствующая ей нота должна выделяться другим цветом.