2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нужен алгоритм решения
Сообщение27.03.2009, 15:15 
Аватара пользователя
Здравствуйте, для подготовки к олимпиаде по программированию дали типовые задачи, не могу разобраться в методе решения одной из них.

Дано разложение числа с на простые множители.
$c={\alpha_1}^b \alpha_2 ... \alpha_n$

Если первый множитель в разложении равен 2, то b=3, в противном случае b=1.

Требуется найти такое разбиение множества множителей числа с на два непустых непересекающихся подмножества, чтобы произведение всех членов первого подмножества отличалось на минимальную величину от произведения всех членов второго подмножества.

Просьба перебор не предлагать.

 
 
 
 
Сообщение27.03.2009, 16:21 
выложите ограничения на числа $n$ и $a_n$. В задачах по программированию это важно.
Но вообще жадный алгоритм по идее должен подойти.

 
 
 
 
Сообщение27.03.2009, 16:29 
Аватара пользователя
На счет ограничений ничего не сказано...
Насколько я знаю, задачи оценивают по тому, сколько тестовых заданий они проходят за определенное время.
В прошлом году, была близкая задача ранца с максимальным количеством n=75 и максимальной стоимостью предмета 196.
Надеюсь это поможет.

Я думаю о решении этой задачи посредством преобразования ее в задачу о ранце посредством назначения каждому множителю стоимости 1 и назначением целой части квадратного корня из с: $\sqrt c$ в качестве ограничения.
Но в этом случае при n > 10 уже могу вылететь за временные ограничения.

 
 
 
 
Сообщение27.03.2009, 16:57 
да просто жадным алгоритмом попробуйте. Разбиваете любым образом на два подмножества, а дальше туда сюда перекидываете числа уменьшая требуемую разницу.

 
 
 
 
Сообщение27.03.2009, 17:20 
Аватара пользователя
Не думаю, что жадный алгоритм здесь приемлем.
К тому же вопрос с произвольным разбиением на множества приводит к необходимости перебора, а это уже $2^{n-1}$ вариантов.
Просто приведу 2 примера:
{3,5,7,11} -> {3,11} и {5,7}
{3,5,7,109} -> {3,5,7} и {109}

 
 
 
 
Сообщение27.03.2009, 17:42 
Аватара пользователя
Другими словами нужно представить $c$ в виде произведения двух сомножителей с минимальной разностью.
Если эта разность небольшая - то можно организовать перебор ее значений. Дело в том, что если $c=xy$, то $4c=(x+y)^2-(x-y)^2.$ Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.

 
 
 
 
Сообщение27.03.2009, 18:12 
Алекс77 писал(а):
Не думаю, что жадный алгоритм здесь приемлем.
К тому же вопрос с произвольным разбиением на множества приводит к необходимости перебора, а это уже $2^{n-1}$ вариантов.
Просто приведу 2 примера:
{3,5,7,11} -> {3,11} и {5,7}
{3,5,7,109} -> {3,5,7} и {109}

Пусть $a_i$ упорядочены по возрастанию.
Предлагаю сначала найти величину $\frac{\sqrt{a_1^ba_2\dots a_n}}{a_n}$, а затем приближаться к ней, перемножая остальные $a_i$, начиная с самого большого, поиском в глубину.

PS: Удивительные совпадения бывают.
Сегодня вел кружок у школьников (по математике, а не по информатике) и просто так, из головы предложил им такую задачку: разбить цифры от 1 до 9 на две группы так, чтобы произведения чисел в группах отличались на минимально возможную величину.

 
 
 
 
Сообщение27.03.2009, 18:30 
Аватара пользователя
maxal писал(а):
Другими словами нужно представить $c$ в виде произведения двух сомножителей с минимальной разностью.
Если эта разность небольшая - то можно организовать перебор ее значений. Дело в том, что если $c=xy$, то $4c=(x+y)^2-(x-y)^2.$ Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.


Спасибо maxal, очень интересное наблюдение.
А есть какие-нибудь математические выкладки на тему ускорения поиска числа d?
Просто при n>10 уже вроде за 1 миллион произведение перескакивает даже при минимальных множителях, а там квадраты перебирать может долго получиться...

 
 
 
 
Сообщение27.03.2009, 18:45 
Аватара пользователя
maxal писал(а):
Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.

Гениально! Но тогда эффективнее искать такое натуральное $f$, что $\left(\lfloor2\sqrt{c}\rfloor+f\right)^2-4c$ является полным квадратом.
По крайней мере, применительно к задаче VAL этот способ находит решение уже при $f=2$, тогда как $d=54$.

 
 
 
 
Сообщение27.03.2009, 18:53 
maxal писал(а):
Другими словами нужно представить $c$ в виде произведения двух сомножителей с минимальной разностью.
Если эта разность небольшая - то можно организовать перебор ее значений. Дело в том, что если $c=xy$, то $4c=(x+y)^2-(x-y)^2.$ Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.

Идеи Ферма живут и побеждают? Симпатично!

Однако при малых n (или большом различии между $a_i$) моим способом быстрее получается.
Впрочем, при малых n не сложно и вручную решить :)

 
 
 
 
Сообщение27.03.2009, 19:38 
Аватара пользователя
VAL писал(а):
Однако при малых n (или большом различии между $a_i$) моим способом быстрее получается.
Впрочем, при малых n не сложно и вручную решить :)


Одна просьба, можно чуть-чуть поподробней описать алгоритм, скажем так, для чайника?

Заранее спасибо!

 
 
 
 
Сообщение28.03.2009, 08:13 
Алекс77 писал(а):
VAL писал(а):
Однако при малых n (или большом различии между $a_i$) моим способом быстрее получается.
Впрочем, при малых n не сложно и вручную решить :)


Одна просьба, можно чуть-чуть поподробней описать алгоритм, скажем так, для чайника?

А зачем?
Насчет того, что моим методом будет считаться быстрее, чем у maxalа, я шутил.
Впрочем, мне не жалко. Вот код на Maple (на другом в последнее время не пишу :) )

Код:
mindiff := proc(L)
local n, m, p, pr, s, i, j, c, st, St;
    n := nops(L);
    pr := mul(L[j], j = 1 .. n);
    c := evalf(sqrt(pr));
    m := pr;
    St := [[L[1], 2]];
    do
        st := St[-1];
        s := st[1];
        i := st[2];
        if c < s or n < i then
            if abs(s - c) < m then m := abs(s - c); p := s
            end if;
            St := [St[j] $ (j = 1 .. nops(St) - 1)];
            if St = [] then break end if;
            St[-1][2] := St[-1][2] + 1;
            s := St[-1][1];
            if c - s < m then m := c - s; p := s end if
        else St := [op(St), [s*L[i], i + 1]]
        end if
    end do;
    [pr/p, p]
end proc


А вот пример обращения (восьмерка, пркедставляется в виде произведения четверки и двойки):
Код:
mindiff([37,17,11,7,5,4,3,2]);
                             [2380, 2442]

 
 
 
 
Сообщение30.03.2009, 13:53 
Аватара пользователя
Огромное спасибо всем - очень помогли,
Владимиру - особенные респекты! :)

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group