Основные понятия программирования
Программирование — это раздел информатики, изучающий методы и приемы составления программ для компьютеров. Кроме того, программирование — это подготовка задачи к решению ее на компьютере.
Программа — это последовательность команд, понятных компьютеру.
Программа записывается в виде символов, к числу которых относятся латинские и русские буквы, цифры, знаки препинания и знаки операций.
Требования, предъявляемые к программе
1. Минимальные требования к компьютеру, на котором работает программа.
2. Ясность входных и выходных данных и простота программы.
3. Минимальное время создания программы и простота ее изменения.
4. Минимальное время работы программы, минимум занимаемой памяти и минимум использованных в программе операторов.
Чтобы программа удовлетворяла этим противоречивым требованиям, необходимо обладать искусством программирования.
Свойства программ — выполнимость, мобильность, правильность, эффективность.
Урок №6. Последовательность команд в Scratch
Выполнимость — возможность выполнения программы на данном типе компьютеров.
Мобильность — возможность переноса программы на другой тип компьютеров.
Правильность программы — правильность результатов, получаемых с помощью данной программы.
Эффективность — минимум времени выполнения, минимум машинной памяти и других ресурсов компьютера.
Языки программирования — языки для записи программ для компьютеров. Это совокупность средств и правил представления алгоритма в виде, приемлемом для компьютера.
Оператор — выражение обозначающее и описывающее какую-либо операцию.
Типы языков программирования: машинные, машинно-ориентированные, алгоритмические, логические, функциональные, учебные, инструментальные, диалоговые, графические и т.д.
Алгоритмический язык — это формальный язык, предназначенный для записи алгоритмов.
Системы программирования — это набор средств ввода, редактирования, трансляции и выполнения программ на ЭВМ.
Транслятор — это комплекс программ, обеспечивающий перевод программы, написанной на символическом языке, в совокупность машинных команд.
Компилятор — это транслятор, обеспечивающий перевод программы, написанной на алгоритмическом языке, в совокупность машинных команд без ее выполнения в компьютере.
Интерпретатор — это транслятор, обеспечивающий перевод каждой конструкции алгоритмического языка в машинные команды и одновременное выполнение этой конструкции в компьютере.
Все системы (языки) программирования имеют свой транслятор, компилятор и интерпретатор.
Виды языков программирования:
1. Машинно-ориентированные языки (языки ассемблера).
2. Языки высокого уровня.
3. Командные языки баз данных.
Примеры языков программирования высокого уровня: Фортран, Алгол, Бейсик (Basic), Паскаль (Pascal), Си++, Пролог, Лисп, Форт и др
Источник: www.examen.ru
Программы с обязательным этапом
Студия Компьютерного Мастерства
Задание 23. Умение анализировать результат исполнения алгоритма: все задания Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).
- Количество программ с обязательным этапом
- Количество программ с избегаемым этапом
- Количество программ с обязательным и избегаемым этапами
- Поиск количества программ по заданному числу
- Поиск количества чисел по заданному числу команд
- Задачи Поляков ЕГЭ
DEMO вариант:
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
- Прибавить 1
- Умножить на 2
РЕШЕНИЕ:
Проверим решение программой (Python)
Количество программ с обязательным этапом
Исполнитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
- Прибавить 1 (увеличивает число на экране на 1)
- Прибавить 2 (увеличивает его на 2)
- Умножить на 2 (умножает его на 2)
Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
РЕШЕНИЕ:
Искомое количество программ равно произведению количества программ, получающих из числа 3 число 10, на количество программ, получающих из числа 10 число 12.
Пусть R(n) — количество программ, которые число 3 преобразуют в число n, а P(n) — количество программ, которые число 10 преобразуют в число n.
Для всех n > 5 верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(n — 1) + R(n — 2), так как существует два способа получения n — прибавлением единицы или прибавлением двойки. Аналогично P(n) = P(n — 1) + P(n — 2)
2. Если n делится на 2, тогда R(n) = R(n — 1) + R(n — 2) + R(n / 2). Аналогично P(n) = P(n — 1) + P(n — 2) + P(n / 2)
Последовательно вычислим значения R(n):
R(5) = R(4) + R(3) = 1 + 1 = 2
R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4
R(7) = R(6) + R(5) = 4 + 2 = 6
R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11
R(9) = R(8) + R(7) = 11 + 6 = 17
R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30
Теперь вычислим значения P(n):
P(12) = P(11) + P(10) = 2
Таким образом, количество программ, удовлетворяющих условию задачи, равно 30 · 2 = 60.
Источник: css-info.ru
Алгоритм и программа
Как вам уже известно, компьютер — это программно-управляемая система для работы с информацией, и именно программное управление делает его столь универсальным. Тому, как составляются программы, посвящена эта часть курса информатики и информационных технологий. А начнем мы ее с двух базовых понятий: «алгоритм» и «программа».
Алгоритм1 — одно из фундаментальных понятий информатики. Этим словом обозначают точное и безотказное предписание последовательности действий, переводящей автоматическое устройство из исходного состояния в результирующее. Т.е. мы можем считать алгоритмом любую инструкцию, если:
ее команды не допускают различных вариантов исполнения;
указания предусмотрены для всех возможных вариантов развития событий.
С этой точки зрения можно составить, к примеру, алгоритм переливания из пустого в порожнее. Однако, на практике алгоритмы составляют для решения тех или иных задач, т.е. получения необходимых результатов по заданным исходным данным. Вид алгоритма, да и сама возможность его написания зависят от исполнителя (это может быть и человек, и автоматическое устройство), или точнее, от его системы команд (т.е. набора инструкций, которые он «умеет» выполнять). Поэтому, в дальнейшем мы будем пользоваться следующим определением.
Алгоритм решения задачи — это последовательность допустимых команд исполнителя, определяющих его действия по переходу от исходных данных к искомому результату.
Какими свойствами должен обладать алгоритм? Перечислим их:
дискретность2 — алгоритм делится на отдельные элементарные шаги;
определенность — каждая команда однозначно определяет действие исполнителя;
конечность(результативность) — алгоритм должен завершаться за конечное число шагов.
Кроме этого, алгоритм может обладать еще одним полезным (но не обязательным) свойством — массовостью. Это значит, что он будет годиться не для одной конкретной задачи, а для целого класса похожих задач.
С определенностью непосредственно связана существенная особенность, о которой нельзя забывать: исполнитель выполняет алгоритм формально3, абсолютно не задумываясь над смыслом производимых действий. Поэтому не стоит обижаться на компьютер, «не догадавшийся», что вы подразумевали, — он честно делает то, что вы написали.
Существует много разных способов записи алгоритмов: графические (например, в виде блок-схем), с помощью естественного языка, какими-нибудь условными знаками идр. Но если мы хотим, чтобы алгоритм был исполнен компьютером, он должен быть обязательно записан на особом языке. Такая запись называется программой4, а язык — языком программирования.
Вы знаете, что вся информация в компьютере представляется в виде двоичных кодов. В кодах, каждый из которых обозначал одно простейшее действие (вроде, «перенести число из одной ячейки памяти в другую»), приходилось писать и программы для первых ЭВМ. Но это занятие очень сложное и кропотливое, а кроме того, требующее глубокого знания особенностей конкретной машины.
Поэтому были придуманы языки программирования высокого уровня. Программа на таком языке — это последовательность команд, обозначаемых словами естественного языка или их сокращениями. Каждая из них соответствует последовательности из десятков, а то и сотен машинных команд. В результате запись получается гораздо более компактной и понятной.
Но процессор не понимает команд языков высокого уровня, поэтому их предварительно нужно «перевести». Для этого служат особые программы — трансляторы5.
Сейчас в мире существует множество языков программирования, рассчитанных на различные области применения. Мы в нашем курсе будем использовать Лого6 — язык, специально созданный для обучения основам программирования. Этот язык очень простой (кстати, в отличие от профессиональных языков программирования, он позволяет записывать команды на русском языке), но, в то же время, способствует формированию навыков, позволяющих затем, при желании, без особых проблем перейти к работе с такими популярными языками, как Си или Паскаль. Особо знаменит язык Лого своей «черепашьей графикой». О том, что это такое, мы и поговорим в следующей главе.
Algorithmi (лат.) — искаженное имя математика IX века аль-Хорезми, предложившего способ выполнения арифметических вычислений с многозначными числами.
Заметим, что подход к определению алгоритма как последовательности операций — не единственно возможный. Кроме такого — процедурного (императивного), возможен и функциональный подход, когда алгоритм рассматривается как система функций.
Discrete (англ.) — состоящий из отдельных частей
Formalis (лат.) — строго по установленным правилам
Programma (греч.) — распоряжение
Translator (англ.) — переводчик
Язык Лого (Logo, от греч. Logos — слово, мысль) разработан в 1972 г. Сеймуром Пейпертом (Массачусетский Технологический институт, США). «Прародителем» его был наиболее известный из языков функционального программирования — Лисп, однако, в процессе развития Лого приобрел ряд особенностей, позволяющих использовать при работе с ним как функциональный, так и процедурный подходы.
Источник: kazedu.com