Страница 1 из 3

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

Добавлено: 19 дек 2013, 15:19
lavlutik
30,5
772,3
338,5
293,2
532,1
377,8
108,2
236,9
928,1

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

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

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


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

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


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

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

Добавлено: 19 дек 2013, 18:39
balans
Здравия Вам желаю.
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.
Интересно, можно ли эту программу улучшить?

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

Добавлено: 19 дек 2013, 18:57
kiv
balans писал(а):Source of the post
Интересно, можно ли эту программу улучшить?


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

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

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

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

Добавлено: 19 дек 2013, 19:24
lavlutik
Спасибо за помощь!

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

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

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

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


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

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

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

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

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

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

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


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

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