Форум программистов  
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

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

Здравствуйте
Мне нужна ваша помощь в следующем задании
Дана последовательность чисел 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, 22:41   #2
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 16,642
Репутация: 5851
По умолчанию

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

Действительно
-----
Это изменило работу программы в лучшую сторону, но по-прежнему не то
dimon_snake вне форума   Ответить с цитированием
Старый 05.03.2017, 14:06   #4
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 16,642
Репутация: 5851
По умолчанию

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

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

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



Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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




03:05.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.

купить трафик


как улучшить посещаемость, а также решения по монетизации сайтов, видео и приложений

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru