Сборник задач и упражнений по информатике


СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ
Серия основана в 2001 году




В.Д. КОЛДАЕВ

СБОРНИК ЗАДАЧ И УПРАЖНЕНИЙ ПО ИНФОРМАТИКЕ

УЧЕБНОЕ ПОСОБИЕ

Под редакцией профессора Л.Г. Гагариной



                       Допущено Министерством образования и науки Российской Федерации в качестве учебного пособия для студентов учреждений среднего профессионального образования


znanium.com

Москва
ИД «ФОРУМ» — ИНФРА-М
2022

УДК 004(075.32)
ББК 32.81я723
      К60

      Рецензенты:
         Лисов О.И., доктор технических наук, профессор кафедры информатики и программного обеспечения вычислительных систем Московского государственного института электронной техники (технического университета);
         Кичкин Ю.Л., кандидат технических наук, профессор кафедры радиоэлектроники Московского государственного института электронной техники (технического университета)


      Колдаев В.Д.
К60 Сборник задач и упражнений по информатике : учебное пособие / В.Д. Колдаев ; под ред. проф. Л.Г. Гагариной. — Москва : ИД «ФОРУМ» : ИНФРА-М, 2022. — 255 с. — (Среднее профессиональное образование).
         ISBN 978-5-8199-0928-7 (ИД «ФОРУМ»)
         ISBN 978-5-16-017299-6 (ИНФРА-М, print)
         ISBN 978-5-16-102904-6 (ИНФРА-М, online)
         Предложен широкий круг задач, сгруппированных по темам, по основам алгоритмизации, программирования и информационным технологиям для закрепления, углубления и контроля знаний и умений, полученных во время занятий или из учебников. Содержит справочные материалы по алгоритмическому языку Turbo Pascal, структурам данных, текстовому процессору Word и табличному процессору Excel.
         Для студентов, обучающихся по специальности «Программное обеспечение вычислительной техники и автоматизированных систем». Рекомендуется учащимся лицеев, гимназий и школ, колледжей и техникумов, а также преподавателям информатики и информационных технологий.

УДК 004(075.32)
ББК 32.81я723












ISBN 978-5-8199-0928-7 (ИД «ФОРУМ»)
ISBN 978-5-16-017299-6 (ИНФРА-М, print)
ISBN 978-5-16-102904-6 (ИНФРА-М, online)


© Колдаев В.Д., 2015
© ИД «ФОРУМ», 2015

                Введение






   Современное состояние курса информатики характеризуется устойчивым ростом социального заказа на обучение информатике, обусловленным насущной потребностью овладения современными информационными технологиями, и изменением содержания курса, обусловленным очередной сменой парадигм. В этой связи информатику предлагается рассматривать как «одну из фундаментальных отраслей научного знания, формирующую системно-информационный подход к анализу окружающего мира, изучающую информационные процессы, методы и средства получения, преобразования, передачи, хранения и использования информации; стремительно развивающуюся и постоянно расширяющуюся область практической деятельности человека, связанную с использованием информационных технологий».
   Современные курсы информатики можно классифицировать следующим образом:
   • математические основы фундаментальной информатики (к этому разделу относятся теории графов, алгоритмов, множеств, информационных моделей, баз данных, а также дискретная математика);
   • алгоритмизация и программирование (преподавание алгоритмических языков — Pascal, C++ и т. п.);
   • основы компьютерных технологий (компьютерная (информационная) технология — один из разделов информатики, позволяющий использовать его при различной профессиональной ориентации учебного процесса).
   Так как обучение является передачей информации ученику, то можно сделать вывод о том, что в обучении информационные технологии использовались всегда. Любая педагогическая технология — информационная технология, так как информационные технологии — процессы, связанные с переработкой информации. Когда же компьютеры стали использоваться в образовании, тогда появился термин «новая информационная техноло

Введение

гия (НИТ) обучения». Рассматривая имеющиеся на сегодняшний день НИТ, обычно выделяют следующие характеристики:
   • типы компьютерных обучающих систем (обучающие машины, обучение и тренировка, программированное обучение, интеллектуальное репетиторство, руководство и пользователи);
   • используемые обучающие средства (ЛОГО, обучение через открытия, микромиры, гипертекст, мультимедиа);
   • инструментальные средства (программирование, текстовые и табличные процессоры, базы данных, инструменты представления, авторские системы, инструменты группового обучения).
   Данное пособие — вариант задачника для изучающих информатику и информационные технологии. Конечно, это не самоучитель, прежде всего оно необходимо для закрепления, углубления и контроля знаний. В приложении, которое является чисто методическим, содержится описание практических приемов и методов, которыми удобно пользоваться для быстрого освоения любого незнакомого материала. В книге приведены упражнения, для выполнения которых достаточно здравого смысла, знания элементарной математики и начальных сведений из математического анализа и линейной алгебры. Задачи не требуют знания какого-то конкретного языка программирования, так как их можно решать на любом изучаемом в учебном заведении языке программирования.
   Эта книга служит формированию знаний, которые образуют фундамент, необходимый для корректной постановки и решения проблем в области информатики, для осознания целей и ограничений при создании вычислительных структур и программ обработки информации.
   Рекомендуется учащимся лицеев, гимназий и школ, колледжей и техникумов, студентам младших курсов институтов и университетов, всем изучающим и преподающим информатику.

Глава 1
Теоретические сведения по информатике и информационным технологиям





        1.1. Представление и обработка данных

   Информация — отражение реального мира, выраженное в виде символов и знаков. Представляться информация может в непрерывном и дискретном виде.
   Данные — объекты любой формы, выступающие в качестве средства представления информации. Одни и те же данные могут нести различную информацию для разных потребителей. Фиксация информации в виде данных осуществляется с помощью конкретных средств (языковых, изобразительных, числовых и т. д.) на конкретном физическом носителе.
   Для того чтобы использовать ПЭВМ для обработки данных, необходимо располагать некоторым способом представления данных. Любые виды данных, обрабатываемых на ПЭВМ, могут быть сведены к совокупности простейших форм: набор символов (текст), звук (мелодия), изображение (фотографии, рисунки, схемы), вещественные и целые числа (числовая информация).
   Во внешнем представлении все данные хранятся в виде файлов . Во многих случаях требуется еще более высокий уровень организации данных на внешнем уровне, тогда данные группируются в базы данных (рис. 1.1).
   Задачи по обработке данных предполагают также способы описания процесса самой обработки. Процедуры обработки данных представляются на внешнем и внутреннем уровнях. На внутреннем уровне каждая такая процедура представляет собой последовательность логических операций с целыми числами и называется программой. Сами логические операции кодируются с помощью средств машинного языка.

Глава 1. Теоретические сведения

Исходные данные

Данные в любой форме

Внешнее представление

Рис. 1.1. Уровни представления данных

Исходная задача

Внутреннее представление данных Целые числа









      Задача в любой форме

Программа

Машинный язык

Алгоритм

Рис. 1.2. Уровни представления обработки данных

    На внешнем уровне процедуры представляются в виде алгоритма (рис. 1.2). Конкретный вид алгоритма зависит от используемого алгоритмического языка.
    Таким образом, решение любых задач с помощью ПЭВМ в конечном счете сводится к двум взаимосвязанным проблемам: цифровому представлению данных и алгоритмическому представлению способов обработки данных.



1.1.1. Внутреннее представление данных

   ПЭВМ является электрическим прибором, который управляется с помощью электрических сигналов. Поэтому любые данные должны быть некоторым универсальным образом представлены в виде электрического сигнала. Таким свойством обладает двоичная форма целых чисел. Для записи числа в двоичной форме используются только два символа 0 и 1. Эти символы легко поставить в соответствие некоторому фиксированному значению напряжения в электрических схемах ПЭВМ (рис. 1.3).
   Таким образом, все данные, с которыми работают ПЭВМ, представлены в виде двоичных чисел, а все действия с данными сводятся к комбинации трех логических операций (табл. 1.1).

1.1. Представление и обработка данных

7

U

1
0


        -> t


Рис. 1.3. Поток данных в двоичной форме

Таблица 1.1. Операции с двоичными числами

x y или и НЕ х
0 0  0  0  1  
0 1  1  0  1  
1 0  1  0  0  
1 1  1  1  0  

    Количество информации, соответствующее двоичному числу, называют битом. Число, которое представлено N битами называется N-битным или N-разрядным. Количество информации, соответствующее 8 битам, называется байтом. Кроме того, используются группы, называемые словом. Размер слова зависит от характеристик конкретной ПЭВМ, но как правило, он равен 2 или 4 байтам.
    В 1948 г. американский математик К. Шеннон предложил формулу для вычисления количества информации для событий с различными вероятностями. Если I — количество информации, К — количество возможных событий, pi — вероятности отдельных событий, то количество информации для событий с различными вероятностями можно определить по формуле
           k
I = -^ pi log₂ pi, где i принимает значения от 1 до k.
           1

Как частный случай формулы Шеннона можно рассматривать формулу Хартли:
           I = log2 K = log2<1/p) = -log2 p или K = 2¹, где каждое из К событий имеет равновероятный исход p = 1/K.

Глава 1. Теоретические сведения

Таблица 1.2. Протокол игры «Угадай число»

                  Ответ    Количество возможных    Полученное
Вопрос второго   первого          событий          количество
                         (неопределенность знаний) информации
                                    32                       
Число больше 16?   Да               16               1 бит   
Число больше 24?   Да                8               1 бит   
Число больше 28?   Да                4               1 бит   
Число больше 30?   Нет               2               1 бит   
Число 30?          Да                1               1 бит   

    Пример 1. Игра «Угадай число».
    Один из участников загадывает целое число (например 30) из заданного интервала (например от 1 до 32), цель второго — «угадать» число первого участника. Для второго игрока начальная неопределенность знания составляет 32 возможных события. Чтобы найти число, необходимо получить определенное количество информации. Первый участник может отвечать только «да» и «нет». Второй должен выбрать следующую стратегию: последовательно, на каждом шаге уменьшать неопределенность знания в 2 раза. Для этого он должен делить числовой интервал пополам, задавая свои вопросы. Протокол игры показан в табл. 1.2.
    Для того чтобы угадать число из интервала от 1 до 32, потребовалось пять вопросов. Количество информации, необходимое для определения одного из 32 чисел, составило 5 бит: K = 2¹; 32 = 2¹; отсюда I = 5;

    Пример 2. Определить количество информации, получаемое при реализации события, когда бросают несимметричную четырехгранную пирамидку. Пусть вероятность отдельных событий будет такова:
pi = 1/2; p₂ = 1/4; p3 = 18; p₄ = 1/8.
    Тогда количество информации, получаемой после реализации одного из этих событий, рассчитывается по формуле Шеннона:
I = -(1/2 log₂ 1/2 + 1/4log₂1/4 +1/8 log₂1/8 +1/8 log₂18) =
= 1/2 + 2/4 + 3/8 + 3/8 = 14/8 = 1,75 (бит).

1.1. Представление и обработка данных

9

   Пример 3. В корзине лежат 16 шаров, все разного цвета. Сколько информации несет сообщение о том, что из корзины достали белый шар?
   По формуле Хартли сообщение содержит I = log₂16 = 4 бита информации.

   Пример 4. Рассмотрим последовательность строчных букв русского алфавита: а, ..., я. Присвоив каждой букве номер от 0 до 32, получим простейший способ представления символов. Последнее число — 32 — в двоичной форме имеет вид 100000, т. е. для хранения символа в памяти понадобится 6 бит. Так как с помощью 6 бит можно представить число 2⁶ -1 = 63, то 6 бит будет достаточно для представления 64 букв.



1.1.2. Цифровое представление изображений


    Под изображением будем понимать прямоугольную область, закрашенную непрерывно изменяющимся цветом. Поэтому для представления изображений в целых числах необходимо отдельно дискретизировать прямоугольную область и цвет. Для описания области она разбивается на множество точечных элементов — пикселей (pixel). Само множество называется растром (рис. 1.4), а изображения, которые формируются на основе растра, называются растровыми.
    Число пикселей называется разрешением. Часто встречаются значения 640 х 480, 800 х 600, 1024 х 768, 1280 х 1024. Каждый пиксель нумеруется, начиная с нуля, слева направо и сверху вниз.
    Для представления цвета используются цветовые модели. Цветовая модель — это правило, по которому может быть вычислен цвет. Самая простая цветовая модель — битовая. В ней для


Рис. 1.4. Дискретизация области изображения

Глава 1. Теоретические сведения

описания цвета каждого пикселя (черного или белого) используется всего один бит. Для представления цветных изображений используются несколько более сложных моделей. Известно, что любой цвет может быть представлен как сумма трех основных цветов: красного, зеленого и синего. Если интенсивность каждого цвета представить числом, то любой цвет будет выражаться через набор из трех чисел. Так определяется наиболее известная цветовая RGB-модель. На каждое число отводится 1 байт. Так можно представить 2 ²⁴ цвета, т. е. примерно 16,7 млн цветов. Белый цвет в этой модели представляется как (1, 1, 1), черный — (0, 0, 0), красный (1, 0, 0), синий (0, 0, 1). Желтый цвет является комбинацией красного и зеленого и потому представляется как (1, 1, 0).

    Пример. Пусть имеется изображение вида:


Рис. 1.5. Исходное черно-белое изображение

    Будем считать, что белый цвет представляется нулем, а черный — единицей, тогда в однобитовой модели такое изображение представится в виде:
0000000000000000
0000000000000000
0000111110000000
0000100010000000
0000100010000000
0000111110000000
0000000000000000
0000000000000000
    В шестнадцатеричном виде этот двоичный набор будет выглядеть так:
00 00 00 00 0F 80 08 80 08 80 0F 80 00 00 00 00
    Всего для хранения такого изображения потребуется 16 байт.