Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на языке Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 2.943 RSS
←   Январь 2012   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/pascal
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

2.943 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на языке Pascal


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Орловский Дмитрий
Статус: Советник
Рейтинг: 6992
∙ повысить рейтинг » 		lamed
Статус: Академик
Рейтинг: 5750
∙ повысить рейтинг » 		Роман Селиверстов
Статус: Советник
Рейтинг: 4297
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Pascal (Паскаль)

Номер выпуска:1226
Дата выхода:22.01.2012, 16:00
Администратор рассылки:Boriss (Академик)
Подписчиков / экспертов:134 / 139
Вопросов / ответов:1 / 1

Консультация # 185217: Уважаемые эксперты! Прошу помощи со следующей задачей: 1. Решить задачу, приведенную ниже, методом поиска с возвратом, используя рекурсивный или нерекурсивный вариант (задача на Turbo Pascal) 2. Решить эту же задачу с помощью жадного алгоритма (можно вручную). 3. Обосновать возможность решения данной задачи методом динамического программир...

Консультация # 185217:

Уважаемые эксперты! Прошу помощи со следующей задачей:
1. Решить задачу, приведенную ниже, методом поиска с возвратом, используя рекурсивный или нерекурсивный вариант (задача на Turbo Pascal)
2. Решить эту же задачу с помощью жадного алгоритма (можно вручную).
3. Обосновать возможность решения данной задачи методом динамического программирования.

Условие задачи:


Так же прикрепляю пример решения другой задачи методом динамического программирования:
Primer_reshenia_1.doc (34.5 кб)

Спасибо.

Дата отправки: 19.01.2012, 15:44
Вопрос задал: Sanek (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Сергей Бендер (Бакалавр):

Здравствуйте, Sanek!

Вот решение первой задачи рекурсивным поиском с возвратом. Пытался как-то оптимизировать процесс -- но, кажется, здесь нет возможностей для отсечения каких-то ветвей рекурсии. Т.е. получился по сути полный перебор всех допустымых вариантов распределения средств.

Насчёт жадного алгоритма я удивлен. В данной задаче я не вижу возможности для его осмысленного применения.

Код :
const dohod_tabl:array[1..5,0..7] of real=
      ((0, 0.86, 0.95, 1.66, 2.52, 2.81, 3.45, 4.28),
       (0, 0.87, 1.78, 2.22, 2.57, 3.0,  3.0,  3.77),
       (0, 0.09, 0.77, 0.92, 0.97, 0.99, 1.64, 2.55),
       (0, 0.43, 0.67, 1.32, 1.34, 1.48, 2.03, 2.49),
       (0, 0.3,  0.64, 1.25, 2.23, 2.38, 3.09, 3.87));

var vlozh,vlozh_max:array[1..5] of integer;
    dohod,dohod_max:array[1..5] of real;
    i,j:integer;

procedure GetDohodMax(i:integer;sum:integer);
var n:integer;
begin
     if sum>=0 then {Проверка наличия денег (по сути перестраховка 
                                   -- это обеспечивается алгоритмом)}
     if (i<5) then  {Терминальное условие: не дошли до последнего предприятия}
     begin
          for n:=sum downto 0 do  {Перебираются возможные вложения в передалх оставшейся суммы}
          begin
               vlozh[i]:=n;  {Задаётся вложение в i-е предприятие}
               dohod[i]:=dohod[i-1]+dohod_tabl[i,n]; {вычисляется доходность от сделанного вложения}
               GetDohodMax(i+1,sum-n); {Рекурсивный вызов для следуюущего предприятия
                                        с оставшейся суммой}
          end
     end
     else begin
          vlozh[5]:=sum;  {В последнее предприятие вкладывается вся оставшаяся сумма}
          dohod[5]:=dohod[4]+dohod_tabl[5,sum];
          if dohod[5]>dohod_max[5]  {Сравнение максимумом из предыдущих раскладов}
          then begin
               dohod_max:=dohod;
               vlozh_max:=vlozh;
          end;
     end
end;

begin
     {Начальное состояние}
     for i:=1 to 5 do
     begin
          vlozh[i]:=0;
          vlozh_max[i]:=0;
          dohod[i]:=0;
          dohod_max[i]:=0
     end;

     {Решение задачи}
     GetDohodMax(1,7);

     {Вывод на экран}
     write('Predpriyatie       ');
     for i:=1 to 5 do
         write(i:5);
     writeln;
     write('Vlozhenie          ');
     for i:=1 to 5 do
         write(vlozh_max[i]:5);
     writeln;
     write('Dohod (narast.itog)');
     for i:=1 to 5 do
         write(dohod_max[i]:5:2);
     writeln;
     readln;
end.

Консультировал: Сергей Бендер (Бакалавр)
Дата отправки: 20.01.2012, 18:04

5
Спасибо за помощь)))
-----
Дата оценки: 20.01.2012, 18:47
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.35 от 21.01.2012
В избранное