AlgoList

[Jane]

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

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

Михаил Густокашин: не совсем понятно, а вернее совсем непонятно условие задачи. Какие именно комбинации необходимо найти?

[az]

Если я правильно понял, то необходимо найти все шестерки чисел a,b,c,d,e,f из промежутка 10..120, такие, что
(a*b*c)/(d*e*f)=k с точностью до 7 знаков

Я бы, наверное, решал так: Будем рассматривать приближения
m/n к числу k, где 10^3<m,n<120^3
Тогда заметим, что если m/n - наилучшее приближение снизу для данного знаменателя m, то (m-1)/n отличается от k хотя бы на 1/120^3>1/10^7. Аналогично (m+2)/n. Тогда возможно подходят для данного знаменателя n только m/n и (m+1)/n. Их и проверим: сначала на отличие от k, а потом специальной функцией посчитаем
количество различных троек a,b,c с условием a*b*c=m
количество различных троек d,e,f с условием d*e*f=n
Перемножим их. Прибавим к текущей сумме и перейдем к знаменателю на 1 больше. Вот общая идея (моя).

[Jane]

Всем доброго времени суток.
Да az ты правельно понял(а) условие этой задачки, необходимо найки все возможные комбинации чисел.
az а можно немного поподробнее про твой вариант решения, он меня заинтересовал.

[az]

Конечно!
"понял"

Представь себе, что тебе дан числитель и знаменатель
a*b*c и d*e*f.
Тогда задачка в том, чтобы найти все возможные такие a,b,c, что они в промежутке от 10 до 120 и что a*b*c=m. Аналогично (той же функцией) получим все возможные d,e,f. Потом возьмем для каждого набора a,b,c каждый набор d,e,f и получим все наборы. Опять таки повторюсь - в том случае, если числитель и знаменатель зафиксированы, мы свели задачу к перебору всех различных троек чисел a,b,c с заданным произведением и в заданном промежутке.
А вот как мы будем находить числитель и знаменатель
Сначала заметим, что их имеет смысл рассматривать только в промежутке от 10^3 до 120^3. Теперь я доказал в прошлом сообщении, что для каждого знаменателя под ограничение погрешности подходит не более двух числителей, более того - последовательных - таких, что m/n<k, а (m+1)/n>k
Поэтому присвоим значение числителю (Ч) и знаменателю (З) 1000. Теперь будем увеличивать З, пока (Ч-1)/З>k. (Если это выполняется, то Ч/З не равно k с необходимой точностью)

Теперь пока (Ч-1)/З<=k и Ч/З>k, будем вызывать процедуру проверки для Ч/З - если есть нужная точность, то процедуру вывода всех a,b,c,d,e,f
Увеличваем З.

Теперь если мы не закончили, то случилось, что
Ч/З<k

Теперь в цикле пока знаменатель<120^3 и числитель<120^3 делаем
Проверить Ч/З.
Проверить (Ч+1)/З
Увеличить З
Пока (Ч+1<З) увеличивать Ч

Теперь самое интересное. Мы свели задачу к разложению на 3 множителя:
Итак нам осталось решить задачу. Дано число 1000<=N<=120^3. Необходимо найти все тройки чисел a,b,c, что a*b*c=N
Здесь идеи разные:
можно разложить N на множители так, что N=p1^m1*p2^m2*...
И заметить, что упорядоченность троек a<b<c позволяет получить неповторяемость (a,b,c) и скажем (a,c,b). При этом будем говорить, что a может содержать каждый простой делитель в любой степени, поэтому придется проверить все:
количество делителей числа N равно (m1+1)*(m2+1)*...
Так как степень вхождения первого простого числа в N может быть от 0 до m1. Теперь просто перебираем пусть в a число p1 входит t1 раз, тогда вызываем рекурсию на p2, если a<N/a и для каждых найденных t нам остается только поделить N на a и полученное N/a разложить на 2 множителя...
А есть более простой способ:
опять таки считаем, что a<b<c, тогда переберем все числа от 10 до корня из N (можно кубического, можно квадратного) и проверим или 120 (в зависимости от того, что меньше), являются ли они делителями N. Если является, то возьмем a, равное этому делителю и рассмотрим задачу для N/a b и c. Но b уже можно перебирать от a до квадратного корня из N/a или 120.

Что-то я по-моему все очень запутанно объяснил... Хотя я на то и математик, чтобы так объяснять. Но если есть вопросы - задавай!

[Jane]

Взможно это так и надо делать но все же мне не очень ясен сам метод вычисления числителя и знаменателя. Я бы очень была тебе благодарна если ты смог бы написать примерный алгоритм программ ы а не просто обьяснения , так было бы понятнее.

[az]

Нет проблем.
Примерный алгоритм:

[Jane]

Да если тебе не трудно. А можно енто написать на С или С++. Былобы совсем замечательно. Ты меня и так очень выручил большое тебе человеческое спасибо.
Просмотрев программу я поняла, что проверка идет с числом K но это число не задано по условию о нем извесно только то что после точки оно имеет 7 знаков и оно получается в результате деления числителя и знаменателя при их разных комбинациях получаются новые числа. А здесь как я понимаю подразумевается конкретное число. А как задается число epsilon?
Я не очень хорошо знаю Pascal точнее совсем его не знаю и возможно я что то поняла не правильно.