Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 778156.01.99
В учебном пособии подробно рассмотрены все этапы решения задач по основам программирования, приведены рекомендации по выполнению и варианты практических заданий. Предназначено для студентов I курса ФПМИ направлений 01.03.02 - Прикладная математика и информатика; 02.03.03 - Математическое обеспечение и администрирование информационных систем.
Тракимус, Ю. В. Основы программирования : учебное пособие / Ю. В. Тракимус, В. П. Хиценко. - Новосибирск : Изд-во НГТУ, 2020. - 66 с. - ISBN 978-5-7782-4089-6. - Текст : электронный. - URL: https://znanium.com/catalog/product/1866908 (дата обращения: 23.07.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Министерство науки и высшего образования Российской Федерации 

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

 
 
 
 
 
 
 
Ю.В. ТРАКИМУС, В.П. ХИЦЕНКО 
 
 
 
 
 
ОСНОВЫ 
ПРОГРАММИРОВАНИЯ 
 
Утверждено Редакционно-издательским советом университета  
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2020 

 

УДК 004.42(075.8) 
        Т 652 
 
 
 
 
Рецензенты: 
д-р техн. наук, профессор кафедры ПМт М.Э. Рояк 
канд. техн. наук, доцент кафедры ТПИ И.Л. Еланцева 
 
 
 
Работа подготовлена на кафедре прикладной математики НГТУ 
 
 
 
Тракимус Ю.В. 
Т 652   
Основы программирования: учебное пособие / Ю.В. Тракимус, В.П. Хиценко. – Новосибирск: Изд-во НГТУ, 2020. – 66 с. 
 
ISBN 978-5-7782-4089-6 
 
В учебном пособии подробно рассмотрены все этапы решения задач по основам программирования, приведены рекомендации по выполнению и варианты практических заданий. Предназначено для студентов I курса ФПМИ направлений 01.03.02 – Прикладная математика 
и информатика; 02.03.03 – Математическое обеспечение и администрирование информационных систем. 
 
 
 
УДК 004.42(075.8) 
 
 
 
 
 
ISBN 978-5-7782-4089-6  
 
 
 
 
 
© Тракимус Ю.В., Хиценко В.П., 2020 
© Новосибирский государственный  
 
 
 
 
 
 
 
 
 
 
 
 
 
    технический университет, 2020 

 

ОГЛАВЛЕНИЕ 

 
 

Основные этапы компьютерного решения задач ............................................ 5 
   Понятие алгоритма ............................................................................................... 5 
   Этапы компьютерного решения задачи .............................................................. 7 
   Алгоритм решения задачи .................................................................................. 14 

Рекомендации по выполнению ПЗ ................................................................... 17 
   Требования к выполнению ПЗ ........................................................................... 17 
   Формализация и анализ задачи .......................................................................... 18 
   Структуры данных .............................................................................................. 21 
   Описание алгоритма ........................................................................................... 22 
   Разработка и структура программы .................................................................. 24 
   Отладка программы ............................................................................................ 25 

Оформление отчета и защита ПЗ ...................................................................... 26 

Варианты для ПЗ ................................................................................................. 28 
   Геометрия ............................................................................................................ 28 
   Матрицы и векторы ............................................................................................ 32 

Об отступах в текстах программ ....................................................................... 35 

Рекомендации по программированию ............................................................. 37 
   Принципы машинной обработки данных ......................................................... 38 
   Введение в программирование на С .................................................................. 39 
   Структурная разработка программ .................................................................... 42 
   Управление программой .................................................................................... 45 

Функции ............................................................................................................... 47 
   Массивы ............................................................................................................... 52 
   Указатели ............................................................................................................. 54 
   Символы и строки ............................................................................................... 57 
   Форматированный ввод/вывод .......................................................................... 58 
   Структуры, объединения, операции с битами и перечисления ...................... 60 
   Работа с файлами ................................................................................................ 62 

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

 

ОСНОВНЫЕ ЭТАПЫ КОМПЬЮТЕРНОГО  
РЕШЕНИЯ ЗАДАЧ 

Понятие алгоритма 

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

позволяющий также использовать понятия и действия, свойственные 
предметной области задачи. Такими несущественными деталями, могут 
быть описания переменных, системно зависимый код (ввод-вывод значений и подпрограммы). Главная цель использования псевдоязыка – 
сделать описание алгоритма более воспринимаемым человеком, чем 
текст на языке программирования. Псевдоязык удобно использовать 
на начальных стадиях обучения программированию. Описание алгоритма можно делать с разной степенью детализации в зависимости от 
своего профессионального опыта, практических навыков, новизны задачи. Если задача является новой, то алгоритм описывается, как правило, в несколько этапов: сначала крупно с целью уяснения основных 
действий, а затем более детально, пока они не окажутся выраженными 
в терминах действий, понятных исполнителю алгоритма (т. е. когда отвечаем на вопрос, как это реализовать на языке исполнителя алгоритма). В нашем случае в терминах действий языка программирования 
высокого уровня. 
– Ввод. Алгоритм имеет некоторое число (иногда возможно равное нулю) входных данных, т. е. величин, значения которых должны 
быть известны к моменту решения задачи. Значения этих величин являются результатами каких-то измерений, исследований, опросов 
специалистами предметной области задачи. В алгоритме входные 
данные задаются как результат действия, которое называется чтение 
значений из внешней среды компьютера, т. е. с внешних устройств 
компьютера. 
– Вывод. У алгоритма должны быть выходные данные, т. е. величины, значения которых вычисляются в процессе решения задачи и могут быть интерпретированы как результаты решения специалистами задачи из предметной области. Выходные данные имеют вполне определенную связь с входными данными. Поставленная задача не всегда может быть решена, но и в этом случае алгоритм должен иметь выходные 
данные, которые своим значением сообщают об этом. 
– Эффективность. Определяет качество алгоритма. Алгоритм считается эффективным, если он удовлетворяет критериям эффективности. 
Одним из них является время, необходимое для его выполнения; другим 
важным критерием является объем оперативной памяти (ОП), используемой в процессе компьютерного решения. Критериями качества 
также могут быть читабельность алгоритма, наглядность, надежность, 

массовость, адаптируемость к различным изменениям (например, к различным компьютерам). Часто одну и ту же задачу можно решить с помощью нескольких алгоритмов и нужно выбирать наилучший из них в 
соответствии с выбранным критерием эффективности. Оценка эффективности алгоритма требует исследования (анализа) алгоритма с целью 
получения его количественных характеристик, таких как время выполнения, объем оперативной памяти, и позволяет получить важную характеристику алгоритма – оценку его сложности. 
Алгоритм может быть использован для определения целого ряда математических понятий главным образом для того, чтобы определить новое действие (операцию) через ранее известные действия. Это позволяет 
расширить набор операций исполнителя, вводя в употребление более 
крупные и свойственные предметной области действия. Это свойство 
алгоритма на языке программирования реализуется механизмом подпрограмм и позволяет осуществлять декомпозицию задачи. 

Этапы компьютерного решения задачи 

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

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

– Что будет результатом решения? 
Ответ на этот вопрос состоит в определении выходных данных задачи: выходные данные задаются перечислением имен переменных, 
значения которых надо вычислить как результат задачи, а также описанием их свойств. Главные свойства: структура значения величины (простая или сложная), множество значений величины. 

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

– Как решать задачу? 
Поиск решения базируется на установлении закономерностей, взаимосвязей и соотношений между входными данными и результатами задачи в соответствии с предметной областью задачи. Решение описывается в виде действий, которые должен выполнить исполнитель для получения результатов решения. Действия описываются в математической форме с учетом возможностей и особенностей их реализации исполнителем, каковыми являются язык программирования и ЭВМ. 
Рассмотрим этап анализа задачи на следующих примерах. 
1. Пример задачи из класса линейных вычислительных процессов. 
Вычислить сумму цифр натурального трехзначного числа. 
Входные данные: x  N. 
Выходные данные: s  N. 
Решение: s =  / 1 00   % 1 00 / 1 0
 % 1 0
x
x
x


. 

Комментарии к анализу задачи. Заданное число обозначили 
именем x и определили его свойства (множество значений) – натуральное число. Можно было определить свойства числа диапазоном: 
100   x  999. 
Результат решения обозначили именем s и определили его свойства – натуральное число. 
Решение задачи заключается в выделении из значения числа x значений его отдельных разрядов. Для этого воспользуемся операцией деления целого числа x на основе системы счисления с учетом веса разряда числа. Для получения разряда сотен x / 100  и разряда десятков получаем  % 100 /10
x
  и разряда единиц  % 1 0
x
. 
2. Пример задачи из класса разветвляющихся вычислительных процессов. Даны четыре произвольных числа. Найти наибольшее (наименьшее) значение среди них. 
Входные данные: a, b, c, d  R. 
Выходные данные: x  R 

Решение: 

если 

a
b

a
c

a
d















, то x = a; 

если 

b
a

b
c

b
d















, то x = b; 

если 

c
a

c
b

c
d















, то x = c; 

если 

d
a

d
b

d
c















, то x = d. 

3. Пример задачи из класса циклических вычислительных процессов. Дана последовательность из n вещественных чисел (n заранее неизвестно). Найти наибольшее значение среди них. 
Входные данные: n  N, A = {ai |ai  R, i = 1, n}. 
Выходные данные: x  R. 
Решение: 
ПРИ x = 1-й элемент A, y = 2-й элемент A, i = 2 
ПОВТОРЯТЬ 
| если x < y, то x = y 
| y = следующий элемент A 
| i = i + 1 
ПОКА i  n 

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

Результат решения обозначили именем x и определили его свойства – вещественное число. 
Данные задачи могут быть как простой, так и сложной природы – 
последовательности. Решение задачи должно базироваться на возможности представления этих данных в памяти компьютера. Когда в задаче 
размер данных (т. е. количество элементов в последовательности) неизвестен, возможен только один способ их представления (отображения, 
хранения) в ОП компьютера – частями. На данном примере рассматривается представление данных частями минимально необходимого для 
решения задачи размера, их называют единица обработки. Единица обработки может состоять из одного или нескольких элементов последовательности в соответствии с условием задачи. 
Так как размер последовательности в данной задаче заранее неизвестен, а фактическое количество элементов последовательности является 
входной величиной, то будем отображать последовательность в ОП 
компьютера частями. В данной задаче единица обработки – это один 
(текущий) элемент последовательности. 
Решение задачи заключается в поиске среди элементов A элемента с 
наибольшим значением. Поиск осуществляется путем перебора элементов последовательности A. Поэтому в ОП достаточно хранить один (текущий) элемент A. При этом предположим, что первый элемент имеет 
наибольшее значение (x = 1-й элемент A), затем, перебирая элементы, 
начиная со второго и до последнего включительно, сравниваем очередной элемент (y) с наибольшим из уже рассмотренных (x). Изменяем значение x, если очередной элемент имеет значение большее x. Для ограничения перебора ведем подсчет количества рассмотренных элементов. 
Заканчиваем перебор, когда количество рассмотренных элементов 
равно размеру последовательности n. 
Для описания перебора на шаге анализа задачи используем схему, 
которая позволяет описать многократно повторяющийся процесс. 
Схема состоит из трех ключевых элементов: ПРИ,  ПОВТОРЯТЬ,  
ПОКА. После ключевого слова ПРИ записываем действия, позволяющие задать значения, с которых должен начаться перебор (начальные 
значения). После ключевого слова ПОВТОРЯТЬ записываем действия, 
многократное повторение которых позволяет вычислить результат. После ключевого слова ПОКА записываем условие продолжения повторения действий. Сами действия записываются, как правило, в виде рекуррентного соотношения (новое значение величины определяется как 

функция от предыдущего их значения). Рекуррентное соотношение позволяет записать действие в наиболее общей форме (обобщенная форма 
записи многократно повторяемого действия). 
4. Пример задачи из класса обработки сложных данных. Дана последовательность из n вещественных чисел, n не превышает 50. Преобразовать последовательность по следующему правилу: циклически сдвинуть 
ее элементы на k позиций вправо. 
 
Входные данные: n  N, n  50, k  N, k < 50, A = {ai |ai  R, i = 1, n} 
Выходные данные: A = {ai |ai  R, i = 1, n}. 

Решение: 
Начальная спецификация решения задачи: 
ПРИ n = 1 
ПОВТОРЯТЬ 
| y = an 
| сдвиг элементов A на одну позицию вправо (к концу последо- 
        вательности A) 
| an = y 
| n = n + 1 
ПОКА n   k 
 
Более детальное описание решения задачи: 
ПРИ n =1 
ПОВТОРЯТЬ 
| ПРИ i = n, y = ai 
| ПОВТОРЯТЬ 
| | ai = ai-1 
| | i = i – 1 
| Пока i > 1 
| ai = y 
| n = n + 1 
ПОКА n  k 

Комментарии к анализу задачи. Входными данными являются три 
величины: простая n – количество элементов последовательности, простая k – величина сдвига и сложная A – последовательность вещественных чисел. Свойства величин: n и k – натуральные числа, n ограничено 
сверху значением 50; A – последовательность, состоящая из элементов ai, 

где ai есть вещественное число, фактическое количество элементов последовательности не превышает n. 
Результатом решения будет эта же последовательность A с измененными значениями элементов в результате сдвига. 
Так как размер последовательности заранее известен (50), то будем 
отображать в ОП компьютера все элементы последовательности. Поскольку элементы в последовательности однородны, в программной реализации решения будем использовать тип массив, для обращения к элементу будем использовать индекс элемента. Представление значения 
сложной величины в ОП позволяет описывать решение задачи в самом 
общем виде и этим самым выполнить простейшую декомпозицию решения – разбить решение на три части: получение входных данных, собственно решение, выдача результатов. Декомпозиция решения – важный элемент проектирования. Она предоставляет пользователю обдумывать каждую часть решения независимо от других. 
Возможно несколько способов решения данной задачи. Один из них 
основан на использовании дополнительной памяти размером не менее 50, другой – на минимальном использовании дополнительной памяти: для хранения одного элемента. В первом варианте решения поместим в дополнительную память последние k элементов последовательности. Первые n – k элементов A сместим на k позиций вправо (к концу 
последовательности). Отложенные в дополнительную память k элементов перенесем в первые k позиций A. Во втором варианте решение задачи заключается в смещении (сдвиге) элементов A вправо на одну позицию. Для циклического сдвига, используя дополнительную память, 
последний элемент помещаем в первую позицию. Повторив это смещение k раз, выполним циклический сдвиг элементов A на k позиций 
вправо. В приведенном решении реализован второй вариант. 
5. Пример задачи из класса обработки сложных данных. Дана последовательность, содержащая не более 50 слов, в каждом слове не более 
10 строчных латинских букв; между соседними словами пробел, за последним словом точка. Среди слов, отличных от последнего, найти 
слова, длина которых максимальна. 
Входные данные: A = {ai |ai  WORD, i = 1, n, n  50}, 
WORD = {wj | wj  {‘a’, ’b’, ‘c’…’x’, ’y’, ’z’}, j = 1, m, m  10}. 
Выходные данные: B = {bi |bi  WORD, i = 1, k}, –1 < k < 50. 

Решение: 
ПРИ i = 1, k = 0, n = |A|, max = 0