Как вы знаете, невозможно создать вечный двигатель, потому что это противоречит универсальным физическим законам сохранения. Точно так же в математике и информатике существуют задачи, для которых решение в общем виде отсутствует.
Поскольку алгоритм работает только с дискретными объектами, любая алгоритмическая задача — это функция, заданная на множестве дискретных объектов (входных слов).
Пусть, например, требуется по шахматной позиции определить, кто выигрывает при правильной игре — белые, чёрные или будет ничья. Построим функцию, соответствующую этому алгоритму. Для этого выберем способ кодирования, при котором каждая позиция может быть закодирована словом (символьной строкой) v в подходящем алфавите. Тогда приведённой задаче может соответствовать функция f(v), заданная на множестве таких слов:
Если функция, соответствующая задаче, вычислима, то задача называется алгоритмически разрешимой — для её вычисления можно построить алгоритм. Если определённая в задаче функция невычислима, то алгоритма для её решения не существует.
ЧТО ДЕЛАТЬ ЕСЛИ НЕ ПОНИМАЕШЬ ПРОГРАММИРОВАНИЕ | КАК ВЫУЧИТЬ ПРОГРАММИРОВАНИЕ
Алгоритмически неразрешимая задача — это задача, соответствующая невычислимой функции.
В 1900 г. на Международном математическом конгрессе в Париже известный математик Давид Гильберт сформулировал 23 нерешённые математические проблемы 1 .
1 Сейчас большинство из них решено полностью или частично.
В знаменитой «десятой проблеме Гильберта» требуется найти метод, который позволяет определить, имеет ли заданное алгебраическое уравнение с целыми коэффициентами решение в целых числах. Например, уравнение
имеет два целочисленных решения, (5; -3) и (-5; -3). Сложность состояла в том, что требовалось найти единый метод (алгоритм), позволяющий решить задачу для любого такого уравнения со многими неизвестными.
В начале XX века была уверенность, что такой алгоритм есть, и поэтому его упорно искали. Однако в 1970 г. советскому математику Ю. В. Матиясевичу удалось доказать, что общего алгоритма решения этой задачи не существует.
Немецкий математик Г. В. Лейбниц в XVII веке безуспешно пытался найти метод проверки правильности любых математических утверждений. Как вы знаете, почти все математические теории основаны на использовании аксиом (положений, принимаемых без доказательства), из которых выводятся все остальные утверждения (теоремы). Задача заключалась в том, чтобы разработать алгоритм, позволяющий установить, можно ли вывести формулу Б из формулы А в рамках заданной системы аксиом («проблема распознавания выводимости»).
В 1936 г. американский математик А. Чёрч доказал, что эта задача в общем виде алгоритмически неразрешима, поэтому нельзя сформулировать универсальный алгоритм, пригодный для доказательства любой теоремы 2 .
БЕЗ АЛГОРИТМОВ – ТЫ НЕ ПРОГРАММИСТ
2 Тем не менее отдельные классы теорем можно доказывать на компьютере.
Таким образом, уточнённые определения алгоритма, основанные на понятии универсальных исполнителей, сыграли в науке очень важную роль — позволили получить отрицательные результаты, т. е. доказать, что алгоритмов решения некоторых задач в общем виде не существует.
Для того чтобы доказать неразрешимость какой-то новой задачи, пытаются свести её к уже известным алгоритмически неразрешимым задачам. Если это удаётся, значит, и новая задача алгоритмически неразрешима 3 .
3 Допустим, что (1) задача А неразрешима и (2) если мы можем построить алгоритм для решения задачи Б, то с его помощью можно построить алгоритм решения задачи А. Тогда задача Б тоже неразрешима.
Существуют также задачи, про которые неизвестно, алгоритмически разрешимы они или нет — решение не найдено, но алгоритмическая неразрешимость не доказана.
Алгоритмически неразрешимые задачи встречаются не только в математике, но и в информатике, например при разработке программ. Оказывается, невозможно написать программу для машины Тьюринга (алгоритм), которая по тексту любой программы Р и её входным данным X определяет, завершается ли программа Р при входе X за конечное число шагов или зацикливается.
Это так называемая проблема останова. Её неразрешимость означает, в частности, что нельзя полностью автоматизировать тестирование любых программ, поручив это компьютеру. Однако для некоторых классов алгоритмов проблему останова решить можно. Например, линейная программа, не содержащая ветвлений и циклов, всегда завершится.
Было доказано, что алгоритмически неразрешима проблема эквивалентности: по двум заданным алгоритмам определить, будут ли они выдавать одинаковые результаты для любых допустимых исходных данных. Следовательно, невозможно полностью автоматизировать решение многих важных задач, связанных с разработкой программ, например:
• по заданному тексту программы определить, что она «делает»;
• определить, правильно ли работает программа при любых допустимых исходных данных;
• найти ошибку в программе, работающей неправильно. Поэтому при отладке программы большую роль играет интуиция. Помогают (но не решают проблему полностью!) стандартные приёмы, позволяющие найти ошибку:
• сравнение результатов работы программы с результатами ручного счёта;
• эксперименты с программой при различных исходных данных для того, чтобы выявить закономерность появления ошибок;
• временное отключение (комментирование) частей программы и др.
Поскольку многие этапы разработки программного обеспечения в принципе невозможно представить в виде алгоритмов, программирование остаётся работой человека. Полностью поручить его компьютеру не удаётся, хотя решение некоторых задач всё же можно автоматизировать.
Следующая страница Вопросы и задания
Cкачать материалы урока
Источник: xn—-7sbbfb7a7aej.xn--p1ai
Можно написать программу которая не будет алгоритмом да или нет
Списки часто используются для программирования различных викторин. Сделаем компьютерную игру «Да или нет?» В которой Скретч случайным образом будет называть предмет и спрашивать, съедобный ли он? Добавим к проекту подсчет баллов и времени игры с помощью переменных.
Для проекта нам понадобятся 2 списка: съедобное, несъедобное и 5 переменных: баллы, номер, список, начало и время.
- Создайте новый проект.
- Создайте два глобальных списки: съедобное, несъедобное (рис.12.15).
баллы — для подсчета количества правильных ответов;
список — для случайного выбора в каждом туре игры одного из списков — 1 (съедобное) или 2 (несъедобное);
номер — для случайного выбора в каждом туре одного из трех номеров элементов списка;
начало — для сохранения стартового значения таймера;
время — для сохранения продолжительности игры.
4. Соберите скрипт игры по образцу (рис.12.16)
Рис. 12.16. Скрипт игры «Да — Нет»
5. Проверьте работу скрипта.
6. Сохраните проект в файле да_нет.
Задание 1
Как можно сделать проект интереснее? Давайте улучшим игру, добавив в нее журнал ответов игрока в виде списка — игра . Наша программа должна записывать в журнал заданный вопрос и полученный от игрока ответ. По итогам игры список можно сохранить в текстовом файле, что мы уже умеем делать.
Создайте глобальный список игра . Блоки добавления элементов в список игра нужно установить в определенные места скрипта. Самостоятельно решите, где именно они (рис.12.17.) должны находиться, чтобы правильно записывать ответы игрока?
Рис. 12.17. Блоки записи вопросов и ответов игрока в список игра
В список игра можно также записать продолжительность игры и полученные баллы. Для этого достаточно в нужное место скрипта вставить два блока (рис.12.18). Самостоятельно решите, где именно они должны находиться.
Рис. 12.18. Блоки записи продолжительности игры и баллов в список игра
При желании можно также записать имя игрока. Для этого, как не трудно догадаться, нужно поставить вопрос об имени в начале игры, до старта подсчета времени игры, и сохранить полученный ответ в списке игра (рис.12.19).
Рис. 12.19. Сохранения имени игрока в списке игра
Сохраните проект да_нет _2 с внесенными изменениями.
Задание 2
Как можно сделать проект еще интереснее?
Во-первых, можно добавить количество съедобных и несъедобных объектов. Вы это можете сделать самостоятельно.
Во-вторых, нашей игре не хватает зрелищности. Было бы интересно не только называть объекты, но и показывать их изображения. Однако списки не могут сохранять образы. Эту проблему легко решить, создав еще один спрайт, список костюмов которого будет состоять из образов съедобных и несъедобных объектов.
Этот спрайт, получив сообщение образ , должен показать костюм, который соответствует предмету. В наших списках содержатся объекты, образы которых можно найти в папке Things , при желании их можно нарисовать самостоятельно.
- Создайте новый спрайт образы.
- Сделайте для спрайта список костюмов в той же последовательности, которая изображена на рисунке (рис.12.20.), с 1 по 3 — съедобные, с 4 по 6 — несъедобные.
Задание 3
Можно ли сделать игру еще интереснее? Создавая проект, мы не обращали внимания на сцену, звуки и графические эффекты. Попробуйте внести собственные изменения в проект и сохраните его ремикс под другим именем.
Источник: www.sites.google.com
Используем условия для создания квеста с ветвлением
Программы, которые мы научились писать в прошлом уроке всегда работают линейно — выполняются одни и те же команды вне зависимости от того, что вводит пользователь. Но иногда возникает необходимость добавить программе вариантивности. Например, если на часах день — использовать светлую тему, а если ночь — темную. Для этого нам пригодится условный оператор.
По сути условный оператор — это команда ЕСЛИ. Если условие верно, выполняется одная часть кода, иначе — другая.
По английски ЕСЛИ — это if, поэтому условный оператор обозначается ключевым словом if . Записывается условный оператор следующим образом:
любой код до условного оператора if условие: код в случае правильности условия код в случае правильности условия код в случае правильности условия else: код в случае неправильности условия код в случае неправильности условия код в случае неправильности условия любой код после условного оператора
Для определения уровня вложенности, т.е. определения какой код относится к условному оператору, а какой нет, в питоне используются отступы.
Если отступы стоят неправильно, программа работать не будет.
а) Код внутри веток ДА и НЕТ условного оператора отделен пробелами или символами табуляции от остального кода.
б) Если условный оператор вложен в другой условный оператор, размер отступа увеличивается.
в) В одном блоке отступы должны быть одинаковыми и содержать либо только пробелы, либо только табуляцию.
Если ветка «Нет» пуста, else можно не писать. Если сомневаешься, что использовать, табы или пробелы, просто всегда ставь 4 пробела (или не мешай IDLE делать это за тебя ).
Пример из урока про алгоритмы будет записан следующим образом:
time = int(input(«Который час? «)) if time > 12: print(«Добрый день!») else: print(«Доброе утро!»)
Условия в условном операторе
В условном операторе нам доступны все стандартные для математики операции сравнения переменных:
a > b # a больше b a >= b # больше либо равно a < b # меньше a
Также можно использовать логические операции and , or и not .
- Операция and соединяет два цельных условия, и верна тогда, когда оба эти условия верны.
- Операция or также соединяет два цельных условия, но верна тогда, когда верно хотя бы одно из двух условий.
print(«Добро пожаловать!») temperature = int(input(‘Сколько там градусов? ‘)) is_raining = input(‘Идет дождь (да/нет)? ‘) if is_raining == «нет» and temperature >= 20: print(«Иди гуляй, че как сыч сидишь!») else: print(«Можно и дома посидеть. «)
Если арифметические операции применяются к числам, то логические — к высказываниям, утверждениям, которые могут быть истинными или ложными (например, «на часах больше 13 часов»). Если попробовать написать вот так.
temperature = int(input()) if temperature > 15 and < 23: print(«Температура комфортная»)
. то работать ничего не будет. Логический оператор and тут разделяет temperature > 15 и < 23 . А < 23 — это не высказывание!
temperature = int(input()) if temperature > 15 and temperature < 23: print(«Температура комфортная»)
Кстати, в примере выше программа даже не запустилась, сообщив, что в коде синтаксическая ошибка. До этого мы уже успели встретиться с ошибкой времени выполнения (когда пытались прибавить число к строке). По аналогии с уроками русского языка, синтаксическая ошибка — это когда написано не правильно («карова доет малако»), а ошибка времени выполнения — когда невозможно сделать то, что ты просишь (пингвин лети. ). Обычно синтаксические ошибки поймать и исправить куда проще, т.к. IDLE сразу подчеркнет место, в котором что-то написано не так.
Вложенные условия
А что делать, если мы заходим добавить еще один вариант — если жарко, предложить погулять под дождем? На самом деле никто не запрещает нам писать условный оператор внутри другого условного оператора.
print(«Добро пожаловать!») temperature = int(input(‘Сколько там градусов? ‘)) is_raining = input(‘Идет дождь (да/нет)? ‘) if is_raining == «нет» and temperature >= 20: print(«Иди гуляй, че как сыч сидишь!») else: print(«Можно и дома посидеть. «) if is_raining == «нет» or temperature >= 23: print(«Ну вообще и прогуляться можно. «) else: print(«Го в КС, я создал!»)
Главное не забыть, что для каждого вложенного условного оператора нужно увеличивать отступ, чтобы питон не запутался. Если в первом условном операторе мы сделали отступ в 4 пробела (IDLE нам в этом помог), то во вложенном отступ будет уже 8 (и IDLE снова поможет). Если добавить еще один — отступ будет уже 12. Но лучше не увлекаться, иначе код станет нечитаемым и ты сам в нем скоро запутаешься.
Что делать? Можно уменьшить вложенность кода (один if у нас включен в блок else), используя оператор elif — сокращение от else и if (если. иначе если. иначе. ).
print(«Добро пожаловать!») temperature = int(input(‘Сколько там градусов? ‘)) is_raining = input(‘Идет дождь (да/нет)? ‘) if is_raining == «нет» and temperature >= 20: print(«Иди гуляй, че как сыч сидишь!») elif is_raining == «нет» or temperature >= 23: print(«Ну вообще и прогуляться можно. «) else: print(«Го в КС, я создал!»)
Если elif много, питон будет по очереди проверять все варианты в условном сверху вниз (ты же уже понял, что программы всегда работают сверху вниз?), пока не найдет подходящий. Если не найдет — выполнит else .
Как и с арифметическими операциями, явно нужно попрактиковаться!
Дано целое число n. Выведите следующее за ним четное число.
Как должно работать:
| 6 | 5 |
| 124 | 122 |
После очередного успеха на олимпиаде Никита и Кирилл решили открыть собственный бизнес. Бизнес не простой, а золотой — продажа яблок сорта Golden.
Миллионер Семён решил порадовать любимую мамочку — купить ей вкусных яблок. Он пришёл на импровизированный рынок НиК, где работали Никита и Кирилл. Семён решил купить все яблоки, благо денег у него хватает.
Продав все яблоки, Никита и Кирилл стали считать прибыль. Известно, что Никита продал A яблок по M тугриков, а Кирилл продал B яблок по N тугриков. К сожалению, с математикой у ребят плохо, поэтому они хотят узнать у вас, кто же получил бОльшую прибыль.
Числа A,B,M,N вводятся пользователем.
Как должно работать:
| A: M: B: N: Никита заработал больше |
5 1000 6 500 |
| A: M: B: N: Кирилл заработал больше |
5 1000 10 8000 |
| A: M: B: N: Никита и Кирилл заработали поровну |
5 1000 10 500 |
Красная Шапочка часто навещает свою бабушку. Но она очень боится, что рано или поздно ее бабушку опять навестит волк. Поэтому она решила договориться с Лесничим об охране бабушки. Лесничий согласился охранять бабушку за 10 пирожков.
Узнав об этом, волк сказал Красной Шапочке, что ей совершенно незачем тратить пирожки на Лесничего. За половину тех пирожков, которые Красная Шапочка несет бабушке, Волк пообещал не трогать ее.
Мама испекла несколько пирожков, и попросила Красную Шапочку отнести их бабушке. Требуется определить, кому выгоднее платить пирожки за спокойствие бабушки.
| Кому платить: Лесничий |
50 |
| Кому платить: Волк |
5 |
| Кому платить: Волк |
19 |
| Кому платить: Лесничий |
20 |
Генерация случайных чисел
Предположим, мы хотим добавить в наш квест долю везения. Например, результат выстрела будет зависеть от подкидывания монетки или броска кубика. Для этого можно попросить компьютер сгенерировать случайное число и в зависимости от результат выдать пользователю тот или иной вариант развития событий.
Генерация случайных чисел доступна в модуле random (уже третий модуль, с которым мы сталкиваемся!), который нужно импортировать в начале программы.
Код:
import random points = random.randint(1, 100) print(«Очков на барабане: «, points) if points > 80: print(«А-а-а-автомобиль!») else: print(«Всего лишь банка с огурцами.»)
Результат:
Очков на барабане: 70 Всего лишь банка с огурцами.
Для тренировки можно написать программу, в которой пользователю предлагается с первого раза угадать число от 1 до 10. Если пользователь угадал, программа поздравляет его с выигрышем!
Пишем альфа-версию квеста!
Если ты решил задачи в этом уроке, то скорее всего уже более-менее уверенно обращаешься с условным оператором. А значит можно смело приступать к квесту с ветвлением!
Сейчас уже можно придумать полноценный и реализовать небольшую его часть. Кода должно хватать минимум на 30 секунд игры, попробуй добавить несколько сюжетных развилок и случайных событий (с рандомом!).
Источник: codingprojects.ru