ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Maxim Litvinov                       2:5020/400     05 Dec 2001  00:41:14
 To : All
 Subject : Поиск наименьшего члена входящего в несколько рядов
 -------------------------------------------------------------------------------- 
 

 Писал в ru.math, там ответа не нашли.
 
 Даны группы рядов:
 [(ax+b_1), (ax+b_2), ..., (ax+b_n)], a,b_i,n - константы, n=(a+1)/2,
 x=0,1,2...
 [(cx+d_1), (cx+d_2), ..., (cx+d_m)], c,d_i,m - константы, m=(c+1)/2,
 x=0,1,2...
 [(ex+f_1), (ex+f_2), ..., (ex+f_p)], e,f_i,p - константы, p=(e+1)/2,
 x=0,1,2...
 И т.д...
 Таких групп - ограниченное кол-во, но много (штук 1000), но все коэффициенты
 (здесь a,c,e) - взаимно простые числа. b_i<>b_j, d_i<>d_j, f_i<>f_j для
 любого i<>j, т.е. дубликатов рядов в группах нет.
 Вопрос: можно ли найти _наименьшее_ число, входящее во все группы рядов
 (т.е. которое входит в каждой группе в один ряд) не перебирая все варианты
 ответа или все сочетания рядов (а это n*m*p*... вариантов)?
 Если нельзя наименьшее, тогда хоть ниже какой-нибудь границы B, которая
 много меньше произведения всех множителей (a*c*e*...)?
 
 Простейший пример:
 
 Даны 2 группы рядов:
 [(3x+1), (3x+2)], т.е. n=2 ряда;
 [(7x+3), (7x+4)], т.е. m=2 ряда;
 
 Задача: найти _наименьшее_ z, такое, что оно входит в _один_ ряд в _каждой_
 группе.
 В данном случае это будет 4, но нахожу я это простым перебором вариантов:
 0: нет,  нет
 1: 3x+1, нет
 2: 3x+2, нет
 3: нет,  7x+3
 4: 3x+1, 7x+4
 
 Можно перебирать с другого конца, т.е. перебирать коомбинации рядов и
 находить их пересечение по Китайской теореме об остатках:
 (3x+1)&(7x+3)=(21x+10)
 (3x+2)&(7x+3)=(21x+17)
 (3x+1)&(7x+4)=(21x+4) <- наименьшее, при x=0.
 (3x+2)&(7x+4)=(21x+11)
 Hо для этого понадобится ещё больше времени.
 
 А что делать, если групп - 1000 штук? И в каждой группе по 100 рядов?
 Перебор вариантов - (n*m*p*...) / (100^1000)
 Перебор комбинаций рядов - это 100^1000
 
 Максим
 
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор