Как составить программу по задаче

Перевод статьи Валинды Чен.

Это сборник советов для разработчиков-новичков, которые смотрят на пустой экран и не знают, с чего начать. Нередко можно услышать от молодых разработчиков, работающих над решением каких-то задач в программировании, что они не уверены, за что нужно хвататься. Ты понимаешь саму задачу, логику, основы синтаксиса и так далее. Если ты видишь чей-то код, или тебе кто-то помогает, то можно всё сделать самому. Но бывает, что ты не уверен в своих силах, или поначалу тебе трудно реализовать свои мысли в коде, несмотря на то, что ты знаешь синтаксис и логику. Под катом — несколько советов по решению этой проблемы, которые помогут вам в повседневной работе.

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

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

Иногда можно попробовать объяснить задачу другу и посмотреть, поймёт ли он ваше объяснение. Вы же не хотите пройти половину пути и обнаружить, что неправильно поняли требования. Так что лучше потратить в начале больше времени, чтобы всё прояснить. Чем лучше поймёте задачу, тем легче будет её решить.

Допустим, мы создаём простую функцию selectEvenNumbers, которая берёт массив чисел и возвращает массив evenNumbers с одними лишь чётными числами. Если чётных чисел в исходном массиве нет, то массив evenNumbers возвращается пустым.

function selectEvenNumbers() {
  // здесь ваш код
}

Какие вопросы можно себе задать:

• Как компьютер может сказать, что число является чётным? Разделить на 2 и проверить, чтобы результат получился целым.
• Что я передаю этой функции? Массив.
• Что содержит этот массив? Одно или несколько чисел.
• Какие типы данных у элементов массива? Числа.
• Какова цель этой функции? Что я возвращаю в конце её выполнения? Цель — получить все чётные числа и вернуть их в массиве. Если нет чётных чисел, то массив возвращается пустым.

2. Пройдите по задаче вручную как минимум с тремя наборами данных

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

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

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

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

[1]
[1, 2]
[1, 2, 3, 4, 5, 6]
[-200.25]
[-800.1, 2000, 3.1, -1000.25, 42, 600]

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

Давайте пройдём по массиву [1]

1. Смотрим на единственный элемент массива [1].
2. Определяем, является ли он чётным. Не является.
3. Замечаем, что других элементов в массиве нет.
4. Определяем, что здесь нет чётных чисел.
5. Возвращаем пустой массив.

Теперь пройдём по массиву [1, 2]

1. Смотрим на первый элемент массива [1, 2]
2. Это 1.
3. Определяем, является ли он чётным. Не является.
4. Смотрим на следующий элемент.
5. Это 2.
6. Определяем, является ли он чётным. Является.
7. Создаём массив evenNumbers и добавляем в него 2.
8. Замечаем, что других элементов в массиве нет.
9. Возвращаем массив evenNumbers — [2].

Можно пройти по задаче ещё несколько раз. Обратите внимание, что количество шагов в алгоритме для [1] отличается от алгоритма для [1, 2]. Поэтому рекомендуется проходить по нескольким наборам данных. Например, с единственным элементом; смесь целых и нецелых чисел; многоразрядные числа; наборы с отрицательными числами.

3. Упрощайте и оптимизируйте свой алгоритм

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

1. Создадим функцию selectEvenNumbers.
2. Создадим новый пустой массив evenNumbers для хранения чётных чисел.
3. Проходим по каждому элементу массива [1, 2].
4. Находим первый элемент.
5. Делим его на 2 и определяем, чётный ли он. Если да, то прибавляем к evenNumbers.
6. Находим следующий элемент.
7. Повторяем шаг №4.
8. Повторяем шаги №5 и №4, пока не кончатся элементы в массиве.
9. Возвращаем массив evenNumbers вне зависимости от того, есть ли в нём что-то.

Этот подход напоминает математическую индукцию:

1. Доказываем истинность для n = 1, n = 2, …
2. Предполагаем, что будет истинно для n = k.
3. Доказываем истинность для n = k + 1.

4. Пишите псевдокод

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

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

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

Вот пример псевдокода, в основном состоящего из слов:

function selectEvenNumbers
создаём массив evenNumbers и делаем его эквивалентным пустому массиву
для каждого элемента в этом массиве
  смотрим, является ли элемент чётным
   если чётный (при делении на 2 результат получается нецелым)
     добавляем его к массиву evenNumbers
return evenNumbers

А вот псевдокод, в котором слов гораздо меньше:

function selectEvenNumbers
evenNumbers = []
for i = 0 to i = length of evenNumbers
  if (element % 2 === 0) 
    добавляем его к массиву evenNumbers
return evenNumbers

Главное, писать код построчно и понимать логику каждой строки.

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

5. Преобразуйте псевдокод в нормальный код и отладьте его

Когда ваш псевдокод будет готов, преобразуйте каждую строку в реальный код на вашем языке. Здесь мы воспользуемся JavaScript.

Если вы писали на бумаге, то перенесите всё в редактор в виде комментариев, а затем замените каждую строку.

Теперь вызовите функцию и дайте ей некоторые из ранее использованных наборов данных. Так можно проверить, возвращает ли код нужный результат. Также можете написать тесты для проверки соответствия выходных данных ожидаемому результату.

selectEvenNumbers([1])
selectEvenNumbers([1, 2])
selectEvenNumbers([1, 2, 3, 4, 5, 6])
selectEvenNumbers([-200.25])
selectEvenNumbers([-800.1, 2000, 3.1, -1000.25, 42, 600])

После каждой переменной или строки можно использовать console.log(). Это поможет проверить, ведут ли себя значения и код так, как ожидается, прежде чем двигаться дальше. Таким образом вы выловите любые проблемы, не зайдя слишком далеко. Вот пример того, какие значения можно проверить при начале работы.

function selectEvenNumbers(arrayofNumbers) {
let evenNumbers = []
 console.log(evenNumbers) // Удаляем после проверки выходных данных
 console.log(arrayofNumbers) // Удаляем после проверки выходных данных
}

Ниже приведён код, полученный после обработки каждой строки псевдокода. Символы // обозначают строки из псевдокода. Жирным выделен реальный код на JavaScript.

// function selectEvenNumbers
<b>function selectEvenNumbers(arrayofNumbers) {</b>
// evenNumbers = []
 <b> let evenNumbers = []</b>
// for i = 0 to i = length of evenNumbers
 <b> for (var i = 0; i < arrayofNumbers.length; i++) {</b>
// if (element % 2 === 0) 
<b>    if (arrayofNumbers[i] % 2 === 0) {</b>
// добавляем его к массиву evenNumbers
  <b>    evenNumbers.push(arrayofNumbers[i])
    }
  }</b>
// return evenNumbers
 <b> return evenNumbers
}</b>

Уберём псевдокод, чтобы не путаться.

function selectEvenNumbers(arrayofNumbers) {
  let evenNumbers = []
for (var i = 0; i < arrayofNumbers.length; i++) {
    if (arrayofNumbers[i] % 2 === 0) {
      evenNumbers.push(arrayofNumbers[i])
    }
  }
return evenNumbers
}

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

6. Упрощайте и оптимизируйте код

Возможно, вы заметили, что упрощение и оптимизация — это повторяющиеся темы.

«Простота — предпосылка надёжности».

Эдсгер Дейкстра, нидерландский учёный и один из первопроходцев в ряде областей информатики

В нашем примере одним из путей оптимизации будет фильтрация элементов в массиве посредством возвращения нового массива с помощью filter. В этом случае нам не нужно определять переменную evenNumbers, потому что filter вернёт новый массив с копиями элементов, которые соответствуют фильтру. При этом исходный массив не изменится. Также нам не нужно использовать цикл for. filter пройдёт по каждому элементу, и если вернёт true, то элемент попадёт в массив, а если false, то будет пропущен.

function selectEvenNumbers(arrayofNumbers) {
  let evenNumbers = arrayofNumbers.filter(n => n % 2 === 0)
  return evenNumbers
}

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

Задавайте себе такие вопросы:

• Каковы цели упрощения и оптимизации? Цели зависят от принятого в вашей команде стиля или ваших личных предпочтений. Вы пытаетесь максимально уплотнить код? Или вы хотите сделать его более читабельным? В таком случае вы можете добавить отдельные строки с определением переменной или вычислением чего-либо, а не пытаться всё сделать в одной строке.
• Как ещё можно сделать код более читабельным?
• Можно ли ещё уменьшить количество шагов?
• Есть ли переменные или функции, которые не нужны или не используются?
• Какие-то шаги повторяются? Посмотрите, можно ли определить в другой функции.
• Существуют ли более эффективные способы обработки крайних случаев?

«Программы должны быть написаны так, чтобы люди их читали, и лишь во вторую очередь — чтобы машины их исполняли».

Джеральд Сассман и Гарольд Абельсон, авторы “Structure and Interpretation of Computer Programs”

7. Отлаживайте

Этот шаг необходимо выполнять в ходе всего процесса. Сквозная отладка поможет раньше выловить любые ошибки синтаксиса или недостатки логики. Воспользуйтесь преимуществами своего IDE (Integrated Development Environment) и отладчика. При обнаружении бага рекомендуется просматривать код построчно, стараясь найти неожиданные вещи. Несколько советов:

• Читайте, что пишется в сообщения об ошибках в консоли. Иногда в них указываются номера строк для проверки. Это даст вам исходную точку для поисков, хотя иногда проблемы могут скрываться в других строках.
• Комментируйте блоки кода или строки, а также выходные данные, чтобы быстро подмечать поведение кода. При необходимости код можно всегда раскомментировать.
• Используйте другие образцы данных, если возникают непредусмотренные сценарии.
• Сохраняйте разные версии файла, если применяете другие подходы. Не стоит терять наработанное, если захочется откатиться к прежнему решению!

«Самый эффективный инструмент отладки — тщательное продумывание в сочетании с разумно размещёнными командами вывода на экран».

Брайан Керниган, профессор информатики в Принстонском университете

8. Пишите полезные комментарии

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

Избегайте таких комментариев:

// Это массив. Итерируем его.
// Это переменная.

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

• Для чего этот код?
• Что он делает?

9. Получайте отзывы посредством ревизии кода

Получайте отзывы от коллег, руководителей и других разработчиков. Читайте Stack Overflow. Смотрите, как другие решали аналогичные задачи и учитесь у них. Нередко бывает несколько способов решения задачи. Узнайте, что они собой представляют, и вам будет быстрее и проще приходить к ним самостоятельно.

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

Дядя Боб Мартин, программный инженер и соавтор манифеста Agile

10. Практикуйтесь, практикуйтесь, практикуйтесь

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

«Гордитесь тем, сколько вы прошли. Верьте в то, что пройдёте ещё больше. Но не забывайте наслаждаться путешествием».

Майкл Джозефсон, основатель Института этики Джозефа и Эдны Джозефсон

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

При решении задачи
существует несколько этапов:

1.     Постановка
задачи;

2.     Формализация
задачи;

3.     Анализ
математической задачи;

4.     Построение
алгоритма;

5.     Составление
программы и тестирование.

Давайте рассмотрим их
более подробно на примере следующего равенства:

|a|
· x = 3.

a
– вводится с клавиатуры.

Начнём
с постановки задачи. Нам нужно найти решение равенства, то есть x.
Таким образом, на этапе постановки задачи нужно:

·       
понять
условие задачи;

·       
выделить
исходные и результирующие данные;

·       
понять
отношения между ними.

Можно
сказать, что нам нужно ответить на вопросы:

·       
Что
нужно найти по условию задачи? В нашем случае нужно найти x.

·       
Что
при этом дано? Дано значение a.

·       
Чем
можно пользоваться при решении задачи? При решении нужно из равенства вывести
значение x.

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

.

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

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

Перейдём к этапу построения
алгоритма.

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

·       
каждая
базовая структура должна иметь один вход и один выход;

·       
блок-схема
должна изображаться при помощи стандартных элементов.

В начале нам нужно
нарисовать блок ввода переменной a.
Далее идёт проверка a. Если условие a
= 0 истинно, то на экран выведем сообщение, что «Нет решений». Если же условие ложно,
то снова будет идти блок условия, в котором проверим следующее: a
> 0. Если условие истинно, то x
= 3/a. Если условие ложно, то x
= 3/ (–a). После проверки этого
условия будет идти блок вывода значения x.
Конец программы.

Алгоритмический язык
– это язык описания алгоритмов с русскими служебными словами.

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

·       
конструкции
одного уровня вложенности записываются на одном вертикальном уровне;

·       
вложенная
конструкция записывается смещённой по строке на несколько позиций вправо
относительно внешней для неё конструкции.

Наш алгоритм будет
выглядеть следующим образом:

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

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

Запишем следующее:

program prim;

Далее объявим переменные a,
x вещественного типа.

begin

Организуем диалог между
компьютером и пользователем:

Writeln (‘Введите
значение a ‘);

Считаем её при помощи
функции Read и присвоим
соответствующей переменной.

Далее идёт первый
условный оператор, в котором проверяем следующее: a
= 0. Если условие истинно, то запишем вывод на экран сообщения «Нет решений»,
так как наше неравенство не будет иметь решения.

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

Итак, если условие ложно,
то после слова begin снова будет идти
условие, в котором будет проверяться следующее: a
> 0.

Если это условие истинно,
то x:=3/a.
Если же условие a > 0 ложно, то после else
x:=3/(–a).
Оформим вывод на экран x
при помощи функции Write.

Так как у нас операторная
скобка уже закрыта, переходим на строку ниже после end.

Завершим программу.

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

Заключительным этапом
построения программы решения задачи является тестирование.

Тестирование
– это этап, на котором экспериментально доказывается правильность алгоритма,
заключённого в программе, и работоспособность программы.

Тест
– это вариант решения задачи с заданными исходными данными, для которых
известен результат.

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

Начнём с простого. Если a
= 0, то ответом должно быть «Нет решений».

Проверим.

Эта ветвь работает верно.

Далее при a
> 0, x = 3/a.
Для простоты вычисления возьмём a
= 3. То есть x=1.

Проверим.

И снова мы получаем
верный результат.

Проверим заключительную
ветвь, если a < 0. Снова возьмём
для простоты вычислений число –3. Вычислим x:
3/(-(-3)) = 0.

Проверим нашу программу.

Мы получили верный ответ.

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

Пришла пора подвести
итоги урока.

Вспомним ещё раз, что в
себя включает каждый этап решения задачи.

Итак, на этапе постановки
задачи происходит определение исходных данных и искомых результатов.

На этапе формализации
происходит переход к задаче обработки некоторой знаковой системы, например, к
математической задаче.

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

При построении
алгоритма нужно определить структуру алгоритма и последовательности команд.
После чего представить алгоритм на каком-либо языке описания алгоритмов.
Например, в виде блок-схемы или же на учебном Алгоритмическом языке.

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

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

Муниципальное
общеобразовательное учреждение

средняя
общеобразовательная школа №3

Учебное
пособие

по
программированию

для учащихся
10 классов

Составила:

Жесткова Светлана
Семеновна

Учитель информатики
МОУ СШ№3

Саяногорск

Оглавление

Основные
этапы решения задач на компьютере 3

Язык
программирования Паскаль 5

Структура
программы на Паскале 8

Типы
данных 10

Операторы
ввода и вывода 11

Линейный
алгоритм 12

Разветвляющиеся
вычислительные процессы 17

Циклические
вычислительные процессы 19

Массивы 22

Процедуры и
функции 24

Строковые
переменные 26

Множества 28

Список
использованной литературы: 31

Основные этапы решения задач на компьютере

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

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

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

Второй
этап – математическое или информационное
моделирование. Цель этого этапа –
создать такую математическую модель
решаемой задачи, которая может быть
реализована в компьютере. Существует
целый ряд задач, где математическая
постановка сводится к простому
перечислению формул и логических
условий. Этот этап тесно связан с первым
этапом, и его можно отдельно рассматривать,
однако возможно, что для полученной
модели известны несколько методов
решения, и тогда предстоит выбрать
лучший. Для вышеописанной задачи данный
этап сведется к следующему: введенные
в компьютер числа запомним в памяти под
именами А и В, затем вычислим значение
суммы этих чисел по формуле А+В, и
результат запомним в памяти под именемS.

Третий
этап – алгоритмизация задачи. На основе
математического описания необходимо
разработать алгоритм решения.

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

Используются
различные способы записи алгоритмов,
Широко распространен словесный способ
записи: это записи рецептов приготовления
различных блюд в кулинарной книге,
инструкции по использованию технических
устройств, правила правописания и многие
другие. Наглядно представляется алгоритм
языком блок-схем:

.

Выполнение

действий

Например:

Составим
блок схему для приведенной выше задачи:

Введем
два числа, найдем их сумму и выведем на
экран.

Свойства
алгоритма

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

Однозначность
алгоритма,под которой понимается
единственность толкования исполнителем
правил выполнения действий и порядка
их выполнения. Чтобы алгоритм обладал
этим свойством, он должен быть записан
командами из системы команд исполнителя.

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

Конечность
алгоритма – обязательность
завершения каждого из действий,
составляющих алгоритм, и завершимость

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

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

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

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

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

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

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

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

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

Для
повышения качества выполнения этого
этапа используются специальные программы
– отладчики,которые позволяют
исполнить программу “по шагам” с
наблюдением за изменением значений
переменных, выражений и других объектов
программы, с отслеживанием выполняемых
операторов.

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

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

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Тема: Решение задач на языке Pascal.

Цели урока:

1. Обобщить и систематизировать знания учащихся по данной теме.
2. Продолжить формировать практические навыки по составлению блок схем и программ.
3. Показать взаимосвязь математики и информатики. Научить использовать знания, полученные на уроке математики при решении задач по информатике.
4. Развивать логическое мышление, умение обобщать, сопоставлять и применять полученные знания на практике.
5. Развивать познавательную деятельность учащихся, прививать интерес к составлению программ, развивать умение анализировать происходящие изменения в решении задач.

Воспитательные цели:

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

Тип урока: Комбинированный.

Метод: Проблемно – поисковый метод при решении задач по информатике.

ХОД УРОКА

Учитель: В начале урока я предлагаю следующую задачу для решения в классе: Найти наибольшее число из трех заданных чисел. На доске записываю несколько троек чисел: 568, 742, 390.

Учащиеся называют максимальное число: 742.

Вопрос: “Каким образом вы определили, что данное число максимальное?”.

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

Учитель: Мы сравнили числа друг с другом.

Учитель: А как на уроке математике вы бы сравнили натуральные трехзначные числа?

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

Вывод: Итак, максимальное число: 742

Проблема: “А как компьютер сравнит три числа?”

Я обращаю внимание ребят, что машина может сравнивать только два числа

Обозначим одно число буквой А, второе число буквой B, третье число – буквой С.

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

Учитель: Нарисуйте в тетради блок – схему для сравнения трех чисел.

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

Учащиеся самостоятельно составляют программу.

Учитель: Проверьте правильность работы программы, введите заданные числа и посмотрите результат.

Проблема: А может ли измениться исходное значение переменной А в процессе работы программы?

Ответ: Да.

Учитель: А как? Ответ обоснуйте.

Решение:

1. Находим наибольшее из первых двух данных чисел A и B, а затем – максимальное из полученного числа и третьего данного числа С.

Program MAX1;
Var A, B, C, max: real;
begin
writeln (‘Введите три числа A, B, C’);
readln (A, B, С);
if AB then max:=A else max:=b;
if C max then max:=C;
writeln(‘Максимальное значение=’,max);
end.

Учитель: Как вы думаете, можно ли решить задачу другими способами?

Учащиеся получают задание на уроке и продолжают поиск решения задачи.

Предполагаемые решения учащихся:

2 способ. При решении задачи можно проверить, является ли первое число A максимальным и если не является, то сравниваем второе и третье число B и C.

Program MAX2;
Var A, B, C, max: real;
begin
writeln (‘Введите три числа A, B, C’);
readln (A, B, С);
If (AB) and (AC) then max:=A;
if BC then Max:=B else Max :=C;
Writeln(‘Максимальное значение =’, Max);
End;

3 способ. Можно решить задачу, сравнивая попарно все числа .

Program MAX3;
var A, B, C, Max: real;
begin
Writeln(‘Введем три числа’);
readln(A, B, C);
If (AB) and (AC) then Max:= A;
If (BA) and (BC) then Max:=B;
If (CA) and (CB) then Max:=C;
Writeln(Max:6:2);
end.

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

Проблема: А можно написать программу, чтобы она выстраивала числа в порядке возрастания или убывания?

Ученики предлагают свои варианты решения данной проблемы.

Варианты решения задачи:

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

Program MAX4;
Var A, B, C, Max: real;
begin
Writeln(‘Введите три числа’);
Readln(A, B, C);
If (AB) and (AC) and (BC) then writeln (A, ‘ ‘,B,’ ‘,C);
If (BC) and (BA) and (AC) then writeln (B, ‘ ‘,A,’ ‘,C);
If (CA) and (CB) and (AB) then writeln (C, ‘ ‘,A,’ ‘,B);
If (AB) and (AC) and (CB) then writeln (A, ‘ ‘,C,’ ‘,B);
If (BC) and (BA) and (CA) then writeln (B, ‘ ‘,C,’ ‘,A);
If (CA) and (CB) and (BA) then writeln (C, ‘ ‘,B,’ ‘,A);
End.

Программа печатает максимальное число, минимальное число и среднее число.

Program MAX5;
Var A, B, C, Max, Min, Sr : real;
begin
Writeln(‘Введите три числа’);
Readln(A, B, C);
If AB Then Max:=A else Max:=B;
If C Max Then Max:=C;
If AIf CIf (AB) and (AIf (BA) and (BIf (CA) and (CIf (BC) Then Sr:=B;
If (AC) Then Sr:=A;
If (CB) Then Sr:=C;
Writeln (‘Max=’, Max:6:2);
Writeln (‘Sr=’, Sr:6:2);
Writeln (‘Min=’, Min:6:2);
End.

РАССМОТРИМ ЗАДАЧУ № 2.

Даны три натуральных числа. Найти их наибольший общий делитель.

Вопрос: Какие существуют методы нахождения НОД?

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

1. разложения на простые сомножители,
2. алгоритм Евклида,
3. целочисленное деление.

Найти НОД чисел 48, 36, 24

Разложим на множители числа:

48 = 2 * 2 * 2 * 2 *3
36 = 2 * 2 * 3 * 3
24 = 2 * 2 * 2 * 3

Из множителей вычеркиваем те, которые не входят в разложение второго и третьего числа

– это числа 2 * 2 * 3 =12

Учитель: Сделайте вывод для тройки чисел x, y, z.

Проблема: Какие же знания и умения необходимы для построения алгоритма нахождения НОД?

Для того чтобы построить алгоритм, необходимо уметь:

• определять все простые множители в пределах заранее неизвестных чисел х и у, z;

• хранить эти простые множители и обращаться к ним;

• хранить все сомножители для чисел х и у, z;

• выбирать из трех множеств одинаковые элементы.

Сделайте анализ.

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

Второй метод решения – рекурсивный. Его общепринятое название – алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.

НОД (х, у) вычисляется в соответствии со следующим правилом:

НОД (х, у)=

Мы разбирали решение задачи для нахождения НОД двух чисел.

Для решения данной задачи воспользуемся циклом с постусловием.

Третий метод решения – это целочисленное деление.

Пусть х и у – одновременно не равные нулю целые неотрицательные числа, и пусть ху. Если у = 0, то НОД (х, у) = х, а если у0, то для чисел х, у и r, где r остаток от деления х на у, выполняется равенство НОД (х, у) = НОД (у, r).

В соответствие со следующим правилом:

НОД(48, 18) = НОД(18, 12) = НОД(12, 6) = 6.

Первое число делим нацело на второе. Очевидно, что остаток целочисленного деления меньше второго числа. Если остаток равен нулю, то это значит, что первое число нацело делится на второе, и в этом случае второе число и будем считать НОД (в соответствие с определением). Если остаток не равен нулю, то заменим первое число на второе, а второе – на остаток, и будем повторять действия до тех пор, пока остаток не станет равным нулю.

Запишем алгоритм решения задачи:

1. Ввод натуральных чисел х, у.

2. Найдем r – остаток от деления х нацело на у.

3. Если r = 0, то найдем значение у, иначе х:=у; у:= r.

4. Найдем r – остаток от деления х нацело на у.

• Вычислить значение х

• Порядок действий имеет большое значение. Результат выполнения операций x:=x; y:=r отличен от результата выполнения операций
  y: = r; x: =y.

Проблема: А правильно ли мы составили алгоритм?

Задание на дом: Докажите правильность алгоритма.

Решение задачи для нахождения НОД двух чисел.

Program NOD_1;
Var x, y:integer;
Begin
Writeln(‘Введите два числа’);
Readln (x, y);
Repeat
If x y then x:= x mod y else y:= y mod x;
Until (x = 0) or ( y = 0);
{до тех пор, пока одно из чисел не станет равно нулю}
Writeln (‘НОД=’, x + y);
{ Вывод НОД. Одно из чисел обязательно равно нулю}
Readln;
End.

Машина может находить НОД двух чисел.

Проблема:

Как составить программу для нахождения НОД трех?

Учащиеся:

Сначала находим НОД двух чисел, а затем находим НОД третьего числа.

НОД (a, b, c) = НОД (НОД(a, b), c).

Я предлагаю ученикам самим решить задачу.

Один из способов решения задачи, предлагаемый учениками приведен ниже.

Программа на Паскале:

Program NOD_2;
Var A, B,C, S:integer;
Begin
Readln(A, B, C);
Repeat
If AB then A:=A mod B
Else B:=B mod A;
Until (A = 0) or ( B = 0);
Writeln (‘НОД=’, A + B);
S:=A + B;
Repeat
If S C then S:= s mod C else C:= C mod S;
Until (S = 0) or ( C = 0);
Writeln (‘НОД=’, S + C);
{Вывод НОД. Одно из чисел обязательно равно нулю
Readln;
End.

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

Для учеников проблема состоит еще и в том, чтобы выбрать метод, который будет более эффективен и прост в решении.

Домашнее задание:

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

Итак, вы получили задание написать программу на некотором языке программирования (Basic, Pascal, C++, Fortran,…). Что делать?
 

1. Постановка задачи

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

2. Алгоритм

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

  123
  124
  125
  134
  135
  145
  234
  235
  245
  345

Далее вы снова проделываете шаг 2 и снова шаг 3.
 

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

Так, например, если нужно создать комбинации из N чисел по K элементов, надо слегка усовершенствовать шаг 3. Сначала вы увеличиваете предпоследнее число на единицу, затем число, стоящее перед ним, и так до первого числа в комбинации.
 

3. “Читабельность”

Вы должны понимать, что код должен быть написан таким образом, что проверяющий или кто-либо другой без лишнего труда разобрался в логике программы. Возможно, Вам самим придется использовать старый код спустя некоторое время, и легко читаемая структура позволит Вам быстро освежить в памяти написанное ранее. В этом Вам помогут отступы, небольшие комментарии, удобные имена, имена со смыслом для переменных и функций (например, Comb для комбинации, Time для времени, Num от “number” для числа или номера в списке).

4. Простота

Нет смысла писать программу в 100 строк, если можно уложиться в 20 строк! Если вам необходимо повторять какое-либо действие много раз, используйте цикл. А если вам нужно повторять набор циклов и команд? Тогда лучше создавать функции, процедуры или классы, которые вы можете вызвать в любой части программы столько раз, сколько необходимо.
 

Так, например, для приведенного выше примера, мы можем создать процедуру, которую будем вызывать в цикле много раз. На языке С++, мы можем написать это в следующем виде:
 

int NewPermutation (int* Comb, int N, int K, int step)
{
    if (step == 0)
       for (int i = 0; i < K; i++)
          Comb[i] = i;
    if (step != 0)
       if (N - 1 > Comb[K - 1])
          Comb[K - 1] = Comb[K - 1] + 1;
       else
       {
          for (int i = K - 1; i > 0; i--)
             if ((N - K + i - 1) > Comb[i - 1])
             {
                Comb [i - 1] = Comb [i - 1] + 1;
                for (int j = i; j < K; j++)
                   Comb[j] = Comb[i - 1] + j - (i - 1);
                break;
             }
       }
    return 0;
}

 
Здесь функция использует предыдущую комбинацию Comb и создает следующую.
Если вы хотите создать весь список, то вам надо будет запустить цикл

for (int step = 0; step < NumComb; step++),

в котором будете вызывать функцию для создания каждой следующей комбинации.
 

5. Не изобретайте велосипед

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

6. Проверка и работа над ошибками

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

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

7. Навороты и Оптимизация

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

Заказать задачу по программированию

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