Make your own free website on Tripod.com

יסודות מדעי המחשב. יסודות- 1. מחבר ד"ר דוד גינת.

צוות הפיתוח: פרופ' מרדכי בן-ארי, דר' דוד גינת, ארנה הרשקוביץ ,

דר' ארנה ליכטנשטיין, חנה מחלב, אלה צור, יפעת קוליקנט, נורית רייך

מהדורה ניסויית, 1998

Основания компьютерных наук. Основания-1

Разработчики: проф. Мордехай Бен-Ари, д-р Давид Гинат, Орна Гершкович,

д-р Орна Лихтенштейн, Хана Махлев, Эла Цур, Ифат Куликант, Нурит Райх

Пробное издание, 1998

Предисловие

Главы Основания компьютерных наук предназначены для овладения основыми понятиями и принципами, на которых базируются компьютерные науки. Изучаемые главы содержат два раздела - абстрактный и реализацию. Абстрактный содержит разработку и формулировку алгоритма, который является рецептом для осуществления задания. Второй раздел содержит реализацию алгоритма с помощью программы на языке программирования. В изучаемых главах мы познакомимся с разнообразными сложными заданиями, предназначенными для осуществления на компьюторе, и узнаем о том, как разложить такие задания на их простые составные части. Мы будем формулировать алгоритмы для выполнения заданий, проверять корректность алгоритмов и их эффективность, и реализовать алгоритмы с помощью программ, которые будут выполняться на компьютере. Главы Основания компьютерных наук поделены на две книги - Основания-1 и Основания-2. Основания-1 содержат 11 глав, в которых сосредоточено большинство основных понятий и базовых принципов. Основания-2 состоят из 9 глав, которые содержат расширение основных понятий, углубление и расширение принципов. Книги выходят в свет в виде пробных изданий, поэтому мы заранее приносим извинения за возможные ошибки в их материале.

Глава 1. Введение

Ключевые слова: компьютер, ввод, вывод, компьютерная программа; аппаратные средства, центральный процессор, память, бит, устройства ввода, устройства вывода; программное обеспечение, операционная система, язык программирования, синтаксические правила, программист, машинный язык, язык высокого уровня, компилятор, компиляция, прогон, синтаксическая ошибка, ошибка прогона, отладка программы(устранение ошибок).

Компьютеры имеются во многих местах: они управляют самолетами, кораблями и космическими аппаратами; надзирают за миллионами телефонов, соединенных в сети и находящихся во многих странах; они используются для прогноза погоды, для заполнения и печати документов, для контроля за автоматизированными системами, для сочинения музыки, для игр, для управления большими организациями вроде банков, правительственных ведомств и авиакомпаний и еще для многих вещей. Без компьютера посадка человека на луну не была бы возможной. Эта операция требовала решения громоздких и сложных вычислительных задач для установления космической траектории, на которую вляет луна, земной шар и солнце. Выполнение таких вычислений посредством бумаги и карандаша потребовала бы работы огромной команды вычислителей в течение десятков лет. И еще - каждое изменение в позиции запуска или в траектории полета требует решать заново эти задачи вычислений. Эта операция без компьютеров была бы невозможной.

 

1.1. Что такое компьютер?

Компьютер(computer) есть электронная машина, которая вводит данные, обрабатывет их и выводит информацию, созданную в ходе обработки. Данные, которые читает компьютер, называются вводом(input), а информация, которую он выдает, называется выводом(output); обработка выполняется в компьтере под управлением группы команд, которая именуется компьютерной программой (computer program).

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

Художник рисованного фильма в качестве ввода задает две точки - начала и завершения - движения изображения на экране компьютера. Компьютер обрабатывает эти данные вместе с данными об изображении и представляет на экране в качестве вывода движение изображения между точками начала и конца.

Бухгалтер набирает в качестве ввода имя работника и число отработанных им в последний месяц дней. Компьютер обрабатывает эти данные вместе с теми, что хранятся в нем (например, разряд работника), и печатает в качестве вывода зарплату работника.

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

?Вопрос 1.1. Приведи примеры использования компьютера в твоем доме и твоей школе. Отметь в этих примерах, что есть ввод, а что - вывод.

У машины-компьютера в отличие от других машин имеется широкий спектр применений. В случае со стиральной машиной мы пользуемся компьютером, чтобы стирать, в холодильнике - для хранения продуктов и в автомобиле - для перемещения из одной точки в другую. Т.е. компьютером пользуются в широком спектре различных действий. Это вытекает из того, что компьютер выполняет различные действия обработки и хранения информации, у которых есть сходство с действиями, выполняемыми человеческим мозгом. Разноробразные действия компьютера управляются соответствующими компьютерными программами.

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

Компьютер выполняет вычислительные действия и обработку информации с огромной скростью и высокой точностью. Например, компьютер способен ввести тысячу пятизначных чисел и в течение доли секунды вычислить их сумму. Компьютер способен ввести текст из тысячи слов и в течение доли секунды определить наиболее распространенную букву в этом тексте. В компьютере можно хранить миллионы данных. Скажем, в компьютере министерства внутренних дел хранятся данные относительно всех жителей страны, о каждом хранятся личные данные вроде: имя, номер удостоверения личности, возраст, семейное положение, адрес и т.д. В компьютере банка хранятся личные данные всех его клиентов и данные о движении денег на счету каждого клиента.

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

?! На секунду задумаемся ... Что такое ошибочная программа?

Компьютерная программа пишется человеком, и возможно, что команды, написанные им, не отражают требуемую обработку. В этом случае программа - ошибочная. И как результат этого компьютер может выдать неверный результат обработки. Например, при написании программы вычисления среднего тысячи чисел челевек мог запрограммировать вычисление суммы, но забыть об указании поделить сумму на 1000. Обработка, которая будет выполнена по такой программе, не выдаст среднее как положено. В следующих главах мы познакомимся с ошибочными программами.

Мы различаем две стороны компьютера: оборудование(аппаратные средства) и программное обеспечение. Аппаратные средства(hardware) это компоненты собственно компьютера. Программное обеспечение(software) это набор компьютерных программ.

 

1.2. Оборудование

В этом параграфе мы опишем составные части компьтера.. В ходе изучения Основ компьютерных наук мы познакомимся в лаборатории с персональным

компьютером (personal computer или кратко PC). Персональный компьютер невелик по размерам, он предназначен для одновременного обслуживания только одного пользователя. Существуют компьютеры больших размеров, способные одновременно обслуживать несколько пользователей. Но общее строение компьютеров не зависит от их размеров. У компьютера есть несколько основных блоков(единиц):

Центральный блок обработки (central processing unit - процессор), его еще принято называть кратко CPU. CPU есть блок компьютера, который обрабатывает данные, осуществляет вычисления и управляет всеми процессами, происходящими в компьютере.

Память(memory). В памяти сохраняется информация, которую использует компьтер, компьютерные программы и промежуточные результаты процессов обработки.

Средства ввода(input devices). Присутствуют в компьютере для ввода данных.

Средства вывода(output devices). Присутствуют в компьютере для вывода данных.

Рис. 1.1. описывает основные блоки компьтера.

Компьютер

CPU

Средства ввода Средства вывода

Память

Рис. 1.1. Основные блоки компьютера

Процессор является мозгом компьтера. Он выполняет команды, написанные в компьютерной программе, в которых имеются указания на выполнение вычислительных действий, действий сравнения и т.д. Процессор в ходе выполнения этих действий обращается к памяти и к средствам ввода и вывода.

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

Процесс записи в (ячейку) памяти приводит к стиранию предыдущей информации в ней и записи(сохранения) в ней новой информации. Процесс чтения из памяти приводит к передаче прочитанной информации в процессор, но не приводит к стиранию информации в памяти. Процесс этот назван чтением, поскольку он напоминает ход чтения, которое мы осуществляем. Когда ты читаешь эти строчки, слова со страниц книги не стираются, лишь копируются в твою память.

Информация, хранящаяся в памяти, представляется посредством битов. Бит(bit) - сокращение английских слов binary digit(двоичная цифра, на иврите סיבית) - есть одна из цифр 0 или 1(подобно тому, как цифры 0 ... 9 являются десятичными).

Обычно ячейка памяти компьютера состоит из 16, 32 или 64 битов согласно проекта оборудования. В свете приведенных примеров и разнообразия компьютеров в нашей жизни удивляет, что содержимое каждой ячейки памяти есть всего лишь последовательность битов! Компьтер истолковывет последовательности битов как числа, как буквы, как команды для исполнения или другие типы информации. Процессор исполняет самые простые команды вроде: :Прочти биты из ячеек памяти с адресами 13 и 37, отнесись к ним как к числам, сложи их и запиши результат в ячейку по адресу 116.

Память компьютера делится на две части: главную память(main memory) и вспомогательную(secondary memory). Главная память используется для хранения программ во время их исполнения, хранения исходных данных и промежуточных результатов исполняемых программ. Вспомогательная память используется для неограниченного во времени хранения информации и компьютерных программ.

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

 

средствах хранения(информации). Примерами внешних запоминающих устройств являются дискета и жесткий диск.

(Рис. 1.2 Внешние запоминающие устройства - дискета и жесткий диск)

?Вопрос 1.2. Проведи аналогию некоторой вещи из школьного класса, пользование которой позволяет уподобить ее главной памяти, а для сранения - также предмета подобного вспомогательной памяти.

Средствами ввода пользуются для передачи данных в компьютер от пользователя. Средствами вывода пользуются для передачи информации из компьютера пользователю. Рисунок 1.3 описывает персональный компьютер. Подключенные к нему средства ввода - клавиатура и мышка. Средства вывода - это экран и принтер. (Рис. 1.3 Персональный компьютер)

?Вопрос 1.3. Калькулятор предназначен для выполнения арифметических действий, задаваемых пользователем. Какие у него средства ввода? А какие - средства вывода.

?Вопрос 1.4. Компьютер вводит информацию, перерабатывает ее и выводит результат обработки. И человеческий мозг получает информацию, перерабатывает ее и выводит результат обработки. a).Дай примеры элементов вводимой и выводимой человеком информации. b).Дай примеры информации, хранимой в памяти человека.

1.3. Программное обеспечение

Программное обеспечение это набор компьютерных программ. Компьютерные программы управляют обработкой, выполняемой оборудованием. Существуют программы для выполнения математических вычислений, для управления информационными базами, для контроля процессов, для моделирования систем, для обработки текстов, для игр и других различных применений. В дополнение к программам различного назначения в любом компьютере есть некая специальная программа, которая называется операционной системой. Операционная система есть программа, которая управляет остальными программами и выделяет им для использования различные ресурсы оборудования (CPU, память, средства ввода и вывода). На лабораторных занятиях мы познакомимся с операционной системой персонального компьютера, на котором нам предстоит работать.

Компьютерная программа или кратко - программа, которая есть группа команд для исполнения в компьютере, записывается на языке программирования. Язык программирования (programming language), содержит правила, согласно которым записываются команды, составляющие программу, и определяет смысл каждого указания. Человек, который пишет программу, называется программистом (programmer). Работа программиста включает анализ задания, предназначенного к исполнению на компьютере, разбиение задания на простые подзадания, написание их текстов для исполнения и реализацию посредством компьютерной программы. Это и есть процесс программирования.

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

В начале развития компьютеров в конце 40-х годов компьютерные программы писались только на машинном языке. Процесс их написания был очень громоздким, в нем находили много недостатков.

?! На секунду задумаемся ... В чем недостатки написания программы на машинном языке?

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

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

Эти недостатки вызвали, начиная с середины 50-х годов, развитие более удобных для написания, чтения и использования языков, называемых языками высокого уровня(high level language): Фортран(FORTRAN), Бейсик(BASIC), Паскаль (Pascal).

 

Язык высокого уровня есть язык программирования, команды которого подобны предложениям природного языка вроде английского или формулам математики. Но эти команды не пишутся свободной записью, но согласно правил, определенных в языке. Эти правила синтаксиса(syntax) языка.

?! На секунду задумаемся ... Программист в наши дни пишет программу на языке выокого уровня, в то время как компьютер понимает только машинный язык. Как же компьютер поймет программу, написанную на языке высокого уровня?

Программа, написанная на языке высокого уровня, проходит процесс перевода на машинный язык. Этот перевод выполняется с помощью специальной компьютерной программы.

Программа, которая переводит с языка высокого уровня на машинный язык, называется компилятором(compiler), а процесс перевода - компиляцией (compilation). Компилятор получает в качестве ввода программу на языке высокого уровня и переводит ее в программу на машинном языке. Чтобы осуществить работу программы на языке высокого уровня, необходимо пройти два этапа: компиляцию и прогон. На этапе компиляции программа на языке высокого уровня переводится на язык машины, а на этапе прогона компьютер выполняет укзания программы на языке машины.

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

 

Компьютер 1

Компилятор 1 Программа на языке

машины компьютера 1

Программа на языке высокого

Уровня

 

 

Компьютер 2

Компилятор 2 Программа на языке

машины компьютера 2

Рис. 1.4.Компиляция программы на языке высокого уровня на разных компьютерах

Если так, то язык высокого уровня не только более удобен для написания и чтения, но и наводит мосты между различными типами компьютеров. Можно переводить любую программу, написанную на языке высокого уровня, на машинные языки разных компьютеров посредством соответствующих компиляторов. Процесс компиляции состоит из двух этапов: a).Синтаксическая проверка программы на языке высокого уровня. b).Перевод(трансляция) программы на языке высокого уровня в программу на языке машины.

На первом этапе программа на языке высокого уровня проверяется на соответствие законам синтаксиса этого языка. Если написание программы осуществлено не в соответствии с законами синтаксиса, имеют место синтаксические ошибки(syntax errors) в тех местах программы, где отмечаются отклонения от норм законов. Компилятор отмечает каждую синтаксическую ошибку, теперь надо позаботиться об их исправлении. Например, первое слово в программе на Паскале должно быть program. Если же программа начинается со слова grogram, компиляторр сообщает, что это синтаксическая ошибка. Если в программе нет синтаксических ошибок, начинается второй этап - трансляции программы на машинный язык. В конце процесса перевода получается программа на машинном языке, которую можно прогнать(выполнить) на компьютере. В ходе прогона этой программы могут обнаружиться ошибки, которые приведут к печати соответствующих сообщений или к останову прогона до предусмотренного завершения. Эти ошибки называются ошибками прогона(run-time errors), которые не могли быть обнаружены во время компиляции.

Чтобы продемонстрировать разницу между синтаксической ошибкой и ошибкой прогона(исполнения), представим себе, что в определенном языке программирования можно пользоваться указанием х/у. Смысл его: раздели

 

некоторое число х на другое число - у. Если это указание написано против синтаксических правил, например, х!у вместо х/у, то это - ошибка синтаксическая, которая обнаруживается во время компиляции. Если же, с другой стороны, число у, на которое производится деление, будет равно нулю во время исполнения программы, то такое деление недопустимо. Этот факт обнаружится только во время попытки исполнить деление, которая приведет к ошибке прогона.

Процесс локализации ошибок прогона и их исправления называется отладкой ошибок, по-английски debugging(т.е. устранение bugs(клопов, насекомых)). Источник этого иностранного термина относится к ранним периодам использования компьютеров, занимавших целые залы. Некий компьютер прекращал действовать, а спустя определенное время среди его частей обнаруживалось большое насекомое, которое застряло там и мешало исправному функционированию компьютера. С тех пор принято называть ошибку программы багом, а отладку программ - поиском багов и их устранением.

Со времен появления первого языка высокого уровня было создано очень много различных языков. Этот феномен побуждает задать следующие вопросы:

Зачем нужно так много языков?

Не лучше ли иметь один универсальный язык, этакое компьютерное эсперанто, чтобы на нем писались все программы, и каждый мог бы с легкостью изучить его?

Что отличает разные языки?

Кто какими языками пользуется и в каких целях?

У множественности языков есть две основные причины. Первая связана с разработкой языков, как реакцией на потребности в различных новых областях использования компьютеров. Каждый язык характеризуется собственными качествами. Есть языки высокого уровня, предназначенные, в основном, для выполнения научных вычислений, а есть другие, более подходящие к обработке данных управления(расчет зарплат, бухгалтерия). Второй причиной является развитие научных исследований языков программирования, направленных на их совершенствование. Мы уже упоминали прежде языки высокого уровня Фортран, Бейсик и Фортран. Возможно знакомы и имена языков Кобол (Cobol), Лого (LOGO), Пролог (PROLOG) и С. При изучении Основ компьютерных наук мы будем пользоваться языком Паскаль. Этот язык разработан в Швейцарии Николаусом Виртом(Niklaus Wirth) в конце 60-х и начале 70-х годов. Назван он в честь французского филисофа и математика Блеза Паскаля(Blaise Pascal), который построил одну из первых вычислительных машин (см. следующий параграф). Язык Паскаль является простым, с его помощью удобно изучать основания программирования. Во время создания Паскаля были очень распростанены Фортран и Кобол. Но многие считали их недостаточными, особенно во всем, что касалось удобочитаемости и структуризации. Удобочитаемость это удобства при чтении программы и ее понимании; структуризация это деление совокупности указаний на подгруппы указаний таким образом, чтобы каждая подгруппа управляла выполнением подзадания. Язык Паскаль дает возможность программисту писать программы удобочитаемые и структурированные, поэтому он является языком, позволяющим приобретать соответствующие навыки программирования.

 

1.4. Развитие компьютера и компьютерных наук

Одним из заметных событий на пути развития компьютеров является создание простой машины автоматического выполнения действий сложения и вычитания чисел. В середине 17 века французский математик Блез Паскаль(Blaise Pascal)

разработал своему отцу машину сложения и вычитания для подсчета денежных сумм при взимании налогов. Машина Паскаля, построенная для облегчения ручных подсчетов и в особенности для сокращения человеческих ошибок, впервые ввела автоматический компонент в действия вычислений.

Через несколько десятков лет германский ученый Вильгельм Лейбниц (Wilhelm Leibnitz) высказал утверждение, что вычисления, без которых наука не может существовать, есть действия повторяющиеся, скучные и непродуктивные. Вычисления, утверждал Лейбниц, есть действия, которые необходимо передать для

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

Но действие численных вычислений не было единственным объектом, для которого разрабатывался изощренный автоматический механизм. В 1801 году француз Жозеф Жаккард(Joseph Jacquard) разработал совершенный ткацкий станок для создания многоцветных тканей по трафаретам. Трафареты устанавливались посредством карт с отверстиями в разных местах. Специальный контроллер выявлял отверстия и надзирал над выбором нитей и над другими действиями машины.

Первым, кто спроектировал машину, которая могла бы выполнять разного рода программы с целью вычислений, контроля и обработки некоторой информации, был английский математик Чарльз Беббидж(Charles Babbage). В 1833 году Беббидж спроектировал Аналитическую машину, которая должна была выполнять программы, закодированные отверстиями в картах. Этот проект Беббиджа считается первым проектом многоцелевого автоматического компьютера, в нем можно найти те же составные элементы, из которых строятся современные компьютеры. Машина Беббиджа была по своим характерристикам механической , сделанной из стержней, ручек и зубчатых колес. Ада Ловлейс(Ada Lovlace), по имени которой назван язык высокого уровня Ada, написала для этой первой теоретической машины программу, которая считается первой в истории. Изготовление частей этой машины требовало чрезмерной для времени изобретения точности, поэтому идея ее построения была надолго отложена. Тем не менее идеи, выраженные в проекте аналитической машины, составили основу внутреннего устройства и действия современных компьютеров. Беббидж сильно опередил свое время, его идеи получили настоящую оценку значительно позднее.

После смерти Беббиджа центр изготовления вычислительных машин переместился в Соединенные Штаты. Одной из причин повышенного интереса к этой теме в Соединенных Штатах было подведение итогов переписи населения, проведенной в 1880 году. Через шесть лет после переписи все еще не было надежды, что обработка ее результатов будет завершена к 1890 году - времени проведения следующей переписи. Инженер Герман Холлерит(Herman Hollerith), служащий ведомстве учета населения, предложил в 1986 году несколько разработанных им устройств для решения указанной проблемы. И действительно, его разработка позволила подвести итоги следующей 1980 года переписи в течение одного месяца! Разработка Холлерита по аналогии со способом Жаккарда базировалась на перфокартах(картах с отверстиями) для прохождения электрического тока через отверстия. На волне своего успеха Холлерит основал компанию вычислительных машин, которая в 1928 году превратилась в международную компанию деловых машин и изменила свое название на IBM (International Business Machines).

Начиная с середины 30-х годов осуществлялись важные теоретические работы, составившие основания компьютерных наук. В 1936 году английский математик Алан Тьюринг(Alan Turing) опубликовал модель простой машины, работа которой велась по программе, пробитой на кинопленке. Машина Тьюринга составила теоретическую модель современных компьютеров. Тьюринг также показал, что компьютеры не всемогущи. (Деяния Тьюрринга описаны в прекрасной книге Алан Тьюринг Рольфа Хохета, изданной Библиотекой рабочих в 1989 году). Другие математики и среди них немец Курт Гёдель (Kurt Godel), русский Андрей Марков(Andrei Markov), американцы Алонзо Чёрч(Alonzo Church), Эмиль Пост(Emil Post) и Стефан Клейн(Stephen Kleene) занимались возможностями и ограничениями, вытекащими из теоретических моделей компьютеров. Существо этих теоретических работы привело к построению первого компьютера.

В 1937 году американский ученый Говард Айкен(Howard Aiken) приступил, совместно с IBM, к созданию первого электро-механического компьютера. Айкен, проект которого основывался на идеях Беббиджа, сумел воплотить мечту Беббиджа вследствие доступности новых электронных и электро-механических приборов. В 1944 году было завершено построение компьютера, названного MARK - 1, размером в гимнастический зал. В ходе второй мировой войны британцы построили компьютер Enigma, с помощью которого взламывали германские шифры. (Существование этого компьютера хранилось в секрете до последнего времени). В 1946 году было завершено создание существенно более быстрого компьютера, который не базировался на механических движениях. Этот компьютер, названный ENIAC, спроектиррованный американцами Эккертом(Eckert) и Мочли(Mauchly), считается первым электронным компьютером. Его длина равнялась 30 м, ширина 1 метру, а высота - 3 метрам, он содержал 18000 вакуумных трубок. С тех пор принято рассказывать, что всякий раз при запуске ENIAK гасли лампочки в Филадельфии, городе, где он был установлен.

Первые компьютеры воспринимали данные и программы с перфорированной бумажной леты. Для каждой обработки компьютеру поставлялась соответствующая программа вместе с обрабатываемыми данными. В 1946 году германо-американский ученый Джон фон-Нейман(John von Neuman) предложил помещать программы в памяти компьютера. Таким образом осуществление команд стало доступным, и это, среди прочего, привело к заметному возрастанию скорости обработки. Модель функционирования компьютеров, предложенная фон-Нейманом, является наиболее распрространенной в наши дни. В 1951 году был построен UNIVAC - первый промышленный компьютер, в котором применена указанная модель функционирования.

В 50 - 60 годы совершился перспективный технологический прорыв. Вакуумные трубки(электронные лампы) заменялись транзисторами, уменьшались размеры компьютеров и потребление электричества, возрастало быстродействие. К большим компьютерам, т.н. сверхкомпьютерам(Mainframe), добавились компьютеры средних размеров(как книжная этажерка), названные мидикомпьютерами, и миникомпьютеры (Midi/Mini Computers). В конце 60-х и начале 70-х появилась технология интегральных схем. Цена компьютеров упала, скорость - возросла, начали появляться миниатюрные компьютеры, названные микрокомпьютерами (Micro Computers), размер которых был со спичечную коробку. Появление микрокомпьютеров привело к перевороту: их размеры стали маленькими, стоимость относительно дешевая, это позволило расширить использование компьютеров для разнообразных нужд. Микрокомпьютеры стали использовать в качестве контроллеров в различных электронных системах, а в конце 70-х был построен на основе микрокомпьютеров первый персональный компьютер. Сегодняшние микрокомпьютерры обладают значительно большими возможностями обработки, чем первые компьютеры-гиганты.

Первые компьютерные программы писались на машинном языке. Неудобства в написании программ на машинном языке и рост потребности в компьютерных программах для математических вычислений привел в середине 50-х к разработке языка высокого уровня Фортрана(FORTRAN - FORmula TRANslator). Но язык Форртран не позволял удобное написание программ для обработки таких источников информации как управление кадрами или запасами, поэтому в начале 60-х годов был разработан язык программирования Кобол(COBOL - COmmon Business Oriented Language). Еще один удачный язык программирования LISP (LISt Programming) для написания реализаций, в которых удобно представлять информацию посредством списков, выражающих связи между данными, был разработан в начале 60-х. Подобные реализации включают системы принятия решений, обучающие системы, игры и т.п. Учебный язык программирования Лого(LOGO), используемый в качестве средства развития навыков мышления для решения задач, является дружественной версией языка LIPS. Другим языком, разработанным в учебных целях, является язык Бейсик (BASIC - Beginners All-purpose Symbolic Instruction Code). Просто устроенный Бейсик был разработан в середине 60-х с намерением создать легкий для обучения и использования язык программирования. В 1970 году разработан язык программирования Пролог(PROLOG - PROgramming in LOGic), базирующийся на математической логике, согласно законам которой определенные факты логически вытекают из других фактов(например, если Х является отцом У, а У является отцом Z, то Х является дедом Z). В начале 70-х был разработан язык С для написания операционных систем. Этот язык позволяет среди прочего напрямую обращаться к ресурсам оборудования. Сегодня язык С - один из наиболее распространенных для разработки программного обеспечения. Язык Паскаль (Pascal), который мы уже упоминали, разработан также в начале 70-х годов.

Все отмеченные языки программирования пригодны для разработки не слишком больших программ(до 10000 строк), допускающих относительно легкое слежение за их ходом и согласование действий разработчиков различных частей этих программ. В 80-е годы были разработаны такие языки, как Modula и Ada83, предназначенные для разработки больших программ. В последние годы упор делается на разработку языков, поддерживающих объектно ориентированное программирование(object - oriented - programming), среди них C++, SmallTalk, Ada95, Eiffel и Java. В этих языках подчеркивается деление больших программ на небольшие и повторное использование существующих небольших программ.

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

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

Резюме

В этой главе мы кратко описали, что такое компьютер, из каких основных частей он состоит, и как пишутся и осуществляются компьютерные программы. Мы также описали историю развития компьютеров, привели примеры разнообразного их использования и отметили различные области компьютерных наук.

Компьютер это электронная машина, вводящая данные, обрабатывающая их и выдающая информацию, созданную в ходе обработки. Данные, которые вводит компьютер, называют вводом; информацию, которую компьютер выводит, называют выводом; обработка осуществляется в компьютере под управлением группы указаний, называемой компьютерной программой.

Физические компоненты компьютера называются аппаратными средствами (оборудованием). Оборудование делится на несколько основных составных частей: центральный процессор, память, средства ввода и средства вывода. Центральный процессор управляет всеми действиями компьютера. В памяти, которая делится на основную и вспомогательную, хранится информация, программы и промежуточные результаты процессов обработки. Средства ввода и средства вывода входят в компьютер, чтобы вводить и выводить данные. Информация, хранящаяся в памяти, представляется посредством битов. Бит это одна из цифр 0 или 1.

Набор компьютерных программ называется программным обеспечением.

Программное обеспечение включает операционную систему, компиляторы и программы различного назначения. Программист пишет компьютерную программу на языке программирования. Команды, составляющие программы, пишутся по правилам языка программирования. Языки программирования, на которых пишут в наши дни программисты, являются, в своем большинстве, языками высокого уровня. Предложения такого языка подобны предложениям естественных языков, вроде английского. Программа на языке высокого уровня переводится на машинный язык с помощью компилятора в ходе процесса, называемого компиляцией. Машинный язык это язык, понимаемый компьютером, его команды кодируются посредством битов.

Чтобы компьютер выполнил программу, написанную на языке высокого уровня, необходимо пройти два этапа: компиляцию и прогон. В ходе осуществления двух этих этапов могут обнаружиться синтаксические ошибки и ошибки исполнения. Синтаксические ошибки обнаруживаются компилятором. Ошибки прогона выявляются в ходе исполнения программы. Процесс локализации ошибок прогона и их исправления называется отладкой.

Компьютерная программа есть группа команд для выполнения задания, предназначенного компьютеру. Работа программиста включает анализ задания, разделение его на простые подзадания, разработку рецепта их реализации в компьютерной программе. Рецепт осуществления задания называется алгоритмом. В следующей главе мы представим термин алгоритм и напишем первые алгоритмы. А далее мы будем заниматься разработкой алгоритмов, проверкой их свойств и реализацией посредством компьютерных программ.

Дополнительные вопросы

1.Почему нельзя написать программу для компьютера на языке, на котором мы говорим?

2.Почему язык программирования высокого уровня именно так называется?

3.Что имеется ввиду, когда говорят машинный язык, понятный компьютеру?

4 чем преимущества написания программ на языке высокого уровня по сравнению с использованием машинного языка?

5.Компилятор это компьютерная программа. Что есть ввод компилятора, а что - вывод его?

6.Есть ли необходимость в разных компиляторах с языка высокого уровня Паскаль для различных типов компьютеров? Аргументируй.

7.Сколько компиляторов потребуется для компиляции программы на языке Бейсик, программы на языке Паскаль и программы на Фортране - на трех компьютерах различного типа?

8.Почему языков программирования много?

 

Глава 2. Алгоритм

Ключевые слова: алгоритм, алгоритмическая задача.

Алгоритм есть рецепт выполнения задания. Алгоритм состоит из группы однозначных и выполнимых в строго определенном порядке указаний.

Термин алгоритм является центральным в компьютерных науках. В этой главе мы познакомимся с ним и разработаем первые алгоритмы, не предназначенные для осуществления на компьютере. А далее мы будем разрабатывать алгоритмы для их реализации в программах и выполнения на компьютере. Группа указаний в следующем примере есть алгоритм:

Вскипяти десять стаканов воды

Добавь немного соли

Добавь в скипевшую воду полкило мелкой лапши

Снова доведи воду до кипения

Вари лапшу в течение 20 минут на слабом огне

Процеди лапшу

Алгоритм в этом примере есть рецепт варки полкилограмма мелкой лапши.

Следующая группа указаний также является алгоритмом:

Выбери целое положительное число

Сложи цифры числа

Раздели результат на 3

Запиши остаток от деления

?Вопрос 2.1. Каков результат выполнения этого алгоритма для числа 1977?

Указание в составе алгоритма является однозначным, т.е. любое его исполнение должно завершаться одинаковым результатом. Так, например, указание Сложи цифры числа (из последнего примера) - однозначное. А вот указание Подвинься немного в сторону - неоднозначное: разные люди передвинутся по нему на разные места, и даже один и тот же человек будет смещаться по этому указанию всякий раз неодинаково. Указание в алгоритме должно соответствовать

тому, кто предназначен для его осуществления. Например: повар может выполнить указание Вскипяти 10 стаканов воды, но не может осуществить команду Посадить самолет. Порядок выполнения указаний алгоритма соответствует порядку их появления, если не сказано иначе. Выполнение алгоритма завершается, когда больше не осталось команд. Каждое указание так или иначе состоит из команды на выполнение действия в предположении продвижения к следующей команде или останова исполнения.

Термин алгоритм происходит от имени математика Мухамеда Аль-Хорезми, искаженно - Аль-Горезми. Аль-Горезми жил в 9 веке нашей эры в районе Хорезма, сегодня это Узбекистан. Он был первым, кто сформулировал правила, используемые нами по сей день для выполнения четырех основных арифметических действий. Термин алгоритм вошел в язык математиков, начиная с 14 века. Алгоритм стал обозначеннием математического рецепта. Мы знаем много подобных рецептов. Например: алгоритм умножения двух чисел, алгоритм возведения числа в степень, алгоритм нахождения наибольшего общего делителя двух целых положительных чисел.

Мы займемся алгоритмами, решающими алгоритмические задачи.

В алгоритмической задаче описываются исходная точка и цель и требуется алгоритм достижения цели.

Далее идет пример алгорритмической задачи.

Назначение следующей задачи и ее решения: представление первой алгоритмической задачи и последовательного алгоритма ее решения.

Задача 1. Лодочник находится на берегу реки с волком, овцой и капустой. Он хочет переправить их на другой берег в маленькой лодке. На лодке могут одновременно находиться только сам лодочник и один из указанных объектов. Но нельзя оставлять вместе волка и овцу без присмотра, и нельзя без присмотра оставлять вместе овцу и капусту. Разработай алгоритм, который укажет лодочнику, как переправить волка, овцу и капусту с одного берега на другой.

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

Алгоритм

капуста овца волк

Плыви от берега 1 к берегу 2 с овцой овца / капуста волк

Плыви один от берега 2 к берегу 1 овца / капуста волк

Плыви от берега 1 к берегу 2 с волком овца волк / капуста

Плыви от берега 2 к берегу 1 с овцой волк / капуста овца

Плыви от берега 1 к берегу 2 с капустой капуста волк / овца

Плыви один от берега 2 к берегу 1 капуста волк / овца

Плыви от берега 1 к берегу 2 с овцой капуста волк овца

Конец решения задачи 1

Во многих случаях существует больше чем один алгоритм решения данной алгоритмической задачи.

И следующий алгоритм также решает задачу 1:

Плыви от берега 1 к берегу 2 с овцой

Плыви один от берега 2 к берегу 1

Плыви от берега 1 к берегу 2 с капустой

Плыви от берега 2 к берегу 1 с овцой

Плыви от берега 1 к берегу 2 с волком

Плыви один от берега 2 к берегу 1

Плыви от берега 1 к берегу 2 с овцой

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

?Вопрос 2.2. Проследи посредством соответствующих иллюстраций за ходом выполнения дополнительного алгоритма решения задачи 1.

Три объекта задачи 1 это волк, овца и капуста; но можно поставить более общую задачу, в которой предметы будут называться - предмет-1, предмет-2 и предмет-3; им будут поставлены в соответствие ограничения задачи 1. У общей задачи имеется много возможных исходных точек.

Примеры. волк, овца, хаса(салат) собака, кот, мышь лев, корова, сено

Решением общей задачи будет алгоритм решения задачи 1, только ее объекты будут называться предмет-1, предмет-2 и предмет-3 вместо волка, овцы и капусты. Этот алгоритм станет общим и будет соответствовать любой возможной исходной точке общей задачи.

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

?Вопрос 2.3. На доску из пяти клеток положены два игровых камня одного цвета и два камня другого цвета. Их исходное положение:

 

Целью является приведение игровых камней к положению:

 

Разрешенные действия: перевод камня на прилежащую пустую клетку и прыжек камня одного цвета через камень другого цвета на пустую клетку. Разработай алгоритм перевода игровых камней из исходного положения в положение цели.

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

любой паре цветов, а потому будет общим.

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

Назначение следующей задачи и ее решения: представление алгоритма, в котором есть команда выполнения с условием.

Задача 2. Две емкости, емкость 1 и емкость 2, содержат разное количество апельсинов. Сумма числа апельсинов в обеих емкостях четная. Разработай алгоритм для перекладывания апельсинов из емкости в емкость так, чтобы они перекладывались только один раз. В конце - емкости должны содержать одинаковое число апельсинов.

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

?Вопрос 2.4. В алгоритме решения надо будет отметить, сколько апельсинов следует переложить из емкости в емкость, чтобы число апельсинов в обеих емкостях стало одинаковым. Ниже даны пары чисел апельсинов: в каждой паре слева число апельсинов в емкости 1, а справа - в емкости 2. Для каждой пары определи, сколько апельсинов надо переложить из более полной емкости в емкость заполненную меньше: a). 100, 160; b). 971, 935; c). 1, 1001.

С помощью ответа на последний вопрос можно утверждать, что число перекладываемых апельсинов равно половине разницы чисел апельсинов в емкостях. Эта величина определяется до выполнения перекладывания. Поэтому первой командой алгоритма будет:

Вычисли число перекладываемых апельсинов как половину разницы между их числом в емкостях

Когда в емкости 1 больше апельсинов, необходимо выполнить указание:

Переложи из емкости 1 в емкость 2 вычисленное число апельсинов

А когда в емкости 1 меньше апельсинов, необходимо выполнить указание:

Переложи из емкости 2 в емкость 1 вычисленное число апельсинов

?! На секунду задумаемся ... Как выбрать, какое из двух указаний выполнить?

Выбирается нужное указания для исполнения согласно условия. Условие таково:

в емкости 1 больше апельсинов чем в емкости 2

Если условие выполняется, то осуществляется первое указание. Иначе, осуществляется второе указание. Сформулируем эту обусловленность в алгоритме решения задачи посредством команды условия вида если .... то ... иначе ...

Алгоритм

Вычисли число перекладываемых апельсинов как половину разницы между их числом в емкостях

Если в емкости 1 больше апельсинов чем в емкости 2 то

Переложи из емкости 1 в емкость 2 вычисленное число апельсинов

Иначе

Переложи из емкости 2 в емкость 1 вычисленное число апельсинов

Конец решения задачи 2

Команда если .... то ... иначе ... есть команда выполнения с условием, указывающая на выполнение одной или другой группы команд согласно условия.

Команда выполнения с условием есть команда управления. Команда управления влияет на ход выполнения команд алгоритма.

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

?Вопрос 2.5. На столе в ряд положили три конверта, в каждом записка, на которой написано число: в одном конверте записка с числом 0, а в двух других - с числами, отличными от 0. Конверт с запиской, на которой 0, не находится посредине ряда. a).Обрати внимание на то, что имеется бесконечное множество возможностей для исходной точки, поскольку на двух записках могут быть написаны любые числа, отличные от 0. Опиши пять разных возможностей исходной точки. b).Разработай алгоритм, целью которого является размещение конверта с нулем посредине между двумя другими записками. Используемые для выполнения задания действия: чтение числа на записке в конверте и перемена местами соседних конвертов.

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

Назначение следующей задачи и ее решения: представление алгоритма, в котором есть команда повторного исполнения.

Задача 3. На столе дан ряд нечетного числа карт. Средняя в ряду карта - белая, все карты слева от нее - черные, а справа - красные. Даны также две закладки, закладка-1, указывающая на карту на левом краю, и закладка-2, указывающая на карту на правом краю. Разработай алгоритм, в результате действия которого все красные карты окажутся слева от белой, а черные - справа. Разрешенные к выполнению действия: *Установка закладки справа или слева от той карты, на которую она указывает. Установка закладки включает чтение цвета карты, на которую она указывет. *Перемена местами карт, на которые указывают закладки.

Исходной точкой задачи является заданное положение ряда карт и двух закладок. А целью является положение, в котором красные и черные карты поменяются местами. Обрати внимание, есть бесконечное число возможностей для исходной точки, и это потому, что длина ряда карт может равняться любому нечетному числу: Б Ч Б К Ч Ч Б К К . . . .

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

Карты в исходной точке : Ч Ч Ч Б К К К

Карты в положении цели: К К К Б Ч Ч Ч

Решение частного случая. Надо поменять местами пару карт на краях ряда и продвинуть закладки внутрь. После этого поменять местами новую пару карт, на которые указывают закладки, и снова продвинуть закладки внутрь. И в конце поменять местами оставшуюся пару карт. Алгоритм решения частного случая в сопровождении состояний его исполнения дается ниже. На иллюстрации черная закладка это закладка-1, а белая есть закладка-2.

Ч Ч Ч Б К К К

Поменяй местами карты, на которые указывают закладки

К Ч Ч Б К К Ч

Подведи закладку-1 к следующей карте справа

К Ч Ч Б К К Ч

Подведи закладку-2 к следующей карте слева

К Ч Ч Б К К Ч

Поменяй местами карты, на которые указывают закладки

К К Ч Б К Ч Ч

Подведи закладку-1 к следующей карте справа

К К Ч Б К Ч Ч

Подведи закладку-2 к следующей карте слева

К К Ч Б К Ч Ч

Поменяй местами карты, на которые указывают закладки

К К К Б Ч Ч Ч

Решение частного случая задачи учит, что для достижения цели надо несколько раз выполнить подзадание:

Перемена местами карт, на которые указывают закладки, и продвижение закладок внутрь

Это подзадание исполняется следующей группой команд:

Поменяй местами карты, на которые указывают закладки

Подведи закладку-1 к следующей карте справа

Подведи закладку-2 к следующей карте слева

Искомый алгорритм должен обращаться к повторному исполнению этого подзадания(группы команд). Число повторений зависит от длины ряда карт. Мы взялись разработать алгоритм, который бы годился ряду карт любой длины. Поэтому недостаточно было написать алгоритм для некоторой определенной длины ряда. Также если бы нам была дана особая длина, пусть 401, пришлось бы написать алгоритм, сложенный развертыванием большого числа повторений описанной группы команд.

?! На секунду задумаемся ... Если так, то каким образом сформулировать алгоритм, который будет годиться для любой нечетной длины ряда карт?

Чтобы сформулировать искомый алгоритм, воспользуемся командой повторения с условием, которая требует повторного исполнения группы из трех описанных команд до тех пор, пока выполняется условие:

карта, на которую указывают закладки, - не белая.

Следующий алгоритм и есть решение задачи, он включает команду повторного исполнения с условием, которая имеет вид: до тех пор пока ... выполняй ...

Алгоритм

До тех пор пока карта, на которую указывают закладки, не белая выполняй

Поменяй местами карты, на которые указывают закладки

Установи закладку-1 у следующей карты справа

Установи закладку-2 у следующей карты слева

Конец решения задачи 3

Команда до тех пор пока ... выполняй ... есть команда повторного исполнения с условием, требующая возвращаться к исполнению группы команд до тех пор, пока выполняется некоторое условие. Подобно команде выполнения с условием команда повторного исполнения с условием есть команда управления.

 

?Вопрос 2.6. Опиши состояния исполнения алгоритма задачи 3 для следующих возможных исходных точек: a).ряд карт длиной 9; b).ряд карт длиной 3.

?Вопрос 2.7. Измени алгоритм решения задачи 3 так, чтобы с окончанием его исполнения была достигнута другая цель: карты по обе стороны от белой карты были бы упорядочены согласно цветам попеременно( К, Ч, К, ..., Б, ..., Ч, К, Ч).

Резюме. В этой главе мы познакомились с терминами алгоритм и алгоритмическая задача. Алгоритм это рецепт исполнения задания. Алгоритм состоит из групп однозначных и доступных для выполнения указаний, порядок осуществления которых внятно определен. Алгоритмическая задача описывает исходную точку и цель, определяющие задание, и требуется алгоритм для достижения цели. У алгоритмических задач, которые мы рассматривали, было много, иногда бесконечно много, возможных исходных точек. Возможно существование более одного алгоритма для решения алгоритмической задачи. Порядок выполнения указаний алгоритма соответствует порядку их появления, если не говорится иначе. Когда есть нужда обусловить выполнение команд, в алгоритм включается команда управления - команда выполнения с условием. Когда требуется повторное выполнение указаний, в алгоритм включается команда управления - команда повторного выполнения с условием.

Форма написания алгоритма в этой главе и в следующих главах называется записью псевдокодом. Псевдокод(pseudo-code) алгоритма есть его представление в форме, похожей на язык программирования, т.е. словами и предложениями на вольном языке, но внятно и однозначно.

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

В этой главе мы поставили различные вопросы. У каждого из них появлялся знак вопроса - черный прерывистый или белый. Черный прерывистый вопросительный знак помечает вопрос об этапе или ряде этапов в разработке алгоритма. Белый вопросительный знак отмечает вопрос анализа разработанного алгоритма. По ходу изучения глав мы поставим разнообразные вопросы разработки и вопросы анализа алгоритмов и будем их отмечать этими вопросительными знаками.

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

Дополнительные задачи

1.Осуществи следующий алгоритм и опиши ход его выполнения. Какой результат

будет объявлен в конце этого исполнения?

Умножь на два год твоего рождения

Добавь к результату число 5

Результат умножь на 50

Добавь к результату свой возраст(целое число)

Отними от результата 250

Результат раздели на 100

Объяви результат

2.На столе положены в ряд три карты. На каждой карте написано число. Дан следующий алгоритм:

Сравни число, написанное на левой карте с числом на средней карте

Если число на левой карте больше числа на средней карте то

Поменяй их местами

Сравни число на нынешней средней карте с числом на правой карте

Если число на нынешней средней карте больше числа на правой карте то

Поменяй их местами

a).Опиши ход исполнения алгоритма для исходной точки: 24 2 15 .

b).Опиши ход исполнения алгоритма для исходной точки: 13 24 2 .

c).Опиши ход исполнения алгоритма для исходной точки: 13 2 15 .

d).Какую алгоритмическую задачу решает этот алгоритм?

e).Измени этот алгоритм так, чтобы он преследовал следующую цель: карта с наименьшим числом должна оказаться на правом краю ряда карт.

3.Фабрика помечает каждое свое изделие знаком, который состоит из большой буквы английского алфавита и цифры. Порядок знаков фабрики таков: A0, A1, ... , A9, B0, B1, ... , Z0, ... , Z9. A0 - первый знак в серии, Z9 - последний знак в серии.

a).Какие знаки следуют за А1, за В9, за Z0?

b).Разработай алгоритм чтения не последнего знака и выдачи знака, следующего за ним. Разрешенные к исполнению действия:

*чтение знака(данные - буква и цифра); *вывод буквы; *вывод цифры.

4 классе среди учеников есть одна девочка, остальные - мальчики. Ученики построены в ряд. Девочка не стоит на первом месте в ряду(во главе ряда). Разработай алгоритм, целью которого поставить девочку на первое место в ряду. Разрешенные к исполнению действия: *остановка против ученика, который стоит во главе ряда; *продвижение к следущему в ряду ученику(девочке или мальчику); *перемена местами ученика, против которого ты стоишь, и ученика во главе ряда.

5.На столе дан ряд черных и красных карт числом не менее трех. Черные карты находятся слева от красных. Известно, что число красных карт меньше числа черных карт. Даны две закладки: закладка-1, указывающая на карту на левом краю, и закладка-2, указывающая на карту с правого края. Разрешенные действия описаны в задаче 3. a).Отметь три различные возможные ряда карт. b).Дан нижеследующий алгоритм, цель которого - расположить все красные карты слева от всех черных. Дополни этот алгоритм:

До тех пор пока ______________________________________________ выполняй

Поменяй местами карты, на которые указывают закладки

Установи закладку-1 у следующей карты справа

Установи закладку-2 у следующей карты слева

 

Глава 3. Основная вычислительная модель

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

В первой главе мы познакомились с вычислительной машиной. Во второй главе увидели первые алгоритмы, которые не предназначены к выполнению на компьютере. В этой главе мы узнаем алгоритмы, предназначенные для исполнения на компьютере. Эти алгоритмы состоят из кирпичиков основной вычислительной модели, в которой определены способ хранения данных и команды, выполняющие ввод, вывод и операции вычисления. Кирпичики основной вычислительной модели будут представлены через решение различных алгоритмических задач. В каждой задаче будет описываться требуемый вывод для данного ввода. Ввод это исходная точка задачи, а вывод - цель. Каждый разрабатываемый алгоритм будет описываться в словесной форме, подобно описаниям из главы 2, а после этого будет представлена его реализация посредством программы на языке Паскаль.

В параграфе 3.1 мы познакомимся со средствами хранения данных в компьютере и командами выполнения ввода и вывода; в параграфе 3.2 узнаем команды выполнения вычислений; в параграфе 3.3 детализируем способ слежения за ходом выполнения алгоритма, а в параграфе 3.4 научимся различать различные типы значений, хранимых в компьютере.

3.1.Переменная, команда ввода и команда вывода

Компьютер печатает или выводит на экран сообщения с помощью устройств вывода. В первой главе мы познакомились с двумя распространенными устройствами вывода: принтером и экраном. При решении следующей задачи мы увидим алгоритм вывода слова на экран. Алгоритм реализуется программой на Паскале, первой в этой главе.

Назначение следующей задачи и ее решения: представление команды вывода(строки) и первой программы, содержащей один оператор,

Задача 1. Разработай алгоритм, на выводе которого было бы слово Привет, и реализуй его посредством компьютерной программы на языке Паскаль.

Простой алгоритм решения этой задачи содержит всего одно указание вывода:

Выведи на экран слово Привет

Реализуем этот алгоритм с помощью компьютерной программы на языке Паскаль. Реализация на Паскале команды вывода выполняется оператором writeln:

writeln(Привет)

Добавим к этому оператору writeln необходимые части для получения полной программы на Паскале. Программа, реализующая алгоритм решения нашей задачи будет такой:

program Hello (input, output);

{ Вывод слова Привет }

begin

writeln('Привет')

end.

Результатом исполнения(прогона) программы будет вывод на экран слова Привет

Аналогично, результатом выполнения программы с оператором вывода

writeln('Привет и до свидания') будет(на экране) Привет и до свидания.

Конец решения задачи 1

Представим понятия, с которыми мы познакомились, решая задачу 1. Мы разработали короткий алгоритм и реализовали его на Паскале. Программа Паскаля содержит заголовок и операторы. Заголовок программы на Паскале начинается со слова program (программа - по-английски), за ним следует имя

 

Программы и в конце заключенные в скобки слова input (по-английски - ввод) и output (по-английски - вывод). Заголовок программы отделен от остальной программы точкой с запятой. Имя программы выбирается программистом. Слова input и output извещают компьютер о том, что программа содержит ввод/вывод. (Примечание переводчика. Имена input и output необязательны и впредь будут опускаться).

Операторы программы есть команды компьютеру для исполнения, они возникают между словами begin и end. Справа от end ставится точка, обозначающая конец программы. Оператор writeln(...) в Паскале является оператором вывода, указывающим компьютеру вывести на экран строку между апострофами. Одиночные апострофы отмечают в Паскале строку(символов). Обрати внимание на использование одиночного апострофа, а не кавычек двойного апострофа ().Суффикс ln в конце слова writeln означает переход на новую строку после вывода.

В программу можно включать примечания. Примечание записывается между открывающей и закрывающей фигурными скобками. Оно предназначено и программисту и пользователю программы, но не компьютеру. Примечания используются для документирования программы, чтобы облегчить ее читабельность. Нами принято включать после заголовка программы примечание, описывающее цель программы. В этом примечании описывается ввод программы (как - увидим в дальнейшем) и ее вывод.

Имя программы, решающей задачу 1 есть Hello. Программа Hello содержит один оператор и одно примечание.

?Вопрос 3.1. Заполни примечание, описывающее цель следующей программы:

program Find;

{ . . }

begin

writeln( Что здесь выполняется?);

end

?Вопрос 3.2. Разработай алгоритм, целью которого является вывод сообщения Первая программа, и реализуй его с помощью программы на Паскале.

Компьютер вводит данные с помощью устройств ввода. Распространенным устройством ввода является клавиатура. Решая следующую задачу, мы увидим алгоритм ввода данных и их вывода на экран.

Назначение следующей задачи и ее решения: представление понятия переменной, использование переменных, команда ввода, команда вывода переменных, программа, включающая раздел деклараций и несколько переменных, первое слежение за ходом исполнения программы.

Задача 2. Разработай алгоритм, который вводит два целых числа (разделенных на вводе пробелом), а вывод его есть сообщение Два введенных числа:, под которым два введенных числа. Реализуй алгоритм посредством программы.

Обрати внимание, что возможно большое число различных вводов, которыми может быть любая пара целых чисел, например, 5 и 2 или 47 и 12. Нам необходимо сформулировать и реализовать алгоритм, у которого любая пара целых чисел может быть вводом, выдать на экран требуемое сообщение и введенную пару чисел.

Поделим сначала задание требуемого алгоритма на три подзадания:

Ввод двух целых чисел

Вывод на экран сообщения Два введеных числа:

Вывод на экран новой строки из двух введенных чисел

Приступим к написанию алгоритма, предназначенного к реализации в виде компьютерной программы.

?! На секунду задумаемся ... Как введет компьютер заданные числа и где будет их хранить?

Компьютер вводит данные через средства ввода. Вводимые данные хранятся в ячейках памяти, называемых ячейками переменных или кратко - переменными. Переменная(variable) есть ячейка памяти, которая позволяет хранить в ней значение и читать значение, хранящееся в ней, в ходе выполнения алгоритма. Хранящееся значение переменной и есть значение переменной. Обращение к переменной осуществляется по имени, которое есть имя переменной.

Ввод, определенный в задаче, составляют два отдельных данных(числа). Поскольку у нас есть два данных, определим две переменных Num1 и Num2 и будем хранить каждое данное в отдельной переменной:

Num1 - будет хранить первое данное ввода.

Num2 - будет хранить второе данное ввода.

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

Введи два целых числа в переменные Num1, Num2

Выведи на экран сообщение 'Два введенных числа:'

Выведи на экран в новую строку значения переменных Num1, Num2

Реализуем теперь этот алгоритм с помощью программы Паскаля. Первое указание алгоритма реализуется командой readln:

readln(Num1,Num2)

Указание вывода на экран сообщения реализуется так:

writeln('Два введенных числа:');

Указание вывода на экран значений, хранящихся в переменных Num1 и Num2 реализуется так:

writeln(Num1, Num2);

Операторы программы, разработанные до сих пор:

readln(Num1,Num2);

writeln('Два введенных числа:');

writeln(Num1,Num2)

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

В этой главе мы полагаем, что устройство ввода это клавиатура, а устройство вывода - экран. В ходе исполнения программы компьютер будет ждать набора данных ввода, когда придет к выполнению оператора readln. Чтобы пользователь (прогоняющий программу) знал, когда ему надо набрать два данных(два целых числа), предварим оператор readln выводом на экран сообщения, что надо эти данные набрать:

writeln('Набери два целых числа через пробел и Enter!');

readln(Num1,Num2);

writeln('Два введенных числа:');

writeln(Num1,Num2)

Обрати внимание - пара букв ln, присоединенная к словам write и read, обозначает переход к новой строке после выполнения каждого оператора вывода(writeln) и после выполнения каждого оператора ввода(readln).

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

В Паскале необходимо объявлять(декларировать) все переменные программы. Объявление переменных начинается со слова var , оно располагается между заголовком программы и словом begin. Переменная объявлется посредством упоминания ее имени и указания типа значения, которое в ней хранится. В переменные Num1 и Num2 помещаются целые числа. Поэтому эти переменные будут провозглашены как переменные типа integer(целый).

Добавим около каждого объявления переменной примечание, описывающее ее назначение. Нижеследующая программа на Паскале будет реализацией алгоритма решения нашей задачи:

program ReadWrite;

{ Ввод: два целых числа. Вывод: сообщение и два введенных числа. }

var

Num1: integer; { Будет хранить первое данное ввода }

Num2: integer; { Будет хранить второе данное ввода }

begin

writeln('Набери два целых числа через пробел и Enter!');

readln(Num1,Num2);

writeln('Два введенных числа:');

writeln(Num1,Num2) { Надо: writelen(Num1, ' ' ,Num2) }

end.

Проследим за ходом исполнения(прогона) программы ReadWrite для заданного ввода. Когда компьютеру задается строка данных, он вводит данные в строке слева направо. Пусть ввод во время исполнения программы будет 10 20. Левое число 10 будет введено первым, а правое 20 - вторым. Диалог между компьютером и пользователем во время исполнения программы будет выглядеть на экране так:

Компьютер выведет на экран: Набери два целых числа через пробел и Enter!

Пользователь введет данные: 10 20

Компьютер выведет на экран: Два введенных числа:

Компьютер выведет на экран: 10 20

Конец решения задачи 2

Детализируем слежение за ходом выполнения, рассмотрвая память в дополнение к слежению за вводом и выводом. До начала выполнения операторов программы выделяются две ячейки памяти для переменных Num1 и Num2. Значения, хранящиеся в ячейках памяти во время их выделения, заранее неизвестны. Представим себе переменные в виде коробок с именами Num1 и Num2 и обозначим через ? заранее неизвестные значения внутри коробки:

Num1: ? Num2: ?

Компьютер исполнит первый оператор программы и выведет на экран сообщение:

Набери два целых числа через пробел и Enter!

Сразу после этого компьютер исполнит второй оператор - readln. Компьютер подождет ввода от пользователя; пользователь наберет число 10 и после пробела число 20, а в конце нажмет на клавишу <Enter>; компьютер введет два данных и поместит их в две переменные: Num1: 10 Num2: 20

После запоминания в переменных компьютер выполнит следующий, третий в программе, оператор - выведет на экран сообщение:

Два введенных числа:

И в конце компьютер исполнит четвертый(последний в программе) оператор - выведет на экран значения переменных: 10 20

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

Проследим за исполнением программы для ввода 2 1

Компьютер выведет на экран: Набери два целых числа через пробел и Enter!

Пользователь введет данные: 2 1

Компьютер выведет на экран: Два введенных числа:

Компьютер выведет на экран: 2 1

И при этом исполнении программы сначала будут выделены две ячейки памяти для двух переменных программы, и до выполнения оператора readln их значения будут неизвестны(не определены). Благодаря исполнению оператора readln значения переменных поместятся: 2 в Num1 и 1 в Num2. Эти значения будут хранится в указанных переменных до завершения исполнения программы.

Представим понятия, с которыми мы познакомились в ходе решения примера - задачи 2. При ее решении мы пользовались переменными для хранения данных ввода. Введенные в компьютер данные хранятся в ячейках памяти, называемых переменными. Переменная(variable) это ячейка памяти, в которой по ходу программы можно хранить значение и читать хранящееся в ней значение. В переменной хранится значение переменной. Обращение к переменной осуществляется по имени переменной. У каждой переменной определен тип. Тип переменной определяет вид значения, которрое можно хранить в ней (например, целое число). Название переменная вытекает из того, что по ходу программы можно вновь и вновь изменять ее значение(как - увидим далее).

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

Обрати внимание на имена, которые в программе ReadWrite даны переменным. Мы настаиваем на выборе имени для переменной в соответствии с ее функцией в программе. Можно рассматривать использование переменной как использование кассеты, на которой хранится единственное значение. Во время выполнения операции записи на нее записывается и хранитсятся значение взамен того, которое на ней было; а во время выполнения операции вывода хранимое на касете значение читается и является выводом. Чтение значения не изменяет содержимого кассеты(т.е. значение на кассете остается прежним).

В программе на Паскале каждая из ее переменных объявляется в явной форме. Провозглашение переменных появляется между заголовком программы и словом begin, которое отмечает начало раздела операторов программы. Провозглашение переменных начинается словом var(сокращение variable), за которым идут их объявления. Каждое объявление содержит обозначение имени переменной, затем идет знак двоеточия, обозначение типа переменной и в конце - точка с запятой. После точки с запятой мы документируем назначение переменной в примечании, которое предназначено исключительно читающему программу, но не компьютеру.

В алгоритм решения задачи 2 мы включили команду ввода данных в переменные и команду вывода на экран значений переменных. Команды ввода и вывода реализуются в программе на Паскале операторами readln и writeln. Команда readln (перечень переменных) в Паскале есть оператор ввода, указывающий на ввод данных и их сохранение в переменных, отмеченных в перечне, заключенном в скобки. Выполнение оператора приводит к занесению каждого данного на вводе в отдельную переменную. Первое данное на вводе заносится в самую левую переменную перечня в скобках, следующее данное ввода помещается в следующую переменную в перечне и т.д.

Команда writeln (перечень переменных) в Паскале есть оператор, указывающий на вывод значений переменных, отмеченных в перечне, заключенном в скобки. Выполнение оператора приводит к тому, что значение, хранимое в самой левой переменной перечня в скобках, выводится на экран первым, значение, хранимое в следующей переменной перечня выводится справа от предыдущего и т.д.

Разделение следующих один за другим операторов программы Паскаля осуществляется знаком точка с запятой. Операторы программы выполняютя последовательно в порядке их появления в программе.

?Вопрос 3.2. a).Опиши диалог между пользователем и компьютером во время выполнения программы ReadWrite, решающей задачу 2, для ввода: 5 10.

b).Опиши диалог между пользователем и компьютером во время выполнения программы ReadWrite, решающей задачу 2, для ввода: 10 5.

c).Какими будут значения, хранящиеся в переменных Num1 и Num2 в самом начале исполнения программы, после выполнения оператора readln и после выполнения оператора writeln, который идет следом.

Напомним снова смысл понятия тип переменной. Тип переменной определяет вид значения, которое может содержать переменная. В первых параграфах этой главы мы будем пользоваться исключительно переменными целого типа, т.е. такими, в которых будут храниться только целые числа, например, -17, 0, 5.

Объявление переменных в программе ReadWrite(решение задачи 2) выгдядит так:

var

Num1: integer; { Будет хранить первое данное ввода }

Num2: integer; { Будет хранить второе данное ввода }

Каждая переменная объявлена как переменная целого типа, ее назначение в программе задокументировано в соответствующем комментарии.

Обрати внимание, мы требуем объвлять каждую переменную в отдельной строке.

?Вопрос 3.4. Выбери две переменных - первую для хранения числа мальчишек в классе, вторую - для хранения числа девочек в классе. Для каждой переменной подбери соответствующее имя и объяви его в Паскале с отмечанием типа. Задукометируй его назначение подходящим комментарием.

Разработка и реализация алгоритма, решающего задачу 2, осуществлена поэтапно; каждый этап отмечен соответствующим знаком(в книге - пазлом).

- исследование различных примеров ввода и связи между вводом и выводом.

- деление алгоритмического задания на подзадания.

- выбор переменных - назначение, имя и тип для каждой переменной.

- формулирование алгоритма.

- написание программы, реализующей алгоритм.

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

?Вопрос 3.5. Поэтапно разработай и реализуй алгоритм, который вводит целое число, а вывод состоит из сообщения Введенное число: , а ниже - само число.

Выполнение команды ввода приводит, как сказано, к уточнению значения переменной, указанной в этой команде. И на Паскале, если, например, программа содержит оператор readln(Num) и в ходе его исполнения будет произведен ввод числа 8, то после исполнения оператора переменная Num будет содержать значение 8 вне зависимости от его значения до действия оператора. А вот выполнение команды вывода некоторой переменной не приводит к уточнению ее значения, но только к копированию значения переменной на устройстве вывода. И на Паскале, если, например, программа содержит оператор writeln(Num), а значение Num равно 8 перед исполнением этого оператора, то оно останется равным 8 и после исполнения(результат есть вывод на экран числа 8).

?Вопрос 3.6. Дана следующая программа:

program InOut; {Программа, поясняющая смысл ввода-вывода }

var Num1: integer;

Num2: integer;

begin

writeln('Набери два целых числа:');

readln(Num1,Num2);

writeln(Num1);

writeln(Num2);

writeln('Набери еще одно целое число:');

readln(Num2);

writeln(Num1,' ',Num2)

end.

a).Опиши диалог между пользователем и компьютером в программе InOut для ввода 2 3 первым оператором readln и ввода 5 вторым readln.

b).Опиши диалог между пользователем и компьютером в программе InOut для ввода 2 5 первым оператором readln и ввода 3 вторым readln.

Напомним, что при выполнении команды ввода с несколькими переменными значения вводятся в переменные в порядке их появления в команде. И в Паскале - выполнение оператора readln (перечень переменных) приведет к тому, что самое левое данное на вводе присваивается самой левой переменной перечня, следующее справа данное - следующей переменной перечня и т.д.

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

Продемонстрируем это слежением за ходом исполнения операторов:

writeln('Набери два целых числа:');

readln(Num1,Num2);

writeln(Num1,' ',Num2);

writeln(Num2,' ',Num1)

Для ввода 1 2 получится такой диалог между пользователем и компьютером:

Компьютер: Набери два целых числа:

Пользователь: 1 2

Компьютер: 1 2

Компьютер: 2 1

Такой же диалог, для того же ввода, будет получен операторами:

writeln('Набери два целых числа:');

readln(Num2,Num1);

writeln(Num2,' ',Num1);

writeln(Num1,' ',Num2)

В ходе выполнения первой группы операторов в переменную Num1 будет введено число 1, а в Num2 - число 2. В ходе выполнения второй группы операторов в переменную Num2 будет введено число 1, а в Num1 - число 2.

Обрати внимание, что порядок ввода данных и вывода их на экран не устанавливается по именам переменных(Num1, Num2), а согласно порядку их появления в операторах ввода и вывода.

?Вопрос 3.7. Поэтапно разработай и реализуй алгоритм, ввод которого состоит из трех целых чисел, а вывод - из двух строк, в каждой по два введенных числа: в первой строке - второе и третье число в порядке их ввода, а во второй - первое и второе число в порядке, обратном порядку ввода.

В команде ввода не следует указывать переменную больше одного раза, т.к. такое действие потребует присвоения различных данных одной переменной. А вот в команде вывода можно указывать одну переменную больше одного раза. Значение этой переменной будет выведено на экран столько раз, сколько раз оно появлялось в команде. И в Паскале - выполнение, например, оператора writeln(Num,' ',Num), когда значение Num равно 5, приведет к выводу 5 5 .

При объявлении переменных программой Паскаля можно декларировать несколько переменных одного типа в перечне, за которым двоеточие и обозначение типа. В перечне переменные отделяются друг от друга запятыми. Мы будем объявлять перечень переменных(вместо того, чтобы объявлять их отдельно) только, когда у переменных подобные назначения. Пример:

var

Num1, Num2, Num3: integer; {Будут содержать три целых числа}

?Вопрос 3.8. Поэтапно разработай и реализуй алгоритм, который вводит три целых числа, составляющих последовательность, а выводит - последовательность из шести чисел, в которой каждое введенное данное повторено число раз, равное его месту на вводе.Например, для<