В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ В. Ю. Наумов Введение в информатику. Основы программирования на языкеС++. Волгоград 2016 2 Р е ц е н з е н т ы : Издается по решению редакционно-издательского совета Волгоградского государственного технического университета Наумов, В. Ю. Введение в информатику. Основы программирования на языке С++/ В. Ю. Наумов; ВолгГТУ. – Волгоград, 2016. – 248 с. Содержит начальные сведения по дисциплинам «Информатика» и «Основы программирования», изучаемые в техническом вузе. В качестве основного языка программирования выбран С++. Ил. 116. Табл. 14. Библиогр.: 5 назв. © Волгоградский государственный технический университет, 2016. © В. Ю. Наумов, 2016 3 Оглавление ВВЕДЕНИЕ .......................................................................................................... 5 1. Базовые сведения об информатике, программах и ЭВМ ............................ 9 1.1. Общие сведения ........................................................................................ 9 1.2. Двоичная система исчисления .............................................................. 11 1.3. Понятие информации ............................................................................. 16 1.4. Программное обеспечение .................................................................... 20 1.5. Архитектура персональной ЭВМ ......................................................... 23 2. Методы решения задач. Алгоритмизация. Логика .................................... 28 2.1. Этапы решения задач на ЭВМ .............................................................. 28 2.2. Алгоритмизация ..................................................................................... 30 2.3. Понятие переменной и операции присваивания ................................. 34 2.4. Основы алгебры логики ......................................................................... 36 2.5. Правила использования логических выражений ................................ 41 2.6. Базовые алгоритмические конструкции .............................................. 42 3. Основные сведения о языке С++ ................................................................. 56 3.1. Алфавит языка. Идентификаторы ........................................................ 56 3.2. Структура программы на языке C++ .................................................... 58 3.3. Типы данных в С++ ................................................................................ 61 3.4. Переменные и операции над ними в С++ ............................................ 65 3.5. Простейший ввод/вывод ........................................................................ 72 3.6. Указатели и ссылки ................................................................................ 77 3.7. Строковый тип данных .......................................................................... 84 3.8. Программирование развилок ................................................................ 88 3.9. Программирование циклов ................................................................... 93 3.10. Составной оператор ............................................................................. 96 4. Одномерные массивы ................................................................................. 100 4.1. Понятие и объявление массива ........................................................... 100 4.2. Поэлементная прямая обработка одномерных массивов ................. 102 4 4.3. Элементы, удовлетворяющие некоторому условию ....................... 106 4.4. Обработка массивов по индексам ..................................................... 116 4.5. Алгоритмы с использованием вложенных циклов .......................... 128 4.6. Динамические массивы ...................................................................... 136 5. Двумерные массивы .................................................................................... 138 5.1. Понятие и объявление двумерного массива .................................... 138 5.2. Поэлементная обработка двумерных массивов ............................... 140 5.3. Обработка отдельных строк или столбцов матрицы ....................... 153 5.4. Квадратные матрицы .......................................................................... 161 5.5. Матрицы и динамическая память ...................................................... 170 6. ФУНКЦИИ ................................................................................................... 172 6.1. Иерархия. Черный ящик. Функция ................................................... 172 6.2. Функции в языке С++ ......................................................................... 176 6.3. Локальные и глобальные идентификаторы ...................................... 182 6.4. Параметры функций ........................................................................... 185 6.5. Примеры решения задач ..................................................................... 194 7. Файлы ........................................................................................................... 206 7.1. Основные определения и объявление файла ..................................... 206 7.2. Компонентные файлы ......................................................................... 210 7.3. Последовательный доступ к компонентам файла............................. 219 7.4. Произвольный доступ к компонентам файла ................................... 225 7.5. Файлы и функции ................................................................................ 231 7.6. Файлы и массивы ................................................................................ 236 7.7. Работа с файлами в С++ ..................................................................... 246 БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................... 248 5 ВВЕДЕНИЕ Конец XX века по праву называется эпохой информационных технологий. Благодаря прогрессу в области электронной техники общество совершило качественный скачок по кривой своего развития. За последние десятилетия персональный компьютер превратился из экзотики в достаточно заурядную вещь, встречающуюся дома практически у каждого. Более того, современные тенденции разработки техники таковы, что для управления ею все чаще применяют сложные конструкции, в основе работы которых лежит цифровое электронное устройство. Мобильные телефоны, плееры, часы и даже стиральные машины и в настоящее время находятся под управлением небольших встроенных вычислительных устройств. Микропроцессор управляет подачей топлива в двигатель автомобиля, антиблокировочной системой, распределяет нагрузку на электрические сети в электроэнергетике; выбирает режимы работы станка; иные большие и малые задачи возложены сегодня на электронику. Цифровые технологии настолько прочно вошли в нашу жизнь, что мы перестали задумываться над тем, какие принципы в них заложены. Этот факт, с одной стороны, может считаться положительным, поскольку позволяет не размышлять об устройстве инструмента, а сосредоточиться на творческом процессе, а с другой, весьма печален. Печаль вызвана тем, что любая техника априори несовершенна и потому имеет достаточно четкие границы своего применения. Незнание принципов, заложенных в основу ее работы, приводит к завышенным требованиям, необоснованным надеждам на простое решение, или просто – неэффективному использованию. В основе любого цифрового устройства лежат достаточно простые законы – законы машинной логики. Логика машины отчасти похожа на 6 логику человека, однако, есть масса отличий. Знание этих законов позволяет эффективно ставить задачу устройству-исполнителю и принимать результат в ожидаемой форме. Для постановки задачи нужно иметь представление об алгоритмах (последовательности действий), их свойствах. Правильно составленный алгоритм дает надежду на достаточно быстрое и эффективное решение задачи. В данном пособии рассмотрение задач на составление алгоритмов ведется на примере языка высокого уровня С++. Для этого языка существует огромное количество компиляторов и сред разработки, позволяющих запустить и проверить работоспособность составленной программы, наиболее популярной является интегрированная среда разработки от Microsoft – Visual Studio, но для выполнения простых программ обычно используют более простые программые продукты. Кроме того, С++ используется и для серьезных программных разработок. Изучение современных аспектов программирования: объекто- ориентированной разработки, использования классов, наследования, полиморфизма и т.д. невозможно без сформированного понимания концепции программирования, основных подходов к построению алгоритмов решения задач, принципов создания и отладки программ и т. п. В данной работе внимание акцентируется не на конкретном языке, а на алгоритмике процесса. Автор пытался составлять решения задач вообще опосредованно к языку программирования. Для этой цели, как нельзя кстати, пришелся аппарат представления алгоритмов в виде блок-схем. Блок-схемы позволяют «нарисовать» алгоритм, увидеть его целиком, а уж как и на чем он будет реализован – это отдельная задача, причем достаточно часто тривиальная и в большинстве случаев неинтересная. Именно умение корректно составить алгоритм определяет успех при управлении той или иной системой. Причем речь идет о составлении 7 программ не только для компьютера, но и для планирования прочих действий, включая управление людьми. Неправильно поставленная, некорректная, неоптимизированная, недостаточно (или, наоборот, излишне детализированная) задача по выполнению последовательности каких-либо действий может привести к ее неисполнению. Цель при решении задач программирования состоит не в том, чтобы получить конечное значение какой-либо величины, а в том, чтобы научить компьютер самостоятельно искать эту величину, тем самым избавляя себя и других людей от выполнения рутинных действий. Материал, изложенный в настоящем пособии, читается уже многие годы для студентов-первокурсников ВолгГТУ в рамках учебных дисциплин «Информатика» и «Основы программирования». Подход к изучению и последовательность изложения материала показали свою жизнеспособность. Основанием для создания учебного пособия послужило отсутствие литературы, отражающей особенности преподавания информатики как общетехнической дисциплины на кафедре «Вычислительная техника» ВолгГТУ. Несмотря на обилие книг по программированию, подход, основанный на преимуществе блок-схемы перед программным кодом, встречается достаточно редко. Причиной тому служит ориентированность на подготовленного читателя, желающего самостоятельно обрести навыки программирования в той или иной системе программирования, на том или ином языке. Целью данного пособия является изложение учебного материала по информатике в достаточно компактной форме. Даже если студент что-то не понял на лекции, то он всегда сможет обратиться к пособию для уточнения пропущенного материала, или материала, плохо изложенного в его собственном конспекте. 8 Пособие ограничено по объему, потому здесь не изложены вопросы создания пользовательских библиотек; не рассмотрено объектно- ориентированное программирование; нет задач на графы, связанные списки, рекурсию, специальные алгоритмы обработки нестандартных массивов. Все это здесь не уместилось, да и стандартный объем часов по информатике достаточно небольшой; однако есть надежда на скорый выход в свет продолжения, в котором все эти вещи, по-возможности, будут освещены. 9 1. БАЗОВЫЕ СВЕДЕНИЯ ОБ ИНФОРМАТИКЕ, ПРОГРАММАХ И ЭВМ 1.1. Общие сведения Прежде всего, определимся с терминологией, используемой в информатике (в связи с этим дадим основные определения). Информация – способность одной системы оценивать поведение другой системы и различать что-либо. Информатика – наука о средствах сбора, хранения, передачи и обработки информации, выраженной в количественном виде. Информационные процессы – действия, выполняемые над информацией, т. е. процессы получения, передачи, преобразования, хранения и использования информации. Бит – минимальная единица измерения информации (в двоичной системе 0 или 1). Более точные определения бита и информации будут даны ниже. На практике, помимо бита для демонстрации информационной емкости, пользуются байтами и кратными им величинами: 1 байт = 8 бит 1 ; 1 Кбайт = 2 10 байт = 1024 байт; 1 Мбайт = 2 10 Кбайт = 1024 Кбайт; 1 Гбайт = 2 10 Мбайт = 1024 Мбайт; 1 Тбайт = 2 10 Гбайт = 1024 Гбайт. Информационный объем сообщения – количество бит в этом сообщении. Бит в секунду – единица измерения скорости передачи информации 2 : 1 Помимо 8-битного представления байта, существуют иные подходы, например, в знаменитом, ставшем классикой, трехтомнике по программированию «Искусство программирования» Дональда Кнута, в одном байте – 6 бит. Потому и определение этому понятию дают более общее: байт – это минимально адресуемая область памяти. 10 1 кбит/с = 1000 бит/с; 1 Мбит/с = 1000 Кбит/с; 1 Гбит/с = 1000 Мбит/с; 1 Тбит/с = 1000 Гбит/с. Вообще, процессы, происходящие в физическом мире, принято считать непрерывными. Для того чтобы можно было говорить об их информационной обработке, необходимо физическому процессу сопоставить число. Процесс сопоставления чисел непрерывным физическим процессам называется оцифровкой. Очевидно, что оцифровка не полностью отражает реальный процесс. При оцифровке часть инфор- мации теряется. Однако, как говорилось ранее, способ задания информативности зависит от конкретной системы. Если нам не нужно высокое разрешение сигнала, то достаточно ограничиться малым. Оцифровку можно наглядно представить, например, при переводе аналоговой записи (магнитофонной кассеты) в цифровую форму (рис. 1.1). Видно, что через равные промежутки времени мы снимаем показания уровня сигнала; причем шкала, по которой этот уровень снимается, имеет конечную разрешающую способность, что выражается в 2 В отношении скорости передачи информации существуют разногласия по поводу того, каким образом представлять кратные величины: степенью двойки, или десятичным множителем. Однако наиболее распространенным является подход образования кратных величин согласно правилам, принятым в системе СИ (умножение на 10). При работе с байтами же, приходится чаще иметь дело со степенями двойки. t t y y Аналоговый сигнал Цифровой сигнал шаг квантования период дискретизазии Рис. 1.1. Аналого-цифровое преобразование сигнала 11 «ступенчатости» графика. Величина ступеньки по оси y называется разрешением по уровню или шагом квантования, а длина ступеньки вдоль оси t – периодом дискретизации. 1.2. Двоичная система исчисления Исторически сложилось, что люди используют десятичную систему исчисления, т. е. систему исчисления, в которой цифровой алфавит состоит из десяти цифр: 0–9. Это связано с тем, что у человека 10 пальцев на руках, которые он с давних времен использовал для счета. Прежде всего, рассмотрим отличия двух понятий – «цифра» и «число». Цифры – символы, с помощью которых можно записать число. Число – смысл (количественное значение), вкладываемый в запись, состоящую из одной или нескольких цифр. Рассмотрим, по какой схеме формируются натуральные числа по порядку в десятичной системе исчисления. Выбирается по очереди весь цифровой алфавит этой системы. Первые десять чисел от (0 до 9) совпадают по написанию с десятью цифрами алфавита десятичной системы, но мы можем записать эти числа не 0, 1, 2, …, 9, а, например, 00, 01, 02, …, 09. Тем самым мы поставили на первое место цифру ноль (незначащий ноль), что мы можем сделать перед любым числом, не меняя его количественного значения. Справа же мы перебрали весь цифровой алфавит. Чтобы записать числа 10, 11 и так далее, на первом месте пишут 1, а справа перебирают весь цифровой алфавит, тем самым, получая числа от 10 до 19. Для получения числа 20 ставят 2 на первое место, и так далее, пока не переберут на первом месте весь цифровой алфавит. Затем слева добавляют третий разряд и перебирают на нем весь цифровой алфавит по тем же правилам, которые применялись для формирования двузначных чисел. 12 Аналогичным образом формируются натуральные числа в любой другой системе исчисления, например, двоичной (табл. 1.1). Двоичной системой называют систему исчисления, в которой не 10, а лишь две цифры: 0 и 1. Таблица 1.1 Соответствие десятичных и двоичных чисел Десятичная запись Двоичная запись Десятичная запись Двоичная Запись 0 1 2 3 4 5 6 7 0 1 10 11 100 101 110 111 8 9 10 11 12 13 14 15 16 1000 1001 1010 1011 1100 1101 1110 1111 10 000 Компьютерные микропроцессоры представляют собой схему из миллионов соединенных транзисторных ключей, которые могут находиться лишь в двух состояниях – «открыто» или «закрыто». Если соотнести 0 с состоянием, например, открытого транзисторного ключа, а 1 – с состоянием закрытого, то двоичная система исчисления может быть удобной для представления числовой информации в компьютерах. Вся информация в памяти компьютера хранится в цифровом представлении, в том числе и звук, и графика, и текст, не говоря уже, собственно, о числах. Для представления нечисловой информации в цифровом виде используют различные виды кодировок. Методы кодировок основаны на свойствах человеческого зрения и слуха. Например, чтобы закодировать звук так, чтобы среднестатистическое человеческое ухо не уловило потери качества, достаточно измерять и записывать амплитуду акустического колебания 13 каждую 1/44 000 с. Далее достаточно воспроизвести последовательность записанных звуковых амплитуд с частотой 44 кГц для того, чтобы услышать неискаженную музыку или речь. Потеря качества в действительности существует, но мы не ощущаем ее. Это связано с тем, что естественный способ воспроизведения звуков непрерывен, т. е., можно сказать, что природа воспроизводит звуки с бесконечной частотой дискретизации, а не 44 кГц, но человеческое ухо не сможет отличить разницы. 3 Это является примером дискретизации по времени. Кроме того, для перевода звука в цифру необходимо произвести квантование по амплитуде. Наиболее распространенным является 16-битное квантование, т. е. мы можем отчетливо различить 2 16 = 65 536 различных позиций амплитуды звукового колебания (см. рис.1.1). Для кодирования графики изображение разбивают, например, на строки и столбцы, на пересечении которых располагаются точки, называемые пикселями. Количество пикселей выбирают из требуемого качества изображения, а также из предполагаемого размера экрана монитора или листа бумаги, на котором будет в дальнейшем представлено это изображение. Очевидно, что чем больше точек, тем качественнее изображение. В связи с эти существует, если можно так сказать, единица измерения качества изображения – dpi (dot per inch) – точек на дюйм; чем выше эта величина, тем качественнее изображение, но больше места занимает в памяти компьютера. Присутствие черной точки (или ее отсутствие) позволяет строить лишь черно-белое изображение, такое как, например, с использованием аналогового копира. Чтобы получить цветное изображение, необходимо измерять цвет каждой точки. Средний 3 Это связано с механическими особенностями строения слухового аппарата человека. В частности, этот диапазон совпадает со спектром собственных частот звуковоспринимающей и звукопроводящей систем уха. Кроме частотной восприимчивости, существует еще и амплитудная, показывающая верхнюю и нижнюю границу чувствительности уровня акустического давления. 14 человеческий глаз отличает до 10 млн. оттенков цветов. В связи с этим цвет каждой точки достаточно закодировать с помощью 10 млн. чисел, чтобы человеческий глаз не отличил «искусственности» изображения. Обычно цвет кодируют с помощью 2 16 = 65 536 (High Color) или 2 24 = 16 777 216 (True Color) чисел. Для кодирования текста используют так называемые таблицы кодировок, в которых каждому символу (в том числе и буквам) поставлен в соответствие какой-либо код (число). Примером подобной таблицы может служить 8-битная таблица ASCII (говорят «АСКИ») (в которой описано 256 кодов, соответствующих, в том числе, латинским и русским буквам) или 16-битная таблица Unicode (содержащая символы алфавитов практически всех языков мира). Итак, мы рассмотрели, как может быть перекодирована различная нечисловая информация для представления в памяти ЭВМ. Разберемся теперь, как перекодировать число из десятичной в двоичную систему исчисления. Рассмотрим подробнее табл. 1.1. Обратим внимание на числа 1, 2, 4, 8, 16. Их можно записать как 2 0 , 2 1 , 2 2 , 2 3 , 2 4 . В двоичной записи им соответствую числа 1, 10, 100, 1000, 10 000. Посчитаем количество нулей каждого двоичного числа и обратим внимание на показатель степени соответствующего десятичного. Получается, что количество нулей в двоичных числах совпадает с показателем степени двойки в десятичном представлении числа. Можно сделать следующий вывод: всякое круглое двоичное число можно представить в десятичном виде как 2 в степени, равной количеству нулей, стоящих после 1 в двоичной записи числа. Рассмотрим один из возможных способов перевода десятичного числа в двоичный вид. 15 |