Всем доброго времени суток.
У меня есть такая задачка, она достаточно сложная но вполне решаемая, помогите чем сможете.
Вот задача:
Есть 6 чисел, обозначим их как a, b, c, d, e, f , каждое из которых евляется целым и лежит в диапазоне от 10 до 120. Произведение первых трех разделить на произведение последних трех должно получится число с точностью до 7 знака. Найти все комбинации этих чисел.

Я очень надеюсь, что вы мне сможете чем нибуть помочь

BrutForce тебе поможет. Несколько часов работы компьютера - и готово.

Hello ALL !

Какие пару часов ?
Прочитйте _внимательно_ условие :-|
IMHO это Комбинаторика !
a b c d e f -> 10...120 Перебрать _только_эти_ комбинации.

Результат их деления и точность до 7-го знака что-бы сбить с толку :-)

Удачи !

Цитата

Hello ALL ! Какие пару часов ? Прочитйте _внимательно_ условие :-| IMHO это Комбинаторика ! a b c d e f -> 10...120 Перебрать _только_эти_ комбинации. Результат их деления и точность до 7-го знака что-бы сбить с толку :-)

Ага, комбинаторика....

каждое число имеет 110 вариантов, следовательно, при подходе решения задачи "в лоб" требуется проверить 110 в 6-й степени, т.е. больше чем 1000000000000 вариантов. Тут может и пары часиков не хватить.

Простая прикидка. Предположим, что за 1 секунду можно успеть проверить 100 миллионов комбинаций. Тогда нам надо затратить примерно 10000 секунд что соответствует примерно 3 часам. Однако, следует понимать, что даже процессор класса Pentium III-IV не справится с таким темпом. Считается, что среднее быстродействие таких процессоров составляет 150-200 миллионов элементарных операций. А на проверку каждого условия потребуется не менее десятка отдельных операций (организация циклов, вычисление, сравнение и сохранение в случае необходимости). Кроме того, не надо забывать, что Ваша программа не монополист в использовании ресурсов компа. Поэтому, смело можно набросить еще порядок. Получаем, что необходимо затратить часов тридцать.

Понятно, что в этой задаче надо применить что то оригинальное -
1. усекать варианты
2. использовать метод Монте Карло (правда тогда сложно доказать наличие всех решений)
3. что нибудь еще, например использовать нечеткую логику или нейронные сети

Если действительно нужны _комбинации_ этих чисел, то тогды
как у remax-a, а если _количество_, тода вот твоё решение :-)

(120-10) ^ 3 * (120-10) ^ 3

Для вычисления этого выражения достаточно 0,00...01 сек :-)

Удачи !

А можно и в уме посчитать

Почитай мож чего выкапаешь для себя )))

Пришла в голову идея.
Заведем два трехмерных массива [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],
тут еще масса вариантов оптимизации...

Это сообщение отредактировал(а) Alex101 - 18.3.2004, 20:29

Цитата

Если действительно нужны _комбинации_ этих чисел, то тогды как у remax-a, а если _количество_, тода вот твоё решение :-) (120-10) ^ 3 * (120-10) ^ 3 Для вычисления этого выражения достаточно 0,00...01 сек :-) Удачи !

ответ не правильный, ты не учел одинаковые значения чисел при разных расстановок множителей (10*11*12 == 11*10*12), а так же одинаковые значения от делений разных чиел
(10*10*10/10*10*10 == 100*10*10/100*10*10)

ИМХО, народ не совсем правильно понял условия задачи. Нужно подобрать такие числа, чтобы результат выражения (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;
.
.
.
Надеюсь продолжать не стоит