|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
18.03.2009, 15:37 | #1 |
Форумчанин
Регистрация: 07.03.2009
Сообщений: 123
|
Прочитать со стандартного ввода арифметическое выражение. В нем могут содержаться операции +, -, *, /, exp, ln, sin, cos, числовые константы и переменная x. Выражение необходимо представить в виде дерева, листья которого – числа или переменные, а внутренние узлы – операции (при этом есть у операции только один аргумент, то один из сыновей может быть nil). Результатом должна быть структура указателей, описанная так ,как предыдущая. Но теперь это не обязательно должно быть дерево. Если с правой стороны равенства находятся подвыражения исходного выражения, то не стоит создавать в памяти новых узлов, а использовать уже существующие. В частности, это относится ко всему выражению exp(A). Почитанное выражение и результат необходимо держать в программе в виде (псевдо)дерева.
Подкиньте хоть какую0нибудь идею. Насколько я понимаю, сначала нужно написать процедуру со стринговым входным параметром (строка ввода), а выходным деревом. После этого написать процедуру прямого обхода дерева для формирования префиксной формы записи выражения. Еще вопрос: нет ни у кого модуля FParser? За основу можно взять это: Код:
Не говорите что мне делать, и я не скажу куда Вам идти.
Пишу программы на заказ на Delphi и Pascal Форум разработчиков Pascal и Delphi Последний раз редактировалось Stilet; 19.03.2009 в 09:11. |
18.03.2009, 18:18 | #2 | |
Форумчанин
Регистрация: 06.12.2008
Сообщений: 613
|
Цитата:
|
|
18.03.2009, 19:34 | #3 | |
Форумчанин
Регистрация: 07.03.2009
Сообщений: 123
|
Цитата:
1. Прочитать со стандартного ввода арифметическое выражение. В нем могут содержаться операции +, -, *, /, exp, ln, sin, cos, числовые константы и переменная x. Выражение необходимо представить в виде дерева, листья которого – числа или переменные, а внутренние узлы – операции (при этом есть у операции только один аргумент, то один из сыновей может быть nil). Более подробная информация о вводимых данных находится ниже. 2. Найти производную выражения: * D(число) = число_0 * D(переменная_x) = переменная_1 * D(A + B) = D(A) + D(B) * D(A - B) = D(A) - D(B) * D(A * B) = D(A) * B + A * D(B) * D(A / B) = (D(A) * B - A * D(B)) / (B * B) * D(exp A) = (exp A) * D(A) * D(ln A) = (число_1 / A) * D(A) * D(sin A) = (cos A) * D(A) * D(cos A) = (число_0 - sin A) * D(A) Важно, чтобы программа считала производную именно так, не стоит ничего упрощать или менять порядок подвыражений. Результатом должна быть структура указателей, описанная так ,как предыдущая. Но теперь это не обязательно должно быть дерево. Если с правой стороны равенства находятся подвыражения исходного выражения, то не стоит создавать в памяти новых узлов, а использовать уже существующие. В частности, это относится ко всему выражению exp(A) Программа должна считать производную в линейном времени – нужно только раз (конкретное число раз) проходить по определенному фрагменту дерева (чтобы это было возможно, фрагменты, которые выступают несколько раз, должны быть «подцеплены» в нескольких местах) 3. Освободить уже не используемые части памяти (то есть узлы оригинального дерева, которые уже не используются в структуре ответа). 4. Выписать ответ в формате таком же, как и формат входа (время пропорционально длине). Не стоит вставлять дополнительные пробелы или знаки конца строки (последняя строка должна заканчиваться знаком конца строки, так же как и предыдущие). 5. Освободить всю занятую память. ВАЖНО: прочитанное выражение и результат необходимо держать в программе в виде (псевдо)дерева. Это часть задания, и нельзя это сделать иначе. Спецификация входа/выхода Выражение записано префиксно. Это значит, что запись выражения ни что иное как (индукционно): * число, означающее постоянную, или * символ 'x' означающий переменную x, или * одна из надписей (без кавычек) '+', '-', '*', '/', 'exp', 'ln', 'sin', 'cos' означающая данную операцию, за которой следует запись первого аргумента, а дальше (только для первых четырех операция) запись второго аргумента. Каждая из этих надписей (число, 'x', операция) записана в отдельной строке. Нету никаких пробелов, а также дополнительных знаков конца строки. Вход будет содержать максимум 1000 строк, а все числа будут помещаться в Integer (могут быть отрицательными). Можно считать, что на входе – правильное выражение: не надо проверять на ошибки входные данные и выводить сообщения о неправильных данных. Производную выражения надо выписать на стандартный выход в таком же формате. Если программа не может посчитать производную какого-либо выражения, можно выписать на стандартный выход ошибок 'Производная не может быть посчитана' (без кавычек) Если же программа может найти производную выражения, то кроме самой производной она должна выписать на стандартный выход ошибок в следующем порядке и по одному в строке: число узлов в памяти перед нахождением производной, после (но перед удалением из памяти ненужных уже узлов) и после удаления этих узлов.
Не говорите что мне делать, и я не скажу куда Вам идти.
Пишу программы на заказ на Delphi и Pascal Форум разработчиков Pascal и Delphi Последний раз редактировалось Gonzo; 18.03.2009 в 19:37. |
|
18.03.2009, 21:02 | #4 |
Форумчанин
Регистрация: 07.03.2009
Сообщений: 123
|
C этим уже можно работать...
Код:
Уточню задание: Пусть дана строка, содержащая выражение в инфиксной форме, где могут содержаться: +, -, *, /, exp, ln, sin, cos. 1. Написать процедуру построения по этой строке дерева выражений. 2. Написать процедуру прямого обхода дерева выражений с составлением списка меток (значений узлов) дерева выражений.
Не говорите что мне делать, и я не скажу куда Вам идти.
Пишу программы на заказ на Delphi и Pascal Форум разработчиков Pascal и Delphi Последний раз редактировалось Stilet; 19.03.2009 в 09:11. |
19.03.2009, 02:03 | #5 |
Форумчанин
Регистрация: 07.03.2009
Сообщений: 123
|
Чем дальше, тем страшней.
Уточнили задачу!
Оказывается: 1.Вводится выражение в префиксной форме: одна строка - одна константа (все константы целочисленные), одна переменная, одна операция (+, -, *, /, exp, ln, sin, cos). 2.Строится дерево этого выражения. 3.Производится обход дерева и формируется линейный список, содержащий промежуточные результаты нахождения производной. * D(число) = число_0 * D(переменная_x) = переменная_1 * D(A + B) = D(A) + D(B) * D(A - B) = D(A) - D(B) * D(A * B) = D(A) * B + A * D(B) * D(A / B) = (D(A) * B - A * D(B)) / (B * B) * D(exp A) = (exp A) * D(A) * D(ln A) = (число_1 / A) * D(A) * D(sin A) = (cos A) * D(A) * D(cos A) = (число_0 - sin A) * D(A) Последний элемент - производная всего выражения. Если производная не найдена выводится сообщение. (Если с правой стороны равенства находятся подвыражения исходного выражения, то не стоит создавать в памяти новых узлов, а использовать уже существующие. В частности, это относится ко всему выражению exp(A).Важно: нужно только раз (конкретное число раз) проходить по определенному фрагменту дерева (чтобы это было возможно, фрагменты, которые выступают несколько раз, должны быть «подцеплены» в нескольких местах)). 4.Освобождаются неиспользуемые узлы дерева выражения. 5.Выводятся узлы дерева выражения, и их производная в зависимости от операции. Например: >2 0 >4 0 >2+4 0 и т.д. Так же должно быть выведенно число узлов в памяти перед нахождением производной, после (но перед удалением из памяти ненужных уже узлов) и после удаления этих узлов. 6.Освобождается вся память.
Не говорите что мне делать, и я не скажу куда Вам идти.
Пишу программы на заказ на Delphi и Pascal Форум разработчиков Pascal и Delphi |
19.03.2009, 13:49 | #6 |
Форумчанин
Регистрация: 07.03.2009
Сообщений: 123
|
Есть успехи
Но удается строить дерево только при вводе выражения в инфиксной форме, а надо в префиксной. Причем число может состоять больше чем из одной цифры, а так же должны быть exp, ln, sin, cos. По идее считывать надо из файла *.in, где каждая строка одна константа, один оператор (+, -, *, /, exp, ln, sin, cos) или переменная x, но думаю просто написать процедуру которая формировала бы строку из этого файла.
Возможно ли всё организовать таким образом? Код:
Не говорите что мне делать, и я не скажу куда Вам идти.
Пишу программы на заказ на Delphi и Pascal Форум разработчиков Pascal и Delphi |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Математические формулы в Delphi | Botanik1987 | Помощь студентам | 10 | 25.02.2017 19:09 |
битовые операции, Pascal | TOSAgrk | Помощь студентам | 2 | 02.02.2009 17:41 |
Математические формулы в PHP | kutt | PHP | 2 | 01.09.2008 23:33 |
Математические пакеты | yudjin | Общие вопросы Delphi | 0 | 03.05.2008 09:02 |
Строковые операции (Virtual Pascal) | Vitek220 | Помощь студентам | 1 | 02.05.2008 18:11 |