Основным в процессе программирования является разработка алгоритма. Это один из наиболее сложных этапов решения задачи с использованием ЭВМ. В начале обучения программированию, на наш взгляд, целесообразно не привязываться сразу к какому-либо языку, разрабатывать алгоритмы без записи на ЯПВУ, а, например, с помощью блок-схем или иным аналогичным способом. После такой «чистой» алгоритмизации учащимся или студентам проще перейти к записи того же алгоритма на определённом языке программирования. В настоящей публикации продемонстрирован именно такой подход.
Напомним, что основными алгоритмическими структурами (ОАС) являются следование, развилка и цикл. В более сложных случаях используются суперпозиции (вложения) ОАС.
Ниже приведены графические обозначения (обозначения на блок-схемах) ОАС.
| Структура “следование” | Полная развилка | Неполная развилка |
| Цикл с предусловие (цикл ПОКА) | Цикл с постусловием (цикл ДО) | Цикл с параметром |
На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.
Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.
В примерах мы будем использовать запись алгоритмов с помощью блок-схем и словесное описание.
Линейные алгоритмы
Простейшие задачи имеют линейный алгоритм решения. Это означает, что он не содержит проверок условий и повторений.
Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?
1. Ввести v1, v2, v3, t1, t2, t3. 2. S1 := v1 * t1. 3. S2 := v2 * t2. 4. S3 := v3 * t3. 5. S := S1 + S2 + S3. 6. Вывести значение S. 7. Конец. |
Для проверки работоспособности алгоритма необходимо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результатом ручного счета.
Пример 2. Дано натуральное трехзначное число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: «число n кратно каждой своей цифре», и ЛОЖЬ — в противном случае.
1. Ввести число n 2. A := n mod 10 {разряд единиц} 3. B := n div 100 {разряд сотен} 4. C := n div 10 mod 10 {десятки} 5. L := (n mod A=0) and (n mod B=0) and (n mod C=0) 6. Вывод L 7. Конец |
На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.
Развилка
Достаточно часто то или иное действие должно быть выполнено в зависимости от значения логического выражения, выступающего в качестве условия. В таких случаях используется развилка.
Пример 1. Вычислить значение функции
1. Ввести x. 2. Если x£–12, то y:=–x2 3. Если x<0, то y:=x4 4. y := x–2 5. Вывести y 6. Конец |
При тестировании алгоритмов с развилкой необходимо подбирать такие исходные данные, чтобы можно было проверить все ветви. В приведенном выше примере должно быть по крайней мере три тестовых набора.
Пример 2. Дано натуральное число n. Если число нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое число со знаком), удвоить его, иначе — оставить без изменения.
Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.
1. Ввести число n 2. Если число n нечетное и меньше 16384, то n := n * 2 3. Вывод n 4. Конец |
Рассмотренный пример иллюстрирует неполную развилку. Также следует отметить, здесь логическое выражение, являющееся условием, содержит 2 операнда.
Циклы
Если какие-либо операторы необходимо выполнить несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Пример 1. Подсчитать количество нечетных цифр в записи натурального числа n.
Идея решения. Из заданного числа выбирать из младшего разряда цифру за цифрой до тех пор, пока оно не исчерпается, т.е. станет равным нулю. Каждую нечётную цифру учитывать.
1. Ввести число n 2. K := 0 {подготавливаем счётчик} 3. Если n = 0, переход к п. 7 4. Если n mod 10 mod 2 = 1, то K := K +1 5. n := n div 10 6. Переход к п. 3 7. Вывод K 8. Конец |
Задача решена двумя способами. Слева решение оформлено с использованием цикла с предусловием, справа — с постусловием.
Пример 2. Дана последовательность, общий член которой определяется формулой
Вычислить при n>2 сумму тех ее членов, которые больше заданного числа e.
При решении задачи находится очередной член последовательно и, если он больше e, добавляется к сумме.
1. Ввестиe 2. S := 0 3. A := 1/4 4. n := 3 5. Сравнить А с e. Если A>=e, переход к п. 10 6. S := S + A 7. A := (n-1)/(n*n) 8. n := n + 1 9. Переход к п. 5 10. Вывод S 11. Конец |
В рассмотренных выше примерах количество повторений заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во втором — от числа e.
В тех же случая, когда количество шагов известно из условия задачи, проще и предпочтительней использовать цикл с параметром.
Пример 3. Найти произведение первых k натуральных чисел, кратных трём.
При составлении алгоритма учтем, что первое натуральное число, кратное 3, есть тройка, а все последующие больше предыдущего на 3.
1. Ввод k 2. P := 1 {здесь накапливаем произведение} 3. T := 0 {здесь будут числа, кратные 3} 4. I := 1 5. Если I > k, переход к п. 10 6. T := T + 3 7. P := P * T 8. I := I + 1 9. Перейти к п. 5 10. Вывод P 11. Конец |
Другие примеры будут записаны уже на ЯПВУ. В настоящей же публикации предпринята попытка продемонстрировать, что изучение программирования разумно начинать собственно с разработки алгоритмов, не акцентируя первоначально внимания на записи алгоритма на том или ином языке программирования. В то же время автор, являясь сторонником структурного подхода к программированию, предлагает придерживаться этого подхода и при программировании на уровне блок-схем.
www.ronl.ru
Основным в процессе программирования является разработка алгоритма. Это один из наиболее сложных этапов решения задачи с использованием ЭВМ. В начале обучения программированию, на наш взгляд, целесообразно не привязываться сразу к какому-либо языку, разрабатывать алгоритмы без записи на ЯПВУ, а, например, с помощью блок-схем или иным аналогичным способом. После такой «чистой» алгоритмизации учащимся или студентам проще перейти к записи того же алгоритма на определённом языке программирования. В настоящей публикации продемонстрирован именно такой подход.
Напомним, что основными алгоритмическими структурами (ОАС) являются следование, развилка и цикл. В более сложных случаях используются суперпозиции (вложения) ОАС.
Ниже приведены графические обозначения (обозначения на блок-схемах) ОАС.
| Структура “следование” | Полная развилка | Неполная развилка |
| Цикл с предусловие (цикл ПОКА) | Цикл с постусловием (цикл ДО) | Цикл с параметром |
На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.
Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.
В примерах мы будем использовать запись алгоритмов с помощью блок-схем и словесное описание.
Линейные алгоритмы
Простейшие задачи имеют линейный алгоритм решения. Это означает, что он не содержит проверок условий и повторений.
Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?
1. Ввести v1, v2, v3, t1, t2, t3. 2. S1 := v1 * t1. 3. S2 := v2 * t2. 4. S3 := v3 * t3. 5. S := S1 + S2 + S3. 6. Вывести значение S. 7. Конец. |
Для проверки работоспособности алгоритма необходимо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результатом ручного счета.
Пример 2. Дано натуральное трехзначное число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: «число n кратно каждой своей цифре», и ЛОЖЬ — в противном случае.
1. Ввести число n 2. A := n mod 10 {разряд единиц} 3. B := n div 100 {разряд сотен} 4. C := n div 10 mod 10 {десятки} 5. L := (n mod A=0) and (n mod B=0) and (n mod C=0) 6. Вывод L 7. Конец |
На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.
Развилка
Достаточно часто то или иное действие должно быть выполнено в зависимости от значения логического выражения, выступающего в качестве условия. В таких случаях используется развилка.
Пример 1. Вычислить значение функции
1. Ввести x. 2. Если x£–12, то y:=–x2 3. Если x<0, то y:=x4 4. y := x–2 5. Вывести y 6. Конец |
При тестировании алгоритмов с развилкой необходимо подбирать такие исходные данные, чтобы можно было проверить все ветви. В приведенном выше примере должно быть по крайней мере три тестовых набора.
Пример 2. Дано натуральное число n. Если число нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое число со знаком), удвоить его, иначе — оставить без изменения.
Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.
1. Ввести число n 2. Если число n нечетное и меньше 16384, то n := n * 2 3. Вывод n 4. Конец |
Рассмотренный пример иллюстрирует неполную развилку. Также следует отметить, здесь логическое выражение, являющееся условием, содержит 2 операнда.
Циклы
Если какие-либо операторы необходимо выполнить несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Пример 1. Подсчитать количество нечетных цифр в записи натурального числа n.
Идея решения. Из заданного числа выбирать из младшего разряда цифру за цифрой до тех пор, пока оно не исчерпается, т.е. станет равным нулю. Каждую нечётную цифру учитывать.
1. Ввести число n 2. K := 0 {подготавливаем счётчик} 3. Если n = 0, переход к п. 7 4. Если n mod 10 mod 2 = 1, то K := K +1 5. n := n div 10 6. Переход к п. 3 7. Вывод K 8. Конец |
Задача решена двумя способами. Слева решение оформлено с использованием цикла с предусловием, справа — с постусловием.
Пример 2. Дана последовательность, общий член которой определяется формулой
Вычислить при n>2 сумму тех ее членов, которые больше заданного числа e.
При решении задачи находится очередной член последовательно и, если он больше e, добавляется к сумме.
1. Ввестиe 2. S := 0 3. A := 1/4 4. n := 3 5. Сравнить А с e. Если A>=e, переход к п. 10 6. S := S + A 7. A := (n-1)/(n*n) 8. n := n + 1 9. Переход к п. 5 10. Вывод S 11. Конец |
В рассмотренных выше примерах количество повторений заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во втором — от числа e.
В тех же случая, когда количество шагов известно из условия задачи, проще и предпочтительней использовать цикл с параметром.
Пример 3. Найти произведение первых k натуральных чисел, кратных трём.
При составлении алгоритма учтем, что первое натуральное число, кратное 3, есть тройка, а все последующие больше предыдущего на 3.
1. Ввод k 2. P := 1 {здесь накапливаем произведение} 3. T := 0 {здесь будут числа, кратные 3} 4. I := 1 5. Если I > k, переход к п. 10 6. T := T + 3 7. P := P * T 8. I := I + 1 9. Перейти к п. 5 10. Вывод P 11. Конец |
Другие примеры будут записаны уже на ЯПВУ. В настоящей же публикации предпринята попытка продемонстрировать, что изучение программирования разумно начинать собственно с разработки алгоритмов, не акцентируя первоначально внимания на записи алгоритма на том или ином языке программирования. В то же время автор, являясь сторонником структурного подхода к программированию, предлагает придерживаться этого подхода и при программировании на уровне блок-схем.
www.ronl.ru
Реферат на тему:
Алгори́тм, от имени учёного аль-Хорезми (перс. خوارزمی [al-Khwārazmī]) — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.
Ранее часто писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм Маркова).
Часто в качестве исполнителя выступает некоторый механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.
Единого «истинного» определения понятия «алгоритм» нет.
«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
«Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов».
«Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».
«Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи».
«Алгоритм — это некоторый конечный набор рассчитанных на определённого исполнителя операций в результате выполнения которых через определённое число шагов может быть достигнута поставленная цель или решена задача определённого типа».
«Алгоритм — это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».
«Алгоритм — это точная, однозначная, конечная последовательность действий, которую должен выполнить пользователь для достижения конкретной цели либо для решения конкретной задачи или группы задач».
«Алгоритм — это точное предписание, которое задаёт вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемым этим исходным данным результата».
«Алгоритм — это описание последовательности действий, которое ведёт к конечному результату».[]
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
Современное формальное определение алгоритма было дано в 30—50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.
Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритмы о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра (алгебра — аль-джебр).
Таким образом, мы видим, что латинизированное имя среднеазиатского учёного было вынесено в заглавие книги, и сегодня ни у кого нет сомнений, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.
Одни выводили algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Или же лингвистам больными казались люди, имеющие несчастье заниматься вычислениями? Своё объяснение предлагал и энциклопедический словарь Брокгауза и Ефрона. В нём алгорифм (кстати, до революции использовалось написание алгориѳм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень». Разумеется, эти объяснения вряд ли можно счесть убедительными.
Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.
Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманнской рукописи XIII века, написанной в стихах, читаем:
"Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм».
Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике Algorismus vulgaris, на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (Algus). А в популярной средневековой поэме «Роман о Розе» (1275—1280) Жана де Мена «греческий философ Алгус» ставится в один ряд с Платоном, Аристотелем, Евклидом и Птолемеем! Встречался также вариант написания имени Аргус (Argus). И хотя, согласно древнегреческой мифологии, корабль «Арго» был построен Ясоном, именно этому Арго приписывалось строительство корабля.
«Мастер Алгус» (или Аргус) стал в средневековой литературе олицетворением счётного искусства. И в уже упоминавшейся «Романе о розе», и в известной итальянской поэме «Цветок», написанной Дуранте, имеются фрагменты, в которых говорится, что даже «mestre Argus» не сумеет подсчитать, сколько раз ссорятся и мирятся влюблённые. Английский поэт Джефри Чосер в поэме «Книга герцогини» (1369 г.) пишет, что даже «славный счётчик Аргус» (noble countour Argu) не сможет счесть чудовищ, явившихся в кошмарных видениях герою.
Впрочем, греческая версия была не единственной. Мифический Алгор (Algor) именовался то королём Кастилии (Rex quodam Castelliae), то индийским королём, то арабским мудрецом (philosophus Algus nomine Arabicus).
Однако со временем такие объяснения всё менее занимали математиков, и слово algorism (или algorismus), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге, без использования абака. Именно в таком значении оно вошло во многие европейские языки. Например, с пометкой «устар.» оно присутствует в представительном словаре английского языка Webster’s New World Dictionary, изданном в 1957 г.
Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куанси (Gautier de Coincy, 1177—1236) в одном из стихотворений использовал слова algorismus-cipher (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была им достаточно хорошо известна.
Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский (938—1003), ставший в 999 г. папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей алгорисмиков и абацистов (иногда называемых гербекистами), которые пропагандировали использование для вычислений абака вместо арабских цифр. Интересно, что известный французский математик Николя Шюке (Nicolas Chuquet, 1445—1488) в реестр налогоплательщиков города Лиона был вписан как алгорисмик (algoriste). Но прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Западной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», как, например, математика Никколо Тарталью (1500—1557).
Итак, сочинения по искусству счёта назывались Алгоритмами. Из многих сотен можно выделить и такие необычные, как написанный в стихах трактат Carmen de Algorismo (латинское carmen и означает стихи) Александра де Вилла Деи (Alexander de Villa Dei, ум. 1240) или учебник венского астронома и математика Георга Пурбаха (Georg Peurbach, 1423—1461) Opus algorismi jocundissimi («Веселейшее сочинение по алгоритму»).
Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ Николай Орем (Nicolaus Oresme, 1323/25-1382) написал математический трактат Algorismus proportionum («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть Algorithmus linealis, то есть правила счёта на линиях.
Можно обратить внимание на то, что первоначальная форма algorismi спустя какое-то время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид algorism. Позднее и оно, в свою очередь, подверглось искажению, скорее всего, связанному со словом arithmetic.
В 1684 году Готфрид Лейбниц в сочинении Nova Methodvs pro maximis et minimis, itemque tangentibus… впервые использовал слово «алгоритм» (Algorithmo) в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления.
В XVIII веке в одном из германских математических словарей, Vollstandiges mathematisches Lexicon (изданном в Лейпциге в 1747 г.), термин algorithmus всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение algorithmus infinitesimalis применялось к способам выполнения действий с бесконечно малыми величинами. Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется — «Использование нового алгоритма для решения проблемы Пелля» (De usu novi algorithmi in problemate Pelliano solvendo). Мы видим, что понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.
Однако потребовалось ещё почти два столетия, чтобы все старинные значения слова вышли из употребления. Этот процесс можно проследить на примере проникновения слова «алгоритм» в русский язык.
Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах (самые ранние из них почти на сто лет старше) и восходит к ещё более древним рукописям XVI в. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Полное название этого учебника — «Сия книга, глаголемая по еллински и по гречески арифметика, а по немецки алгоризма, а по русски цифирная счётная мудрость».
Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Однако его не было ни в знаменитом словаре В. И. Даля, ни спустя сто лет в «Толковом словаре русского языка» под редакцией Д. Н. Ушакова (1935 г.). Зато слово «алгорифм» можно найти и в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой советской энциклопедии (БСЭ), изданном в 1926 г. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. Однако к началу XX в. для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в следующих изданиях БСЭ.
Алгоритмы становились предметом всё более пристального внимания учёных, и постепенно это понятие заняло одно из центральных мест в современной математике. Что же касается людей, от математики далёких, то к началу сороковых годов это слово они могли услышать разве что во время учёбы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм всё ещё воспринимался как термин сугубо специальный, что подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности, его нет даже в десятитомной Малой советской энциклопедии (1957 г.), не говоря уже об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании Большой советской энциклопедии (1969 г.) алгоритм уже характеризуется как одна из основных категорий математики, «не обладающих формальным определением в терминах более простых понятий, и абстрагируемых непосредственно из опыта». Как мы видим, отличие даже от трактовки первым изданием БСЭ разительное! За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики.
Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» вошло в 1985 г. во все школьные учебники информатики и обрело новую жизнь. Вообще можно сказать, что его сегодняшняя известность напрямую связана со степенью распространения компьютеров. Например, в третьем томе «Детской энциклопедии» (1959 г.) о вычислительных машинах говорится немало, но они ещё не стали чем-то привычным и воспринимаются скорее как некий атрибут светлого, но достаточно далёкого будущего. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход. Это чутко фиксируют энциклопедические издания. В «Энциклопедии кибернетики» (1974 г.) в статье «Алгоритм» он уже связывается с реализацией на вычислительных машинах, а в «Советской военной энциклопедии» (1976 г.) даже появляется отдельная статья «Алгоритм решения задачи на ЭВМ». За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится всё более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства». Академик Н. Н. Моисеев назвал свою книгу «Алгоритмы развития», а известный врач Н. М. Амосов — «Алгоритм здоровья» и «Алгоритмы разума». А это означает, что слово живёт, обогащаясь всё новыми значениями и смысловыми оттенками.
Особую роль выполняют прикладные алгоритмы, предназначенные для решения определённых прикладных задач. Алгоритм считается правильным, если он отвечает требованиям задачи (например, даёт физически правдоподобный результат). Алгоритм (программа) содержит ошибки, если для некоторых исходных данных он даёт неправильные результаты, сбои, отказы или не даёт никаких результатов вообще. Последний тезис используется в олимпиадах по алгоритмическому программированию, чтобы оценить составленные участниками программы.
Важную роль играют рекурсивные алгоритмы (алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения). Начиная с конца XX — начала XXI века активно разрабатываются параллельные алгоритмы, предназначенные для вычислительных машин, способных выполнять несколько операций одновременно.
Алгоритм — это точно определённая инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель не может быть равен нулю.
Алгоритм служит, как правило, для решения не одной конкретной задачи, а некоторого класса задач. Так, алгоритм сложения применим к любой паре натуральных чисел. В этом выражается его свойство массовости, то есть возможности применять многократно один и тот же алгоритм для любой задачи одного класса.
Для разработки алгоритмов и программ используется алгоритмизация — процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально важны детерминированность, результативность и массовость, а также правильность результатов решения поставленных задач.
Алгоритм — это понятное и точное предписание, исполнительно совершить последовательность действий, направленных на достижение цели.
Алгоритм может быть записан словами и изображён схематически. Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, машинный код). Например, для описания алгоритма применяются блок-схемы. Другим вариантом описания, не зависимым от языка программирования, является псевдокод.
Хотя в определении алгоритма требуется лишь конечность числа шагов, требуемых для достижения результата, на практике выполнение даже хотя бы миллиарда шагов является слишком медленным. Также обычно есть другие ограничения (на размер программы, на допустимые действия). В связи с этим вводят такие понятия как сложность алгоритма (временна́я, по размеру программы, вычислительная и др.).
Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики. В 50-х гг. XX века появилась даже отдельная её область — быстрые алгоритмы. В частности, в известной всем с детства задаче об умножении десятичных чисел обнаружился ряд алгоритмов, позволяющих существенно (в асимптотическом смысле) ускорить нахождение произведения. См. быстрое умножение
Ярким примером является алгоритм Чудновского для вычисления числа π.
wreferat.baza-referat.ru
МОУ Нижнеингашская средняя общеобразовательная школа №2
Реферат
по информатике на тему:
Выполнила: Нерушкина Е. В.
Проверила: Алексеева О.В.
п. Нижний Ингаш
2006 г.
1.
Введение
3
2.
О происхождении слова «Алгоритм»
4
3.
Понятие алгоритма
6
4.
Классификация понятия «Алгоритм»
6
5.
Свойства алгоритмов
7
6.
Способы записи алгоритма
8
7.
Линейная алгоритмическая структура
9
8.
Алгоритмическая структура «Ветвление»
10
11
12
9.
Алгоритмическая структура «Цикл»
Цикл «Пока . . .»
Цикл «Для . . .»
14
14
14
16
17
10.
Вспомогательный алгоритм
18
11.
Заключение
21
12.
Список используемой литературы
22
13.
Приложение
23
Тема, которую я рассматриваю в своем реферате, на мой взгляд, сложна и объёмна. В школьном курсе информатики предложены основные виды алгоритмических структур и, как мне кажется, представлены поверхностно.
Недостаток, просмотренных мной источников литературы по вопросам алгоритмизации, в том, что в них это уделено совсем небольшое внимание построению блок-схем для решения определенных задач по программированию.
Решение любой задачи включает в себя следующие этапы:
Запись на формальном языке.
Построение блок-схемы.
Составление программы.
Чаще всего в литературе большое внимание уделяется первому и третьему этапам решения. Я же самым важным этапом считаю именно второй, т.к. это самый наглядный и доступный способ.
Цели моей работы:
дать понятие алгоритма;
провести классификацию алгоритмических структур на основе диалектической логики;
рассмотреть примеры различных алгоритмических структур, на основе которых строится алгоритм решения задачи.
Известно, что в раннем средневековье слово algorism использовали для обозначения способа арифметических вычислений на бумаге без применения счетных досок (абаков). Именно в таком значении оно вошло в некоторые европейские языки. Например, в авторитетном словаре английского языка «Webster s New World Dictionary», изданном в 1957 г., оно снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.
Несмотря на то, что известно, когда появился термин «алгоритм», лингвисты по-разному пытались толковать его происхождение. Одни выводили algorism из греческих «алгирос» - «больной» и «арифмос» - «число». Правда, не понятно, почему числа «больные»? Другие склонялись к еще более экстравагантному объяснению, связывая слово с неким мифическим древним испанским правителем King Algor of Castil. Свой вариант предлагает и Энциклопедический словарь Брокгауза и Ефрона (1890 г.). В нем «алгортфм» производится от арабского слова «Аль-Горетм», то есть корень.
Н
о истину удалось остановить не лингвистам, а историкам математики. Они доказали, что слово происходит от имени великого среднеазиатского ученого, автора популярнейшего на протяжении многих веков учебника по математике, аль-Хорезми, жившего в первой половине IX в. В латинской транскрипции его имя означает «Мухаммад, сын Муссы, отец Абдулы, родом из Хорезма». Хорезм – это историческая область на территории современного Узбекистана, центром которой является древний город Хива.
Почти все словари сходятся на том, что первоначально слово имело форму algorismi и лишь спустя какое-то время потеряло последнюю букву, приобретя более удобный для европейского произношения вид algorism.
Позднее оно, в свою очередь, неоднократно подвергалось искажениям, последнее из которых, скорее всего, связано со словом arithmetic, имеющим греческое происхождение. Уже в новом написании оно встречается XVIII в. в одном из германских математических словарей «Vollstandiges mathematisches Lexicon», изданном в Лейпциге в 1747 г.
Постепенно все старинные значения вышли из употребления. К началу XX в. слово «алгоритм» уже означало «всякий арифметический или алгебраический процесс, который выполняется по строго определенным правилам», именно так оно объясняется в Большой Советской Энциклопедии (1926 г.).
То, что алгоритм воспринимался как термин сугубо специальный и малозначительный подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности его нет даже в десятитомной Малой советской энциклопедии, не говоря об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании БСЭ «алгоритм» характеризуется как одно из основных понятий (категорий) математики. За 40 лет из понятия, знакомого лишь узкому кругу специалистов, превратился в одно из ключевых понятий математики.
Одновременно с развитием понятия алгоритма происходила и его экспансия в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» обрело новую жизнь.
За последние полтора-два десятилетия XX в. компьютер сделался неотделимым атрибутом нашей жизни, общеупотребительной становится и компьютерная лексика. Слово «алгоритм» в наши дни известно каждому. Оно настолько уверенно шагнуло в разговорную речь, что сейчас мы нередко встречаем на страницах газет, слышим в выступлениях политиков. Слово живет, обогащается всё новыми значениями и смысловыми значениями, так что, скорее всего, в словарях будущего его уже никогда не придется снабжать пометкой устаревшее.
Алгоритм –
это информационная модель, описывающая процесс преобразования объекта из начального состояния в конечное, в форме последовательности понятных исполнителю команд;
это описание конечной последовательности действий, строгое исполнение которых приводит к решению задачи за конечное число шагов.
это понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
Мир алгоритмов разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает каждый алгоритм. Основные свойства алгоритмов следующие:
Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.
Дискретность (прерывность, раздельность) — т.е. алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).
Детерменированность — т.е. каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический хаpактеp и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.
Массовость. Это означает, что алгоритм решения задачи pазpабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Существуют различные формы записи алгоритмов, отличающиеся друг от друга наглядностью, компактностью, степенью формализации. На практике наиболее распространены следующие формы представления алгоритмов:
Назначение
Обозначение
Начало
блок-схемы
Ввод
данных
Простая
команда
Условие
Цикл с параметром
Конец
блок-схемы
Существует большое количество алгоритмов, в которых команды выполняются строго последовательно и ничем не осложняясь (например, условия, подпрограммы, многократные повторения одной команды или группы команд).
Найти скорость, если известна масса и ускорение.
Дано: Решение:
m, a Находим скорость с помощью формулы
второго закона Ньютона.
Найти:
F
Cls
Rem «Нахождение скорости»
Input m, a
F=m*a
Print F
End
В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в алгоритмическую структуру «ветвление» входит условие, в зависимости от выполнения или невыполнения которого реализуется та или иная последовательность команд (серия).
Условие – высказывание, которое может быть либо истинным, либо ложным.
Вспомним сюжет русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: «Направо пойдешь – коня потеряешь, налево пойдешь – пропадешь...»
Подобная ситуация, заставляющая нас принимать решения в зависимости от условия, постоянно встречаются в повседневной жизни.
Условие, записанное на формальном языке, называется условным или логическим выражением.
Условные выражения могут быть простыми и сложными. Простое условие включает в себя два числа, две переменных или два арифметических выражения, которые сравниваются между собой с использованием операций сравнения (больше, меньше, равно и пр.). Например, 5>3, 2*8=4*4)
Сложное условие – это последовательность простых условий, объединенных между собой знаками логических операций. Например, 5>3 and 2*8=4*4 и т.д.
Алгоритм, в котором используется условие, получил название разветвляющегося, т.к. в зависимости от значения условия выбираются те или иные действия.
Разветвляющийся алгоритм – алгоритм, в котором в зависимости от выполнения условия выполняется либо одна, либо другая последовательность действий.
В общем случае схема разветвляющегося алгоритма будет выглядеть так: «если условие, то…, иначе…». Такое представление алгоритма получило название полной формы.
Полный разветвляющийся алгоритм
Даны два числа. Найдите большее из двух чисел.
Дано: Решение:
а, b 1.Сравнить два числа.
Найти: 2.Записать большее.
m (большее из а и b)
Вывод m
CLS
Rem «Найти большее из двух чисел»
Input a, b
If a > b Then m = a Else m = b’ (реализация полной развилки (формы))
Print m
End
В разветвляющемся алгоритме при невыполнении условия действия могут не предусматриваются. Тогда это будет неполная форма, в которой действия пропускаются: «если условие, то …».
Неполный разветвляющийся алгоритм
Вычислите значения составной функции.
x3, при x ≤ 0
y= - x, при 0 < x ≤ 4
4, при x > 4
CLS
Rem «Вычисление значения составной функции
I
nput x
If x ≤ 0 Then y = x3
If 0 < x ≤ 4 Then y = x (реализация неполной развилки)
If x > 0 Then y = 4
Print y
End
Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий. Каждый год наступает весна, лето, осень и зима. Жизнь растений в течение года проходит одни и те же циклы. Подсчитывая число полных оборотов минутной стрелки, человек отсчитывает время.
По расположению команды проверки условия циклические алгоритмы делятся на:
Алгоритм с предусловием – алгоритм, в котором условие проверяется до выполнения команд – тела цикла.
Алгоритм с постусловием – алгоритм, в котором условие проверяется после выполнения команд – тела цикла.
Алгоритм с предусловием
В свою очередь алгоритм с предусловием по типу команд делится на:
Найдите наибольший общий делитель, с помощью алгоритма Евклида.
Дано: Решение:
х, y Пока два числа не равны, большее
число заменять разностью большего
Найти: и меньшего. Когда числа станут равны.
НОД Любое из них можно считать НОД-ем.
Cls
Input x, y
Wheil x<>y
If x>y Then x=x-y Else y=y-x
Wend
Print y
End
Найти факториал числа.
Дано: Решение:
Факториал числа – это произведение
N натуральных чисел от 1 до этого числа.
Найдем факториал по определению.
Найти:
F
Cls
Rem «Нахождение факториала числа»
F=1
For i to N
F=F * i
Next
Print F
End
Алгоритм с постусловием
Найдите наибольший общий делитель, с помощью алгоритма Евклида.
Дано: Решение:
х, y Делим большее число на меньшее с
остатком и заменяем его на получен-
ный остаток до тех пор пока остаток
не станет равным нулю. НОД-ем будет
Найти: являться последний остаток не равный
НОД нулю.
Cls
Input x, y
Do
If x>y Then x=x mod y Else y=y mod x
Loop Until x=0 or y=0
Print x+y
Допустим, вы хотите научиться жонглировать двумя или тремя мячами. Если внимательно приглядеться к действиям профессионального артиста и попытаться понять, как это ему удаётся делать, то оказывается – секрет в том, что надо научиться искусно, выполнять несколько определённых движений, которым присвоено следующие названия:
Бросок левой – подбросить мяч левой рукой.
Бросок правой – подбросить мяч правой рукой.
Захват левой – поймать мяч левой рукой.
Захват правой – поймать мяч правой рукой.
Выполняться каждое такое движение будет по своему алгоритму. Научившись таким действиям, вы сможете применить своё умение в другом деле, например, показывая фокусы или участвуя в соревнованиях. Благодаря тому, что подобные алгоритмы могут в дальнейшем многократно использоваться в других алгоритмах, их стали называть вспомогательными.
Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя. Вспомогательному алгоритму должно быть присвоено имя.
Найдите большее из трех чисел.
Дано: Решение:
а, b, с Сравнить первые два числа. Выбрать
большее. Теперь это большее
Найти: М сравнить с третьим числом. Выбрать
(большее) большее. Записать ответ.
CLS
Rem «Найти большее из трех чисел»
Input a, b
X=a: y=b
Gosub 1
Print M
End
1.Rem «Нахождение большего из двух чисел»
If x > y Then M = x Else M = y
Return
Мой реферат можно использовать как методическое пособие для учащихся. Мне удалось представить полное схематичное деление алгоритмов на виды по разным признакам.
Ни в одном из рассмотренных мною учебных либо методических пособий эта тема не была представлена полностью. В своем реферате я рассмотрела все виды алгоритмических структур, и систематизировала их по определенному плану:
определение понятия алгоритмической структуры;
пример задачи на использование данной алгоритмической структуры, записанной на естественном языке;
построение блок-схемы;
запись программы на языке программирования QBasic.
Ценность моего реферата в том, что в нем, помимо алгоритмических структур, входящих в школьный курс информатики, разобраны два вида алгоритмической структуры «Цикл», которые не изучаются в школьном курсе информатики (циклический алгоритм с постусловием и алгоритм с предусловием «Пока…»).
Большинство источников учебной литературы представляют нам огромное количество жизненных примеров применения алгоритмов, а также решение алгоритмических задач в разных предметных областях. Я же в своем реферате выделяю ту группу задач, которые могут быть решены средствами программирования. И именно на примере этих задач я подтверждаю принцип их поэтапного решения.
Я считаю, что добилась поставленной цели и надеюсь, что мой реферат поможет учителю информатики в преподавании программирования, а также учащимся в самостоятельном изучении данной темы совместно с учебным пособием по информатике.
Информатика и информационные технологии. Учебник для 10-11 классов/ Н.Д. Угринович. – 2-е изд. – М.: БИНОМ. Лаборатория знаний, 2005. – 511 с.: ил. ISBN 5-94774-189 –X
Информатика. 7-9 класс. Базовый курс. Теория. / Под ред. Н.В. Макаровой. – СПб.: Питер, 2003. – 368с.: ил. ISBN 5-273-00186-9
Энциклопедия для детей. Том 22. Информатика/Глав.ред. Е.А. Хлебалина, вед.науч.ред. А.Г. Леонов. – М.: Аванта+,2003. – 625с.:ил. ISBN 5-94623-040-9 ?ISBN 5-94623-001-8
Бейсик и Паскаль в вопросах и задачах.(Рабочая тетрадь 2) Житкова О.А., Кудрявцева Е.К. – М. Интеллект Центр. 2001 80 с.
Информатика. 5-6 класс. Начальный курс. / Под ред. Н.В. Макаровой. – СПб.: Питер, 2002. – 160с.: ил. ISBN 5-272-00129-Х
Конспекты уроков информатики в 9-11 классах: Практикум по программированию / Авт.-сост. А.А. Чернов – Волгоград: Учитель, 2005. – 236 с. ISBN 5-7057-0548-4
Приложение 1
Понятие
Содержание
Объём
Алгоритм
1. Информационная модель, описывающая процесс преобразования объекта из начального состояния в конечное, в форме последовательности понятных исполнителю команд.
2. Описание конечной последовательности действий, строгое исполнение которых приводит к решению задачи за конечное число шагов.
3. Понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
I. По порядку выполнения действий:
1.1. Линейный;
1.2. Нелинейный.
Линейный алгоритм
1. Алгоритм, в котором команды выполняются однократно одна за другой.
2. Описание действий, которые выполняются однократно в заданном порядке.
3.Алгоритм, в котором команды выполняются одна за другой.
Нелинейный алгоритм
1. Алгоритм, в котором действия могут выполняться неоднократно и не в том порядке, в котором записаны.
По наличию условия:
Алгоритм с условием;
Алгоритм без условия (Вспомогательный алгоритм).
Алгоритм с условием
1. Нелинейный алгоритм, в состав которого входит команда проверки условия.
По количеству проверок:
Разветвляющийся;
Циклический.
Разветвляющийся алгоритм
1. Алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
По наличию действия при ложном значении условия:
1.1. Полный разветвляющийся алгоритм;
1.2. Неполный разветвляющийся алгоритм.
Полный разветвляющийся алгоритм
Разветвляющийся алгоритм, в котором определены действия для любого значения условия.
Неполный разветвляющийся алгоритм
1. Разветвляющийся алгоритм, в котором действия определены только для истинного значения условия.
Циклический алгоритм
1. Описание действий, которые должны повторяться указанное число раз, или пока не выполнено заданное условие.
2. Алгоритм с условием, в котором действия повторяются многократно.
I. По расположению команды проверки условия:
1.1. Циклический алгоритм с предусловием;
1.2. Циклический алгоритм с постусловием.
Циклический алгоритм с предусловием
1. Циклический алгоритм, в котором условие проверяется до выполнения команд - тела цикла.
I. По виду команды:
1.1. Цикл «пока»;
1.2. Цикл «для» ( с параметром).
Цикл «пока»
1. Циклический алгоритм с предусловием, в состав которого входит команда пока <условие>, делай <тело цикла>.
Цикл «для» ( с параметром)
1. Циклический алгоритм с предусловием, в состав которого входит команда «для каждого значения…выполнить», что требует того, что действия должны повторятся заданное число раз.
Циклический алгоритм с постусловием
1. Циклический алгоритм, в котором условие проверяется после выполнения команд - тела цикла.
Вспомогательный алгоритм (Подпрограмма, процедура)
1. . Алгоритм, по которому решается некоторая подзадача из основной задачи и который, как правило, выполняется многократно без проверки условия.
2. Алгоритм, который можно использовать в других алгоритмах, указав только его имя.
3. Алгоритм, по которому решается некоторая подзадача из основной задачи и который, как правило, выполняется многократно.
Данный сборник понятий составлен
Алексеевой О. В.
Приложение 2
Есть люди, для которых соблюдение точного, сложного и многогранного режима – своего рода хобби. Такие всегда знают, что им надлежит делать в следующий момент, у них всё расписано. Другие поступают так по необходимости, из-за большого числа разнообразных нагрузок. Честь и хвала! Но для подавляющего большинства такое четкое расписание нереально: их жизнь слишком зависит от непредвидимых внешних обстоятельств. Поэтому главнейший принцип составления расписания: чем меньше предусмотрено в нем пунктов. Тем лучше. Забредший приятель, телефонный звонок или захватывающая телепередача легко разрушает наши намерения. Вы сердитесь на себя и на людей, но завтра сами своей неотложной нуждой разобьёте планы вашего друга. Лучше совсем отказаться от режима, чем постоянно переживать по поводу его нарушения. При составлении режима необходимо, прежде всего, считаться с реальностью внешнего мира. Но не забудем еще и реальность внутреннего мира. Люди различаются не только своим сознательным отношением к режиму, но и, если можно так выразиться, способностями к нему. Некоторым людям режим дня даётся почти без усилий, даже при необходимых условиях, он будто сам собой вытекает из их натуры. Я называю таких людей «ритмиками». Не берусь утверждать, что главное в возникновении этого типа: рано и прочно выработанная привычка или прирождённая психофизиологическая скоординорованность.
Другой полюс – дизритмики. Здесь всё наоборот: режим поддерживать трудно, и не потому, что нет желания: как раз стремление огромно, именно из-за трудности! Но мозг и организм этих людей, никак не вписываются ни в какие режимные рамки: их внутренние ритмы слишком сложны, изменчивы, мало предсказуемы, плохо управляемы. Два дня у дизритмика нет аппетита, на третий появляется волчий голод, три ночи почти нет потребности во сне, затем два дня сплошной сон…
Это два крайних полюса. Обычный человек находится где-то между тем и другим.
Нечего и говорить, что в обычном режиме трудового дня ритмика живётся хорошо, полуритмикам средне, а дизритмик оказывается в положении хронической катастрофы. Если он подчиняется ритмам среды, он плохо себя чувствует. Если не подчиняется – тоже плохо, ибо никто ему это не прощает. По моим наблюдениям, дизритмики не столь уж редко оказываются людьми психически высокопродуктивными, весьма способными, а физически несмотря ни на какие недомогания, крепкими и выносливыми. Только и психическая и физическая их продуктивность неравномерны, капризны, причудливо распределены во времени. Относительно жесткого режима, принятого обществом, их внутренняя организация, конечно, неудача, но это не значит, что они не представляют собой более совершенный тип по каким-то другим критериям.
Если вы в течение ряда лет честно выдерживали режимы и перепробовали несколько вариантов с достаточной длительностью, но всё равно ничего не получалось, то вы, скорее всего, дизритмик. Это значит, что вам нет смысла стремиться к жестокому режиму, а целесообразнее по возможности следовать тому прихотливому расписанию жизни и работы, которые диктует ваш организм. Делайте режим возможно более гибким (я сознаю свою слабость этого совета для множества людей, зависящих от расписания работы общественных учреждений, транспорта, предприятий и т.д.). Не требуйте от себя высокой продуктивности те часы и дни, когда организм её не даст, подлавливайте хорошее время и полноценно выкладываётесь. Спите и ешьте, когда хочется и можется. Возможно, изучив себя, вам удастся и в неправильных колебаниях вашего состояния уловить кое-какие закономерности. Кроме того, всё меняется: со временем, быть может, изменятся и ритмы вашего организма; возможно, они упростятся и скоординируются. Во всяком случае, не считайте себя менее здоровым и полноценным, чем люди, легко поддерживающие режим.
infourok.ru
Алгоритмизация
Основным в процессе программирования является разработка алгоритма. Это один из наиболее сложных этапов решения задачи с использованием ЭВМ. В начале обучения программированию, на наш взгляд, целесообразно не привязываться сразу к какому-либо языку, разрабатывать алгоритмы без записи на ЯПВУ, а, например, с помощью блок-схем или иным аналогичным способом. После такой "чистой" алгоритмизации учащимся или студентам проще перейти к записи того же алгоритма на определённом языке программирования. В настоящей публикации продемонстрирован именно такой подход.
Напомним, что основными алгоритмическими структурами (ОАС) являются следование, развилка и цикл. В более сложных случаях используются суперпозиции (вложения) ОАС.
Ниже приведены графические обозначения (обозначения на блок-схемах) ОАС.
| | | |
| | | |
На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.
Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.
В примерах мы будем использовать запись алгоритмов с помощью блок-схем и словесное описание.
Линейные алгоритмы
Простейшие задачи имеют линейный алгоритм решения. Это означает, что он не содержит проверок условий и повторений.
Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?
| | 1. Ввести v1, v2, v3, t1, t2, t3. 2. S1 := v1 * t1. 3. S2 := v2 * t2. 4. S3 := v3 * t3. 5. S := S1 + S2 + S3. 6. Вывести значение S. 7. Конец. |
Для проверки работоспособности алгоритма необходимо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результатом ручного счета.
Пример 2. Дано натуральное трехзначное число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: "число n кратно каждой своей цифре", и ЛОЖЬ — в противном случае.
| | 1. Ввести число n 2. A := n mod 10 {разряд единиц} 3. B := n div 100 {разряд сотен} 4. C := n div 10 mod 10 {десятки} 5. L := (n mod A=0) and (n mod B=0) and (n mod C=0) 6. Вывод L 7. Конец |
На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.
Развилка
Достаточно часто то или иное действие должно быть выполнено в зависимости от значения логического выражения, выступающего в качестве условия. В таких случаях используется развилка.
Пример 1. Вычислить значение функции
| | 1. Ввести x. 2. Если x£–12, то y:=–x2 3. Если x<0, то y:=x4 4. y := x–2 5. Вывести y 6. Конец |
При тестировании алгоритмов с развилкой необходимо подбирать такие исходные данные, чтобы можно было проверить все ветви. В приведенном выше примере должно быть по крайней мере три тестовых набора.
Пример 2. Дано натуральное число n. Если число нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое число со знаком), удвоить его, иначе — оставить без изменения.
Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.
| | 1. Ввести число n 2. Если число n нечетное и меньше 16384, то n := n * 2 3. Вывод n 4. Конец |
Рассмотренный пример иллюстрирует неполную развилку. Также следует отметить, здесь логическое выражение, являющееся условием, содержит 2 операнда.
Циклы
Если какие-либо операторы необходимо выполнить несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Пример 1. Подсчитать количество нечетных цифр в записи натурального числа n.
Идея решения. Из заданного числа выбирать из младшего разряда цифру за цифрой до тех пор, пока оно не исчерпается, т.е. станет равным нулю. Каждую нечётную цифру учитывать.
| |
| 1. Ввести число n 2. K := 0 {подготавливаем счётчик} 3. Если n = 0, переход к п. 7 4. Если n mod 10 mod 2 = 1, то K := K +1 5. n := n div 10 6. Переход к п. 3 7. Вывод K 8. Конец |
Задача решена двумя способами. Слева решение оформлено с использованием цикла с предусловием, справа — с постусловием.
Пример 2. Дана последовательность, общий член которой определяется формулой
Вычислить при n>2 сумму тех ее членов, которые больше заданного числа e.
При решении задачи находится очередной член последовательно и, если он больше e, добавляется к сумме.
| | 1. Ввести e 2. S := 0 3. A := 1/4 4. n := 3 5. Сравнить А с e. Если A>=e, переход к п. 10 6. S := S + A 7. A := (n-1)/(n*n) 8. n := n + 1 9. Переход к п. 5 10. Вывод S 11. Конец |
В рассмотренных выше примерах количество повторений заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во втором — от числа e.
В тех же случая, когда количество шагов известно из условия задачи, проще и предпочтительней использовать цикл с параметром.
Пример 3. Найти произведение первых k натуральных чисел, кратных трём.
При составлении алгоритма учтем, что первое натуральное число, кратное 3, есть тройка, а все последующие больше предыдущего на 3.
| | 1. Ввод k 2. P := 1 {здесь накапливаем произведение} 3. T := 0 {здесь будут числа, кратные 3} 4. I := 1 5. Если I > k, переход к п. 10 6. T := T + 3 7. P := P * T 8. I := I + 1 9. Перейти к п. 5 10. Вывод P 11. Конец |
Другие примеры будут записаны уже на ЯПВУ. В настоящей же публикации предпринята попытка продемонстрировать, что изучение программирования разумно начинать собственно с разработки алгоритмов, не акцентируя первоначально внимания на записи алгоритма на том или ином языке программирования. В то же время автор, являясь сторонником структурного подхода к программированию, предлагает придерживаться этого подхода и при программировании на уровне блок-схем.
Список литературы
Для подготовки данной работы были использованы материалы с сайта http://www.comp-science.ru/
topref.ru
Основным в процессе программирования является разработка алгоритма. Это один из наиболее сложных этапов решения задачи с использованием ЭВМ. В начале обучения программированию, на наш взгляд, целесообразно не привязываться сразу к какому-либо языку, разрабатывать алгоритмы без записи на ЯПВУ, а, например, с помощью блок-схем или иным аналогичным способом. После такой "чистой" алгоритмизации учащимся или студентам проще перейти к записи того же алгоритма на определённом языке программирования. В настоящей публикации продемонстрирован именно такой подход.
Напомним, что основными алгоритмическими структурами (ОАС) являются следование, развилка и цикл. В более сложных случаях используются суперпозиции (вложения) ОАС.
Ниже приведены графические обозначения (обозначения на блок-схемах) ОАС.
|
|
|
|
|
|
|
|
На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.
Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.
В примерах мы будем использовать запись алгоритмов с помощью блок-схем и словесное описание.
Простейшие задачи имеют линейный алгоритм решения. Это означает, что он не содержит проверок условий и повторений.
Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?
| | 1. Ввести v1, v2, v3, t1, t2, t3. 2. S1 := v1 * t1. 3. S2 := v2 * t2. 4. S3 := v3 * t3. 5. S := S1 + S2 + S3. 6. Вывести значение S. 7. Конец. |
Для проверки работоспособности алгоритма необходимо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результатом ручного счета.
Пример 2. Дано натуральное трехзначное число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: "число n кратно каждой своей цифре", и ЛОЖЬ — в противном случае.
| | 1. Ввести число n 2. A := n mod 10 {разряд единиц} 3. B := n div 100 {разряд сотен} 4. C := n div 10 mod 10 {десятки} 5. L := (n mod A=0) and (n mod B=0) and (n mod C=0) 6. Вывод L 7. Конец |
На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.
Достаточно часто то или иное действие должно быть выполнено в зависимости от значения логического выражения, выступающего в качестве условия. В таких случаях используется развилка.
Пример 1. Вычислить значение функции
| | 1. Ввести x. 2. Если x£–12, то y:=–x2 3. Если x2 сумму тех ее членов, которые больше заданного числа e. При решении задачи находится очередной член последовательно и, если он больше e, добавляется к сумме.
В рассмотренных выше примерах количество повторений заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во втором — от числа e. В тех же случая, когда количество шагов известно из условия задачи, проще и предпочтительней использовать цикл с параметром. Пример 3. Найти произведение первых k натуральных чисел, кратных трём. При составлении алгоритма учтем, что первое натуральное число, кратное 3, есть тройка, а все последующие больше предыдущего на 3.
Другие примеры будут записаны уже на ЯПВУ. В настоящей же публикации предпринята попытка продемонстрировать, что изучение программирования разумно начинать собственно с разработки алгоритмов, не акцентируя первоначально внимания на записи алгоритма на том или ином языке программирования. В то же время автор, являясь сторонником структурного подхода к программированию, предлагает придерживаться этого подхода и при программировании на уровне блок-схем. |
bukvasha.ru
Основным в процессе программирования является разработка алгоритма. Это один из наиболее сложных этапов решения задачи с использованием ЭВМ. В начале обучения программированию, на наш взгляд, целесообразно не привязываться сразу к какому-либо языку, разрабатывать алгоритмы без записи на ЯПВУ, а, например, с помощью блок-схем или иным аналогичным способом. После такой "чистой" алгоритмизации учащимся или студентам проще перейти к записи того же алгоритма на определённом языке программирования. В настоящей публикации продемонстрирован именно такой подход.
Напомним, что основными алгоритмическими структурами (ОАС) являются следование, развилка и цикл. В более сложных случаях используются суперпозиции (вложения) ОАС.
Ниже приведены графические обозначения (обозначения на блок-схемах) ОАС.
На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.
Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.
В примерах мы будем использовать запись алгоритмов с помощью блок-схем и словесное описание.
Линейные алгоритмы
Простейшие задачи имеют линейный алгоритм решения. Это означает, что он не содержит проверок условий и повторений.
Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?
 | 1. Ввести v1, v2, v3, t1, t2, t3. 2. S1 := v1 * t1. 3. S2 := v2 * t2. 4. S3 := v3 * t3. 5. S := S1 + S2 + S3. 6. Вывести значение S. 7. Конец. |
Для проверки работоспособности алгоритма необходимо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результатом ручного счета.
Пример 2. Дано натуральное трехзначное число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: "число n кратно каждой своей цифре", и ЛОЖЬ — в противном случае.
 | 1. Ввести число n 2. A := n mod 10 {разряд единиц} 3. B := n div 100 {разряд сотен} 4. C := n div 10 mod 10 {десятки} 5. L := (n mod A=0) and (n mod B=0) and (n mod C=0) 6. Вывод L 7. Конец |
На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.
Развилка
Достаточно часто то или иное действие должно быть выполнено в зависимости от значения логического выражения, выступающего в качестве условия. В таких случаях используется развилка.
Пример 1. Вычислить значение функции
 | 1. Ввести x. 2. Если x£–12, то y:=–x2 3. Если x<0, то y:=x4 4. y := x–2 5. Вывести y 6. Конец |
При тестировании алгоритмов с развилкой необходимо подбирать такие исходные данные, чтобы можно было проверить все ветви. В приведенном выше примере должно быть по крайней мере три тестовых набора.
Пример 2. Дано натуральное число n. Если число нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое число со знаком), удвоить его, иначе — оставить без изменения.
Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.
 | 1. Ввести число n 2. Если число n нечетное и меньше 16384, то n := n * 2 3. Вывод n 4. Конец |
Рассмотренный пример иллюстрирует неполную развилку. Также следует отметить, здесь логическое выражение, являющееся условием, содержит 2 операнда.
Циклы
Если какие-либо операторы необходимо выполнить несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Пример 1. Подсчитать количество нечетных цифр в записи натурального числа n.
Идея решения. Из заданного числа выбирать из младшего разряда цифру за цифрой до тех пор, пока оно не исчерпается, т.е. станет равным нулю. Каждую нечётную цифру учитывать.
 |
1. Ввести число n 2. K := 0 {подготавливаем счётчик} 3. Если n = 0, переход к п. 7 4. Если n mod 10 mod 2 = 1, то K := K +1 5. n := n div 10 6. Переход к п. 3 7. Вывод K 8. Конец |
Задача решена двумя способами. Слева решение оформлено с использованием цикла с предусловием, справа — с постусловием.
Пример 2. Дана последовательность, общий член которой определяется формулой
Вычислить при n>2 сумму тех ее членов, которые больше заданного числа e.
При решении задачи находится очередной член последовательно и, если он больше e, добавляется к сумме.
 | 1. Ввестиe 2. S := 0 3. A := 1/4 4. n := 3 5. Сравнить А с e. Если A>=e, переход к п. 10 6. S := S + A 7. A := (n-1)/(n*n) 8. n := n + 1 9. Переход к п. 5 10. Вывод S 11. Конец |
В рассмотренных выше примерах количество повторений заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во втором — от числа e.
В тех же случая, когда количество шагов известно из условия задачи, проще и предпочтительней использовать цикл с параметром.
Пример 3. Найти произведение первых k натуральных чисел, кратных трём.
При составлении алгоритма учтем, что первое натуральное число, кратное 3, есть тройка, а все последующие больше предыдущего на 3.
 | 1. Ввод k 2. P := 1 {здесь накапливаем произведение} 3. T := 0 {здесь будут числа, кратные 3} 4. I := 1 5. Если I > k, переход к п. 10 6. T := T + 3 7. P := P * T 8. I := I + 1 9. Перейти к п. 5 10. Вывод P 11. Конец |
Другие примеры будут записаны уже на ЯПВУ. В настоящей же публикации предпринята попытка продемонстрировать, что изучение программирования разумно начинать собственно с разработки алгоритмов, не акцентируя первоначально внимания на записи алгоритма на том или ином языке программирования. В то же время автор, являясь сторонником структурного подхода к программированию, предлагает придерживаться этого подхода и при программировании на уровне блок-схем.
superbotanik.net
Структура “следование”
Полная развилка
Неполная развилка
Цикл с предусловие (цикл ПОКА)
Цикл с постусловием (цикл ДО)
Цикл с параметром
Структура “следование”
Полная развилка
Неполная развилка
Цикл с предусловие (цикл ПОКА)
Цикл с постусловием (цикл ДО)
Цикл с параметром
