Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C] Задача "Скрудж Мак-Дак"

Автор: deadlegolas 12.3.2009, 20:27

Дали задачку на контрольную на дом, а я даже просто не понимаю что надо сделать... Если кто-то может помочь - буду благодарен... Цитата Скрудж Мак-дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта зависимость довольно сложна. Его механик сделал устройство, вычисляющее эту функцию в несколько этапов с использованием промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется , чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления. Вычисление функции без параметров может производиться в любое время. После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функции такова, что каждая функция вычисляется не более одного раза и любой параметр (имя функции) используется не более одного раза. Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функциий. Структура входных данных (файл INPUT.TXT) - 1я строка: содержит число N - общее количество функций; - 2я строка: содержит имя функции,которую необходимо вычислить; - 3я строка: имя функции кол-во параметров [список имен параметров]; - .... - (N+2)я строка: имя функции кол-во параметров [список имен параметров]; Структура выходных данных (файл OUTPUT.TXT) - размер памяти (в ячейках); - имя 1-й вычисляемой функции; - имя 2-й вычисляемой функции; - .... - имя функции которую необходимо вычислить; ПРИМЕЧАНИЕ- Имя функции - натуральное число от 1 до N. Например: INPUT.TXT 5 1 1 2 2 3 2 0 3 2 4 5 4 0 5 0 OUTPUT.TXT 4 5 3 2 1 Короче говоря, в данной задаче требуется сделать следующее. 1. Найти S - максимальную степень среди тех вершин, что подлежат обходу (поиск в глубину DFS1). 2. Необходимая память вычисляется по формуле MaxS = S + k - 1, где S - найдено в предыдущем шаге(DFS1), k - максимальное количество вершин одного уровня вложенности с такой же степенью S. для вычисления k совершается обход повторным поиском в глубину DFS2. 3.Третьим поиском в глубину DFS3 находим и помещаем в очередь V все вершины, степень которых равна 8. 4. Последним, четвертым поиском в глубину обходим данное дерево в порядке вершин в очереди V, тоесть в первую очередь вычисляем те функции, для которых требуется максимальная память.

Автор: zim22 13.3.2009, 09:59

необходимо реализовать одну из разновидность жадного алгоритма http://ru.wikipedia.org/wiki/Жадный_алгоритм

Автор: deadlegolas 13.3.2009, 13:36

спасибо за алгоритм. прочитал,но не понимаю как это реализовать на С ((

Автор: zim22 13.3.2009, 16:21

Цитата(deadlegolas @  13.3.2009,  13:36 ) прочитал,но не понимаю как это реализовать на С (( реализуйте тогда на другом ЯП. преподаватель вас простит, я уверен. главное - это ваши старания и понимание самого алгоритма. а реализован он на С или на Delphi - дело уже десятое.

Автор: deadlegolas 13.3.2009, 18:49

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

Автор: zim22 13.3.2009, 19:21

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

Автор: deadlegolas 13.3.2009, 19:59

Фак))   ps: если кто-то может нормально намекнуть на решение задачи - буду очень благодарен..

Автор: Soah 13.3.2009, 20:25

Цитата(deadlegolas @  13.3.2009,  18:49 )  что использовать для работы с этим алгоритмом Графы http://fpmi-bsu.narod.ru/stream1/algorithm/tasks/ta_graf.html http://olimpus-belorus.ru/t95_4.htm

Автор: deadlegolas 13.3.2009, 20:32

Цитата(Soah @  13.3.2009,  20:25 ) Графы оу.жесть.почитаю,спасибо. тему оставляю нерешенной, возможно решу её. хотя врятли, эти графы..

Автор: Rififi 13.3.2009, 21:21

... прочитал,но не понимаю как это реализовать на С (( ...  ... дайте хотя бы намек что использовать для работы с этим алгоритмом? ... ... ps: если кто-то может нормально намекнуть на решение задачи - буду очень благодарен..  ... тебе не обойтись без помощников - Авраама, Александра и Эндрю, а в особо тяжелых случаях остается только призвать на помощь Уиллиса или даже Бенджамина. :eek:

Автор: deadlegolas 14.3.2009, 17:08

Цитата тебе не обойтись без помощников - Авраама, Александра и Эндрю, а в особо тяжелых случаях остается только призвать на помощь Уиллиса или даже Бенджамина. :eek: угу.круто. если нечего сказать - зачем вообще что-то говорить?

Автор: zim22 14.3.2009, 17:11

deadlegolas, не груби. репутация в минус может уйти очень быстро.

Автор: deadlegolas 18.3.2009, 21:04

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

Автор: zim22 19.3.2009, 09:32

deadlegolas, алгоритмы работы с графами реализован в библиотеке Boost. в том числе и алгоритм поиска в глубину. Почитайте книжку С++ Boost Graph Library. Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн там есть и теория по графам и практика.

Автор: deadlegolas 19.3.2009, 15:34

спасибо,качаю уже. буду разбираться. Добавлено через 6 минут и 3 секунды а библиотека boost на просто Си есть?

Автор: zim22 19.3.2009, 15:42

deadlegolas, нет. только на С++. более подробно про библиотеку здесь: http://en.wikipedia.org/wiki/Boost_C%2B%2B_Libraries

Автор: deadlegolas 19.3.2009, 22:35

почитал.. к сожалению, встретил много чего непонятного...  хотелось бы на Си все-таки аналог этой библиотеки.

Автор: zim22 19.3.2009, 22:43

Цитата(deadlegolas @  19.3.2009,  22:35 ) хотелось бы на Си все-таки аналог этой библиотеки. хотеть не вредно. даже полезно. Посмотрите в этой книге. Может и найдёте поиск в глубину на С. Фундаментальные алгоритмы на C. Части 1 - 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах. Автор: Роберт Седжвик

Автор: deadlegolas 31.3.2009, 18:50

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

Автор: Rififi 31.3.2009, 21:54

deadlegolas,  А на завтра-послезавтра задачку надо сдать.. Обратись к zim22,  Он в C++ разделе признался что готов безвозмездно впрягаться за других (:

Автор: zim22 1.4.2009, 06:56

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

Автор: deadlegolas 1.4.2009, 15:26

А кто-то еще может помочь?

Автор: Rififi 1.4.2009, 19:11

deadlegolas,  А кто-то еще может помочь?  А что так, или сомневаешься в его скиллах, хочешь найти кого-нибудь "покруче"? :gigi: Напрасно ты гасишь свой, возможно последний, шанс. :horror:

Автор: zim22 1.4.2009, 20:09

Rififi, он ко мне в приват обратился, но его не устроили условия сотрудничества со мной

Автор: deadlegolas 1.4.2009, 22:13

немножко дорого,вот в чем проблема)

Автор: zim22 2.4.2009, 08:01

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

Автор: deadlegolas 2.4.2009, 23:10

Впринципе программа в теории работает, но результат обхода немного отличается от нужного в задании... Код #include <conio.h> #include <stdio.h> int n,k,i,S=0,was[10],mat[10][10]; int st(int c) {     int res=0;     for (int i = 1; i <= n; i++) res+=mat[c][i];     return res; } void DFSprint(int c) {     was[c]=1;     for (int i=1; i <=n; i++)         if (mat[c][i]>0&&was[i]==0) DFSprint(i);     printf("%d\n",c); } void DFS1(int c) {     was[c]=1;     if (S<st(c))     S=st(c);     for (int i=1; i <=n; i++)         if (mat[c][i]==1&&was[i]==0) DFS1(i); } void DFS2(int c) {     was[c]=1;     if (S==st(c)) k++;     for (int i=1; i <=n; i++)         if (mat[c][i]==1&&was[i]==0) DFS2(i); } int main() { clrscr(); n=5;i=1; mat[1][2]=2; mat[1][3]=1; mat[3][2]=1; mat[3][4]=1; mat[3][5]=1; for (int j=0; j < 10; j++) was[j]=0; DFS1(i); for ( j=0; j < 10; j++) was[j]=0; DFS2(i); printf("%d\n",S+k-1); for ( j=0; j < 10; j++) was[j]=0; DFSprint(i); getch(); }

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)