Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Поиск множителей через поиск решения - Страница 3 - Мир MS Excel

Старая форма входа
  • Страница 3 из 3
  • «
  • 1
  • 2
  • 3
Модератор форума: китин  
Мир MS Excel » Работа и общение » Работа / Фриланс » Поиск множителей через поиск решения (Формулы/Formulas)
Поиск множителей через поиск решения
MCH Дата: Четверг, 24.08.2017, 15:00 | Сообщение № 41
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

в итоге было бы интересно обсудить пути решений ;-)


Вар.1. Полный перебор всех сочетаний 8 чисел из 56 с применением методом ветвей и границ (отсечение неперспективных ветвей решения) - менее 10 секунд, для получения всех возможных вариантов решения.
Получение хотя-бы одного решения (первого) - менее 1 сек.

Вар.2
Берем логарифмы каждого числа (множителей и требуемого произведения), тогда задача нахождения произведения сводится к задаче "сумма подмножеств", когда нужно найти необходимую сумму, в качестве слагаемых используем логарифмы чисел.
Для решения можно применять различные алгоритмы, в. т. линейное программирования (симплекс-метод) через "Поиск решения"
В качестве недостатка метода - может быть достаточно большая погрешность связанная с логарифмами и последующее возведение в степень, а также "Поиск решения" работает с определенной точностью, поэтому при малых значениях множителей (как в примере), может получится достаточно большая погрешность. И не возможно перебрать все решения и выбрать наилучшее, будет найдено одно единственное решение из множества, не обязательно оптимальное.
Из плюсов - легко реализовать
 
Ответить
Сообщение
в итоге было бы интересно обсудить пути решений ;-)


Вар.1. Полный перебор всех сочетаний 8 чисел из 56 с применением методом ветвей и границ (отсечение неперспективных ветвей решения) - менее 10 секунд, для получения всех возможных вариантов решения.
Получение хотя-бы одного решения (первого) - менее 1 сек.

Вар.2
Берем логарифмы каждого числа (множителей и требуемого произведения), тогда задача нахождения произведения сводится к задаче "сумма подмножеств", когда нужно найти необходимую сумму, в качестве слагаемых используем логарифмы чисел.
Для решения можно применять различные алгоритмы, в. т. линейное программирования (симплекс-метод) через "Поиск решения"
В качестве недостатка метода - может быть достаточно большая погрешность связанная с логарифмами и последующее возведение в степень, а также "Поиск решения" работает с определенной точностью, поэтому при малых значениях множителей (как в примере), может получится достаточно большая погрешность. И не возможно перебрать все решения и выбрать наилучшее, будет найдено одно единственное решение из множества, не обязательно оптимальное.
Из плюсов - легко реализовать

Автор - MCH
Дата добавления - 24.08.2017 в 15:00
Pelena Дата: Четверг, 24.08.2017, 21:10 | Сообщение № 42
Группа: Админы
Ранг: Местный житель
Сообщений: 19160
Репутация: 4412 ±
Замечаний: ±

Excel 365 & Mac Excel
в итоге было бы интересно обсудить пути решений

Ключевое слово "в итоге". До принятия работы и оплаты делать это не следует


"Черт возьми, Холмс! Но как??!!"
Ю-money 41001765434816
 
Ответить
Сообщение
в итоге было бы интересно обсудить пути решений

Ключевое слово "в итоге". До принятия работы и оплаты делать это не следует

Автор - Pelena
Дата добавления - 24.08.2017 в 21:10
Perfect2You Дата: Понедельник, 28.08.2017, 13:35 | Сообщение № 43
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 237
Репутация: 59 ±
Замечаний: 0% ±

Excel 2010
Работа сдана, оплата получена.
Готов к диалогу с позволения старейшин.
 
Ответить
СообщениеРабота сдана, оплата получена.
Готов к диалогу с позволения старейшин.

Автор - Perfect2You
Дата добавления - 28.08.2017 в 13:35
Pelena Дата: Понедельник, 28.08.2017, 13:39 | Сообщение № 44
Группа: Админы
Ранг: Местный житель
Сообщений: 19160
Репутация: 4412 ±
Замечаний: ±

Excel 365 & Mac Excel
Открыла пост MCH


"Черт возьми, Холмс! Но как??!!"
Ю-money 41001765434816
 
Ответить
СообщениеОткрыла пост MCH

Автор - Pelena
Дата добавления - 28.08.2017 в 13:39
Perfect2You Дата: Понедельник, 28.08.2017, 14:08 | Сообщение № 45
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 237
Репутация: 59 ±
Замечаний: 0% ±

Excel 2010
В итоге реализовано в рамках первого подхода.
Не списывал. Решал сам. Давно чесались руки восстановить писанное еще на макросах EXCEL 4.0
Постарался рассмотреть наиболее общий случай. Но поскольку задача была поставлена таким образом, не стал убирать ограничение по количеству операндов, хотя и сделал его задаваемым.

Скорострельности МСН не достиг. Может, хуже написал (хотя перфекционизм включал по полной - чую, пригодится еще), а, может, машинка послабее, на которой отлаживал...

МСН! Вам уважение! Насколько знаю - Вы один из лидеров (а, может, и абсолютный лидер) в подобных задачах. Ваши реализации мне пару раз попадались, но не нашел времени вникнуть.
 
Ответить
СообщениеВ итоге реализовано в рамках первого подхода.
Не списывал. Решал сам. Давно чесались руки восстановить писанное еще на макросах EXCEL 4.0
Постарался рассмотреть наиболее общий случай. Но поскольку задача была поставлена таким образом, не стал убирать ограничение по количеству операндов, хотя и сделал его задаваемым.

Скорострельности МСН не достиг. Может, хуже написал (хотя перфекционизм включал по полной - чую, пригодится еще), а, может, машинка послабее, на которой отлаживал...

МСН! Вам уважение! Насколько знаю - Вы один из лидеров (а, может, и абсолютный лидер) в подобных задачах. Ваши реализации мне пару раз попадались, но не нашел времени вникнуть.

Автор - Perfect2You
Дата добавления - 28.08.2017 в 14:08
K-SerJC Дата: Понедельник, 28.08.2017, 17:00 | Сообщение № 46
Группа: Проверенные
Ранг: Обитатель
Сообщений: 487
Репутация: 86 ±
Замечаний: 0% ±

Excel 2013
мой вариант самый медленный был :-)
полным перебором возможных вариантов (2^56)
преобразование порядкового номера комбинации в двоичное число, определение бит в состоянии 1, если их 8 проверка произведения соответствующих значений.
ну к этому еще добавил выбор количества множителей, количества заданных чисел, диапазон приближения к заданному значению
за ночь моя машинка определила 150 совпадений (с приближением +- 0,01) при этом перебор еще шел в районе 40%...

с логарифмами я немного запустил изучение :-)


Благими намерениями выстелена дорога в АД.
 
Ответить
Сообщениемой вариант самый медленный был :-)
полным перебором возможных вариантов (2^56)
преобразование порядкового номера комбинации в двоичное число, определение бит в состоянии 1, если их 8 проверка произведения соответствующих значений.
ну к этому еще добавил выбор количества множителей, количества заданных чисел, диапазон приближения к заданному значению
за ночь моя машинка определила 150 совпадений (с приближением +- 0,01) при этом перебор еще шел в районе 40%...

с логарифмами я немного запустил изучение :-)

Автор - K-SerJC
Дата добавления - 28.08.2017 в 17:00
MCH Дата: Понедельник, 28.08.2017, 18:20 | Сообщение № 47
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Выложил свое решение здесь: http://www.excelworld.ru/forum/3-5196-1
 
Ответить
СообщениеВыложил свое решение здесь: http://www.excelworld.ru/forum/3-5196-1

Автор - MCH
Дата добавления - 28.08.2017 в 18:20
Мир MS Excel » Работа и общение » Работа / Фриланс » Поиск множителей через поиск решения (Формулы/Formulas)
  • Страница 3 из 3
  • «
  • 1
  • 2
  • 3
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!