Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.73
Mandy
0 / 0 / 0
Регистрация: 27.12.2007
Сообщений: 4
#1

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

07.11.2008, 20:20. Просмотров 2697. Ответов 2
Метки нет (Все метки)

время поджимает, завтра сдавать. препод ни фига не объясняет!!!
есть решение, осталось написать прогу на 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 как раз и есть искомая длина периода.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.11.2008, 20:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти длину периода и сам период бесконечной степенной дроби по основанию Р (C++):

Определить длину периода десятичной записи дроби 1/n - C++
1)Из заданого числа вычли сумму его чисел. Из результата вычли ещё раз сумму его цифр и т. д.Сколько таких действий надо сделать чтоб...

Дано натуральное число n > 1. Определить длину периода десятичной записи дроби 1/n. - C++
Здравствуйте, помогите пожалуста решить задачу на с++... Дано натуральное число n &gt; 1. Определить длину периода десятичной записи дроби...

Определить длину периода - C++
Помогите плизз с прогой!=) Дано натуральное число n&gt; 1. Определить длину периода десятичной записи дроби 1 / n.

Выделить период в десятичной дроби, если таковой имеется - C++
Добрый день, форумчане! Подскажите пожалуйста, стоит задача, выделить период в дроби, если таковой имеется !

Найти период и длину периода десятичной дроби. - Java SE
Здравствуйте. Есть задача, которую необходимо решить с использованием Java: Дано простое число p&gt;5. Определить длину периода...

Определить длину периода десятичной дроби M/N и период данной десятичной дроби M/N - Pascal
Даны два натуральных числа M и N, M &lt; N. Определить длину периода десятичной дроби M/N и период данной десятичной дроби M/N. Добавлено...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Spo1ler
292 / 52 / 3
Регистрация: 22.05.2008
Сообщений: 788
07.11.2008, 21:13 #2
За бесплатно врядли кто-то будет делать, придется тебе идти в раздел "Заказ программ"
Mandy
0 / 0 / 0
Регистрация: 27.12.2007
Сообщений: 4
07.11.2008, 23:23  [ТС] #3
я издалека, виртуальными деньгами не владею поэтому даже не знаю как можно будет заплатить...
надеялась, что может, задачи не такие уж и сложные.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2008, 23:23
Привет! Вот еще темы с ответами:

Определить длину периода дроби - Pascal
Рассмотрим дробь 1/n, n&gt;1. Как известно, цифры в её десятичной записи начиная с некоторого места повторяются. Минимальную по длине...

Определить длину периода десятичной дроби - Pascal ABC
Даны два натуральных числа M и N, M &lt; N. Определить длину периода десятичной дроби M/N и период данной десятичной дроби M/N.

Определить длину периода десятичной дроби, используя функцию - Turbo Pascal
дано натуральное число n&gt;1. определить длину периода десятичной дроби, используя функцию. Помогите переделать. сама задача: var...

Период из запроса разбить на начало периода и конец периода - 1С
есть запрос &quot;выбрать оборотыпродажи. период как период из продажиобороты &quot; на выходе имеем поле период которое указывается в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru