Предмет давно сдан, но есть один вопрос к другим студентам кто его сдавал.
Для допуска к зачету нужно было сделать одну работу. Работа легкая если делать расчеты самому, но программная реализация довольно сложная (IMHO).
Получение польской записи из исходной формулы - можно найти готовые программы, да и самому сделать при наличии желания\времени. НО построение бинарного дерева и отображение графа, построенного на основе бинарного дерева - кто-нибудь вообще это делал? Каким образом?
Буду благодарен за полезную информацию на этот счет. В свое время из-за ограниченного времени просто "захардкодал" нужную формулу и нарисовал граф под свою формулу. Но было интересно как это можно реализовать для любой формулы.
Я писал программу с выводом всяких графов, матриц и таблиц. Построение дерева по формуле у меня было "запечатано", т.е. лишь для моей формулы. Но граф у меня рисовался по дереву, вроде как. Для любой формулы реализовать это можно, но нужно ли лишнюю работу делать? Это надо парсировать формулу определять приоритеты, и ставить порядки... лишний гемор (ИМХО).
Зачет я все еще не сдал... т.к. до сих пор не знаю какие лекции готовить, или Конспект лекций (Волорова Н.А.).doc или Конспект лекций (Мельникова Е.В.).doc
Короче, когда я пришел на зачет я не смог ответить на поставленный вопрос...
Кто нибудь помогите пожалуйста ! Написать программу, которая, используя стек, преобразует арифметическое выражение в обратную польскую запись (постфиксную). Арифметическое выражение должно содержать вложенные скобки и двойные степени. Оформить отчет. В отчете преобразовать выражение a+d*c*f-b/h в польскую запись.
petrvlad, по адресу http://trubetskoy1.narod.ru/ppn.html можно взять готовую программу. Вторая ссылка в гугле, между прочим. Или написать свою, воспользовавшись следующим примером: 1) приоритет операций (** - степень числа): 2) алгоритм работы: 3) пример работы:
Если у тебя действительно график строился на основе бинарного дерева со всеми обозначениями (номера вершин, ребра, знаки и т.д.) то респект тебе и уважуха
petrvlad, в первую очередь там дано описание алгоритма и лишь во-вторую - текст на С++. Если этого недостаточно - покупайте решение. Дальнейшее обсуждение в подобном тоне будут расценены за оффтопик. Все вышесказанное является моим личным мнением.
Дата: Понедельник, 23.02.2009, 01:09 | Сообщение # 10
Абитуриент
Группа: Проверенные
Сообщений: 15
Статус: Оффлайн
Quote (GoodMan)
Если у тебя действительно график строился на основе бинарного дерева со всеми обозначениями (номера вершин, ребра, знаки и т.д.) то респект тебе и уважуха smile
Структура данных была такая:
Code
struct Graf { int val; struct Graf *In1; struct Graf *In2; struct Graf *Out; char Op[4]; int x,y; int level; int Duga; int n; };
typedef Graf *GrafPtr;
struct FTable { char Op[6]; int t,e; };
Graf Grafs[22];
Но я использовал двойную структуру, т.е. обращался к нему как к массиву, и как к дереву, так наиболее удобно. А рисовал его обходом массива, в зависимости от уровня и ветвистой связи , в итоге получилось что-то типа этого: ХОЧУ ВЕРИТЬ...
Дата: Понедельник, 23.02.2009, 01:09 | Сообщение # 11
Абитуриент
Группа: Проверенные
Сообщений: 15
Статус: Оффлайн
Сдавать было сурово, вопрос и ответ, устная сдача, сразу все не ответил, лишь со второй попытки, преподаватель не принципиальная, не ставит не зачет сразу, как некоторые.... Короче решили меня оставить на втором курсе до лета, а там если все сдам за 3-й, то сразу на 4-й. Так что я еще официально второкурсник =)
Дата: Понедельник, 05.10.2009, 22:39 | Сообщение # 12
Группа: Удаленные
Всем привет! Сейчас выложу некоторые контрольные работы. Хочется быть полезной и получить доступ к скачке архива. Не могу понять, как делать задание по предмету АВС. Может, когда получу, доступ к скачке архива разберусь
Народ! Помогите теорией: обьясните или дайте ссылки. Построение графа по заданной формуле - получение польской записи, затем восстановление дерева по коду? Как будут выглядеть вектор назначения, вектор реализации, представление графа в виде функциональной схемы - обыкновенные таблицы .
Получение польской записи по формуле - весьма простой процесс, но у Мариной, о немного запутанно описан (я имею ввиду не в АВС, а далее в СИАОД тоже нужно будет делать польские записи). Лучшего всего в книге Демидовича Евгения Михалыча "Основы алгоритмизации и программирования. Язык Си" стр 292. Продается во втором корпусе. Можете погуглить, только не делайте, имхо, с использованием относительного стекового приоритета, это немного сложней. Восстановление дерева по коду - это вообщем создания бинарного дерева по польской записи. Не знаю где это описано, я понял сам как делать, потому как смотря на обратную польскую запись легко понять закономерность. Построения дерева. Под деревом я подразумеваю сущность в вашем коде (класс или массим объектов -узлов дерева). Когда получите дерево, построить граф не сложно - воспользуйтесь одним из методов обхода дерева для его визуализации. Вектор назначения - номера вершин графа, соответствующие номерам функ устройств (каким именно, зависит от задания, может быть с максимальным(минимальным) временем или максимальным(мин) коэффициентом). Вектор реализации- времена функ устройств, соответствующих номерам из вектора назначения. То есть(пример): в.н. - 14 ; 1 ; 4 ; 4 ; 11 ; 4 ; 11 ; 11 ; 11 ; 4 ; 9 ; 1 ; 4 ; 11 ; 11 ; 11 ; 4 ; 1 ; 11 ; 11 ; 11 ; (соответствие приводится в порядке возрастания номеров вершин графа - то есть для вершин 1,2,3,4 ... ) в. реал. - 25 ; 14 ; 53 ; 53 ; 13 ; 53 ; 13 ; 13 ; 13 ; 53 ; 9 ; 14 ; 53 ; 13 ; 13 ; 13 ; 53 ; 14 ; 13 ; 13 ; 13 ; Из примера, для устройства с номером 4 - время выполнения равняется 53, для устройства 11 - время выполнения 13. Время берется из условия (в условии для функ устройства задана его номер, операция, время и коэф - по крайней мере у меня так было, если ничего не поменялось). Граф в виде функ схемы - просто заменяете номера вершин графа на номера соответствующих функ устройств (то есть берем номера из вектора назначения). P.S. А вообще можете проконсультироваться у Мариной. Я помню когда брал задания, она мне все объяснила, и потом у меня никаких вопросов не возникало.
Добавлено (26.11.2009, 21:14) --------------------------------------------- P.S. Не заметил, что вверху Вася описал приинцип занесения в стек для польской записи. Можете не гуглить) Хотя все таки я делал по Демидовичу, там немного не такие приоритеты, но это не существенно
, в итоге получилось что-то типа этого: 
