Новичок
Профиль
Группа: Участник
Сообщений: 32
Регистрация: 17.4.2008
Репутация: нет
Всего: нет
|
Не получается правильно перевести код с С++ на C# Вот есть деление длинного числа на длинное на С++ | Код |
// Q = A/B, R=A%B
void Div(const BigInt &A, BigInt &B, BigInt &Q, BigInt &R) {
// Вырожденный случай 1. Делитель больше делимого.
if ( A.Size < B.Size ) {
Q.zero();
R=A;
return;
}
// Вырожденный случай 2. Делитель – число базового типа.
if ( B.Size == 1) {
SDiv ( A, B.Coef[0], Q, R.Coef[0]);
R.Size = 1;
return;
}
// Создать временный массив U, равный A
// Максимальный размер U на цифру больше A, с учетом
// возможного удлинения A при нормализации
BigInt U(A.Size+1); U = A; U.Coef[A.Size]=0;
// Указатели для быстрого доступа
short *b=B.Coef, *u=U.Coef, *q=Q.Coef;
long n=B.Size, m=U.Size-B.Size;
long uJ, vJ, i;
long temp1, temp2, temp;
short scale; // коэффициент нормализации
short qGuess, r; // догадка для частного и соответствующий остаток
short borrow, carry; // переносы
// Нормализация
scale = BASE / ( b[n-1] + 1 );
if (scale > 1) {
SMul (U, scale, U);
SMul (B, scale, B);
}
// Главный цикл шагов деления. Каждая итерация дает очередную цифру частного.
// vJ - текущий сдвиг B относительно U, используемый при вычитании,
// по совместительству - индекс очередной цифры частного.
// uJ – индекс текущей цифры U
for (vJ = m, uJ=n+vJ; vJ>=0; --vJ, --uJ) {
qGuess = (u[uJ]*BASE + u[uJ-1]) / b[n-1];
r = (u[uJ]*BASE + u[uJ-1]) % b[n-1];
// Пока не будут выполнены условия (2) уменьшать частное.
while ( r < BASE) {
temp2 = b[n-2]*qGuess;
temp1 = r*BASE + u[uJ-2];
if ( (temp2 > temp1) || (qGuess==BASE) ) {
// условия не выполнены, уменьшить qGuess
// и досчитать новый остаток
--qGuess;
r += b[n-1];
} else break;
}
// Теперь qGuess - правильное частное или на единицу больше q
// Вычесть делитель B, умноженный на qGuess из делимого U,
// начиная с позиции vJ+i
carry = 0; borrow = 0;
short *uShift = u + vJ;
// цикл по цифрам B
for (i=0; i<n;i++) {
// получить в temp цифру произведения B*qGuess
temp1 = b[i]*qGuess + carry;
carry = temp1 / BASE;
temp1 -= carry*BASE;
// Сразу же вычесть из U
temp2 = uShift[i] - temp1 + borrow;
if (temp2 < 0) {
uShift[i] = temp2 + BASE;
borrow = -1;
} else {
uShift[i] = temp2;
borrow = 0;
}
}
// возможно, умноженое на qGuess число B удлинилось.
// Если это так, то после умножения остался
// неиспользованный перенос carry. Вычесть и его тоже.
temp2 = uShift[i] - carry + borrow;
if (temp2 < 0) {
uShift[i] = temp2 + BASE;
borrow = -1;
} else {
uShift[i] = temp2;
borrow = 0;
}
// Прошло ли вычитание нормально ?
if (borrow == 0) { // Да, частное угадано правильно
q[vJ] = qGuess;
} else { // Нет, последний перенос при вычитании borrow = -1,
// значит, qGuess на единицу больше истинного частного
q[vJ] = qGuess-1;
// добавить одно, вычтенное сверх необходимого B к U
carry = 0;
for (i=0; i<n; i++) {
temp = uShift[i] + b[i] + carry;
if (temp >= BASE) {
uShift[i] = temp - BASE;
carry = 1;
} else {
uShift[i] = temp;
carry = 0;
}
}
uShift[i] = uShift[i] + carry - BASE;
}
// Обновим размер U, который после вычитания мог уменьшиться
i = U.Size-1;
while ( (i>0) && (u[i]==0) ) i--;
U.Size = i+1;
}
// Деление завершено !
// Размер частного равен m+1, но, возможно, первая цифра - ноль.
while ( (m>0) && (q[m]==0) ) m--;
Q.Size = m+1;
// Если происходило домножение на нормализующий множитель –
// разделить на него. То, что осталось от U – остаток.
if (scale > 1) {
short junk; // почему-то остаток junk всегда будет равен нулю…
SDiv ( B, scale, B, junk);
SDiv ( U, scale, R, junk);
} else R=U;
} |
Не получается правильно на C# это сделать... у меня есть класс BigInt | Код |
static int BASE = 10;
public class BigInt
{
public int len; //длинна числа
public int[] digs = new int[1000];
}
|
есть функции SMul (умножение длинного на короткое) и SDiv (деление длинного на короткое) | Код |
static void SMul(BigInt NumberA, int NumberB, BigInt Answer)
{
int i, temp;
int carry = 0;
for (i = 0; i < NumberA.len; i++)
{
temp = NumberA.digs[i] * NumberB + carry;
carry = temp / BASE;
Answer.digs[i] = temp - carry * BASE;
}
if (carry == 1)
{
Answer.digs[i] = carry;
i++;
}
Answer.len = i;
}
|
| Код |
static void SDiv(BigInt NumberA, int NumberB, BigInt Answer, BigInt Rest)
{
int i, temp;
Rest.digs[0] = 0;
Rest.len = 1;
for (i = NumberA.len - 1; i >= 0; i--)
{
temp = Rest.digs[0] * BASE + NumberA.digs[i];
Answer.digs[i] = temp / NumberB;
if ((Answer.digs[i] != 0) && (Answer.len < i))
{
Answer.len = i + 1;
}
Rest.digs[0] = temp - Answer.digs[i] * NumberB;
}
}
|
Помогите с делением длинного на длинное..  3 день парюсь никак не получится!!! |
Перевод кода с С++ на C#, Деление длииных чисел 
Загрузка ...
