Как научиться решать алгоритмические задачи


Оглавление (нажмите, чтобы открыть):

Уроки 20 — 24
Основы алгоритмизации

Практикум

Линейные алгоритмы

Выполнив задания этой темы, вы научитесь:

— представлять линейный алгоритм в различных формах;
— использовать линейные алгоритмы при решении задач;
— применять переменные для хранения данных; осуществлять ввод-вывод информации.

Как вам уже известно, существуют различные типы алгоритмов и разные формы их представления.

Для представления линейного алгоритма в виде блок-схемы используются блоки ввода-вывода, выполнения действий, вызова вспомогательного алгоритма.

Для представления линейного алгоритма в виде программы используются операторы ввода-вывода, оператор присваивания, оператор вызова вспомогательного алгоритма.

Задание 8.1

Коллекция Эрмитажа содержит более 2 800 ООО единиц хранения. Если у каждого музейного экспоната задержаться всего на 5 минут и проводить в Эрмитаже по 8 часов каждый день, то может не хватить жизни, чтобы ознакомиться со всей коллекцией. Требуется вычислить суммарное время просмотра всей коллекции в минутах, часах, днях, годах, «жизнях», считая, что средняя продолжительность жизни в Роcсии составляет 70 лет.

Словесный алгоритм

Начало алгоритма
1. Введите количество экземпляров коллекции.
2. Рассчитайте время просмотра всех экземпляров:
• в минутах;
• в часах;
• в днях;
• в годах;
• в «жизнях».
3. Выведите результаты расчетов.
Конец алгоритма

Алгоритм в виде программы

В табл. 8.1 приведена программа к заданию на школьном алгоритмическом языке Кумир (с пояснениями). В табл. 8.2 приведены тексты программ на языках программирования Паскаль и Visual Basic.

Таблица 8.1. Программа на Кумире с пояснениями (к заданию 8.1)

Таблица 8.2. Примеры программ на Паскале и Visual Basic (к заданию 8.1)

Задание 8.2

Требуется рассчитать параметры прямоугольного треугольника с углом 30° по заданному катету, лежащему против угла 30°.

Словесный алгоритм

Начало алгоритма
1. Введите длину катета.
2. Рассчитайте гипотенузу по введенному катету,
исходя из свойств треугольника.
3. Рассчитайте второй катет по теореме Пифагора.
4. Выведите расчеты.
Конец алгоритма

Алгоритм в виде программы

В табл. 8.3 приведена программа к заданию на школьном алгоритмическом языке Кумир. В табл. 8.4 приведены тексты программ на языках программирования Паскаль и Visual Basic.

Таблица 8.3. Программа на Кумире с пояснениями (к заданию 8.2)

Таблица 8.4. Примеры программ на Паскале и Visual Basic (к заданию 8.2)

Задание 8.3

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

Словесный алгоритм

Начало алгоритма
1. Введите значение площади основания цилиндра.
2. Рассчитайте радиус основания цилиндра.
3. Рассчитайте объем цилиндра.
4. Рассчитайте объем шара.
5. Найдите соотношение между объемами цилиндра и шара.
6. Выведите расчеты.
Конец алгоритма

Рис. 8.3. К заданию 8.3

Алгоритм в виде программы

В табл. 8.5 приведена программа к заданию на школьном алгоритмическом языке Кумир. В табл. 8.6 приведены тексты программ на языках программирования Паскаль и Visual Basic.

Таблица 8.5. Программа на Кумире с пояснениями (к заданию 8.3)

Таблица 8.6. Примеры программ на Паскале и Visual Basic (к заданию 8.3)

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

К заданию 8.1

1. Разработчик алгоритма к заданию 8.1 (рис. 8.1), введя переменную п, хотел придать алгоритму свойство массовости. Какие еще переменные следует ввести, чтобы алгоритм соответствовал этому свойству в полной мере?
2. В приведенном последовательном алгоритме порядок вывода расчетных данных можно изменять. Какие команды в приведенных программах нельзя переставлять? Почему?
3. На блок-схеме представлены два блока вывода информации на экран. В чем их различие?
4. Запишите в тетради имена переменных, которые были использованы в процессе решения задания. Напишите под ними значения переменных, полученные в результате тестирования.
5. Что происходит в результате выполнения блока 3 представленного алгоритма?
6. Добавьте в программу блок вычислений, определяющий, сколько экспонатов в день удастся посмотреть посетителю.

К заданию 8.2

1. Замените в программе формулу расчета катета b = a-j3 и убедитесь, что результат от этого не изменится.
2. Используя готовый каркас блок-схемы, заполните его таким образом, чтобы по новой блок-схеме вычислялись высота и площадь равнобедренной трапеции с углом при основании 45° (рис. 8.5). Задание выполните в тетради.
3. Напишите текст программы на Кумире или другом языке для полученной блок-схемы.
4. Что надо изменить в условии задачи, чтобы расширить границы применимости алгоритма?
5. Из пояснительного рисунка видно, что а > b. Что произойдет, если при вводе а и b это соотношение будет нарушено?

К заданию 8.3

1. При расчетах радиуса и объемов используется константа 3,1415926. Что нужно изменить в программе, чтобы не набирать ее каждый раз заново?
2. В примере программы на языке Кумир тип используемых переменных описан следующим образом: вещ r, s, vshara, veil, k. Что означает эта запись? Почему для переменных выбран такой тип?
3. В формуле вычисления объема шара используется формула V — r3. В примерах программ на разных языках она записана по-разному. Есть ли здесь ошибки? Объясните, что означают разные записи? Придумайте такой вид записи, который будет верен для всех языков.

Рис. 8.5. Чертеж для вычисления высоты и площади равнобедренной трапеции

4. Можно ли изменить последовательность операторов расчета?

Разветвляющиеся алгоритмы

Выполнив задания этой темы, вы научитесь:

— использовать различные структуры ветвления;
— использовать простые и сложные условия;
— использовать вложенные ветвления;
— использовать структуру множественного выбора при наличии более чем двух ситуаций;
— тестировать алгоритм в пошаговом режиме для проверки всех его ветвей.

Для представления разветвляющегося алгоритма в виде блок-схемы используются блоки принятия решения. Для представления разветвляющегося алгоритма в виде программы используются условные операторы и операторы выбора (если вариантов выбора больше двух).


Задание 8.4

Требуется разработать алгоритм проверки принадлежности введенного числа данной арифметической прогрессии. Прогрессия задается двумя последовательными членами.

Словесный алгоритм

Начало алгоритма
1. Введите два последовательных члена арифметической прогрессии.
2. Введите произвольное целое число.
3. Найдите разность (d) арифметической прогрессии.
4. Найдите разность между введенным числом и членом арифметической прогрессии.
5. Найдите остаток от деления нацело найденной разности на d.
6. Организуйте проверку остатка:
— если остаток от деления равен 0, выведите сообщение:
«Число принадлежит рассматриваемой арифметической прогрессии»;
— иначе выведите сообщение:
«Число не принадлежит рассматриваемой арифметической прогрессии».
Конец алгоритма

Алгоритм в виде блок-схемы

Алгоритм в виде программы

В табл. 8.7 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.8 приведены тексты программ на языках программирования Паскаль и Visual Basic.

Таблица 8.7. Программа на Кумире с пояснениями (к заданию 8.4)

Таблица 8.8. Примеры программ на Паскале и Visual Basic (к заданию 8.4)

Задание 8.5

Из «Арифметики» таджикского ученого Авиценны (X-XI вв.) известно следующее свойство целых чисел: если число, будучи разделено на 9, дает в остатке 1 или 8, то квадрат этого числа, деленный на 9, даст 1. Требуется подтвердить верность свойства или опровергнуть его.

Словесный алгоритм

Начало алгоритма
1. Введите целое число.
2. Найдите остаток от деления этого числа на 8.
3. Организуйте проверку остатка на равенство 1 или 8:
• если остаток от деления равен 1 или 8, то:
а) найдите квадрат введенного числа;
б) найдите остаток от деления квадрата числа на 9;
в) организуйте проверку остатка от деления:
если остаток равен 1, то выведите сообщение «Свойство верно», иначе выведите сообщение «Свойство не верно»;
• иначе (остаток от деления не равен 1 и остаток от деления не равен 8) выведите сообщение «Остаток от деления 1 и Остаток от деления 8».
Конец алгоритма

Алгоритм в виде блок-схемы

Рис. 8.7. Блок-схема алгоритма (к заданию 8.5)

Алгоритм в виде программы

В табл. 8.9 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.10 приведены тексты программ на языках Паскаль и Visual Basic.

Таблица 8.9. Программа на Кумире с пояснениями (к заданию 8.5)

Таблица 8.10. Примеры программ на Паскале и Visual Basic (к заданию 8.5)

Задание 8.6

Требуется определить тип треугольника по двум введенным углам. При выполнении задания необходимо учесть ситуации некорректного ввода данных, например: 90, 90 или 120, 80.

Словесный алгоритм

Начало алгоритма
1. Введите два угла треугольника в градусах.
2. Организуйте проверку типа треугольника:
• если сумма двух углов меньше 180°, то вычислите значение третьего угла и рассмотрите три ситуации:
а) если все углы острые, то выведите сообщение «Треугольник остроугольный»;
б) если один из углов равен 90°, то выведите сообщение «Треугольник прямоугольный»;
в) в противном случае выведите сообщение «Треугольник тупоугольный »;
• иначе (если сумма углов больше 180°) выведите сообщение «Некорректный ввод».
Конец алгоритма

Алгоритм в виде блок-схемы

Фраза «один из углов равен 90°» в словесном алгоритме понятна человеку. Для компьютера ее следует детализировать, рассмотрев три ситуации (для каждого из углов ul, u2, u3). На алгоритмическом языке эта проверка может выглядеть следующим образом: ((ul = 90) и (и2 о 90) и (иЗ 90)) или ((и2 = 90) и (ul о 90) и (u3 90)) или ((иЗ = 90) и (ul 90) и (и2 90)).

Чтобы упростить проверку, в алгоритм должен быть введен блок, обеспечивающий условие «сумма углов = 180». После этого достаточно рассмотреть выполнение условия «(ul = 90) или (и2 = 90) или (иЗ = 90)».

Алгоритм в виде программы

В табл. 8.11 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.12 приведены тексты программ на языках Паскаль и Visual Basic.

Таблица 8.11. Программа на Кумире с пояснениями (к заданию 8.6)

Таблица 8.12. Примеры программ на Паскале и Visual Basic (к заданию 8.6)

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

К заданию 8.4

1. Какое сообщение будет получено в результате выполнения алгоритма и программ, если введенное число с будет равно al или а2?
2. Могут ли быть введены различающиеся по знаку или отрицательные числа al и а2?
3. Что надо изменить в блок-схеме и программе, чтобы они работали с тремя последовательными членами геометрической прогрессии (al, а2 — являются членами, с — следует проверить)?
4. Найдите на блок-схеме (см. рис. 8.6) блок ветвления и определите, является ли ветвление полным или нет.

К заданию 8.5

1. Заполните таблицу тестирования для числа 10 (см. табл. 8.9).
2. Почему в 7-й строке табл. 8.9 тестирования (первый тест) ничего нет?
3. Достаточно ли представленных в табл. 8.9 тестов, чтобы проверить все ситуации, которые могут возникнуть при выполнении программ (все ветви алгоритма)?
4. Можно ли объединить оба условия проверки (пп. 5 и 8) в одно сложное условие? Напишите логическое выражение для подобной проверки.
5. Составьте самостоятельно фрагмент блок-схемы алгоритма для приема менеджера на работу по следующим условиям:
• возраст от 30 до 40 лет;
• знание персонального компьютера или стаж работы по специальности не менее 5 лет.

К заданию 8.6

1. Почему при формировании сложного условия (см. табл. 8.11, п. 6) использована логическая связка И, а не ИЛИ?
2. Почему при формировании сложного условия (см. табл. 8.11, п. 8) использована логическая связка ИЛИ, а не И?
3. В алгоритме и программе тупоугольный треугольник определяется по веткам «иначе» (не прямоугольный и не остроугольный). Напишите самостоятельно сложное условие, определяющее, является ли треугольник тупоугольным.
4. Выполните тестирование программы для угла 90°.
5. Дополните алгоритм и программу блоком проверки положительных значений углов.

Подготовка к собеседованию — алгоритмические задачи [закрыт]

Для собеседования на работу нужно в течение пары недель подготовится к решению задач типа таких

Подскажите учебники / сайты где бы разбиралось решение таких задач?

Закрыт по причине того, что не по теме участниками Abyx, Vladimir Glinskikh, PashaPash, Nick Volynkin ♦ , Kromster says support Monica 8 авг ’15 в 15:00 .

Похоже, этот вопрос не соответствует тематике сайта. Те, кто голосовал за его закрытие, указывали следующую причину:

  • «Вопросы-опросники запрещены на Stack Overflow на русском. Для получения ответа, перефразируйте ваш вопрос так, чтобы на него можно было дать однозначно правильный ответ.» – Abyx, PashaPash, Nick Volynkin, Kromster says support Monica

Если вопрос можно переформулировать согласно правилам, изложенным в справке, отредактируйте его.

2 ответа 2

Алгоритм: Разобьем последовательность на пары, и будем искать звезду в паре. Например, есть последовательность 1,2,3,4 Вызовем first_knows_second 4ре раза:


Звезда в паре не найдена тогда, когда оба вызова, например first_knows_second(1,2) и first_knows_second(2,1) дали истину, или оба дали ложь. Вспомним условие: о звезде знают все, она же не знает ни о ком. Т.е. если оба в паре знают друг о друге, то ни один из них не является звездой. И так же, если оба не знают друг о друге, то они звездами не являются.

Если в паре есть один элемент, который не знает о другом, а другой о нем знает, то выделяем этого не знающего как звезду.

Итак, мы сделали N вызовов first_knows_second и нашли некоторое количество звезд. Для худшего варианта это будет N/2.

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

Итак, мы имеем последовательность (для худшего варианта): N + N/2 + N/4 + N/8. до тех пор, пока n деленная на что-то не будет равно 2 (внимание! это ограничение важно для понимания следующих строк!).

Чем больше N тем длиннее последовательность. N/2 + N/4 + N/8 + . будет равно N при бесконечном знаменателе. Т.е. при бесконечно большом числе N наша последовательность N + N/2 + N/4 + N/8. будет равна 2*N . Что и является ответом.

АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ
методическая разработка по алгебре (8 класс)

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

Скачать:

Вложение Размер
АЛГОРИТМЫ-ПАМЯТКИ ДЛЯ РЕШЕНИЯ ЗАДАЧ 26 КБ

Предварительный просмотр:

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

1) Обозначить буквой х неизвестную величину, записав ответ на вопрос задачи (Пусть…).

2) Составить уравнение по условию задачи.

3) Решить это уравнение.

  1. Записать краткий ответ на вопрос задачи.

«Алгоритм решения задач на применение теоремы Пифагора»:

1)Выделить на чертеже прямоугольный треугольник, стороной которого является искомый отрезок.

2)Определить катет это или гипотенуза.

3)Записать для этого треугольника теорему Пифагора (для гипотенузы) или следствие из нее (для катета) в обозначениях данной задачи.

4)Подставив в формулу известные величины, найти неизвестную величину.

Как решать задачи.

  1. Прочитай задачу и представь себе то, о чем говорится в задаче.
  2. Запиши задачу кратко или выполни чертеж.
  3. Поясни, что показывает каждое число, повтори вопрос задачи.
  4. Подумай, можно ли сразу ответить на вопрос задачи. Если нет, то почему. Что

нужно узнать сначала, что потом.

  1. Составь план решения.
  2. Выполни решение.
  3. Проверь решение и ответь на вопрос задачи.
  4. Не забудь записать ответ к задаче, проверь правильно ли записаны пояснения к

Рекомендации по решению нестандартных задач:

1. Сделать к задаче рисунок или чертеж; подумай, может быть, нужно сделать на них дополнительные построения или изменить чертеж в процессе решения задачи.

2. Ввести вспомогательный элемент (часть).

3. Использовать для решения задачи способ подбора.

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

5. Разделить условие или вопрос задачи на части и решить ее по частям.

6. Начать решение задачи «с конца».

Алгоритм решения задач на переливание:

В задачах на переливание разрешены следующие операции:

  1. заполнение жидкостью одного сосуда до краев;
  2. переливание жидкости в другой сосуд или выливание жидкости;

При решении таких задач необходимо учитывать следующие замечания:

  • разрешается наливать в сосуд ровно столько жидкости, сколько в нем помещается;
  • разрешается переливать всю жидкость из одного сосуда в другой, если она в него вся помещается;
  • разрешается отливать из одного сосуда в другой столько жидкости, сколько необходимо, чтобы второй сосуд стал полным.

Каждую задачу на переливание таким методом можно решать двумя способами:

а) начать переливания с большего сосуда;

б) начать переливания с меньшего сосуда.

При решении задач первого типа («Водолей») можно использовать такой алгоритм:


  1. Наполнить большую емкость жидкостью из бесконечного источника.
  2. Перелить из большей емкости в меньшую емкость.
  3. Вылить жидкость из меньшей емкости.
  4. Повторить действия 1-3 до тех пор, пока не будет получено обозначенное в условии задачи количество жидкости.

При решении задач второго типа («Переливашка») можно использовать следующий алгоритм:

  1. Из большей емкости наполнить емкость промежуточного объема.
  2. Перелить жидкость из промежуточной емкости в самую маленькую емкость.
  3. Перелить жидкость из самой маленькой емкости в большую емкость.
  4. Повторять действия 2-3 до тех пор, пока емкость промежуточного объема не станет пустой.
  5. Если емкость промежуточного объема опустела, то повторить действия 1-5 до тех пор, пока не будет получено обозначенное в условии задачи количество жидкости.

Алгоритм решения задач :

  • Читаем условие задачи. Условие – это та часть текста, где содержатся сведения об известных и неизвестных значениях величин, об отношениях между ними.
  • Определяем требование, т.е. указание на то, что надо найти. Требование обычно выражается вопросом, начинающимся словом «Сколько…?» и заканчивающимся знаком вопроса.
  • Находим данные задачи. Данные – это известные числа.
  • Определяем искомое. Это конечная цель процесса решения арифметической задачи.
  • Если что-то непонятно, необходимо обратиться за разъяснением к учителю. Могут встретиться непонятные слова и обороты.
  • Ищем пути решения задачи и составляем план решения.
  • Можно использовать графическую модель (схема в «отрезках») или составить таблицу.
  • Записываем решение и ответ.

Понятие алгоритма. Принципы построения алгоритма. Компьютер как исполнитель алгоритма. Этапы решения задач на ЭВМ. Порядок разработки программы для решения

Процесс решения задач на компьютере – это совместная деятельность человека и ЭВМ. На долю человека приходятся этапы, связанные с творческой деятельностью – постановкой, алгоритмизацией, программированием задач и анализом результатов, а на долю персонального компьютера – обработка информации с разработанным алгоритмом.

Первый этап – постановка задачи.На этом этапе участвует человек, хорошо представляющий предметную область задачи. Он должен чётко определить цель задачи, дать словесное описание содержания задачи и предложить общий подход к её решению.

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

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

Третий этап – алгоритмизация задачи.На основе математического описания необходимо разработать алгоритм решения.

Алгоритм –система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа (класса).

Задача составления алгоритма не имеет смысла, если не известны или не учитываются возможности его исполнителя (ребёнок может прочесть, но не может решить сложную задачу).

Исполнителем может быть не только человек, но и автомат. Компьютер – лишь частный, но наиболее впечатляющий пример исполнителя, чьё поведение основано на реализации алгоритма. Более того, создание персонального компьютера оказало воздействие на развитие теории алгоритмов, одной из областей дискретной математики.

Эффективный метод построения алгоритма –метод пошаговой детализации(последовательного построения). При этом сложная задача разбивается на ряд более простых. Для каждой подзадачи – свой алгоритм. Универсальный эффективный метод построения алгоритма является основой структурного программирования (языки QBasic, Turbo Pascal и др.).

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

Используются различные способы записи алгоритмов:

– словесный (запись рецептов в кулинарной книге, инструкции по использованию технических устройств и т. п.);

– графический – пример на рисунке;

– структурно-стилизованный (для записи используется язык псевдокода).

Свойства алгоритма.При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.

Однозначностьалгоритма – единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя (сложитьАиВ).

Конечностьалгоритма – обязательность завершения каждого из действий, составляющих алгоритм, и завершимость алгоритма в целом. Представленный на рисунке алгоритм обладает этим свойством.

Результативностьалгоритма – предполагает, что выполнение алгоритма должно завершиться получением определённых результатов. У нас для целыхАиВвсегда будет вычислена сумма.

Массовость– возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. В нашем примере алгоритмом используется обозначение, а не конкретные числа, поэтому он может быть использован для сложения любых целых чисел.

Правильностьалгоритма – способность алгоритма давать правильные результаты решения поставленных задач.

Четвёртый этап – программирование.Программой называется план действий, подлежащих выполнению некоторым исполнителем, в качестве которого может выступать компьютер. Программа позволяет реализовать разработанный алгоритм. Именно этому этапу посвящена большая часть данного учебного пособия.

Пятый этап – ввод программы и исходных данных в ЭВМс клавиатуры с помощью редактора текстов и их запись на гибкий или жёсткий диск для постоянного хранения.

Шестой этап – тестирование и отладка программы. Исполнение алгоритма с помощью ЭВМ, поиск и исключение ошибок. При этом программисту приходится выполнять рутинную работу по проверке работы программы, поиску и исключению ошибок, и поэтому для сложных программ этот этап часто требует гораздо больше времени и сил, чем написание первоначального текста программы.

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

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

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

Седьмой этап – исполнение отлаженной программы и анализ результатов.На этом этапе программист запускает программу и задаёт исходные данные, требуемые по условию задачи.

Полученные результаты анализируются постановщиком задачи, и на основании этого анализа вырабатываются соответствующие решения, рекомендации, выводы. Например, если при решении задачи на ПК результат 2+3=4, то следует изменить алгоритм и программу.

Чтобы персональный компьютер (ПК) выполнил решение какой-либо задачи, ему необходимо получить от человека инструкции, как её решать. Набор таких инструкций для компьютера, направленный на решение конкретной задачи, называется компьютерной программой.

Современные компьютеры не настолько совершенны, чтобы понимать программы, написанные на каком-либо употребляемом человеком языке.

Команды, записанные для ЭВМ, необходимо представлять в понятной компьютеру форме. С этой целью применяютязыки программирования– искусственные языки, алфавит, словарный запас и структура которых удобны и понятны компьютеру.

В самом общем смыслеязыком программированияназывается фиксированная система обозначений и правил для описания алгоритмов и структур данных.

Язык программирования Турбо- Паскаль. Структура языка Turbo-Pascal, основные понятия. Запись и порядок выполнения операций в арифметическом выражении. Стандартные математические функции и процедуры Turbo-Pascal

Система программирования Turbo Pascal предназначена для выполнения этапов решения задачи на алгоритмическом языке Паскаль и включает в себя три главные компоненты: редактор текстов, компилятор, исполнительную систему.

С помощью встроенного в систему текстового редактора можно формировать в памяти любые тексты, не только программы на Паскале. В частности, это могут быть исходные данные решаемой задачи в текстовой форме. Текст программы, созданный редактором, можно сохранить на диске в виде файла с именем следующего формата .раs, где pas — это стандартное расширение имени файла, созданного системным редактором. Имя файла задается пользователем.

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


Выполнение программы остается под контролем исполнительной системы. Она, в частности, помогает обнаружить ошибку в программе, если при исполнении произошел сбой. Пользователю сообщается причина сбоя и указывается место, где он случился в Паскаль-программе, происходит автоматический возврат в режим редактирования.

Turbo Pascal позволяет редактировать, компилировать, компоновать и выполнять Паскаль-программы. При этом пользователю предоставляется высокая скорость компиляции, удобство работы с компьютером и мощная библиотека процедур и функций.

Программа на Паскале в общем случае состоит из нескольких файлов. Один из них содержит главную программу, а остальные – модули. Главная программа состоит из заголовка, блока и заканчивается точкой — признаком конца программы. В свою очередь, блок содержит разделы описаний и раздел операторов. В общем случае «скелет» программы можно представить следующим образом:

Program (заголовок программы);

Uses(раздел объявления модулей);

Label(раздел объявления меток);

Const(раздел объявления констант);

Type(раздел объявления типов);

Var(раздел объявления переменных);

Procedure(function)(раздел объявления подпрограмм: процедурили функций);

Begin

(раздел операторов, обязательная часть);

end.

Все указанные разделы отделяются друг от друга точкой с запятой.

Раздел операторов должен обязательно присутствовать в любой программе и является основным. Предшествующие разделы носят характер описаний и не обязательно содержаться в программе.

Заголовок программы состоит из зарезервированного словаprogramи имени программы (со списком параметров, заключенных в круглые скобки). Завершается заголовок точкой с запятой.

В Turbo Pascal имеются особенности в структуре программы. Так, заголовок программы необязателен и игнорируется компилятором. Порядок размещения разделов произвольный, можно создавать несколько одинаковых разделов. Единственное правило, которое необходимо выдерживать, — в любом месте программы можно использовать лишь элементы (метки, типы, константы, переменные, подпрограммы и т. д.), которые были определены ранее по тексту программы или являются предопределенными элементами языка. Исключением из этого правила может быть лишь определение типа-указателя через неопределенный до этого тип. Однако этот тип в дальнейшем должен быть обязательно определен.

Операторы в разделе операторов отделяются друг от друга точкой с запятой. Передendточка с запятой не ставится, однако ее наличие не является ошибкой, а лишь означает присутствие между последним исполняемым оператором и служебным словомendеще одного оператора — пустого оператора. Заканчивается программа словомend, после которого ставится точка.

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

Язык программирования Паскаль является языком структурного программирования. В нем есть все необходимые управляющие конструкции для структурного построения программы. Наглядность такому построению придает структуризация внешнего вида текста программы. Основной используемый для этого прием — сдвиги строк, которые должны подчиняться следующим правилам:

— конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);

— вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.

Знаки операций предназначены для обозначения тех или иных арифметических, логических или других действий. Они бывают двух типов: состоящие из небуквенных символов (например, +, -, * и т.д.) и буквенные операции (например, not, mod, div и т. д.), представляющие собой зарезервированные слова. Операции над данными делятся на унарные (применимые к одному операнду) и бинарные (применимые к двум операндам). Приведем примеры бинарных арифметических операций (в таблице буква I обозначает целые типы, R — вещественные типы):

Знак Выражение Типы операндов Тип результата Операция
+ А+В R,R I,I I,R; R,I R I R Сложение
А-В R,R I,I I,R; R,I R I R Вычитание
* А*В R,R I,I I,R; R,I R I R Умножение
/ А/В R,R I,I I,R; R,I R R R Вещественное деление
Div A div B I, I I Целое деление
Mod A mod B I, I I Остаток от деления

Арифметическое выражение задает порядок выполнения действий над числовыми величинами. Арифметические выражения содержат арифметические операции, функции, операнды, круглые скобки. Одна константа или одна переменная — простейшая форма арифметического выражения.

Порядок выполнения операций в арифметическом выражении подчиняется трем правилам:

1. Правилу скобок. Оно гласит, что первыми выполняются операции в скобках. Если имеется несколько пар вложенных скобок, вычисления начинаются с самых внутренних скобок.

2. Правилу учета приоритета операций: вначале вычисляются значения функций, затем выполняются операции умножения и деления и в последнюю очередь — операции сложения и вычитания.

3. Правилу следования: операции одинакового старшинства (приоритета) выполняются слева направо в порядке их следования.

В качестве операндов в выражении, кроме констант и переменных, можно использовать стандартные функции. Аргументы функций обязательно заключаются в круглые скобки. Приоритет выполнения функции выше, чем приоритет выполнения арифметических операций. Рассмотрим стандартные функции Турбо Паскаля (в таблице буква I обозначает целые типы, R — вещественные типы):

Обращение Тип аргумента Тип результата Тип действия
pi R Число π
abs(x) I,R I,R Модуль (абсолютная величина) числа х
sqr(x) I,R I,R Квадрат х
sqrt(x) I,R R Корень квадратный из х (х≥0)
sin(x) I,R R Синус х (х в радианах)
cos(x) I,R R Косинус х (х в радианах)
arctan(x) I,R R Арктангенс х (результат в радианах)
exp(x) I,R R Экспонента е в степени х (е≈2,71828)
ln(x) I,R R Натуральный логарифм х (x>0)
trunc(x) R I Целая часть х
int(x) I,R R Целая часть х
round(x) R I Округление х до ближайшего целого
frac(x) I,R R Дробная часть х
random I Случайное число [0,1)
random(x) I R Случайное число [0,х)
dec(x,[n]) I I Уменьшение х на n, при отсутствии n – на 1
inc(x,[n]) I I Увеличение х на n, при отсутствии n – на 1
odd(x) Longint Boolean true, если значение x нечетное; false, если x четное
ord(x) любой порядковый Longint Порядковый номер значения х в его типе. Если х – символ, то функция возвращает код символа
pred(x) любой порядковый тот же, что для x Предыдущее относительно х значение в его типе
succ(x) любой порядковый тот же, что для x Следующее относительно х значение в его типе
chr(x) Byte Char Определяет символ с указанным кодом (х – число, определяющее код символа)

Турбо Паскале не содержит некоторые часто используемые математические функции, поэтому при их вычислении используют эквивалентные математические формулы:

Функция Эквивалентная математическая формула Запись в программе
ax exp(x*ln(a))
tg(x) sin(x)/cos(x)
arcsin(x) arctan(x/sqrt(1-x*x))
arccos(x) arctan(sqrt(1-x*x)/x)
logax ln(x)/ln(a)

При возведении в небольшую целую степень вместо операции возведения в степень рекомендуется использовать операцию умножения, поскольку возведение в степень выполняется на несколько порядков дольше умножения и не позволяет обрабатывать отрицательные аргументы.

Структура процедуры имеет следующий вид:

Procedure (формальные параметры : их тип);

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

Процедура вызывается по имени:

Значение каждого фактического параметра при вызове процедуры передаётся формальному параметру. Временно управление передаётся процедуре. После завершения работы процедуры управление возвращается в основную программу.

Каждый формальный параметр указывается вместе со своим типом. Соответствующий ему фактический параметр указывается без типа. Между формальными и фактическими параметрами должно быть соответствие по количеству параметров, по их типу и порядку следования.

Заголовок процедуры может выглядеть так:

PROCEDURE GG(a,b,c:integer); вызыватьсятак: GG(3,n,m)

Здесь a,b,c-формальные параметры, а 3, n, m-фактические параметры

Таким образом в процедуру передаются значения: a=3, b=n, c=m

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


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9334 — | 7292 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Алгоритмы как их решать?

Ответ

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

Внимательно ознакомьтесь с условием исходной задачи. Продумайте ее решение: имеется ли цикличность в задаче. Возможно, заданы операции, выполнение которых обусловлено удовлетворением разных условий. Выпишите все известные данные и искомые величины.

Как решать задачи с алгоритмом

Любой алгоритм требует формализованной записи. Если вам требуется составить блок-схему алгоритма, используйте специальные элементы для обозначения каждой операции создаваемой инструкции. Какправило, это блоки из прямоугольных и ромбическихфигур, соединенные в общеедерево.

Составьте общий алгоритмрешения задачи. На первом шаге введите в алгоритм переменные величины, обозначающие известные данные и результирующие значения. Присвойте переменным известные из условия задачизначения.Детализируйте алгоритм. Подробно распишите условиезадачи. Каждый шаг инструкции должен быть записан на отдельной строке. При необходимости задайте циклы или разветвления алгоритма.Все действия в шагах инструкции производите с заданнымипеременными. Если необходимо ввести вспомогательные переменные, включите их дополнительно в самом начале алгоритма.Часто из смысла исходной задачив процессе решения вытекают условия, при удовлетворении которых над данными проводится одно действие, а без удовлетворения – другое. В этом случае речь идет о разветвлении алгоритма. Оформите его двумя ветками дерева-инструкции.Если при разветвлении алгоритма после прохождения условия одну из веток необходимо вернутьназад по телу алгоритма, тообразуется циклический алгоритм. Четко проследите, чтобы цикл внутри инструкции не был бесконечен и имел конечное число итераций.Любая последовательность выполняемых действий должна привести к конечному результату, заданному в условии задачи. После получения искомой величины, завершите тело алгоритма и запишите полученный ответ.

Как научиться решать алгоритмические задачи?

Исключительно важно использовать язык блок-схем при разработке алгоритма решения задачи. Решение одной и той же задачи может быть реализовано с помощью различных алгоритмов, отличающихся друг от друга как по времени счета и объему вычислений, так и по своей сложности. Запись этих алгоритмов с помощью блок-схем позволяет сравнивать их, выбирать наилучший алгоритм, упрощать, находить и устранять ошибки.

Отказ от языка блок-схем при разработке алгоритма и разработка алгоритма сразу на языке программирования приводит к значительным потерям времени, к выбору неоптимального алгоритма. Поэтому необходимо изначально разработать алгоритм решения задачи на языке блок-схем, после чего алгоритм перевести на язык программирования.

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

В процессе разработки алгоритма решения задачи можно выделить следующие этапы:

  • Этап 1 . Математическое описание решения задачи.
  • Этап 2 . Определение входных и выходных данных.
  • Этап 3 . Разработка алгоритма решения задачи.

Базовые алгоритмические конструкции

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

  • следование (линейный алгоритм);
  • ветвление (разветвляющийся алгоритм);
  • цикл-пока (циклический алгоритм).

Линейные алгоритмы

Линейный алгоритм образуется из последовательности действий, следующих одно за другим. Например, для определения площади прямоугольника необходимо сначала задать длину первой стороны, затем задать длину второй стороны, а уже затем по формуле вычислить его площадь.

Пример

ЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.

На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:

Этап 1. Математическое описание решения задачи.

Математическим решением задачи является известная формула:

где с-длина гипотенузы, a, b – длины катетов.

Этап 2. Определение входных и выходных данных.

Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.

Этап 3. Разработка алгоритма решения задачи.

На данной схеме цифрами указаны номера элементов алгоритма, которые соответствуют номерам пунктов словесного описания алгоритма.

Разветвляющиеся алгоритмы

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

Пример

ЗАДАЧА. Разработать алгоритм вычисления наибольшего числа из двух чисел x и y.

Этап 1. Математическое описание решения задачи.

Из курса математики известно, если x > y, то наибольшее число x, если x y, то переход к шагу 6, иначе к шагу 7.

  • Вывод информации: число x больше y. Переход к шагу 8.
  • Вывод информации: число y больше x. Переход к шагу 8.
  • Конец алгоритма.

  • В схеме алгоритма решения задачи цифрами указаны номера элементов алгоритма, которые соответствуют номерам шагов словесного описания алгоритма

    В рассматриваемом алгоритме (рис.3) имеются три ветви решения задачи:

    • первая: это элементы 1, 2, 3, 4, 8.
    • вторая: это элементы 1, 2, 3, 5, 6, 8
    • третья: это элементы 1, 2, 3, 5, 7, 8.

    Выбор ветви определяется значениями x и y в элементах 3 и 5, которые являются условиями, определяющими порядок выполнения элементов алгоритма. Если условие (равенство), записанное внутри символа «решение», выполняется при введенных значениях x и y, то следующими выполняется элементы 4 и 8. Это следует из того, что они соединены линией с надписью «да» и направление (последовательность) вычислений обозначена стрелочкой.

    Если условие в элементе 3 не выполняется, то следующим выполняется элемент 5. Он соединен с элементом 3 линией с надписью «нет». Если условие, записанное в элементе 5, выполняется, то выполняется элементы 6 и 8, в противном случае выполняются элементы 7 и 8.

    Циклические алгоритмы

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

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

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

    • параметр цикла – величина, с изменением значения которой связано многократное выполнение цикла;
    • начальное и конечное значения параметров цикла;
    • шаг цикла – значение, на которое изменяется параметр цикла при каждом повторении.

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

    В подготовку цикла входят действия, связанные с заданием исходных значений для параметров цикла:

    • начальные значения цикла;
    • конечные значения цикла;
    • шаг цикла.

    В тело цикла входят:

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

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

    Пример

    ЗАДАЧА. Разработать алгоритм вычисления суммы натуральных чисел от 1 до 100.

    Этап 1. Математическое описание решения задачи.

    Обозначим сумму натуральных чисел через S. Тогда формула вычисления суммы натуральных чисел от 1 до 100 может быть записана так:

    где Xi – натуральное число X c номером i, который изменяется от 1 до n, n=100 – количество натуральных чисел.

    Этап 2. Определение входных и выходных данных.

    Входными данными являются натуральные числа: 1, 2, 3, 4, 5, …, 98, 99, 100.

    Выходные данные – значение суммы членов последовательности натуральных чисел.

    Параметр цикла величина, определяющая количество повторений цикла. В нашем случае i – номер натурального числа.

    Подготовка цикла заключается в задании начального и конечного значений параметра цикла.

    • начальное значение параметра цикла равно 1,
    • конечное значение параметра цикла равно n,
    • шаг цикла равен 1.

    Для корректного суммирования необходимо предварительно задать начальное значение суммы, равное 0.

    Тело цикла. В теле цикла будет выполняться накопление значения суммы чисел, а также вычисляться следующее значение параметра цикла по формулам:

    Условие продолжения цикла: цикл должен повторяться до тех пор, пока не будет добавлен последний член последовательности натуральных чисел, т.е. пока параметр цикла будет меньше или равен конечному значению параметра цикла.

    Этап 3. Разработка алгоритма решения задачи.

    Введем обозначения: S – сумма последовательности, i – значение натурального числа.

    Начальное значение цикла i=1, конечное значение цикла i =100, шаг цикла 1.

    АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ
    методическая разработка по алгебре (8 класс)

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

    Скачать:

    Словесное описание алгоритма Запись алгоритма на языке блок-схем
    1. Начало алгоритма.
    2. Ввод значений длин катетов a и b.
    3. Вычисление длины гипотенузы с по формуле
    4. Вывод значения длины гипотенузы.
    5. Конец алгоритма
    Вложение Размер
    АЛГОРИТМЫ-ПАМЯТКИ ДЛЯ РЕШЕНИЯ ЗАДАЧ 26 КБ

    Предварительный просмотр:

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


    1) Обозначить буквой х неизвестную величину, записав ответ на вопрос задачи (Пусть…).

    2) Составить уравнение по условию задачи.

    3) Решить это уравнение.

    1. Записать краткий ответ на вопрос задачи.

    «Алгоритм решения задач на применение теоремы Пифагора»:

    1)Выделить на чертеже прямоугольный треугольник, стороной которого является искомый отрезок.

    2)Определить катет это или гипотенуза.

    3)Записать для этого треугольника теорему Пифагора (для гипотенузы) или следствие из нее (для катета) в обозначениях данной задачи.

    4)Подставив в формулу известные величины, найти неизвестную величину.

    Как решать задачи.

    1. Прочитай задачу и представь себе то, о чем говорится в задаче.
    2. Запиши задачу кратко или выполни чертеж.
    3. Поясни, что показывает каждое число, повтори вопрос задачи.
    4. Подумай, можно ли сразу ответить на вопрос задачи. Если нет, то почему. Что

    нужно узнать сначала, что потом.

    1. Составь план решения.
    2. Выполни решение.
    3. Проверь решение и ответь на вопрос задачи.
    4. Не забудь записать ответ к задаче, проверь правильно ли записаны пояснения к

    Рекомендации по решению нестандартных задач:

    1. Сделать к задаче рисунок или чертеж; подумай, может быть, нужно сделать на них дополнительные построения или изменить чертеж в процессе решения задачи.

    2. Ввести вспомогательный элемент (часть).

    3. Использовать для решения задачи способ подбора.

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

    5. Разделить условие или вопрос задачи на части и решить ее по частям.

    6. Начать решение задачи «с конца».

    Алгоритм решения задач на переливание:

    В задачах на переливание разрешены следующие операции:

    1. заполнение жидкостью одного сосуда до краев;
    2. переливание жидкости в другой сосуд или выливание жидкости;

    При решении таких задач необходимо учитывать следующие замечания:

    • разрешается наливать в сосуд ровно столько жидкости, сколько в нем помещается;
    • разрешается переливать всю жидкость из одного сосуда в другой, если она в него вся помещается;
    • разрешается отливать из одного сосуда в другой столько жидкости, сколько необходимо, чтобы второй сосуд стал полным.

    Каждую задачу на переливание таким методом можно решать двумя способами:

    а) начать переливания с большего сосуда;

    б) начать переливания с меньшего сосуда.

    При решении задач первого типа («Водолей») можно использовать такой алгоритм:

    1. Наполнить большую емкость жидкостью из бесконечного источника.
    2. Перелить из большей емкости в меньшую емкость.
    3. Вылить жидкость из меньшей емкости.
    4. Повторить действия 1-3 до тех пор, пока не будет получено обозначенное в условии задачи количество жидкости.

    При решении задач второго типа («Переливашка») можно использовать следующий алгоритм:

    1. Из большей емкости наполнить емкость промежуточного объема.
    2. Перелить жидкость из промежуточной емкости в самую маленькую емкость.
    3. Перелить жидкость из самой маленькой емкости в большую емкость.
    4. Повторять действия 2-3 до тех пор, пока емкость промежуточного объема не станет пустой.
    5. Если емкость промежуточного объема опустела, то повторить действия 1-5 до тех пор, пока не будет получено обозначенное в условии задачи количество жидкости.

    Алгоритм решения задач :

    • Читаем условие задачи. Условие – это та часть текста, где содержатся сведения об известных и неизвестных значениях величин, об отношениях между ними.
    • Определяем требование, т.е. указание на то, что надо найти. Требование обычно выражается вопросом, начинающимся словом «Сколько…?» и заканчивающимся знаком вопроса.
    • Находим данные задачи. Данные – это известные числа.
    • Определяем искомое. Это конечная цель процесса решения арифметической задачи.
    • Если что-то непонятно, необходимо обратиться за разъяснением к учителю. Могут встретиться непонятные слова и обороты.
    • Ищем пути решения задачи и составляем план решения.
    • Можно использовать графическую модель (схема в «отрезках») или составить таблицу.
    • Записываем решение и ответ.

    Задачи на логику, головоломки, загадки, ребусы — Л О Г О — Р А Й

    Задачи на логику, алгоритмы, комбинаторика, принцип Дирихле, вероятности, вычисления, математика, геометрия, физика, история, анаграммы, ребусы, шарады

    Стаканы на столе


    Четыpе стакана поставлены квеpху дном в четыpёх углах вpащающегося квадpатного стола. Вы хотите пеpевеpнуть их в одну стоpону: или все ввеpх или все вниз. Вы можете взять любые два стакана, и должны пеpевеpнуть один или два из них . Есть два условия: у вас завязаны глаза, и стол повоpачивается на произвольное число оборотов каждый pаз, когда вы дотpагиваетесь до стаканов. Так что вы будете делать?

    Голодный студент

    На сковороде могут одновременно жариться две котлеты. Каждую котлету нужно обжаривать с двух сторон, при этом на обжаривание ее с одной стороны требуется 2 мин. Голодный студент мечтает побыстрее поджарить три котлеты. Какое наименьшее время ему потребуется?

    Восемь монет

    Над этой хитрой задачкой будут долго думать твои друзья. Если знать секрет, все очень просто, но найти правильное решение без подсказки действительно трудно. Но тебе, возможно, повезет — попробуй решить задачу самостоятельно, прежде чем посмотришь ответ.

    Нужно положить восемь монет на стол в один ряд, вот так:

    За один ход ты берешь одну монету, переносишь ее через две соседние монеты (монеты, а не стопки!) и кладешь на третью.

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

    Военная переправа

    Командиру взвода нужно переправить через реку 10 солдат. На реке нет мостов, и ни один солдат не пожелал переплывать реку вплавь. Тут командир увидел лодку, в которой сидели два мальчика. Лодка могла удержать либо двоих мальчиков, либо одного солдата. Как командир переправил солдат на другой берег, используя лодку?

    Цели и задачи теории алгоритмов

    Читайте также:

    1. I. ОСНОВНЫЕ ЗАДАЧИ ВНЕШНЕЙ ПОЛИТИКИ
    2. I. ОСНОВНЫЕ ЗАДАЧИ ВНЕШНЕЙ ПОЛИТИКИ
    3. II. ОСНОВНЫЕ ПСИХОЛОГИЧЕСКИЕ ТЕОРИИ ВОЛИ.
    4. II. Основные цели и задачи
    5. А. Современные теории элит
    6. Автоматизированные рабочие места. Функции и задачи АРМ
    7. Аксиоматическое построение теории вероятностей
    8. Аксиомы теории вероятностей
    9. АКТУАЛЬНОСТЬ И ОСНОВНЫЕ ЗАДАЧИ КУРСА
    10. Алгоритмические задачи.
    11. Анализ решения данной задачи.
    12. Аналитические способы представления задачи 1

    Обобщая результаты различных разделов теории алгоритмов можно выделить следующие цели и соотнесенные с ними задачи, решаемые в теории алгоритмов:

    · формализация понятия «алгоритм» и исследование формальных алгоритмических систем;

    · формальное доказательство алгоритмической неразрешимости ряда задач;*

    · классификация задач, определение и исследование сложностных классов;

    · асимптотический анализ сложности алгоритмов;

    · исследование и анализ рекурсивных алгоритмов;

    · получение явных функций трудоемкости в целях сравнительного анализа алгоритмов;

    · разработка критериев сравнительной оценки качества алгоритмов.

    Разделы современной теории алгоритмов

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

    Строгие определения понятия «алгоритм» связаны с введением специальных математических конструкций – формальных моделей вычислений. Одной из таких моделей является машина Тьюринга.

    В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.

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

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

    Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

    · Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а) должна представлять собой пустой символ.

    · Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q) должно быть конечным (завершающим программу) – состояние останова.

    · Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

    Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

    · Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

    · Передвигаться на одну ячейку влево или вправо.

    · Менять свое внутреннее состояние.

    Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).

    | следующая лекция ==>
    Теория алгоритмов | Пример работы машины Тьюринга

    Дата добавления: 2014-01-03 ; Просмотров: 958 ; Нарушение авторских прав? ;

    Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

    Алгоритмы как их решать?

    Ответ

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

    Внимательно ознакомьтесь с условием исходной задачи. Продумайте ее решение: имеется ли цикличность в задаче. Возможно, заданы операции, выполнение которых обусловлено удовлетворением разных условий. Выпишите все известные данные и искомые величины.

    Как решать задачи с алгоритмом

    Любой алгоритм требует формализованной записи. Если вам требуется составить блок-схему алгоритма, используйте специальные элементы для обозначения каждой операции создаваемой инструкции. Какправило, это блоки из прямоугольных и ромбическихфигур, соединенные в общеедерево.

    Составьте общий алгоритмрешения задачи. На первом шаге введите в алгоритм переменные величины, обозначающие известные данные и результирующие значения. Присвойте переменным известные из условия задачизначения.Детализируйте алгоритм. Подробно распишите условиезадачи. Каждый шаг инструкции должен быть записан на отдельной строке. При необходимости задайте циклы или разветвления алгоритма.Все действия в шагах инструкции производите с заданнымипеременными. Если необходимо ввести вспомогательные переменные, включите их дополнительно в самом начале алгоритма.Часто из смысла исходной задачив процессе решения вытекают условия, при удовлетворении которых над данными проводится одно действие, а без удовлетворения – другое. В этом случае речь идет о разветвлении алгоритма. Оформите его двумя ветками дерева-инструкции.Если при разветвлении алгоритма после прохождения условия одну из веток необходимо вернутьназад по телу алгоритма, тообразуется циклический алгоритм. Четко проследите, чтобы цикл внутри инструкции не был бесконечен и имел конечное число итераций.Любая последовательность выполняемых действий должна привести к конечному результату, заданному в условии задачи. После получения искомой величины, завершите тело алгоритма и запишите полученный ответ.

    Мастер Йода рекомендует:  6 книг по Java для программистов любого уровня
    Добавить комментарий