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

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

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

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

07.11.2008, 20:20. Просмотров 2665. Ответов 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++ Дано натуральное число n > 1. Определить длину периода десятичной записи дроби 1/n.
Перевод из системы по основанию 10 в систему по основанию 8 C++
Определить длину периода C++
Перевод из системы по основанию 16 в систему по основанию 10 C++
Перевод из системы по основанию 16 в систему по основанию 10 C++
C++ Найти координаты числа в бесконечной спирали из чисел
Перевод из системы по основанию 8 в систему по основанию 10. C++
Выделить период в десятичной дроби, если таковой имеется C++
Найти значение цепной дроби C++
C++ Перевод из системы по основанию 16 в систему по основанию 10
Вычислить значение дроби (кажется дроби) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
я издалека, виртуальными деньгами не владею поэтому даже не знаю как можно будет заплатить...
надеялась, что может, задачи не такие уж и сложные.
Yandex
Объявления
07.11.2008, 23:23     Найти длину периода и сам период бесконечной степенной дроби по основанию Р
Ответ Создать тему
Опции темы

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