Нужно решить простейший пример

lavlutik · Сообщение **lavlutik** » 19 дек 2013, 15:19

30,5
772,3
338,5
293,2
532,1
377,8
108,2
236,9
928,1

Вот цифры! Нужно сложить несколько из них, чтобы получилось 2401,2!!! Помогите найти эти цифры если они есть! Я уже устал подбирать.

kiv · Сообщение **kiv** » 19 дек 2013, 16:31

lavlutik писал(а):Source of the post
Вот цифры! Нужно сложить несколько из них, чтобы получилось 2401,2!!! Помогите найти эти цифры если они есть! Я уже устал подбирать.

Очень трудно Каю сложить слово "Счастье" из букв О, Ж, П и А...

Намек, надеюсь, ясен

Ближайшее - 2401,9: 30.5+293.2+377.8+928.1+772.3

balans · Сообщение **balans** » 19 дек 2013, 18:39

Здравия Вам желаю.

kiv писал(а):Source of the post
Ближайшее - 2401,9: 30.5+293.2+377.8+928.1+772.3

Я на Фортране попробовал

program A
Real S
integer a1,a2,a3,a4,a5,a6,a7,a8,a9
print *,'30.5+108.2+236.9+293.2+338.5+377.8+532.1+772.3+928.1'
S=0
do 9 a9=0, 1
do 8 a8=0, 1
do 7 a7=0, 1
do 6 a6=0, 1
do 5 a5=0, 1
do 4 a4=0, 1
do 3 a3=0, 1
do 2 a2=0, 1
do 1 a1=0, 1
S=30.5*a1 + 108.2*a2+ 236.9*a3+ 293.2*a4+338.5*a5+377.8*a6+
532.1*a7+772.3*a8+ 928.1*a9
if ( (S-2403)*(S-2400)<0) then print *,a1,a2,a3,a4,a5,a6,a7,a8,a9,S end if 1 continue 2 continue 3 continue 4 continue 5 continue 6 continue 7 continue 8 continue 9 continue end

И получил два ответа

1 0 0 1 0 1 0 1 1 --2401.8999
1 1 1 1 0 0 1 1 1 --2401.30005

Тот что выше Ваш ответ, а тот что ниже... Фортран начал гнать и путает цифру "4" с "9". На самом деле 2901,3.
Интересно, можно ли эту программу улучшить?

kiv · Сообщение **kiv** » 19 дек 2013, 18:57

balans писал(а):Source of the post
Интересно, можно ли эту программу улучшить?

Поскольку задача NP-полная, пока что лучший алгоритм - полный перебор...

geh · Сообщение **geh** » 19 дек 2013, 19:18

Вы написали классную программу. Я тоже попробовал
решить эту задачу на Visual Basic. Но это был поиск с помощью
случайных чисел. Вашу программу легко усовершенствовать.
Надо было изначально оперировать с целыми числами (что я и сделал)
и у вас не было бы никаких проблем с округлениями чисел.
Еще раз. Я потрясен вашей программой и сохраню ее в своей памяти.

lavlutik · Сообщение **lavlutik** » 19 дек 2013, 19:24

Спасибо за помощь!

zykov · Сообщение **zykov** » 20 дек 2013, 18:22

balans писал(а):Source of the post Интересно, можно ли эту программу улучшить?

Можно вместо девяти циклов сделать один от 0 до 511 и в качестве флагов использовать 9 битов этого счётчика.

kiv · Сообщение **kiv** » 20 дек 2013, 20:29

zykov писал(а):Source of the post
balans писал(а):Source of the post Интересно, можно ли эту программу улучшить?
Можно вместо девяти циклов сделать один от 0 до 511 и в качестве флагов использовать 9 битов этого счётчика.

Плохо - надо разбирать число на биты...

См. том 4а "Искусства программирования"

Пожалуй, наиболее эффективна генерация в виде кода Грея - тогда переход от одной суммы к другой выполняется с помощью всего лишь одной арифметической операции.

zykov · Сообщение **zykov** » 20 дек 2013, 20:43

kiv писал(а):Source of the post Плохо - надо разбирать число на биты...

Почему "плохо"?
Вообще "хорошо-плохо" - оно вещи относительные.
В данном случае код будет короче и прозрачнее.

kiv · Сообщение **kiv** » 20 дек 2013, 21:04

zykov писал(а):Source of the post
kiv писал(а):Source of the post Плохо - надо разбирать число на биты...
Почему "плохо"?
Вообще "хорошо-плохо" - оно вещи относительные.
В данном случае код будет короче и прозрачнее.

Так вам надо короткий код или быстрый код? Вообще-то эффективность - это скорость работы...

В данном случае можно еще воспользоваться тем, что должно быть не менее 4 и не более 7 чисел, тоже определенная оптимизация.

yourdomain.com