Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 04.03.2017, 20:54   #1
dimon_snake
Форумчанин
 
Регистрация: 05.11.2015
Сообщений: 167
По умолчанию Задачка о числах

Здравствуйте
Мне нужна ваша помощь в следующем задании
Дана последовательность чисел a1, a2, ..., aN. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.
Код:
type 

s = record
sum,c:integer;
end;

var

n,k,l,j:integer;

a:array[1..100] of s;

ch,min,i,b:longint;

sum:int64;

begin

read(n);

for i:=1 to n do read(a[i].c);

sum:=0;

for i:=1 to n do 
      if (i=1) then 
                  a[i].sum:=a[i+1].c
               else 
                   if i=n then 
                          a[i].sum:=a[i-1].c
               else
                   a[i].sum:=a[i-1].c+a[i+1].c;         //Запись суммы соседей для каждого числа 
b:=n;

for i:=2 to n-1 do 
     begin

           min:=a[2].sum;
           ch:=2;                  //Считаем со второго, т.к.первое удалять не требуется
           for j:=3 to b-1 do
                if min>a[j].sum then 
                  begin
                        ch:=j;
                        min:=a[j].sum;
                 end;                        //Находим минимальную сумму соседей 
           sum:=sum+a[ch].c*a[ch].sum;     //Добавляем к общей сумме произведение числа на минимальную сумму 
           for j:=ch to b do
                       a[j].c:=a[j+1].c;     //Сдвигаем числа 
           dec(b);
           for j:=1 to b do  
                 if(j=1) then 
                               a[j].sum:=a[j+1].c
                         else 
                            if j=b then 
                                    a[j].sum:=a[j-1].c
                         else
                              a[j].sum:=a[j-1].c+a[j+1].c;     //Снова записываем сумму соседей

      end;

write(sum);
end.
Код не идеальный, программа криво работает
Что не так?
Заранее спасибо
dimon_snake вне форума Ответить с цитированием
Старый 04.03.2017, 21:41   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Он не кривой, не верный просто.
Например для чисел 1 2 1 0 он удалит первой 2 и в результате будет 5
А если первой удалить 1, то получим 4
Можно попробовать выбирать не просто минимальную сумму, а минимальное произведение суммы соседних на число. Идея с потолка, уверенности 0 ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 05.03.2017, 12:52   #3
dimon_snake
Форумчанин
 
Регистрация: 05.11.2015
Сообщений: 167
По умолчанию

Действительно
-----
Это изменило работу программы в лучшую сторону, но по-прежнему не то
dimon_snake вне форума Ответить с цитированием
Старый 05.03.2017, 13:06   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Да и я о том же. С чего решил, что таким способом найдешь оптимальное решение?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 08.03.2017, 16:01   #5
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Перебирать все варианты последовательности удаления 98 чисел не подъемная задача. Но можно упростить. Выбрав любое число на отрезке и считая его последним при удалении, оптимальным будет сумма решений левого и правого отрезков и штрафа за удаление этого последнего числа. Точки на отрезке брать в цикле, выбрать минимум. Для полученных отрезков рекурсивно то же самое и ой-ля-ля )) Ну еще оптимизировать, запомнив в массиве для каждого отрезка его минимальный штраф, что бы повторно не считать, когда он опять попадется в этих рекурсиях
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 08.03.2017, 19:16   #6
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

при наличии в последовательности 0 просто удалять ВСЕХ его соседей.
программа — запись алгоритма на языке понятном транслятору
evg_m на форуме Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Проблема с запятой в числах с плавающей точкой sarexer Visual C++ 2 17.09.2016 12:01
МАКРОС_ДОБАВЛЕНИЕ В ЧИСЛАХ НУЛЕЙ, ПОСЛЕ ЗАПЯТОЙ Окоча Юра Microsoft Office Word 4 04.02.2010 12:43
sinh в комплексных числах Brabus Помощь студентам 11 23.01.2010 23:36
Дата в числах Titan123 Общие вопросы Delphi 6 25.12.2008 13:22
Как убрать пробелы в числах!! vavany22 Microsoft Office Excel 27 11.11.2008 11:23