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

Длинная арифметика - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ дана целочисленная матрица размера М*N.найти номер последней из строк,содержащих только четные числа http://www.cyberforum.ru/cpp-beginners/thread82810.html
дана целочисленная матрица размера М*N.найти номер последней из строк,содержащих только четные числа.Если таких строк нет,то вывести 0. #include <math.h> #include <stdio.h> #include <malloc.h> void main() {
C++ Как обьявить String в Visual Studio С++? Подскажите плз как обьявить String в С++ в Visual Studio кучу вариантов перепробовал безрезультатно!!! http://www.cyberforum.ru/cpp-beginners/thread82787.html
C++ Упорядочить столбцы матрицы по не возрастанию значений наименьших элементов столбца
упорядочить столбцы матрицы по не возрастанию значений наименьших элементов столбца! ПОМОГИТЕ!!! Нужно написать на С! Срочно!
C++ Упаковка слов в строке
Ввести массив строк текста с заданным количеством строк и массив символов разделителей. Количество символов разделителей заранее неизвестно. Ввод элементов этого массива заканчивается повторением любого из символов, введённых ранее. Из введённого текста сформировать другой массив строк, в котором задано максимальное количество символов в строке. Слова в этих строках должны быть упакованы...
C++ база лото http://www.cyberforum.ru/cpp-beginners/thread82767.html
товарищи как сделать прогу чтоб забивать туда результаты например лото и чтоб выдавала рандомом самый оптимальный вариант?
C++ Одна ошибка #include<iostream> using namespace std; int max_elem(int **mas, int n); int main(void); { int i, j, temp; mas=new int*; or(i=0; i<n; i++); mas=new int; cout<<"Введите элементы матрицы: "<< endl; подробнее

Показать сообщение отдельно
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
06.01.2010, 14:33     Длинная арифметика
Здесь представление длинных чисел, можно хранить О-о-очень большие числа
(предлагается в качестве упражнения оценить порядок)
Что любопытно - лишней памяти не просят.
Код
// Большие числа
#include <stdio.h>
#include <math.h>
#include <alloc.h>
#include <stdarg.h>

/***** Пакет XXL - работа с большими числами *****/
// Этот пакет есть урезанная и заточенная под большие числа версия
// пакета XTD, созданного в конце восьмидесятых годов.
// В общем-то это штука типа TList в C++
// Числа представлюятся в 2**32-ричной системе счисления

typedef unsigned long LU;
typedef unsigned int uint;

typedef struct { // в этой структуре хранятся большие числа,
                 // При необходимости происходит раздвижка
    LU *ss;    /* Массив LU */
    int ms;    /* Выделено памяти на ss */
    int ns;    /* Заполнено */
    int st;    /* Шаг приращения памяти для ss */
               }  XXL;
// "Цифры" хранятся от младшей. ss[0] - младшая цифра

XXL *newXXL();        /* Создание  */
delXXL(XXL *x);       /* Разрушение  */
nulXXL(XXL *x);       /* Обнуление   */
locXXL (XXL *x);      /* Перераспределение памяти для добавки разряда */
addXXL (XXL *x, LU A);    /* Новый элемент */
/*********************/
XXL *newXXL()           /* Создание (созданное число = 0) */
{ XXL *x;
    x = malloc(sizeof(XXL));
    x->ss = NULL;
    x->ms = x->ns = 0;
    x->st = 20;
    return(x);
}
/*********/
delXXL(XXL *x)          /* Разрушение  */
{
   if (x==NULL) return;
   free(x);
}
/*********/
nulXXL(XXL *x)          /* Обнуление   */
{
   if (x==NULL) return;
   x->ns = 0;
}
/*********/
locXXL (XXL *x)    /* Перераспределение памяти для добавки разряда (если нужно) */
{
   if (x->ss==NULL) {
       x->ms = x->st;
       x->ss = malloc( x->ms * sizeof(LU));
   }
   if (x->ns>=x->ms) {
       x->ms += x->st;
       x->ss = (LU *)realloc(x->ss,x->ms*sizeof(LU));
   }
}
/*********/
addXXL (XXL *x, LU A)    /* Новый элемент */
{
   locXXL(x);
   x->ns++;
   x->ss [x->ns - 1] = A;
}
/********/
// А вот и сами большие числа...
 MultL(XXL *xL, uint n); // xL *= n
 SumL(XXL *xL, XXL *xL2);    // xL += xL2
 CompL(XXL *xL1, XXL *xL2);  // Сравнение
 XXL *Tran2to1000(XXL *X);  // В 1000-ричную системе счисления
 PropisL(XXL *X); // Число прописью
 sklon(int dd);         /* Определение склонения числа */
 uint DivL(XXL *Xres, XXL *XT, uint L); // res = XT % L, Возвращает остаток
 printXXL(char *N, XXL *X);   // Отладочная печать длинного числа
/** --------------------------- */
MultL(XXL *xL, unsigned n)   // xL *= n
{ int j; LU L, Vume, aa, ab, ss, ss2, sa;

   //wrjur("n=%x", n);
   Vume = 0;
   for(j=0; j<xL->ns; j++) {
     L = xL->ss[j];
     aa = (L & 0xFFFF);  // Младшая
     ab = (L >> 16);     // Старшая
     // wrjur("j=%d L=%lx, aa=%lx ab=%lx", j, *L, aa, ab);
     ss = aa * n;
     ss2 = ss + Vume;
     Vume = 0;
     if (ss2 < ss) Vume = 1;
     ss = ab * n;
     sa = ((ss & 0xFFFF) << 16); // В старшую текущей
     ss2 += sa;
     if (ss2 < sa) Vume++;
     Vume += (ss >> 16); // В следующую
     xL->ss[j] = ss2;
   }
   if (Vume > 0) addXXL(xL, Vume);
}
/*****************/
SumL(XXL *xL, XXL *xL2)   // xL += xL2
{ short n1, n2, j; LU Vume, a, b, ss;
    n1 = xL->ns;
    n2 = xL2->ns;
    Vume = 0;
    for(j=0; j<n1; j++) {
      if (j >= n2) b = 0;
      else         b = xL2->ss[j];
      a = xL->ss[j];
      ss = a + b + Vume;
      Vume = 0;
      if (ss < a) Vume = 1;
      //printf("a=%lx b=%lx ss=%lx Vume=%lx\n", a, b, ss, Vume);
      xL->ss[j] = ss;
    }
    while (j < n2) {
      b = xL2->ss[j];
      ss = b + Vume;
      Vume = 0;
      if (ss < b) Vume = 1;
      addXXL(xL, ss);
      j++;
    }
    if (Vume > 0) addXXL(xL, Vume);
}
/*****************/
CompL(XXL *xL1, XXL *xL2)  // Сравнение
{ int j; LU L1, L2;
   if (xL1->ns != xL2->ns) return(xL1->ns - xL2->ns);
   for(j=xL1->ns-1; j>=0; j--) {
     L1 = xL1->ss[j];
     L2 = xL2->ss[j];
     if (L1 > L2) return(1);
     else if (L1 < L2) return(-1);
   }
   return (0);
}
/*********************/
uint DivL(XXL *Xres, XXL *XT, uint n) // res = XT % n, Возвращает остаток
{  LU aa, ab, r, x, L, *kk; int j, i;

  nulXXL(Xres);
  kk = malloc(XT->ns * sizeof(LU));
  for(j=0; j<XT->ns; j++) kk[j] = 0;
  r = 0;
  for(j=XT->ns-1; j>=0; j--) {
    L = XT->ss[j];
    aa = (L & 0xFFFF);  // Младшая
    ab = (L >> 16) + (r<<16);     // Старшая
    x = ab / n;
    r = ab % n;
    kk[j] = (x<<16);
    aa += (r<<16);
    x = aa / n;
    r = aa % n;
    kk[j] += x;
  }
  for(i=XT->ns-1; i>=0; i--) if (kk[i] != 0) break;
  for(j=0; j<=i; j++) addXXL(Xres, kk[j]);
  free(kk);
  return(r);
}
/*********************/
XXL *Tran2to1000(XXL *X)  // В 1000-ричной системе счисления
{  XXL *Itog, *Xres, *XT;  LU R; int j;
  Itog = newXXL();
  Xres = newXXL();
  XT = newXXL();
  for(j=0; j<X->ns; j++) addXXL(XT, X->ss[j]);  // XT := X
  //printXXL("X", X);
  while(1) {
    R = DivL(Xres, XT, 1000);
    addXXL(Itog, R);
    if (Xres->ns == 0) break;
    if (Xres->ns == 1 && Xres->ss[0] < 1000) {
      addXXL(Itog, Xres->ss[0]);
      break;
    }
    nulXXL(XT);
    for(j=0; j<Xres->ns; j++) addXXL(XT, Xres->ss[j]);    // XT := Xres
  }
  delXXL(Xres); delXXL(XT);
  return(Itog);
}
/**********************/
main()
{ XXL *Xchess, *Sum, *X1000; int j;
   Xchess = newXXL();
   addXXL(Xchess, 1);
   Sum = newXXL();
   addXXL(Sum, 1);
   for (j=0; j < 50000; j++) {  
     MultL(Xchess, 2);
     SumL(Sum, Xchess);
   }
      // Число в Sum готово. Теперь бы его напечатать ...
   X1000 = Tran2to1000(Sum);  // В 1000-ричной системе счисления
   for(j=X1000->ns-1; j>=0; j--) { // Печатаем триадами
     if (j==X1000->ns-1) printf("%ld ", X1000->ss[j]);
     else                printf("%03ld ", X1000->ss[j]);
   }
   printf("\n");
}
/* ------------------ */
Если интерсно, можно еще и по-русски написать...
 
Текущее время: 18:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru