| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сложная задачка |
| Автор: Jane 11.3.2004, 08:28 |
| Всем доброго времени суток. У меня есть такая задачка, она достаточно сложная но вполне решаемая, помогите чем сможете. Вот задача: Есть 6 чисел, обозначим их как a, b, c, d, e, f , каждое из которых евляется целым и лежит в диапазоне от 10 до 120. Произведение первых трех разделить на произведение последних трех должно получится число с точностью до 7 знака. Найти все комбинации этих чисел. Я очень надеюсь, что вы мне сможете чем нибуть помочь |
| Автор: Crait 11.3.2004, 15:53 |
| BrutForce тебе поможет. Несколько часов работы компьютера - и готово. |
| Автор: Гость_Eugene 11.3.2004, 16:51 |
| Hello ALL ! Какие пару часов ? Прочитйте _внимательно_ условие :-| IMHO это Комбинаторика ! a b c d e f -> 10...120 Перебрать _только_эти_ комбинации. Результат их деления и точность до 7-го знака что-бы сбить с толку :-) Удачи ! |
| Автор: remax 11.3.2004, 19:06 | ||
Ага, комбинаторика.... каждое число имеет 110 вариантов, следовательно, при подходе решения задачи "в лоб" требуется проверить 110 в 6-й степени, т.е. больше чем 1000000000000 вариантов. Тут может и пары часиков не хватить. Простая прикидка. Предположим, что за 1 секунду можно успеть проверить 100 миллионов комбинаций. Тогда нам надо затратить примерно 10000 секунд что соответствует примерно 3 часам. Однако, следует понимать, что даже процессор класса Pentium III-IV не справится с таким темпом. Считается, что среднее быстродействие таких процессоров составляет 150-200 миллионов элементарных операций. А на проверку каждого условия потребуется не менее десятка отдельных операций (организация циклов, вычисление, сравнение и сохранение в случае необходимости). Кроме того, не надо забывать, что Ваша программа не монополист в использовании ресурсов компа. Поэтому, смело можно набросить еще порядок. Получаем, что необходимо затратить часов тридцать. |
| Автор: remax 11.3.2004, 19:46 |
| Понятно, что в этой задаче надо применить что то оригинальное - 1. усекать варианты 2. использовать метод Монте Карло (правда тогда сложно доказать наличие всех решений) 3. что нибудь еще, например использовать нечеткую логику или нейронные сети |
| Автор: Гость_Eugene 12.3.2004, 10:19 |
| Если действительно нужны _комбинации_ этих чисел, то тогды как у remax-a, а если _количество_, тода вот твоё решение :-) (120-10) ^ 3 * (120-10) ^ 3 Для вычисления этого выражения достаточно 0,00...01 сек :-) Удачи ! |
| Автор: ~FoX~ 12.3.2004, 12:44 |
| А можно и в уме посчитать http://www.arbuz.uz/u_treug.html |
| Автор: Alex101 18.3.2004, 19:59 |
| Пришла в голову идея. Заведем два трехмерных массива [110][110][110] (один для делимого, второй для делителя) Единственная проблема - память, под ДОС работать не будет, но вариант можно отмечать в бите, тогда количество памяти понадобится 110^3/8=1331000/8=166375 байт, запросто укладываемся. В этих массивах будем отмечать варианты. Поясняю какие: Если мы выбрали вариант делимого [i][j][k], то ему соответствуют варианты [i][k][j], [j][i][k], [j][k][i], [k][i][j], [k][j][i]. Ведь 10*11*12 это тоже самое, что 10*12*11 и т.д. Далее. Пусть мы получили выражение res=i*j*k/(x*y*z) Значение выражения i*j*(k+1)/(x*y*z) можно получить таким образом: res*(k+1)/k=res+res/k i*j*(k+2)/(x*y*z)=res+2*res/k Следовательно, i*j*(k+a)/(x*y*z)=res+a*res/k res1=i*j*k/(x*y*z), i*j*k/(x*y*(z+1))=res1*z/(z+1) Понятно, что с остальными множителями будет тоже самое. Главное, при увеличении на единицу какого-то из множителей проверять, не был ли рассмотрен уже этот вариант. Трехмерный массив для того, чтобы экономить время, формула преобразования это уже умножение. При реализации можно поступить так: находим 10*10*10/(10*10*10), далее находим 10*10*11/(10*10*10) ... находим 10*10*120/(10*10*10) находим 10*11*11/(10*10*10) и т.д. Причем вариантов не так уж и много. res1 вообще получаем как res1=1/res То-есть, найдя решение для очередной перестановки делимого, получаем тут же для такой же перестановки делителя. Предварительно можно получить единицы, и сразу обнулить элементы типа [i][i][i], тут еще масса вариантов оптимизации... |
| Автор: Guest 1.4.2004, 11:20 | ||
ответ не правильный, ты не учел одинаковые значения чисел при разных расстановок множителей (10*11*12 == 11*10*12), а так же одинаковые значения от делений разных чиел (10*10*10/10*10*10 == 100*10*10/100*10*10) |
| Автор: Abrek 1.4.2004, 14:49 |
| ИМХО, народ не совсем правильно понял условия задачи. Нужно подобрать такие числа, чтобы результат выражения (a*b*c)/(d*e*f) являлся бы числом с семью знаками после запятой(ровно с семью, например 56,5473867. Ни больше и не меньше). Комбинаторикой сдесь не отделаешься, но упростить задачку можно: (a*b*c)/(d*e*f)=(a/d)*(d/e)*(c/f). То есть достаточно перебрать комбинации одной пары чисел a/d, остальные две будут такими-же. Далее разбиваем этот массив на семь подмассивов - с 0 знаков после запятой, с 1, с 2,....и наконец с 7. Все элементы у которых более семи знаков после запятой отбрасываем. Главное при этом сохранить привязку к изначальмым комбинациям a/d. Ну а дальше все просто: 0+0+7=7; 1+0+6=7; 1+1+5=7; 2+0+5=7; . . . Надеюсь продолжать не стоит  |