Краткое содержание: Параграф § 7 / Информатика 11 класс

Основы программирования и языка Pascal

Изучение программирования начинается с понимания того, что компьютерная программа — это последовательность символов из определенного алфавита. Современные подходы к разработке включают визуальное программирование, использующее элементы интерфейса (окна, иконки) для построения программы. Однако, всегда сохраняется основная, алгоритмическая структура, реализованная на каком-либо языке программирования.

В школьном курсе информатики традиционно используются алгоритмический язык КуМир и язык Pascal. В данном материале продолжается работа именно с Pascal.

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

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

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

Для проверки свойств алгоритма и контроля его соответствия решаемой задаче используются трассировочные таблицы (или таблицы значений). Они фиксируют пошаговое выполнение программы и наглядно показывают изменения значений переменных. Используются два вида таблиц:

• Таблицы, где каждая строка отражает результат одного действия.
• Таблицы, где каждая строка отражает результат выполнения группы действий (до контрольной точки).

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

Пример 5 демонстрирует трассировку вложенных циклов. Переменная \( \text{s} \) накапливает сумму \( \text{s} := \text{s} + \text{i} + \text{j} \). Внешний цикл \( \text{i} \) выполняется 3 раза (от 1 до 3), а внутренний цикл \( \text{j} \) выполняется 3 раза для каждого \( \text{i} \) (от 3 до 1). В результате выполнения программы \( \text{s} \) примет значение \( 24 \).

Пример 6 показывает алгоритм преобразования десятичного натурального числа \( \text{n} \) в его двоичное представление в виде строки \( \text{nd} \). Преобразование выполняется в цикле \( \text{while } \text{n} > 0 \text{ do} \dots \): остаток от деления \( \text{n} \text{ mod } 2 \) (0 или 1) добавляется в начало строки \( \text{nd} \), а само число \( \text{n} \) делится нацело на 2 (\( \text{n} := \text{n} \text{ div } 2 \)).

Пример 7 демонстрирует пошаговый анализ цикла \( \text{while } \text{s} < 2992 \text{ do} \dots \) без построения полной трассировочной таблицы, используя аналитический подход. Начальное значение \( \text{s} = 400 \). На каждом шаге к \( \text{s} \) прибавляется \( 12 \) (\( \text{s} := \text{s} + 12 \)), а счетчик \( \text{n} \) увеличивается на \( 2 \) (\( \text{n} := \text{n} + 2 \)). Условие выхода из цикла — \( \text{s} \ge 2992 \). Количество выполнений цикла \(k\) можно найти из уравнения \( \text{s}_{\text{нач}} + 12 \cdot k = 2992 \), где \( k = \frac{2992 - 400}{12} = 216 \). Итоговое значение \( \text{n} \) будет \( 0 + 2 \cdot k = 2 \cdot 216 = 432 \).

Пример 8 анализирует программу, которая по введенному числу \( \text{x} \) выводит два числа: \( \text{m} \) и \( \text{n} \). Переменная \( \text{m} \) (\( \text{m} := \text{m} + 1 \)) подсчитывает количество «отсеченных» цифр числа \( \text{x} \), то есть количество цифр в числе. Переменная \( \text{n} \) (\( \text{n} := \text{n} \cdot (\text{x} \text{ mod } 10) \)) накапливает произведение цифр числа \( \text{x} \). Выход из цикла происходит, когда \( \text{x} \) становится \( \le 0 \). Задача состоит в том, чтобы найти пятизначное число \( \text{x} \), произведение цифр которого равно \( 25 \), при условии, что программа вывела \( \text{m}=5 \) и \( \text{n}=25 \). Разложение числа 25 на 5 цифр: \( 25 = 5 \cdot 5 \cdot 1 \cdot 1 \cdot 1 \). Наименьшее число: \( 11155 \), наибольшее: \( 55111 \). Формула для подсчета количества таких чисел — формула перестановок с повторениями: \( \text{P}_{\text{n}}^{\text{k}_1, \text{k}_2, \dots, \text{k}_{\text{m}}} = \frac{\text{n}!}{\text{k}_1!\text{k}_2!\dots\text{k}_{\text{m}}!} \). Для \( 5 \) цифр, где \( 5 \) повторяется \( 2 \) раза и \( 1 \) повторяется \( 3 \) раза, общее количество чисел равно \( \frac{5!}{2!3!} = \frac{120}{2 \cdot 6} = 10 \).