Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C] Задача "Скрудж Мак-Дак", Задача "Скрудж Мак-Дак" 
:(
    Опции темы
deadlegolas
Дата 12.3.2009, 20:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

Репутация: нет
Всего: нет
Дали задачку на контрольную на дом, а я даже просто не понимаю что надо сделать...
Если кто-то может помочь - буду благодарен...

Цитата

Скрудж Мак-дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта зависимость довольно сложна. Его механик сделал устройство, вычисляющее эту функцию в несколько этапов с использованием промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется , чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления.
Вычисление функции без параметров может производиться в любое время. После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функции такова, что каждая функция вычисляется не более одного раза и любой параметр (имя функции) используется не более одного раза.
Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функциий.

Структура входных данных (файл 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, тоесть в первую очередь вычисляем те функции, для которых требуется максимальная память.
PM MAIL   Вверх
zim22
Дата 13.3.2009, 09:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

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


--------------------
C++ FAQ Lite
PM MAIL   Вверх
deadlegolas
Дата 13.3.2009, 13:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

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

Это сообщение отредактировал(а) deadlegolas - 13.3.2009, 14:44
PM MAIL   Вверх
zim22
Дата 13.3.2009, 16:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(deadlegolas @  13.3.2009,  13:36 Найти цитируемый пост)
прочитал,но не понимаю как это реализовать на С ((

реализуйте тогда на другом ЯП. преподаватель вас простит, я уверен. главное - это ваши старания и понимание самого алгоритма. а реализован он на С или на Delphi - дело уже десятое. 

Это сообщение отредактировал(а) zim22 - 13.3.2009, 16:24


--------------------
C++ FAQ Lite
PM MAIL   Вверх
deadlegolas
Дата 13.3.2009, 18:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

Репутация: нет
Всего: нет
я имею ввиду, что не знаю как это реализовать на языке программирования...
дайте хотя бы намек что использовать для работы с этим алгоритмом? спасибо.
PM MAIL   Вверх
zim22
Дата 13.3.2009, 19:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

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


--------------------
C++ FAQ Lite
PM MAIL   Вверх
deadlegolas
Дата 13.3.2009, 19:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

Репутация: нет
Всего: нет
Фак)) smile 


ps: если кто-то может нормально намекнуть на решение задачи - буду очень благодарен..
PM MAIL   Вверх
Soah
Дата 13.3.2009, 20:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 512
Регистрация: 18.2.2009

Репутация: 9
Всего: 54
Цитата(deadlegolas @  13.3.2009,  18:49 Найти цитируемый пост)
 что использовать для работы с этим алгоритмом

Графы

24 задача
СКРУДЖ МАК-ДАК
PM MAIL   Вверх
deadlegolas
Дата 13.3.2009, 20:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

Репутация: нет
Всего: нет
Цитата(Soah @  13.3.2009,  20:25 Найти цитируемый пост)
Графы

оу.жесть.почитаю,спасибо.
тему оставляю нерешенной, возможно решу её.
хотя врятли, эти графы..  smile 
PM MAIL   Вверх
Rififi
Дата 13.3.2009, 21:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1254
Регистрация: 9.3.2008

Репутация: 4
Всего: 36
... прочитал,но не понимаю как это реализовать на С (( ... 
... дайте хотя бы намек что использовать для работы с этим алгоритмом? ...
... ps: если кто-то может нормально намекнуть на решение задачи - буду очень благодарен..  ...
тебе не обойтись без помощников - Авраама, Александра и Эндрю, а в особо тяжелых случаях остается только призвать на помощь Уиллиса или даже Бенджамина. :eek:
PM MAIL   Вверх
deadlegolas
Дата 14.3.2009, 17:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

Репутация: нет
Всего: нет
Цитата

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

угу.круто.
если нечего сказать - зачем вообще что-то говорить?

Это сообщение отредактировал(а) deadlegolas - 14.3.2009, 17:09
PM MAIL   Вверх
zim22
Дата 14.3.2009, 17:11 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

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


--------------------
C++ FAQ Lite
PM MAIL   Вверх
deadlegolas
Дата 18.3.2009, 21:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

Репутация: нет
Всего: нет
Помогите хотя бы с реализацией поиска в глубину в этом графе,пожалуйста.. я не могу въехать в это(((((
PM MAIL   Вверх
zim22
Дата 19.3.2009, 09:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

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


--------------------
C++ FAQ Lite
PM MAIL   Вверх
deadlegolas
Дата 19.3.2009, 15:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 95
Регистрация: 19.4.2008

Репутация: нет
Всего: нет
спасибо,качаю уже. буду разбираться.

Добавлено через 6 минут и 3 секунды
а библиотека boost на просто Си есть? 
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1470 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.