VPF::задача о багдатском воре - Форум программистов

Reptor

Дата 15.1.2007, 17:06 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

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

кто нибудь слышал о такой задачи и может знает как её решать. Мне задали а условия и больше нечё нет и немогу найти.

drkot

Дата 15.1.2007, 18:14 (ссылка)

(нет голосов)

Загрузка ...

Ищущий

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

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

Цитата

Багдадский вор В высотном здании (150) этажей багдадского банка возник пожар. Огонь распространяется по зданию со скоростью 1 этаж в минуту. В здании имеется лифт, который движется со скоростью 10 этажей в минуту и застревает, если проходит через этаж, охва- ченный огнем. В момент начала пожара лифт стоит на первом этаже и там же находится знаменитый багдатский вор, задача которого вынести из банка как можно больше хранящихся там золотых монет, воспользовавшись паникой и тем, что служащие спешно покидают здание по наружным пожарным лестницам. Вор знает номера этажей, на которых хранятся монеты, и точные их количества на каждом таком этаже. Для поиска монет на этаже и переноса их в лифт требуется полторы минуты. Написать программу, которая определяет максимально возмож- ное количество монет, которое может унести вор. Программа ввод- ит номер этажа, где начался пожер, и затем последовательность из 149 чисел - количества монет со 2 по 150 этажи (на первом этаже монет нет)

Добавлено @ 18:15
а вобще гугл тебе в руки

Добавлено @ 18:17
решение

Код


Program Багдад2 ;
Var 
___ Fk : Array [ 1..150 ] Of Integer ;
___ A : Array [ 2..150 ] Of Integer ;
___ N : Integer ;
___ Fire, Lift, Find : Real ;
___ k,i,t : Integer ; 
___ Res : Integer ; 
Function Max ( a,b : Integer ) : Integer ;
Begin
___ If a > b Then Max := a 
___ Else Max := b
End ; 
Function CanStand ( k,i,t : Integer ) : Boolean ;
Begin
___ CanStand := (N-i)*Fire > k*Lift + (k-i)*Lift + t*Find 
End ;
Begin
___ Write ( 'Введите номер этажа, где начался пожар : ' ) ; 
___ Read ( N ) ; 
___ Write ( 'Введите время передвижения лифта на 1 этаж ' ) ;
___ Read ( Lift ) ;
___ Write ( 'Введите время распространения огня на 1 этаж ' ) ;
___ Read ( Fire ) ; 
___ Write ( 'Введите время поиска денег на этаже ' ) ; 
___ Read ( Find ) ;
___ For k := 2 To N-1 Do
___ Begin
______ Write ( 'Введите количество монет на зтаже ',k,' => ') ; 
______ Read ( A [k] ) ;
___ End ;
___ Res := 0 ;
___ k := 2 ; { k - начальный этаж для спуска вниз }
___ While CanStand ( k,k,0 ) Do
___ Begin
______ For t := 0 To k-1 Do Fk [t] := 0 ; 
_________ For i := 2 To k Do 
____________ For t := 0 To k-i-1 Do
_______________ If CanStand ( k,i,t+1) Then 
__________________ Fk [t] := Max ( Fk [t], A [i]+Fk [t+1] )
_______________ Else If CanStand ( k,i,t ) Then 
_______________ Else Fk [t] := -Infinity ;
______ Res := Max ( Res, Fk [0] ) ;
______ k := k + 1 
___ End ;
___ Writeln ( 'Вор сможет унести ', Res, ' монет ' )
End.

Это сообщение отредактировал(а) drkot - 15.1.2007, 18:21

--------------------

Ошибка не становится истиной по причине широкого распространения,
как и Истина не становится Ошибкой из-за того, что никто её не видит.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »