Это процесс исполнения программы человеком - как если бы он был компьютером, который должен исполнять эту программу. Основная трудность ручной прокрутки для автора разработанного алгоритма - забыть суть задачи, которая решается, идею алгоритма и "механически и неукоснительно" исполнять то, что написано в алгоритме (ведь именно так и будет поступать компьютер). И тогда если в алгоритме есть ошибки, то человек, выполняющий ручную прокрутку, сможет их обнаружить.
Обнаружив ошибку, нужно скорректировать алгоритм и вновь попробовать выполнять ручную прокрутку, сначала на этом же тесте, а затем и на других, и так до тех пор, пока автору не покажется, что его алгоритм правильно работает на всех тестах.
Как же выполнять ручную прокрутку?
Прежде всего, надо аккуратно выписать алгоритм и тестовый пример, на котором будет выполняться ручная прокрутка. А затем построчно исполнять алгоритм до конца.
1 2 3 4 5 6 7 8 9 10 ответ
A : 5 11 4 4 4 2 2 2 2 2 5
max : 1 3
tek : 1 1 1 2 3 1 2 3 4 5
Ввод А[1..10] i : 2 3 4 5 6 7 8 9 10 11
max = 1, tek = 1
для i от 2 до 10
если A[i] = A[i-1]
то tek = tek + 1
иначе если tek > max то max = tek
tek = 1
Вывод max
Ответ : 3 (max) - ОШИБКА !!!
Выше приведен пример ручной прокрутки для алгоритма о наибольшем числе одинаковых идущих подряд чисел.
Прокомментируем его построчно по ходу выполнения:
Ввод А[1..10]
После выполнения этой строчки в памяти компьютера появятся введенные данные
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
т.е. A[1]=5, A[2]=11, A[3]=4, ..., A[10]=2
Мы помним, что правильный ответ для этого случая - 5 (5 подряд идущих чисел 2, были еще и 3 подряд идущих числа 4, но 5 больше 3 и потому правильный ответ - 5)
max = 1, tek = 1
Переменные max и tek получили значение 1
в ручной прокрутке это записывается так :
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max tek
1 1
В принципе "документирование" ручной прокрутки можно было осуществлять и горизонтально:
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1
сдвигом мы отображаем течение времени, т.е. что переменная tek получила свое значение после переменной max.
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1
i : 2
Переменная i получает значение 2, это значение сверяется с числом 10 - поскольку 2<=10, то управление передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки, чему равно I? 2, следовательно, A[2] сравнивается с A[1], т.е. 11 сравнивается с 5. Равны? Нет! Следовательно, выполняться будет то, что после иначе:
иначе если tek > max то max = tek
Tek сейчас равно 1, max тоже равно 1
1 > 1 ? - нет, значит оператор после то не выполняется и пока все остается как было:
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1
i : 2
tek = 1
У нас в таблице tek и так равно 1 - но сейчас мы - ПК и, как и он, должны вместо старого значения занести новое (пусть даже то же самое)
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1
i : 2
И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1
i : 2 3
i увеличивается на 1 (было 2 - становится 3) 3<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки чему равно I? 3, следовательно A[3] сравнивается с A[2], т.е. 4 сравнивается с 11. Равны? Нет! Следовательно, выполняться будет то, что после
иначе:
иначе если tek > max то max = tek
Tek сейчас равно 1, max тоже равно 1
1 > 1? - нет, значит оператор после то не выполняется и пока все остается как было:
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1
i : 2 3
tek = 1
У нас в таблице tek и так равно 1 - но сейчас мы-ПК и как и он должны вместо старого значения занести новое (пусть даже то же самое)
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1 1
i : 2 3
И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1 1
i : 2 3 4
i увеличивается на 1 (было 3 - становится 4) 4<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки чему равно I? 4, следовательно, A[4] сравнивается с A[3], т.е. 4 сравнивается с 4. Равны? Да! Следовательно, выполняться будет то, что после то:
то tek = tek + 1
Tek сейчас равно 1, станет 2
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1 1 2
i : 2 3 4
При этом операторы после иначе не исполняются (поскольку исполнялись операторы после то). И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1 1 2
i : 2 3 4 5
i увеличивается на 1 (было 4 - становится 5) 5<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки чему равно I? 5,
Следовательно, A[5] сравнивается с A[4], т.е. 4 сравнивается с 4 . Равны? Да! Следовательно, выполняться будет то, что после то:
то tek = tek + 1
Tek сейчас равно 2, станет 3
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1 1 2 3
i : 2 3 4 5
При этом операторы после иначе не исполняются (поскольку исполнялись операторы после то). И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1
tek : 1 1 1 2 3
i : 2 3 4 5 6
i увеличивается на 1 (было 5 - становится 6) 6<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки чему равно I? 6, следовательно A[6] сравнивается с A[5], т.е. 2 сравнивается с 4 . Равны ? Нет ! Следовательно выполняться будет то, что после
иначе:
иначе если tek > max то max = tek
Tek сейчас равно 3, max тоже равно 1
3 > 1 ? - Да , значит выполняется оператор после то
то max = tek
и max получает значение 3:
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3
i : 2 3 4 5 6
!!! напомним размещение операторов
иначе если tek > max то max = tek
tek = 1
Оператор tek=1 находится после иначе на одном уровне с оператором ЕСЛИ - это означает, что в случае иначе он обязательно должен быть выполнен:
tek = 1
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1
i : 2 3 4 5 6
И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1
i : 2 3 4 5 6 7
i увеличивается на 1 (было 6 - становится 7) 7<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки, чему равно I? 7. Следовательно, A[7] сравнивается с A[6], т.е. 2 сравнивается с 2. Равны? Да! Следовательно, выполняться будет то, что после то:
то tek = tek + 1
Tek сейчас равно 1, станет 2
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2
i : 2 3 4 5 6 7
При этом, операторы после иначе не исполняются (поскольку исполнялись операторы после то). И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2
i : 2 3 4 5 6 7 8
i увеличивается на 1 (было 7 - становится 8) 8<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки чему равно I? 8, следовательно A[8] сравнивается с A[7], т.е. 2 сравнивается с 2. Равны? Да! Следовательно, выполняться будет то, что после то:
то tek = tek + 1
Tek сейчас равно 2, станет 3
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2 3
i : 2 3 4 5 6 7 8
При этом, операторы после иначе не исполняются (поскольку исполнялись операторы после то). И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2 3
i : 2 3 4 5 6 7 8
i увеличивается на 1 (было 8 - становится 9) 9<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки чему равно I? 9, следовательно A[9] сравнивается с A[8], т.е. 2 сравнивается с 2 . Равны? Да! Следовательно, выполняться будет то, что после то:
то tek = tek + 1
Tek сейчас равно 3, станет 4
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2 3
i : 2 3 4 5 6 7 8 9
При этом операторы после иначе не исполняются (поскольку исполнялись операторы после то). И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2 3 4
i : 2 3 4 5 6 7 8 9
i увеличивается на 1 (было 9 - становится 10) 10<=10 и потому управление вновь передается внутрь цикла
если A[i] = A[i-1]
Смотрим в таблицу ручной прокрутки чему равно I? 10. Следовательно, A[10] сравнивается с A[9], т.е. 2 сравнивается с 2 . Равны? Да! Следовательно, выполняться будет то, что после то:
то tek = tek + 1
Tek сейчас равно 4, станет 5
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2 3 4 5
i : 2 3 4 5 6 7 8 9 10
При этом операторы после иначе не исполняются (поскольку исполнялись операторы после то). И поскольку в цикле больше операторов нет, то управление вновь передается к строке начала цикла:
для i от 2 до 10
1 2 3 4 5 6 7 8 9 10
A : 5 11 4 4 4 2 2 2 2 2
max : 1 3
tek : 1 1 1 2 3 1 2 3 4 5
i : 2 3 4 5 6 7 8 9 10 11
i увеличивается на 1 (было 10 - становится 11) 11>10 и потому цикл завершен и управление передается к оператору, следующему за оператором цикла :
Вывод (max)
Смотрим, что у нас находится в переменной Max ? 3 !
Число 3 и будет выведено в качестве ответа.
Это - ошибка, ведь правильный ответ - 5 для данного теста.
Ошибка заключается в том, что в алгоритме не предусмотрен случай, когда наибольшее число подряд идущих получается в результате завершения массива. Т.е., когда соответствующие подряд идущие элементы стоят в конце массива. Исправить алгоритм легко - достаточно поставить дополнительный оператор сравнения переменных max и tek после завершения цикла :
Ввод А[1..10]
max = 1, tek = 1
для i от 2 до 10
если A[i] = A[i-1]
то tek = tek + 1
иначе если tek > max то max = t
tek = 1
!!!! если tek > max то max = tek
Вывод (max)
Ну а теперь, когда разработчик алгоритма убежден, что алгоритм работает верно, легко по алгоритму написать текст соответствующей программы. Как это делается, описывается в следующем пункте.
Но прежде несколько замечаний относительно ручной прокрутки. Наверняка многим показалось, что ручная прокрутка - это очень трудоемкий процесс. И некоторые попробуют обходится без него. Это опасный путь, и он может привести к значительно большей трате времени. С другой стороны, регулярное применение ручной прокрутки приводит к тому, что Ваш мозг начинает выполнять эту работу подсознательно еще в тот момент, когда Вы только сочиняете алгоритм, что соответственно резко сокращает количество допущенных Вами ошибок при разработке все новых и новых алгоритмов. Кроме того, выполнение ручной прокрутки позволяет легко найти ошибки на стадии отладки.
