вторник, 17 августа 2010 г.

Ввод длинных чисел

[Вся длинная арифметика]

Рассмотрим два случая считывания длинных чисел. Первый случай(базовый), при котором osn = 10. Во втором, в качестве osn выберем одну из степеней десятки. Забегая вперед отмечу факт, что эту степень нужно выбирать очень аккуратно, чтобы избежать переполнения при реализации операций. Так например, если цифра длинного числа хранится в int’е и мы реализуем операцию плюс, то максимально возможная степень десятки у osn будет 9. (В умных книжках обычно после подобных фраз пишут: “Почему?”). Если же реализуем операцию умножения длинного на длинное, то максимальный osn = 1e4. С учетом всего вышесказанного давайте ознакомимся с возможной реализацией первого случая:

  1. int osn = 10;
  2. ...
  3. struct BigInt
  4. {
  5.   int digits[max_size];
  6.   int amount;
  7.  
  8.   BigInt(){..}
  9.  
  10.   void input()
  11.   {
  12.     memset(digits,0,sizeof(digits));
  13.     string str;
  14.     cin>>str;
  15.     int pos = 0;
  16.     for (int i=str.size()-1;i>=0;i--)
  17.       digits[pos++] = str[i] - '0';
  18.     amount = str.size();
  19.   }
  20.  
  21.   void output(){...}
  22. };
* This source code was highlighted with Source Code Highlighter.

Во втором случае цифра длинного числа является 4 разрядным числом:

  1. int len = 4;
  2. ....
  3. struct BigInt
  4. {
  5.   ...
  6.   void input()
  7.   {
  8.     string str;
  9.     int pos = 0;
  10.     cin>>str;
  11.     for (int i=str.size()-1;i>=0;i-=len)
  12.     {
  13.       int start = i - len + 1;
  14.       if (start<0) start = 0;
  15.       string dig = str.substr(start,i-start+1);
  16.       digits[pos++] = atoi(dig.c_str());
  17.     }
  18.     amount = pos;
  19.   }
  20.   ...
  21. }
* This source code was highlighted with Source Code Highlighter.

1 комментарий: