|
|
|
maxdiver |
|
|||
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Ну вот я закодил эту идею с динамическим программированием, и оставил на час выполняться на случайных данных. Самое медленное время работы - 250 мс, что действительно гораздо меньше двух секунд
ksnk, да, извиняюсь, не посмотрел ваш код - он действительно работает за 2^29. Правда, надо понимать, что одно дело - 2^29 рекурсивных вызовов, а другое - пусть даже столько же по количеству, но гораздо более простых операций (сложение двух чисел и обращение к массиву).
К сожалению, я не представляю, как точно оценить это число "на бумажке", но вот после часа работы не нашлось ни одного теста, на котором было бы достижимо больше, чем 1/4 состояний динамики. Таким образом, "экспериментальное" время работы - около 100 млн операций. |
|||
|
||||
ksnk |
|
|||
прохожий Профиль Группа: Комодератор Сообщений: 6855 Регистрация: 13.4.2007 Где: СПб Репутация: 7 Всего: 386 |
maxdiver, да, метод работает и достаточно эффективно
выдает 2972 варианта при несущественном времени выполнения... -------------------- Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! |
|||
|
||||
ksnk |
|
|||
прохожий Профиль Группа: Комодератор Сообщений: 6855 Регистрация: 13.4.2007 Где: СПб Репутация: 7 Всего: 386 |
maxdiver, Попытался оценить сложность вычисления и внезапно обнаружил, что сложность по этому методу факториальна. То есть при увеличении массива исходных чисел до n+1 получаем увеличение времени на n+1 в худшем случае. А совсем даже не в 2 раза, как при полном переборе.
Я что-то понимаю неправильно? -------------------- Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! |
|||
|
||||
maxdiver |
|
|||
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
ksnk
Не совсем понял. Откуда факториальная, если во-первых мы не считаем никакое состояние (n,m) дважды, а во-вторых нам не нужны m больше s, т.е. больше 1000000? Сложность работы - O (n^2 * m), поскольку у нас есть n * m ячеек, каждая из которых считается за O(n). |
|||
|
||||
ksnk |
|
|||
прохожий Профиль Группа: Комодератор Сообщений: 6855 Регистрация: 13.4.2007 Где: СПб Репутация: 7 Всего: 386 |
Откуда взялся миллион? C клавиатуры можно ввести число от 1 до 2147483648, если ограничиться натуральными числами и стандартным longint, не связываясь с "длинной" арифметикой... Сложность не факториальна, да... Пусть сложность вычисления для n оценивается функцией o(n). Тогда для n+1, сложность алгоритма, описанного выше, можно оценить o(n)+o(n-1)+...+o(0). А если упростить для n-1 и так далее - то получится сложность степени 2... примерно то-же, что и для перебора. Добавлено через 2 минуты и 20 секунд Чтобы получить длительное время выполнения - достаточно поставить большое число в правую часть равенства. Так не будут срабатывать "отсечения" лишних веток пребора -------------------- Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! |
|||
|
||||
maxdiver |
|
|||
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Ну так по условию число не более миллиона:
А без этого ограничения - понятно, что перебор будет не сильно хуже, т.к. динамика по сути тоже ходит по всевозможным достижимым значениям, просто она "сжимает" несколько способов достижения одного и того же числа в одно состояние. А вот при наличии данного ограничения динамика сильно улучшает перебор, т.к. например на тесте N=30, S=30, все a_i = 1 перебор будет перебирать все 2^29 вариантов, а динамика отработает мгновенно. Впрочем, сейчас мне придумалось другое решение, гораздо более быстрое, и которое не использует факта, что S маленькое. Идея называется "meet-in-the-middle". В общем, давайте будем разбивать задачу на две части размера не более 15. А именно, любое подходящее выражение можно разбить на три части: 1) несколько первых слагаемых 2) слагаемое, содержащее N/2-ое число 3) несколько последних слагаемых Основная идея - что мы будем перебирать только слагаемые 2) и 1), а вот слагаемое 3) мы переберём заранее. Таким образом, мы предварительно перебираем все выражения из <=N/2 последних чисел, посчитаем каждое такое выражение, и построим такую табличку - сколько раз каждое возможное значение у нас получилось. Этот шаг выполняется за O (2^{n/2} * log (2^{n/2})), т.е. за O (n * 2^{n/2}). Затем мы перебираем все выражения из <=N/2 первых чисел (это часть #1), а также перебираем, сколько следующих чисел мы относим к части #2. Для каждого получившегося числа мы просто отнимаем его от S и заглядываем в табличку для части 3), прибавляя к ответу количество подходящих частей #3. Этот шаг также можно реализовать за O (n * 2^{n/2}). Итого - O (n * 2^{n/2}), т.е. при наших ограничениях это около 30 * 2^16, т.е. порядка миллиона операций. Закодил - для N=30 работает вообще мгновенно, ну как и следовало ожидать. |
|||
|
||||
ksnk |
|
|||
прохожий Профиль Группа: Комодератор Сообщений: 6855 Регистрация: 13.4.2007 Где: СПб Репутация: 7 Всего: 386 |
Да, про миллион это я пропустил...
особенно то, где все кусочки нужно перемножить... или только с одним плюсом... Что-то мне кажется, что не все так просто. Надо будет подумать -------------------- Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! |
|||
|
||||
maxdiver |
|
|||
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Ну части #1 и #3 могут быть пустыми. Главное, что всегда найдётся среднее слагаемое, разбивающее выражение на две половинки с <=15 числами каждая.
Вообще я эту идею стрессил, т.е. сравнивал на случайных тестах с динамикой, и ответы сходятся. |
|||
|
||||
Dmi3ev |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 1698 Регистрация: 28.11.2007 Репутация: нет Всего: 41 |
Пока ничего не выходит(((
-------------------- |
|||
|
||||
ksnk |
|
|||
прохожий Профиль Группа: Комодератор Сообщений: 6855 Регистрация: 13.4.2007 Где: СПб Репутация: 7 Всего: 386 |
Dmi3ev, а что конкретно не выходит? Может будет правильнее паскальный код сюда бросить?
-------------------- Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! |
|||
|
||||
Dmi3ev |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 1698 Регистрация: 28.11.2007 Репутация: нет Всего: 41 |
Нашел сайт, где указываются темы, которые необходимо изучить для ее решения.
необходимо знать: 1) Динамическое программирование 2) Перебор с отсечением Начал курить это дело... О результатах сообщу... -------------------- |
|||
|
||||
миг |
|
|||
Бывалый Профиль Группа: Участник Сообщений: 157 Регистрация: 15.9.2008 Репутация: нет Всего: 1 |
а если S =10^6-1. то значит решений нет или существует только одно решение... или можно сказать так, чем ближе S приближается к верхней и нижней границы тем меньше решений(если вообще есть решения). я тут попробовал взять несколько примеров первый пример 1,2,3,4,5,6,7,8,9,10=b=1814402 Ряд брал из 10 чисел, т.к. вычисления достаточно громоздкие. 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) вывел ф-лу x=y/(b-z), т.е. x=3628800/(1814402-z) 3) подбираю такое z, чтобы число делилось без остатка и число х было положительным. например если z=2, то x=3628800/(1814402-2)=2 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается только x=1*2=2 5) далее из этих двух чисел нужно составить число равное z. т.е. z=1*2=2 (путем подбора варьируем знаками "*" и "+" числа местами не переставлять в других примерах это будет очень важно). 6) 1*2+3*4*5*6*7*8*9*10=1814402 второй пример 1,2,3,4,5,6,7,8,9,10=b=604806 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) x=y/(b-z)= 3628800/(604806-z). 3) Например если z=6 то x=3628800/(604806-6)=6 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается только x=1*2*3=6 5) далее из этих трех чисел нужно составить число z=1+2+3=6 или 1*2*3=6 6) первое решение 1+2+3+4*5*6*7*8*9*10=604806 второе решение 1*2*3+4*5*6*7*8*9*10=604806 третий пример 1,2,3,4,5,6,7,8,9,10=b=1814403 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) x=y/(b-z)= 3628800/(1814403-z). 3) Например если z=3 то x=3628800/(1814403-3)=2 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается только x=1*2=2 5) далее из этих двух чисел нужно составить число z=1+2=3 6) решение 1+2+3*4*5*6*7*8*9*10=1814403 четвертый пример 1,2,3,4,5,6,7,8,9,10=b=604805 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) x=y/(b-z)= 3628800/(604805-z). 3) Например если z=5 то x=3628800/(604805-5)=6 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается только x=1*2*3=6 5) далее из этих трех чисел нужно составить число z=1*2+3=5 6) решение 1*2+3+4*5*6*7*8*9*10=604805 пятый пример 1,2,3,4,5,6,7,8,9,10=b=151210 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) x=y/(b-z)= 3628800/(604805-z). 3) Например если z=10 то x=3628800/(151210-10)=24 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается только x=1*2*3*4=24 5) далее из этих четырех чисел нужно составить число z=1*2*3+4=10 или z=1+2+3+4=10 6) решение 1*2*3+4+5*6*7*8*9*10=151210 или z=1+2+3+4+5*6*7*8*9*10=151210 шестой пример 1,2,3,4,5,6,7,8,9,10=b=604807 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) x=y/(b-z)= 3628800/(604807-z). 3) Например если z=7 то x=3628800/(604807-7)=6 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается только x=1*2*3=6 5) далее из этих чисел нужно составить число z=1+2*3=7 6) решение 1+2*3+4*5*6*7*8*9*10=604807 седьмой пример 1,2,3,4,5,6,7,8,9,10=b=55 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) x=y/(b-z)= 3628800/(55-z). 3) Например если z=54 то x=3628800/(55-54)=3628800 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается x=2*3*4*5*6*7*8*9*10=3628800=y или x=1*2*3*4*5*6*7*8*9*10=3628800=y 5) далее из этих чисел нужно составить число z=2+3+4+5+6+7+8+9+10=54 6) решение 1+2+3+4+5+6+7+8+9+10=55 восьмой пример 1,2,3,4,5,6,7,8,9,10=b=789 1) Умножаем все числа друг на друга. 1*2*3*4*5*6*7*8*9*10=3628800=y 2) x=y/(b-z)= 3628800/(789-z). 3) Например если z=69 то x=3628800/(789-69)=5040 4) далее смотрим путем подбора при произведение каких, чисел можно получить число x. Получается только х=1*2*3*4*5*6*7=5040 5) далее из этих чисел нужно составить число z=1+2*3+4*5+6*7=69. путем подбора либо по формуле в пункте 2. 6) одно из решений 1+2*3+4*5+6*7+8*9*10=789 .. возможно еще есть решение я просто не пробовал его найти вручную.. а может и нет решения)) Вообщем в пункте 2 если варьировать числом z от 0 до b-1.. Возможно найти еще решения. Это сообщение отредактировал(а) миг - 13.11.2011, 11:42 --------------------
Oaks may fall when reeds stand the storm. |
|||
|
||||
миг |
|
|||
Бывалый Профиль Группа: Участник Сообщений: 157 Регистрация: 15.9.2008 Репутация: нет Всего: 1 |
1,2,3,4,5,6,7,0,8,9,10=S. если в ряде присутствуют нулевые и вещественные числа, то такое решение не подходит. Правда нулевые числа можно обойти. например сразу записать несколько вариантов условий 1,2,3,4,5,6,7+0+8,9,10=S или так 1,2,3,4,5,6+7*0+8,9,10=b или 1*2*3*4*5*6*7*0*8*9*10=b 1,2,3,4,5,6+7*0*8*9+10=b. только в этом случае в ряде будет гораздо меньше чисел, чем планировалось.
Это сообщение отредактировал(а) миг - 14.11.2011, 18:00 --------------------
Oaks may fall when reeds stand the storm. |
|||
|
||||
Bunybi |
|
|||
Новичок Профиль Группа: Участник Сообщений: 1 Регистрация: 26.6.2019 Репутация: нет Всего: нет |
Правильные порядок в расчете очень важен, сначала умножение или сложение, а затем все остальное. Правильный порядок арифметических действий в математике зависит от их типа и условий конкретного примера. Знание правил очередности необходимо, поскольку они являются основой как для многих бытовых операций (покупки, измерения), так и более сложных расчетов.
|
|||
|
||||
Kuroki2223 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 10 Регистрация: 1.11.2020 Репутация: нет Всего: нет |
Пробовал промежуточный результат?
|
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |