| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > разложение числа |
| Автор: stab 16.1.2008, 19:07 |
| дурацкий вопрос, но как некоторое число M представить в виде b^0*x1 + b^1*x2 + b^2*x3 + ... + b^(n - 1)*xn, т.е. выразить в системе счисления с основанием b, используя только целочисленное умножение и сложение\вычитание? |
| Автор: baldina 16.1.2008, 19:20 |
используя только целочисленное умножение и сложение\вычитание его можно представить в виде b^0*x1 + b^1*x2 + b^2*x3 ... b^(n - 1)*xn - сам же написал  а если надо разложить число, потребуется целочисленное деление и остаток. i=0 while not (M = 0) Xi = M%b M = M / b i = i+1 end если надо смоделировать деление и получение остатка - заменяй циклическим вычитанием. как только результат вычитания станет меньше вычитаемого, это и будет "остаток целочисленного деления" |
| Автор: maxim1000 16.1.2008, 19:21 |
| хм... не уверен, что получится без деления есть два алгоритма перевода чисел из одной системы в другую: 1. деление - все операции производятся в исходной системе: переводим в неё x/b и цепляем к рехультату x%b (b - основание целевой системы) 2. умножение - все операции производятся в целевой системе: рассматриваем аргумент, как x1*a^0+a2*a^1+...+xn*a^(n-1). только все операции производим в целевой системе, получая, соответственно, результат в ней же на первый взгляд, достаточно просто использовать алгоритм умножения но проблема в том, что для этого нужна арифметика в целевой системе, а для неё, если я не ошибаюсь, необходима операция деления хотя бы на основание или аналогичные действия (как, например, сдвиг в двоичной системе) |
| Автор: stab 16.1.2008, 19:22 |
| в крайнем случае по модулю можно делить, т.е. находить остаток от деления, но само деление нельзя использовать. |
| Автор: baldina 16.1.2008, 19:28 |
| деление заменять вычитанием запрещено? |
| Автор: stab 16.1.2008, 19:29 | ||
| baldina, наверное я забыл написть что дано только M и b. вообще, меня алгоритм не особо интересует, скорее интересует f(x) = A1 * ((x / 100) % 10) + A2 * ((x / 10) % 10) + A3 * (x % 10) выраженное без деления и желательно без деления по модулю. если это вообще возможно.  Добавлено через 4 минуты и 51 секунду
ммм.. это как? |
| Автор: baldina 16.1.2008, 19:36 | ||
Что-то не пойму я, прости.
Я так понимаю, здесь b=10 и M=f(x). Но ты сказал, что b и M даны. Так что ты хочешь получить? Добавлено через 1 минуту и 40 секунд А если ты хочешь не f(x), а Аi для построение выражения для f, то Ai это Xi в алгоритме, что я привел Добавлено через 5 минут и 40 секунд не, все-таки не понимаю. если в твоей формуле А это цифра в i-й позиции, а x это M, то f(x)=x=M  |
| Автор: stab 16.1.2008, 19:44 |
| An - заданные коэффициенты, на вход приходит х, максимум три знака в десятичной записи, его надо разложить на эти самые знаки и каждый умножить на соответствующий Ai, сложить и вернуть. беда в том, что мне надо не только вычислять это выражение, но и решить аналитически несколько уравнений в целых числах в которых оно фигурирует, если я туда деление введу они слишком сложные станут. Добавлено через 1 минуту и 16 секунд .. они и так уже не шибко простые. |
| Автор: baldina 16.1.2008, 19:48 | ||
| деление заменять вычитанием - это так: результат целочисленного деления a на b - число шагов при вычитании b из а, пока a > b кстати конечное а - остаток деления
вроде это в начальной школе проходят  |
| Автор: stab 16.1.2008, 19:52 | ||
я было подумал, что есть божественный способ сделать это за фиксированное число шагов. |
| Автор: baldina 16.1.2008, 19:52 |
| т.е. фактически тебе нужно вычисление типа ((x / 100) % 10) не используя деление и взятие остатка? если аналитически, то в целых числах умножением не заменишь, а выражение для циклической разности тебя врядли обрадует больше... Добавлено через 1 минуту и 24 секунды не, божественных нет, увы. но если у тебя есть ограничение на число цифр - это и есть максимальное число шагов |
| Автор: stab 16.1.2008, 19:56 | ||
да, и вринципе по барабану будет ли это верным разложением числа, главное чтобы загоняя в функцию все х от 0 до 999, можно было получить все её возможные значения, необязательно в правильном порядке. |
| Автор: baldina 16.1.2008, 19:59 |
| А если ты аналитически будешь решать свои уравнения, положив g(x,n) = (x/10^n)%10 ? т.е. f(x) = A1 * g(x,2) + A2 * g(x,1) + A3 * g(x,0) упростить тут не получится, но само выражение выглядит не так страшно, а в результате возможно g(x,a)/g(x,b) где-нить и сократится |
| Автор: stab 16.1.2008, 20:03 | ||||
хотелось бы фиксированное, чтобы аналитически можно было записать. Добавлено через 1 минуту и 16 секунд
не подходит такой вариант к сожалению. |
| Автор: baldina 16.1.2008, 20:06 |
| а А1, А2 и А3 - составляющие пароля? шутка если ты введешь в своё выражение деление, выражение станет таким как и должно быть. пусть сложным. потом, возможно, сократится. а если нет - так и должно быть сложным. но почему бы тебе в аналитических преобразованиях не использовать действительные числа, контролируя что ты всегда верно сможешь выделить целую часть? Добавлено через 7 минут и 22 секунды кстати, возможных значений f(x) будет гораздо меньше тысячи. например при А=(1,2,3) f(321)=f(22)=10 |
| Автор: stab 16.1.2008, 20:13 | ||
слишком большое множество решений получается, по сути, истинное решение потом придётся искать перебором, а это как раз то от чего нужно избавиться |
| Автор: baldina 16.1.2008, 20:15 |
| понятно... ты про А(1,2,3) и f(321)=f(22)=10 прочитал? |
| Автор: stab 16.1.2008, 20:34 |
| прочитал, думаю что это может дать.. вроде бы ничего, коэффиценты такие, что по разрядам практически не пересекаются, т.е. формируют разные части результата. |
