Среда, 19.06.2019, 05:28

Освіта на базі Гімназії №2 ВМР

Неофіційний сайт школи. Автор - Кренцін Михайло

Меню сайту
Наше опитування
Чи готуєтесь ви до ЗНО?
Всего ответов: 6
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0





Яндекс.Метрика
Форма входу
Пошук
Календар
«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930
Друзі сайту
  • Сайт школи-гімназії №2
  • Центр розвитку школярів в Інтернеті
  • Сайт інтернет олімпіад ФМГ№17
  • Система перевірки знань
  • Програмування та радіотехніка - Мішатронік
  • ВРЦОЯО - ЗНО
  • Лабораторія інформаційно-комунікаційних технологій
  • ДПА
  • Вивчення інформатики
  • Вінницький обласний інститут післядипломної освіти педагогічних працівників
  • Обласний центр технічної творчості учнівської молоді (ОЦТТУМ)
  • Освітній портал
  • НОУ "Интуит"
  • Погода у Вінниці

    Арифметика великих чисел

    Відомо, що операції з числовими значеннями в комп’ютері відбувається з обмеженою кількістю розрядів. Але трапляються випадки, коли приходиться обчислювати числа де кількість знаків становить 20, 100, 1000. Такі числа використовуються в астрономії, мікрофізиці, комбінаториці.

    Для реалізації операцій з довгими числами необхідно розмістити довге число в пам’яті комп’ютера. Розмістимо довге число в цілочисельний масив. В кожну комірку пам’яті помістимо по декілька цифр (для початку 1 цифру) В нульовій комірці пам’яті будемо зберігати кількість цифр довгого числа. Розвернемо масив для зручності уявлення розміщення цифр.

    Запишемо число: 475739541

     

    Масив M:

    Номер елементів масиву

    9

    8

    7

    6

    5

    4

    3

    2

    1

    0

    Елементи масиву

    4

    7

    5

    7

    3

    9

    5

    4

    1

    9

     

     Для реалізації довгої арифметики створимо такі функції:

    -         занесення довгого числа в масив;

    -         виведення довгого числа;

    -         додавання двох довгих чисел;

    -         порівняння довгих чисел;

    -         множення довгого числа на коротке;

    -         множення двох довгих чисел;

    -         ділення довгого числа на коротке;

    -         ділення довгого на довге число.

     

    Довге число зручно вводити у вигляді рядка, при цьому у нульовій комірці розміщується цифра самого високого розряду, а останньою розміщена цифра першого розряду. Розвернемо (реверсуємо) рядок і запишемо кожну цифру в окрему комірку  цілочисельного масиву. Для цього напишемо функцію:

     

    void strtomasiv(char *str,int *T)// Переведення з рядка в масив int

    {int i;

     

          T[0]=strlen(str);  //Знаходження кількості знаків у числі

          strrev(str);      // розвертає (реверсує) символьний масив

          for(i=1;i

           for(i=1;i<=T[0];i++)

    T[i]=str[i-1]-'0';// переведення з символів у цифри

    // і занесення їх у числовий масив

    }

     

    Функція отримує довге число у вигляді символьного масиву *str, і повертає також через параметри масив *T типу int.

    Для прискорення операцій з довгими цифрами у кожну комірку заносять не одну цифру, а декілька. Число типу int (long) у мові С++ може пам’ятати 10 знаків. Враховуючи діапазон данного типу (перша цифра максимального числа не перевищує 2) ми можемо записати у кожну комірку пам’яті массиву по 9 цифр при додаванні  та 4 цифри при множенні. множенні.

     

    void strtomasiv(char *str,int *T)// Переведення з рядка в масив int

    {int i,j,n,p,k;                  // із занесенням по K знаків у кожну комірку

    char temp[10];

          n=strlen(str);

          n-=K;

    for (i=1;i

        for(i=1;n>0;n-=K,i++)

          {strncpy(temp,str+n,K);//копіювання К символів з довгого числа

          p=0;

           for(j=0;j

             p=p*10+temp[j]-'0';  //складання числа

           T[i]=p;

          }

        strncpy(temp,str,n+K);  //формування самого числа самих старших розрядів

          p=0;

           for(j=0;j

             p=p*10+temp[j]-'0';

           T[i]=p;

          T[0]=i;

    }

     

    Для виведення довгих чисел також рекомендується написати окрему функцію.

    Під час виведення масиву довгого числа, де в кожній комірці знаходиться лише по одній цифрі не виникає ніяких проблем, необхідно вивести масив у зворотному порядку.

    void out(int *T)// Виведення масиву

    {

          int i;

          for(i=T[0];i>0;i--)

          {   

          cout<

          }

    }

    Якщо виводите масив, де в кожній комірці знаходиться по декілька цифр можливі проблеми з виведенням ведучиз нулів. Якщо нам потрібно вивести число 12030002, і в кожній комірці знаходтться по 4 цифри, то ми отримуємо масив з двох комірок, в T[1]=2, а в T[2]=1203. Під час виведення, наведеному вище ми отримаємо 12032. Ми втрачаємо три розряди значення яких дорівнюють 0. В такому випадку необхідно застосувати застосувати форматоваий вивід. Для цього застосуємо два флаги форматованого виведення:

     

    void out(int *T)// Виведення масиву

    {

          int i;

          for(i=T[0];i>0;i--)

          {   

          cout<

          cout.width (K); //задається ширина поля виведення К знаків з

              //  вирівнюванням по правому краю

          cout.fill ('0');//заповнення пустих позицый символом '0'.

          }   

    }

    Додавання цілих довгих чисел. Процес додавання довгих чисел – це реалізація додавання чисел в стовпчик. Перше число –масив T1, друге число – масив T2 – результат – T3.

    Наприклад:

    T1  67897

    T2    328

        -----

    T3  68225

     

     

    void add(int *T1,int *T2,int *T3) //додавання довгих чисел T3=T1+T2;

    {

    int n=(T1[0]>T2[0])?T1[0]:T2[0];//знаходиться кількість цифр більшого  числа

          int p=0,i;

          for(i=1;i<=n;i++)

          {

                int temp=T1[i]+T2[i]+p;

    T3[i]=temp%R;     // виділення результуючої групи цифр   

                      p=temp/R; // виділення цифри, що виходить за

    // розрядність групи

          }

          if(p>0) {n++; T3[n]=p; }

        T3[0]=n;

    }

     

    Порівняння довгих чисел. 

    Функція порівняння довгих чисел повертає «0» – коли числа рівні, «1»- коли перше число більше за друге і «-1» коли друге число більше першого. Під час реалізації спочатку порівнюється кількість цифр. Якщо кількість цифр різна, то у більшого числа більше кількість цифр. Якщо ж кількість цифр  однакова, то порівнюють всі цифри по порядку, починаючи з старшого розряду. Даний алгоритм буде працювати правильно і у випадку коли в одній комірці пам’яті масиву будемо зберігати декілька цифр.

     

    int compare(int *T1,int  *T2)//Порівняння довгих чисел 0-рівні,

    // 1 - T1 > T1, -1 - T1

    {int i;

          if(T1[0]>T2[0]) return 1; //якщо в І числа кількість цифр > ніж в ІІ

          else

                if(T1[0]< ніж в ІІ

     

                else

                {for(i=1;i

                    if(T1[0]>T2[0]) return 1;

                      else

                            if(T1[0]

     

          return 0;

                }

    }

     

    Множення довгого числа на коротке.

     

     

    void mult(int *T1,int k)// Множення довгого числа на коротке T1=T1*k

    {

          int i,p=0;

          for(i=1;i

          {

                int temp=T1[i]*k+p;

                T1[i]=temp%R;

                p=temp/R;

          }

          while(p>0)

          {

                T1[0]++;

                T1[T1[0]]=p%R;

                p/=R;

          }

    }

     

    Множення двох довгих чисел

     

    void multDD(int *T1,int *T2,int *T3)// Множення довгого числа на довге T3=T1*T2

    {

          int i,j,p=0;

          for(i=1;i<=T2[0];i++)

          {

     

                for(j=1;j<=T1[0];j++)

                {

                int temp=T2[i]*T1[j]+p+T3[j+i-1];

                T3[i+j-1]=temp%R;

                p=temp/R;

                }

           T3[i+j-1]=p;p=0;

          }

          int n=T2[0]+T1[0]-1;

     

          while(p>0)

          {

                T3[n]=p%R;

                p/=R;

                n++;

          }

          if(T3[n+1]>0) T3[0]=n+1; else T3[0]=n;

    }

     

    Єдина Країна! Единая Страна!