Найти длину периода и сам период бесконечной степенной дроби по основанию Р

время поджимает, завтра сдавать. препод ни фига не объясняет!!!
есть решение, осталось написать прогу на C++.

Задача №1
Имеется N банок с целочисленными объемами V1, ..., Vn литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок налить в сосуд ровно V литров воды.

Решение:
С помощью двух банок мы можем без особых ухищрений саккумулировать в сосуде количество литров, равное их наибольшему общему делителю. Например, с помощью сосудов в 5 и 3 литра, мы можем набрать любое количество воды(проверено на опыте), а их НОД равен 1.
A*x - B*y = НОД(A, B), где A и B - объемы сосудов, а x и y - некоторые величины.
Теперь задача свелась к поиску НОД двух чисел. Постараемся сделать это побыстрее. Для этого воспользуемся алгоритмом Евклида. Из двух чисел выберем большее и заменим его на остаток от деления этого числа на меньшее. Будем повторять этот шаг до тех пор, пока одно из чисел не станет равно 0, при этом оставшееся число будет равно НОД этих чисел.
Найдя НОД объемов двух первых банок (НОД(V1, V2)) будем последовательно находить НОД(НОД(V1, V2), V3) и т.д. до Vn. Теперь, если объем делится нацело на НОД, то выводим "YES!", иначе "NO".

Задача №2
Найти длину периода и сам период бесконечной степенной дроби по основанию Р,
представляющей рациональное число N/M (для конечных дробей считать, что длина периода равна 1).
M,N,P - целые десятичные числа, 0<N<M, 1<P

Решение:
Введем переменную N1=N. Пусть N1 и M заданы в десятичной системе счисления. Переведем дробь N1/M в систему счисления с основанием p: Пусть в системе с основанием p искомая дробь 0.a(1)a(2)... Получаем: a(1)*p-1+a(2)*p-2+ ... =N1/M. Умножим правую и левую части равенства на p: a(1)+a(2)*p-1+ ... = N1*p/M. Выделяя целую часть выражений слева и справа от знака равенства, получаем a(1) = целая часть (N1*p/M). Обозначим N2 = N1*p mod M; очевидным образом получаем a(2)*p-1+ ... = N2/M. Домножая на p и находя целую часть, опять же имеем a(2) = целая часть (N2*p/M); продолжая аналогично, определяем коэффициенты a(3),a(4) и т.д. В ходе выделения цифр ai мы можем получить различных значений Ni не более чем M (по алгоритму выше у нас всегда Ni<M). Если вдруг какие-то два остатка совпадают: Ni=Nj, i<>j, то совпадают и цифры разложения: ai+1=aj+1, ai+2=aj+2, ... , т.е. цифры (ai+1, ... ,aj) образуют один из кратных периодов. Нам надо найти минимальную длину такой периодически повторяющейся последовательности, которая равна количеству цифр между двумя ближайшими повторяющимися остатками, и сами цифры. Поступаем следующим образом: Выделяем M цифр p-ичной дроби (исходя из вышесказанного, к этому моменту период уже обязан начаться). Запоминаем Nm, и ищем первый такой остаток Nk, k>m, что Nm=Nk. Величина k-m как раз и есть искомая длина периода.

0

За бесплатно врядли кто-то будет делать, придется тебе идти в раздел "Заказ программ"

0

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

0