Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: Задача с числами

 PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (1): [1]   

> Без описания
kir55rus
Отправлено: 07 Февраля, 2013 - 17:26:16
Post Id


Новичок


Покинул форум
Сообщений всего: 52
Дата рег-ции: Янв. 2012  
Откуда: Омск, Россия


Помог: 0 раз(а)




Здравствуйте.

есть некоторое число N. нужно разложить его на множители и вывести два, сумма которых наименьшая.
Например, N = 24

Раскладываем на множители:
24 = 2*2*2*3 (простые числа)

из этих чисел можно составить пары, произведение которых будет равно 24:
2 и 12 (2 и 2*2*3)
4 и 6 (2*2 и 2*3)
8 и 3 (2*2*2 и 3)

2+12 = 14
4+6=10
8+3=11

Наименьшая сумма равна 10, следовательно нужно вывести два числа: 4 и 6

Как реализовать такое?
не хотелось бы лепить кучу циклов в коде... (решето Эратосфена, чтобы разложить на множители, само разложение, перебор чисел, составление пар...)

Заранее благодарен
 
 Top
EuGen Администратор
Отправлено: 07 Февраля, 2013 - 18:34:30
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Если не хочется возиться с большим числом циклов, то Вы, безусловно, можете воспользоваться, к примеру, методом эллиптических кривых или методом общего решета числового поля. Правда их реализация много сложнее решета Эратосфена. И вообще факторизация числа - это NP-полная задача (на текущий момент).
Что же до составления пар- этого и не потребуется. В силу верности утверждения
min(Xi)+min(Yj)<=min(Xi+Yj), x,y>=0, i,j in {N}
- достаточно получить список множителей в отсортированном виде (можете воспользоваться, например, sort) и искомая сумма будет суммой первых двух элементов.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Champion Супермодератор
Отправлено: 07 Февраля, 2013 - 22:14:23
Post Id



Активный участник


Покинул форум
Сообщений всего: 4350
Дата рег-ции: Авг. 2008  
Откуда: Москва


Помог: 57 раз(а)




EuGen пишет:
и искомая сумма будет суммой первых двух элементов.
Ну не совсем. В этом примере два первых элемента будет 2 и 3, но они пару не образуют. Лучше все-таки искать минимум в суммах.

А по поводу разложения, такое не покатит?
PHP:
скопировать код в буфер обмена
  1. $rest = $srcNumber;
  2. $mults = array();
  3. for ($i = 2; $rest > 1; ) {
  4.   if ( is_int($rest / $i)) {
  5.     $mults[] = $i;
  6.     $rest /= $i;
  7.    }else {
  8.      ++$i;
  9.    }
  10.  
  11. }

(Добавление)
Но можно разложить и исходное число, и 24 таким способом, а потом, действительно брать по очереди множители исходного числа, если такой же множитель есть и у 24, то отложить его в кучку и убрать из рассмотрения из 24 (только учесть, что и у 24, и у самого исходного числа может быть по несколько одинаковых множителей). Получившаяся последовательность будет состоять из минимальных множителей, которые дадут 24.
Теперь можно циклом, перебрав половину этих множителей получать два числа
div24 и 24/div24 (div24 - это перемноженный на все предыдущие множитель из полученных на предыдущем этапе), найти сумму и сравнить ее с минимальной
 
 Top
EuGen Администратор
Отправлено: 07 Февраля, 2013 - 22:29:36
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Хотя да, я не досмотрел, что нужна именно полная пара, а не просто пара множителей. В таком случае минимальную сумму дадут те, что наиболее близки к квадратному корню от числа. Иными словами - у нас есть множество делителей, выбираем из них тот, что наиболее близок к квадратному корню и затем делим исходное число на него, получая второй множитель. Итог - оба найдены, перебор не нужен.
Champion пишет:
А по поводу разложения, такое не покатит?

Вполне, но этот метод и есть - суть полный перебор. То же решето Эратосфена даст более быстрый результат.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Champion Супермодератор
Отправлено: 07 Февраля, 2013 - 22:40:39
Post Id



Активный участник


Покинул форум
Сообщений всего: 4350
Дата рег-ции: Авг. 2008  
Откуда: Москва


Помог: 57 раз(а)




Но этот перебор остановится, когда делить ни на что не останется.
А решето Эратосфена подразумевается использовать для получения N простых чисел? Нам же все равно сначала надо проинициализировать массив-решето числами в кличестве N (или N-1, не помню).
Хотя, конечно, инициализация решета менее затратна, чем иф с делением, но большинство раз, я думаю, этот цикл будет заканчиваться числа так до 53. Но с большими простыми множителями будет конечно медленноват
 
 Top
EuGen Администратор
Отправлено: 07 Февраля, 2013 - 22:45:08
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Champion пишет:
Но этот перебор остановится, когда делить ни на что не останется.

- так любой перебор должен останавливаться. Кстати, перебирать достаточно до округленного вверх квадратного корня из исходного числа.
Я планирую сделать факторизацию по методу эллиптических кривых. К слову сказать, это на данный момент вообще единственный метод, отличный от перебора, который позволяет факторизовать число с произвольными множителями. Но даже он имеет оценочную сложность \exp(\sqrt{2}/2 + o(1) \sqrt{p \ln p \ln (\ln p)}) , где p - наименьшие делитель исходного числа. Вообще эта задача пока что NP-полна, и именно на этом факте зиждется современная криптография. Если удастся найти полиномиальный способ факторизации, то все шифрование (как, например, RSA) пойдет прахом.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Champion Супермодератор
Отправлено: 07 Февраля, 2013 - 22:46:13
Post Id



Активный участник


Покинул форум
Сообщений всего: 4350
Дата рег-ции: Авг. 2008  
Откуда: Москва


Помог: 57 раз(а)




EuGen пишет:
Иными словами - у нас есть множество делителей, выбираем из них тот, что наиболее близок к квадратному корню и затем делим исходное число на него
Опять же в примере числа 4 и 6 - изначально у нас их нет. Они сами получаются перемножением наших имеющихся делителей.

Кстати, наверное, вообще правильнее разлагать только 24, получать пары, а потом искать пары в большом числе в порядке их сумм
(Добавление)
EuGen пишет:
Я планирую сделать факторизацию по методу эллиптических кривых
Он, к сожаленнию, выходит за границы моих математических познаний, поэтому я не могу оценить, на сколько этот метод крут)

EuGen пишет:
так любой перебор должен останавливаться.

Ну разумеется) Я просто предположил, что это произойдет быстрее, чем перебор до N (я почему-то только о нем подумал).
EuGen пишет:
Кстати, перебирать достаточно до округленного вверх квадратного корня из исходного числа.
Точно.
 
 Top
EuGen Администратор
Отправлено: 07 Февраля, 2013 - 22:48:07
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Champion пишет:
Опять же в примере числа 4 и 6 - изначально у нас их нет. Они сами получаются перемножением наших имеющихся делителей.

Ну так я же и сказал - что нужны все множители. Я не писал, что это разложение должно быть в канонической форме (то есть в виде степеней простых чисел). Если они у нас есть, то алгоритм поиска я уже указал, перебор там не нужен. Перебор же чисел при факторизации - в любом случае неизбежен (можно лишь "оптимизировать затраты").
Champion пишет:
Он, к сожаленнию, выходит за границы моих математических познаний, поэтому я не могу оценить, на сколько это круто)

- метод Ленстры


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Champion Супермодератор
Отправлено: 07 Февраля, 2013 - 22:53:48
Post Id



Активный участник


Покинул форум
Сообщений всего: 4350
Дата рег-ции: Авг. 2008  
Откуда: Москва


Помог: 57 раз(а)




EuGen пишет:
метод Ленстры
Thanks
 
 Top
kir55rus
Отправлено: 08 Февраля, 2013 - 16:21:50
Post Id


Новичок


Покинул форум
Сообщений всего: 52
Дата рег-ции: Янв. 2012  
Откуда: Омск, Россия


Помог: 0 раз(а)




Спасибо за ответы!
Понравилась идея с извлечением корня из числа.
То есть возьмем все то же число 24
sqrt(24) ~ 4.9

Начинаем перебор от 5


PHP:
скопировать код в буфер обмена
  1. $a = 24;
  2.  
  3. for($sq = sqrt($a), $i = (int)($sq+0.99); $i <= $a; $i++){
  4.  
  5.         if($a % $i == 0){
  6.                 echo $i.' и '.($a/$i);
  7.                 break;
  8.         }
  9.  
  10. }


Вот и получаем 2 числа. И при этом используем всего 1 цикл Улыбка
Спасибо огромное!

(Отредактировано автором: 08 Февраля, 2013 - 16:22:07)

 
 Top
SAD
Отправлено: 08 Февраля, 2013 - 16:59:52
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2508
Дата рег-ции: Май 2009  
Откуда: Днепропетровск, Украина


Помог: 75 раз(а)




Хорошие рассуждения
 
 Top
Страниц (1): [1]
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Вопросы новичков »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB