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

Аватар пользователя
lavlutik
Сообщений: 160
Зарегистрирован: 04 июн 2008, 21:00

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

Сообщение 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!!! Помогите найти эти цифры если они есть! Я уже устал подбирать.
Последний раз редактировалось lavlutik 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
kiv
Сообщений: 1012
Зарегистрирован: 02 дек 2011, 21:00

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

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

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


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

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


Ближайшее - 2401,9: 30.5+293.2+377.8+928.1+772.3
Последний раз редактировалось kiv 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

balans
Сообщений: 2030
Зарегистрирован: 29 дек 2012, 21:00

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

Сообщение 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.
Интересно, можно ли эту программу улучшить?
Последний раз редактировалось balans 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
kiv
Сообщений: 1012
Зарегистрирован: 02 дек 2011, 21:00

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

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

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


Поскольку задача NP-полная, пока что лучший алгоритм - полный перебор...
Последний раз редактировалось kiv 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

geh
Сообщений: 224
Зарегистрирован: 09 дек 2013, 21:00

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

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

Вы написали классную программу. Я тоже попробовал
решить эту задачу на Visual Basic. Но это был поиск с помощью
случайных чисел. Вашу программу легко усовершенствовать.
Надо было изначально оперировать с целыми числами (что я и сделал)
и у вас не было бы никаких проблем с округлениями чисел.
Еще раз. Я потрясен вашей программой и сохраню ее в своей памяти.
Последний раз редактировалось geh 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
lavlutik
Сообщений: 160
Зарегистрирован: 04 июн 2008, 21:00

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

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

Спасибо за помощь!
Последний раз редактировалось lavlutik 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
zykov
Сообщений: 1777
Зарегистрирован: 02 ноя 2009, 21:00

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

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

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

Аватар пользователя
kiv
Сообщений: 1012
Зарегистрирован: 02 дек 2011, 21:00

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

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

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


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

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

Пожалуй, наиболее эффективна генерация в виде кода Грея - тогда переход от одной суммы к другой выполняется с помощью всего лишь одной арифметической операции.
Последний раз редактировалось kiv 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
zykov
Сообщений: 1777
Зарегистрирован: 02 ноя 2009, 21:00

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

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

kiv писал(а):Source of the post Плохо - надо разбирать число на биты...
Почему "плохо"?
Вообще "хорошо-плохо" - оно вещи относительные.
В данном случае код будет короче и прозрачнее.
Последний раз редактировалось zykov 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
kiv
Сообщений: 1012
Зарегистрирован: 02 дек 2011, 21:00

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

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

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


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

В данном случае можно еще воспользоваться тем, что должно быть не менее 4 и не более 7 чисел, тоже определенная оптимизация.
Последний раз редактировалось kiv 28 ноя 2019, 06:39, всего редактировалось 1 раз.
Причина: test


Вернуться в «Computer Science»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 4 гостей