Применение лемм 1 и 2


Пусть дано некоторое (большое) число A и число B. Предположим, что 0<B<10 (случай с другими B я пока не рассмотрел). Нас интересует запись числа A. По определению, запись (если смотреть справа налево), это количество единиц каждого разряда, где разряды (тоже некоторые числа, обозначающие число единиц) начинаются с 1 и каждый раз увеличиваются в O раз, где O называется основанием системы счисления. Число определяется количеством единиц, входящих в него, как сумма количеств каждого разряда, умноженных на «величину» разряда. Ключевое слово — сумма.

Рассмотрим ещё одну лемму.

Лемма 3

Лемма

(A + B) mod C = [(A mod C) + (B mod C)] mod C.

Доказательство:
Пусть A = Z*C + G, B = Y*C + H. Тогда (A + B) mod C = [(Z + Y)*C + (G + H)] mod C = (G + H) mod C.

Таким образом, остаток от даления всего числа A на B есть остаток от деления суммы остатков от деления каждого числа из поразрядных составляющих числа А на B. Цикл служит только для ускорения действия.

Задача:

Дана записть некотрого числа в некоторой системе счисления ( основание которой меньше 11 ) — делимое, некоторое число — делитель, Определить остаток от деления.

bigmod.h

#include <string>
#define bigint unsigned long long

class BigMod

{
	public:
		class OutOfRange {};
		BigMod(std::string str):delimoe(str),rez(0),osn(-1) {};

		void setOsn(int osn);
		int operator%(int div);

	private:
		int osn;
		bigint rez;
		std::string delimoe;

		static bool properOsn(int osn);
#ifdef DEBUG
		void sr();

#endif
};

bigmod.cpp

#include <list>
#include «bigmod.h»
#ifdef DEBUG
#include <iostream>
#endif

void BigMod::setOsn(int c_osn)
{

/*__DOC: Устанавливает систему исчисления */

if
( !properOsn( c_osn ) ) throw OutOfRange();

this->osn = c_osn;
#ifdef DEBUG
std::cout << «Основание установлено = « << this->osn << std::endl;

#endif
}

int BigMod::operator%(int div)
{

if
( !properOsn(osn) ) throw OutOfRange();

bool *A = new bool[div];
memset(A,0,sizeof(bool)*div);

/* В массие А значение ИСТИНА элемент A[i] принимает,
* когда такой остаток i уже встречался
*/

std::list<int> frc;
/* Список уже встреченных остатков
*/

/* Вводится вспомогательный массив A,
* чтобы не производить поиск по линейной структуре списка
*/

int curOst = 1 % div;

int mult = osn % div;

/* О назначении этой переменной будет сказано несколько позже
*/

while(!A[curOst]) {
/* Ищем цикл в последовательности остатков */

A[curOst] = true;

frc.push_back(curOst);
curOst = ( curOst * mult ) % div;

/* Для того, чтобы не производить пересчёт
* (если в этом вообще есть необходимость)
* величины (A mod B) при переходе от
* (A^i mod B) к (A^(i+1) mod B) используется mult.
*
* При подсчёте выражения для curOst используется
* лемма 1, что позволяет не использовать
* громоздких вычислений величины A^n,
* в том случае, если в последовательности остатков
* долго не возникает цикл
*/

}

/* Теперь в curOst находится остаток, с которого начинается цикл.
*/

#ifdef DEBUG
std::cout << «Последовательность остатков: « << std::endl;

for(std::list<int>::const_iterator A = frc.begin(); A != frc.end(); A++) {

std::cout << *A << » «;
}

std::cout << std::endl;

#endif
int curPos = delimoe.length()-1;
for
( ; *(frc.begin()) != curOst; frc.pop_front()) {

/* Обравотка элементов вне цикла
*/

rez += ( delimoe[curPos]-‘0’ )*( *(frc.begin()) ) % div;
curPos;

#ifdef DEBUG
std::cout << «Ациклический элемент « << *(frc.begin()) << » использован и удалён» << std::endl;

sr();
#endif
}
for
(std::list<int>::const_iterator A = frc.begin() ; curPos>=0; —curPos) {

rez += ( delimoe[curPos]-‘0’ )*( *A ) % div;

#ifdef DEBUG
std::cout << «Используется элемент « << *A << std::endl;

sr();
#endif
++A;
if
(A == frc.end())

A = frc.begin();
}

delete
[] A;

/* Освобождение памяти — наше всё
*/

return
rez % div;
}

inline bool BigMod::properOsn(int osn)
{

/*__DOC: Проверка допустимых значений */
return
( osn > 0 );
}

#ifdef DEBUG
inline void BigMod::sr()
{

std::cout << «rez = « << rez << std::endl;
}

#endif

Реклама

Метки: , , , , ,

комментария 2 to “Применение лемм 1 и 2”

  1. nix0 Says:

    Прошу прощения, в программе была некоторая ошибка с выделением памяти.

  2. nix0 Says:

    LOOP
    Developer: Ага, вот эти баги! Хотите, я вам покажу особую, отладочную магию?
    Bugs: Не-не-не, вротнамноги, остановись, демон, ааа, он меня скукожил, аааргх…
    Developer: 0_0
    Critical Bug: Эй, хочешь увидеть немного НАСТОЯЩЕЙ магии?
    Developer: Эээ, ну давай.
    Critical Bug: *SYSTEM CRASH*
    Developer: Аааа, фак мой моск, ты чего творишь, я не хочу этого делать, прекрати, ааа…
    Critical Bug: 0_0
    END LOOP

    (взято с http://ibash.org.ru)

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s


%d такие блоггеры, как: