Что такое трассировка алгоритма

Что такое трассировка алгоритма

Все, что необходимо начинающему и опытному программисту


Главная страница
Библиотека (скачать книги)
Скачать софт
Введение в программирование
Стандарты для C++
Уроки по C#
Уроки по Python
HTML
Веб-дизайн
Ассемблер в среде Windows
ActiveX
Javascript
Общее о Линукс
Линукс — подробно
Линукс — новое
Delphi
Паскаль для начинающих
Турбопаскаль
Новости
Партнеры
Наши предложения
Архив новостей

Трассировка

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

Пример 6.4.
Вычисление суммы чисел от 6 до 10

Рис. 6.3. Блок-схема алгоритма вычисления суммы чисел от 6 до 10

Для проверки правильности работы программы рекомендуется пошагово отслеживать изменение всех переменных после выполнения каждого оператора программы.
Такой процесс называется трассирввкой. Продемонстрируем этот прием (табл. 6.1).
В результате работы программы на экране получим число 40.

Таблица 6.1. Трассировка программы из примера 6.4

for N:= 6 to 10 do

For N:= 6 to 10 do

For N:= 6 to 10 do

For N:= 6 to 10 do

For N:= 6 to 10 do

For N:=6 to 10 do

writeln (‘Сумма чисел’,S:3)

На экране: Сумма чисел=40

Для операторов, выполняющих проверку условий (if, for и т. п.) в столбце «Условие» принято указывать результат проверки. В данном случае в цикле for проверяется условие продолжения цикла.
Символы «. » подчеркивают, что значение счетчика цикла по выходе из цикла считается неопределенным.

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

Вычисление суммы ряда

Рассмотрим задачу вычисления суммы ряда:
1/(1*1) + 1/(2*2) + 1/(3*3) + 1/(4*4) + 1/(5*5)

Здесь мы имеем ряд дробей, у которых в знаменателях записаны квадраты чисел от 1 до 5.
Рассмотрим каждую дробь как произведение двух дробей, например:
1/(3*3) = 1/3 * 1/3

В общем виде это можно записать так:
1/(N * N) = 1/N * 1/N

Блок-схема алгоритма решения задачи представлена на рис. 6.4.

Рис. 6.4. Блок-схема алгоритма вычисления суммы ряда

Задание 6.5.
Написать программу вычисления n! (факториал числа n), где n положительно. Определение факториала:

Другими словами, n! — это произведение первых n натуральных чисел.

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

Получаем общий вид выражения: Р = Р * k (то есть воспользуемся рекуррентной формулой вычисления факториала: n! = (n — 1)! * n).

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

Задание 6.6.
Написать программу вычисления суммы ряда S=1 + 2 + 3 + 4 + 5 + 6. Нарисовать блок-схему и заполнить таблицу трассировки. Убедиться при трассировке, что сумма равна 21.

Таблица 6.2. Заготовка для таблицы трассировки алгоритма из задания 6.6

Задание 6.6.
Написать программу вычисления суммы ряда для n слагаемых (n вводится с клавиатуры):
1/(1*2*3) + 1/(2*3*4) + 1/(3*4*5) + 1/(4*5*6) + …

Задание 6.7.
Используя возможности модуля Crt для работы с экраном в текстовом режиме, написать программу, которая 16 раз меняет цвет экрана и выводит любой текст на новом фоне в центр экрана.
Пояснение: разумно, если цвет фона и параметр цикла будут одной переменной (палитра цветов изменяется в диапазоне 0-15).

Задание 6.8.
Используя возможности модуля Crt, напишите программу, в которой символ «звездочка» (*) пробегает по всему периметру экрана из верхнего левого угла.
Пояснение: в программе организуйте 4 цикла. В качестве счетчика используйте координаты X и Y. Нарисуйте блок-схему алгоритма.
Попробуйте изменить программу, используя всего два цикла: в одном цикле звездочки бегут сразу по верхней и нижней строкам экрана, в другом — сразу по левому и правому краю. Пусть каждая следующая звездочка выводится случайным цветом.

Задание 6.9.
По экрану разбросайте 1000 звездочек в случайном месте случайным цветом с небольшой задержкой. Не забудьте инициализировать датчик случайных чисел в начале программы — один раз! Нарисуйте блок-схему алгоритма.

1. Для организации многократно повторяющихся действий с заранее известным числом повторений используется оператор цикла for.
2. Счетчик цикла всегда имеет порядковый тип.
3. Счетчик цикла изменяется с шагом +1, если оператор имеет форму
for . = . to . do
4. Счетчик цикла изменяется с шагом -1, если оператор имеет форму
for . =. downto . do
5. Чтобы узнать, сколько раз выполнится тело цикла for, нужно найти разность между крайними значениями счетчика (по модулю) и прибавить к результату 1.
6. Не рекомендуется изменять счетчик цикла в теле цикла.
7. Если внутри цикла for поставить еще один цикл for, то количество раз, которое выполнится тело внутреннего цикла, равно произведению числа повторений внешнего цикла на число повторений внутреннего.
8. Для проверки правильности работы алгоритма его выполняют вручную, шаг за шагом, отслеживая изменения всех переменных. Это называется трассировкой.

1. Какой оператор нужно использовать, чтобы вывести в каждой строке экрана слово «Привет»?
2. Чем отличаются формы «to» и «downto» оператора for?
3. Переменные какого типа должны использоваться в качестве счетчика цикла for?
4. Сколько раз выполнится тело внутреннего цикла:
for i:=2 to 6 do
for j:=5 downto 3 do
writeln(‘*’).
5. Написанная программа выдает странный результат. Вероятно, программа написана с ошибкой. Как понять, где содержится ошибка?
6. Требуется последовательно присвоить переменной N значения всех трехзначных чисел. Напишите оператор, присваивающий переменной N нужные значения.

Как осуществляется трассировка алгоритма программы?

Подумай

  • Что такое алгоритм?
  • Каково значение алгоритма в программировании?
  • В чем заключается необходимость пошагового выполнения программы?

Трассировка программы

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

Ошибки, допускаемые программистами в процессе составления программ:

  1. Синтаксические ошибки;
  2. Связи со временем выполнения программы;
  3. Алгоритмические ошибки.
  • Как выявить эти ошибки в процессе программирования?
  • Как пошагово исправлять подобные ошибки в процессе написания программы?

При запуске программ, команды выполняются одна за другой со скоростью работы процессора компьютера. Программист не может уследить за тем, какое выполняется действие в данный момент, а также проконтролировать обработку алгоритма. Для того чтобы найти ошибку в программе, нужно знать точный порядок выполнения действий. Это называется трассировкой программы, или ее пошаговым (step-by-step) выполнением. При трассировке программист может выполнять каждую команду в программе по отдельности и найти ошибку. В среде Lazarus есть два способа трассировки: один из них – исправление ошибки без захода в процедуру Шаг в обход (Step over), второй – с заходом в процедуру Шаг со входом (Trace into) (рис. 1). Трассировка без входа в процедуру выполняет только основную часть программы, трассировка сопровождающих (дополнительных) программ не выполняется, все они выполняются одним шагом. Во втором случае выполняется трассировка всех программ, а не только пошаговая проверка основной программы.

Для выполнения трассировки необходимо выбрать из меню Запуск команду Step over или Trace into. В результате в окне редактора выделяется первое указание сопровождающей программе. чтобы выполнить выделенную команду, из меню Запуск выберите команду Step over или Trace into. После выполнения команды выделяется следующее указание.

Трассировку можно активировать с помощью функциональных клавиш. Команде Step over соответствует клавиша , а команде Trace into – клавиша .
​В любой момент времени можно остановить трассировку и продолжить выполнение программы. Для этого из меню Запуск нужно выбрать команду Запустить.
​Если необходимо выполнить трассировку части программы, нужно установить курсор в той строке, с которой нужно начать проверку, и из меню Запуск выбрать команду Run to сursor или нажать клавишу . После этого, при помощи клавиши или можно выполнить трассировку необходимого фрагмента программы.

Теперь рассмотрим конкретный пример. В процессе программирования зададим форму с кнопкой (рис. 2).
​Нажимая на кнопку, откроем поле для кода программы и впишем значение к = 10 (рис. 3).
​Как видно из примера, при выполнении программы была допущена ошибка на 3 позиции 30-го ряда: Identifier not found «k» (переменная k не описана), а на 6-й позиции 30-го ряда по правилам программирования должен быть оператор присваивания (рис. 4). Для исправления ошибок опишем переменную k в разделе var и запишем знак присваивания ":=" (рис. 5). После исправления ошибок появится сообщение «Проект «…» успешно собран» (рис. 6).

Существует достаточно много различных алгоритмов трассировки, которые имеют различную эффективность. Одни алгоритмы более приемлемы на начальных этапах трассировки при свободном от трасс коммутационном поле. Другие алгоритмы более эффективны при уже заполненном трассами коммутационном поле. Уяснение сущности алгоритмов трассировки будет рассмотрено на примере базового волнового алгоритма.

Волновой алгоритм

Волновой алгоритм Ли (по имени математика, автора алгоритма) применяется для трассировки печатных проводников. Предположим есть коммутационное поле, есть точки АиВ, которые нужно соединить проводником, и есть препятствия, которые следует обойти. Необходимо найти трассу минимальной длины в ортогональной метрике (рис. 5.10).

Рис. 5.10. Иллюстрация волнового алгоритма

Алгоритм содержит следующие основные шаги.

Формируем условную числовую волнуот источника к приёмнику (от начала трассы к её концу). Обозначаем ячейку с точкойАкак ячейку № 0, соседние ячейки№ 1, соседние к этим№ 2 и т. д. до достижения конечной точки (в данном случаеВ). Соседними ячейками являются те, которые граничат ребрами.

Строим трассу. Трасса строится от приёмника к источнику по фронтам числовой волны, в порядке уменьшения значения фронта. Направление трассы меняем только при необходимости.

Алгоритм требует огромных вычислительных затрат, и поэтому имеются различные модификации ускоренной трассировки. Например — построение ортогональных лучей на первых этапах трассировки (лучевой алгоритм рис. 5.11).

Рис. 5.11. Лучевой алгоритм

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

Контрольные вопросы

Что является исходным для решения топологических задач?

Перечислите способы задания графов и опишите их?

Назовите наиболее распространенные разновидности графов?

Чем определяются структурные свойства связных графов?

Каков принцип заполнения матрицы соединений?

В чём отличие матрицы инциденций от матрицы соединений?

Какие три основные задачи топологического проектирования можно выделить?

Как формулируется задача разбиения, размещения и трассировки?

Как осуществляется алгоритм последовательного разбиения?

Что такое коммутационное поле и позиция? Приведите их примеры?

Какие основные шаги содержит алгоритм Ли и его применение?

Лекция 6. Элементная база эс и конструкции плат

Элементная база

Основные параметры цифровых ИМС:

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

вольт-амперные характеристики (ВАХ) для входа и выхода микросхем.

мощностные параметры (P 1 ,P 0 )

Параметры быстродействия определяются по форме стандартного цифрового сигнала (рис. 6.1). Эти параметры определяют минимальную длительность такта (рис. 6.2), а следовательно, возможности системы при обработке информации.

Рис. 6.1. Форма стандартного цифрового сигнала

Рис. 6.2. Определение длительности такта цифрового сигнала

Основные временные параметры, характеризующие быстродействие:

twширина импульса на уровне 0,5,

tpдлительность импульса на уроне 0,9,

Минимальная длительность цикла связана с минимальным фронтом: tc10 tr, т.е. максимальная тактовая частота будет равнаT = 1/tc.

Пример. Пусть tr= 1 нс, тогдаtc=10 нс, а максимальная тактовая частота будет

Оператор
Ссылка на основную публикацию
Что такое синтаксический пакет
Одна из проблем, с которыми можно столкнуться при установке приложения apk на Android — сообщение: «Синтаксическая ошибка» — ошибка при...
Что отражает двоичная матрица
Представление информации в табличной форме широко распростране­но. Чаще всего мы пользуемся прямоугольными таблицами. Простейшая таблица состоит из строк и граф...
Что означают значки в погоде на айфоне
Самые интересные новости о технике Apple и не только. Что означают значки погоды на iPhone? Сегодняшняя тема весьма заинтересует многих...
Что такое синтаксическая ошибка на андроиде
При попытке распаковать приложение из APK на Android может появляться «Синтаксическая ошибка. При синтаксическом анализе пакета возникла неполадка». Это значит,...
Adblock detector