Информатика, 10 класс К. Ю. Поляков, Е. А. Еремин
 Скачать 0.95 Mb.
|
|
Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 1 Глава 8. Алгоритмизация и программирование. Язык Си § 54. Алгоритм и его свойства Что такое алгоритм Происхождение слова алгоритм связывают с именем учёного аль-Хорезми (перс. ﯽﻣزراﻮﺧ [al-Khwārazmī]), который описал десятичную систему счисления (придуманную в Индии) и предложил правила выполнения арифметических действий с десятичными числами. Алгоритм — это точное описание порядка действий, которые должен выполнить исполнитель для решения задачи. Здесь исполнитель – это устройство или одушевленное существо (человек, способное понять и выполнить команды, составляющие алгоритм. Человек как исполнитель часто действует неформально, по-своему понимая команды. Несмотря на это, ему тоже часто приходится действовать потому или иному алгоритму. Например, рецепт приготовления какого-либо блюда можно считать алгоритмом. На уроках русского языка, выполняя разбор слова или предложения, вы тоже действуете по определенному алгоритму. Многоразличных алгоритмов в математике (постарайтесь вспомнить известные вам. На производстве, рабочий, вытачивая деталь в соответствии с чертежом, действует по алгоритму, который разработал технолог. И таких примеров может быть множество. В информатике рассматривают только формальных исполнителей, которые не понимают и не могут понять) смысл команд. К этому типу относятся все технические устройства, в том числе и компьютер. Каждый формальный исполнитель обладает собственной системой команд. В алгоритмах для такого исполнителя нельзя использовать команды, которых нет в его системе команд. Свойства алгоритма • Дискретность — алгоритм состоит из отдельных команд (шагов, каждая из которых выполняется ограниченное время. • Детерминированность (определенность — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат. • Понятность — алгоритм содержит только команды, входящие в систему команд исполнителя, для которого он предназначен. • Конечность (результативность — для корректного набора данных алгоритм должен завершаться через конечное время с вполне определенным результатом (результатом может быть сообщение о том, что задача не имеет решений. • Корректность — для допустимых исходных данных алгоритм должен приводить к правильному результату Массовость – алгоритм, как правило, предназначен для решения множества однотипных задач с различными исходными данными. Эти свойства неравноправны. Дискретность, детерминированность и понятность – фундаментальные свойства алгоритма, то есть ими обладают все алгоритмы для формальных исполнителей. Остальные свойства можно рассматривать как требования к правильному алгоритму. Иными словами, алгоритм получает на вход некоторый дискретный входной объект (например, набор чисел или слово) и обрабатывает входной объект по шагам (дискретно, строя промежуточные дискретные объекты. Этот процесс может закончиться или не закончиться. Если процесс выполнения алгоритма заканчивается, то объект, полученный на последнем шаге работы, является результатом работы алгоритма приданном входе. Если процесс выполнения не заканчивается, говорят, что алгоритм зациклился. В этом случае результат его работы не определен. Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 2 Способы записи алгоритмов Алгоритмы можно записывать разными способами • на естественном языке обычно такой способ применяют, записывая основные идеи алгоритма на начальном этапе • на псевдокоде, так называется смешанная запись, в которой используется естественный языки операторы какого-либо языка программирования в сравнении с предыдущим вариантом такая запись гораздо более строгая • в виде блок-схемы (графическая запись • в виде программы на каком-либо языке программирования. Из всех перечисленных здесь способов мы будем использовать два псевдокод и запись алгоритма в виде программы на двух языках программирования, Си С. 1. Что такое алгоритм 2. Что такое исполнитель 3. Чем отличаются формальные и неформальные исполнители 4. Что такое система команд исполнителя Придумайте исполнителя с некоторой системой команд. 5. Перечислите и объясните свойства алгоритма. 6. Какие существуют способы записи алгоритмов Какие из них, по вашему мнению, чаще применяются на практике Почему § 55. Простейшие программы Пустая программа Пустая программа – это программа, которая ничего не делает, но удовлетворяет требованиям выбранного языка программирования. Она полезна, прежде всего, для того, чтобы понять общую структуру программы. main() { // это основная программа /* здесь записывают операторы */ } Язык C++ основан на С, поэтому в данном случае программы на C и C++ выглядят одинаково. Если же они отличаются, мы будем слева приводить программу на языке C, а справа – эквивалентную программу на языке C++. Основная программа всегда называется именем main (от англ. main – основной, главный. Пустые скобки означают, что она не принимает никаких дополнительных данных (параметров) от пользователя. Тело (основная часть) программы ограничено фигурными скобками. Между ними записывают операторы – команды языка программирования. Всё, что следует после символов // до конца строки, это комментарии – пояснения, которые не обрабатываются транслятором. Комментарий можно ограничивать парами символов /* ив этом случае комментарий может занимать несколько строк. Вывод текста на экран Напишем программу, которая выводит на экран такие строки 2+2=? Ответ 4 Вот как она выглядит #include main() #include using namespace std; ? Контрольные вопросы Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 3 22.10.2015 { printf( "2+" ); printf( "2=?\n" ); Ответ 4" ); getchar(); } main() { cout << "2+" ; cout << "2=?\n" ; cout << Ответ 4" ; cin.get(); } Перед заголовком основной программы добавились строки, начинающиеся с символов #include (от англ. include – включить. Это команды (инструкции, директивы) для препроцессора – программы, которая обрабатывает текст нашей программы до того, как за него примется транслятор, генерирующий машинные коды. С помощью команд #include в программу включаются заголовочные файлы, в которых описаны стандартные функции языка программирования и дополнительных библиотек. В программе на языке C мы используем две функции printf (вывод на экран) и getchar ожидание нажатия клавиши и ввод символа. Обе функции описаны в файле stdio.h, который поставляется со средой программирования. Как понятно из программы, функция printf выводит на экран текст, заключенный в кавычки. Сочетание « \n» внутри строки на самом деле обозначает один специальный управляющий символ – переход на новую строку. Задача функции getchar (в этой программе) – организовать задержку в конце работы программы до нажатия любой клавиши, чтобы мы смогли увидеть результаты и окно ввода- вывода (так называемое консольное окно) не закрылось бы автоматически сразу после окончания работы программы. В программе на C++ вводи вывод организован по-другому. Подключается заголовочный файл iostream (от англ. input output stream – поток ввода и вывода. Поток вывода (то есть, последовательность символов, выводимая на экран) называется cout (от англ. console output – вывод на консоль, а поток ввода (последовательность символов, вводимая с клавиатуры) имеет имя cin (от англ. console input – ввод с консоли. Справа от оператора << записывают данные, которые нужно вывести на экран, в нашей программе – это строки в кавычках. Можно записывать несколько операторов << водной команде, например cout << "2+" << "2=?" << "\n" << Ответ 4" ; Вместо символов \n для перехода на новую строку можно использовать специальную инструкцию (манипулятор) endl: cout << "2+" << "2=?" << endl << Ответ 4" ; Обратите внимание, что любая команда заканчивается точкой с запятой. Последняя инструкция cin.get() в программе на C++ обеспечивает задержку до нажатия на клавишу Enter. Дословно она означает получить символы из входного потока и ничего сними не делать. Строчка using namespace std; говорит о том, что будет использоваться пространство имен std, в котором определена вся стандартная библиотека языка C++. Здесь пространство имен – это область действия объектов программы, в том числе переменных. В области std описаны стандартные потоки ввода и вывода с именами cin и cout. Если не объявлять используемое пространство имен, нужно было бы явно указывать его при любом обращении к этим потокам #include main() { std::cout << "2+" ; std::cout << "2=?\n" ; std::cout << Ответ 4" ; std::cin.get(); } 1 Эта функция также определяет код нажатой клавиши. Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 4 Переменные Напишем программу, которая выполняет сложение двух чисел 1) запрашивает у пользователя два целых числа 2) складывает их 3) выводит результат сложения. Программу на псевдокоде (смеси русского языка и языка C) можно записать так main() { // ввести два числа // сложить их // вывести результат } Компьютер не может выполнить псевдокод, потому что команд ввести два числа и ей подобных, которые записаны в комментариях, нет в его системе команд. Поэтому нам нужно расшифровать все такие команды через операторы языка программирования. В отличие от предыдущих задач, данные нужно хранить в памяти. Для этого используют переменные. Переменная — это величина, которая имеет имя, тип и значение. Значение переменной может изменяться вовремя выполнения программы. Переменная (как и любая ячейка памяти) может хранить только одно значение. При записи вне нового значения старое стирается и его уже никак не восстановить. Переменные в программе необходимо объявлять. При объявлении указывается тип переменной и ее имя (идентификатор. Значение переменной сразу после объявления неопределенно переменной выделяется некоторая область памяти, и там могло быть до этого записано любое число. Вот так объявляются целочисленные переменные (в которых могут храниться только целые значения) с именами a, b и c: int a, b, c; Описание переменных начинается с ключевого слова, которое определяет тип переменных, а после него записывают список имён переменных. В данном случае указан тип int (от англ. integer – целочисленный. В именах переменных можно использовать латинские буквы (строчные и заглавные буквы различаются, цифры (но имя не может начинаться с цифры, иначе транслятору будет сложно различить, где начинается имя, а где – число) и знак подчеркивания «_». Желательно давать переменным говорящие имена, чтобы можно было сразу понять, какую роль выполняет таили иная переменная. Тип переменной нужен для того, чтобы • определить область допустимых значений переменной • определить допустимые операции с переменной • определить, какой объем памяти нужно выделить переменной ив каком формате будут храниться данные (вспомните, что целые и вещественные числа хранятся по-разному, см. главу 4); • предотвратить случайные ошибки (опечатки в именах переменных. После объявления переменной её значение не определено (в ней записан мусор – неизвестное значение) и использовать её нельзя. Если нужно, прямо при объявлении можно задать начальные значения переменных int a = 1, b, c = 123; В этом примере переменной b не присваивается начальное значение, в ней содержится мусор. Приведем полную программу сложения двух чисел #include main() { int a, b, c; scanf( "%d%d" , &a, &b); #include using namespace std; main() { int a, b, c; Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 5 22.10.2015 c = a + b; printf( "%d" , c); getchar(); } cin >> a >> b; c = a + b; cout << c; cin.get(); cin.get(); } В языке C ввод данных выполняет функция scanf (от англ. scan formatted – сканирование по формату. В скобках на первом месте записывают формат ввода – символьную строку, в которой формат « %d» означает ввести целое число (для других типов данных используют другие форматы, о которых речь пойдет далее. Далее через запятую записывают адреса переменных, в которые нужно записать введенные значения. Для определения адреса переменной используется операция « &». Например, «&a» означает адрес переменной a». Записанная команда ввода означает ввести два целых числа, первое записать в переменную a, второе – в переменную b». В языке C++ ввод данных из входного потока cin записывается значительно проще cin >> a >> b; Вы, наверное, заметили, что команда cin.get() повторяется два раза. Это сделано потому, что при первом вызове она прочитает все, что осталось во входном потоке после записи значения переменной (хотя бы символ новая строка, и при однократном вызове программа не будет ждать нажатия на клавишу Enter. Оператор, содержащий символ « =» – это оператор присваивания, сего помощью изменяют значение переменной. Он выполняется следующим образом вычисляется выражение справа от символа « =», а затем результат записывается в переменную, записанную слева. Поэтому, например, оператор i= i + 1; увеличивает значение переменной i на 1. Часто используется также сокращенная запись i ++; которая обозначает тоже самое. Аналогичная запись для уменьшения значения переменной на 1 выглядит так i --; У приведенной выше программы сложения чисел есть два недостатка 1) перед вводом данных пользователь не знает, что от него требуется (сколько чисел нужно вводить и каких 2) результат выдается в виде числа, которое означает неизвестно что. Хотелось бы, чтобы диалог программы с пользователем выглядел так Введите два целых числа 2 3 2+3=5 Подсказку для ввода вы можете сделать самостоятельно. При выводе результата ситуация несколько усложняется, потому что нужно вывести значения трёх переменных и два символа «+» и «=». Для этого строится список вывода printf( "%d+%d=%d" ,a,b,c); cout << a << "+" << b << "=" << c; Обратите внимание, что имена переменных записаны без кавычек. В программе на C форматная строка содержит как символы для вывода на экран (+, =), таки форматы для вывода данных. Первое значение из списка (значение переменной a) будет выведено там, где в форматной строке записан первый формат %d, то есть, перед знаком «+», второе значение – на месте второго формата %d и т.д. Элементы в списке вывода разделены запятыми. В принципе, можно было бы обойтись и без переменной c, потому что элементом списка вывода может быть арифметическое выражение, которое сразу вычисляется и на экран выводится результат printf( "%d+%d=%d" ,a,b,a+b); cout << a << "+" << b << "=" << a+b; В обоих языках можно использовать форматный вывод указать общее количество знакомест, отводимое на число. В языке C его записывают в коде формата между знаками « %» и «d», а в языке C++ – при вызове специальной команды-манипулятора setw, которая определена в заголовочном файле iomanip. Например, в результате выполнения команд a = 123 ; printf( "%5d" , a); #include ... Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 6 22.10.2015 a = 123 ; cout << setw( 5 ) << a; значение целой переменной a займет на экране ровно 5 знакомест ◦◦123 Поскольку само число занимает только 3 знакоместа, передним выводятся два пробела, которые обозначены как « ◦». В пределах заданной ширины поля можно выровнять число не только вправо (как по умолчанию, но и влево a = 123 ; printf( "%-5d" , a); #include ... a = 123 ; cout << setw( 5 ) << left << a; В обоих случаях получаем такой результат 123◦◦ 1. Как выдумаете, почему основная программа всегда называется main? 2. Что такое идентификатор 3. Как записываются комментарии Подумайте, как комментирование можно использовать при поиске ошибок в алгоритме 4. Сравните операторы вывода в C и C++. Как выполняется переход на новую строку 5. Что такое переменная Как выдумаете, зачем нужно объявлять переменные 6. Каковы правила построения имён переменных 7. Зачем нужен тип переменной 8. Какое значение записано в переменной сразу после объявления Можно ли его использовать. Как задать начальные значения переменных 10. Что такое оператор присваивания 11. Почему желательно выводить на экран подсказку перед вводом данных 12. Подумайте, когда можно вычислять результат прямо в операторе вывода, а когда нужно заводить отдельную переменную. 13. Что такое форматный вывод Как выдумаете, где он может быть полезен 1. Используя оператор вывода, постройте на экране следующие рисунки из символов Ж Ж Ж Ж Ж Ж Ж ЖЖЖ ЖЖ Ж Ж ЖЖ ЖЖ ЖЖ ЖЖЖЖЖ ЖЖЖЖЖЖ ЖЖЖЖЖ ЖЖЖ ЖЖЖЖЖ Ж Ж ЖЖ Ж Ж Ж ЖЖЖЖЖ ЖЖ ЖЖ ЖЖЖ Ж ЖЖЖЖЖ ЖЖЖЖЖЖЖ Ж Ж 2. Выберите правильные имена переменных 1 Vasya СУ @mail_ru m11 Петя СУ lenta.ru 1m Митин брат _27 "Pes barbos" m 1 Quo vadis СУ) Ладья 3. Пусть a и b – целые переменные. Что будет выведено в результате работы фрагмента программы а) int a = 5 , b = 3 ; printf( "%d=Z(%d)" , a, b); int a = 5 , b = 3 ; cout << a << "=Z(" << b << ")" ); б) int a = 5 , b = 3 ; printf( "Z(a)=(b)" ); int a = 5 , b = 3 ; cout << "Z(a)=(b)" ; в) int a = 5 , b = 3 ; printf( "Z(%d)=(%d)" ,a,a+b); int a = 5 , b = 3 ; cout << "Z(" << a << ")=( " << a+b << ")" ; ? Контрольные вопросы Задачи и задания Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 7 22.10.2015 4. Запишите оператор для вывода значений целых переменных a = 5 ив формате а) 3+5=? б) Z(5)=F(3) в) a=5; b=3; г) Ответ (5;3) |