Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 10.05.2008, 12:30
Новичок

Отправить личное сообщение для SGans Посмотреть профиль Найти все сообщения от SGans
 
Регистрация: 10.05.2008
Сообщений: 4

Представление числа в виде произведения
Существует ли алгоритм представления числа в виде произведения плюс ошибка? Если да, то как минимизировать ошибку? Где об этом можно почитать?
  #2  
Старый 10.05.2008, 12:53
гость

 
Сообщений: n/a

Разложение на простые множители вам не подходит?
  #3  
Старый 12.05.2008, 20:34
гость

 
Сообщений: n/a

запросто. ошибку, как ты ее называешь, на самом деле зовут остатком от деления. например, любое число можно представить в виде:
2*x+r=y, где r - ошибка (остаток от деления) максимум равна 1.
или
3*x+r=y, r - максимум равна 2.
и так с любыми числами, даже с 1.
если r=0, то это разложение числа на множители.
  #4  
Старый 12.05.2008, 23:38
Новичок

Отправить личное сообщение для SGans Посмотреть профиль Найти все сообщения от SGans
 
Регистрация: 10.05.2008
Сообщений: 4

В этом и проблема, как в случае N=x1*x2*x3....*xn +r минимизировать r. Подбор не проходит, столько не живут :-(
  #5  
Старый 12.05.2008, 23:59
гость

 
Сообщений: n/a

В чем проблема с предложением разложить число на множители? Если N не простое это элементарно решает твою задачу, давая r=0. Если не простое, то r как минимум должно быть равно единице, и этот минимум достижим: все простые нечетные (ну кроме одного неинтересного случая), а значит N-1 делится на 2, т.е. N = 2 * ([N-1]/2) + 1. Алгоритмом разложения до фига - в гугл по factorization.

Если проблема с размером чисел, приводи конкретный размер какие у тебя числа, чтоб нам не гадать на кофейной гуще.
  #6  
Старый 13.05.2008, 00:32
Новичок

Отправить личное сообщение для SGans Посмотреть профиль Найти все сообщения от SGans
 
Регистрация: 10.05.2008
Сообщений: 4

Пардон! Не знал, что размер имеет значение в данном случае :-).
Число может достигать 2**2048, а множитель должен помещаться в байт :-(
  #7  
Старый 13.05.2008, 01:04
гость

 
Сообщений: n/a

Да, размер *всегда* имеет значение.

Сообщение от SGans Посмотреть сообщение
а множитель должен помещаться в байт :-(
Каждый множитель должен быть в интервале 2 до 255? Что же вы раньше об этом не сказали, это же кардинально меняет дело.
Еще вопрос - вам нужно точное минимальное значение для r, или приближенного достаточно?
  #8  
Старый 13.05.2008, 08:21
Новичок

Отправить личное сообщение для SGans Посмотреть профиль Найти все сообщения от SGans
 
Регистрация: 10.05.2008
Сообщений: 4

Достаточно знать, что r минимально возможное. Точность не особо важна.
  #9  
Старый 18.06.2008, 12:11
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Перейдите к логарифмам и приближайте логарифм данного числа линейной комбинацией логарифмов чисел 2, 3,..., 255 с целыми коэффициентами.
См. http://mathworld.wolfram.com/IntegerRelation.html
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
представление графов!!! =[miKroZ]= Графы 4 21.01.2008 12:37
представление дроби Хрущев Задачи 3 28.05.2007 13:07