Пятница, 29 Ноября 2024, 16:42

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Длинные числа бросают вызов [2^127]
JSentДата: Четверг, 19 Декабря 2013, 21:31 | Сообщение # 1
постоянный участник
Сейчас нет на сайте
Собственно задача на длинную арифметику:
"Пользователь вводит 2 больших числа (числа от -1*2^127 до 1*2^127-1). Написать программу для суммирования таких чисел."

Решение очевидно - записать два числа в два массива, а после складывать столбиком. Но на деле всплывает много неприятных тонкостей, такие как знаки "-" и "," Эти нюансы разветвляют программу до неприличия.

Самый большой стандартный тип данных, double, не вмещает в себя такие большие числа. А на написание собственного не хватает ни знаний, ни времени их получать.

Так что требуется хитрость! help Что можете предложить сту[денту?

[Решено]


Программист — человек, больной тяжёлой формой поражения коры головного мозга — интеллектом, который выражается в маниакально-деструктивном стремлении писать непонятные и бессмысленные наборы символов и словосочетаний.

Сообщение отредактировал JSent - Четверг, 26 Декабря 2013, 20:15
OpenGOOДата: Четверг, 19 Декабря 2013, 23:40 | Сообщение # 2
почти ветеран
Сейчас нет на сайте
гугли Арифметические операции над большими числами

Мои проекты:
- Свободный и открытый клон World Of Goo
- TrueEngine2D (2D игровой фреймворк основанный на FreeBASIC)

[GameMaker: Studio v1.4.9999]
White9Дата: Пятница, 20 Декабря 2013, 00:25 | Сообщение # 3
заслуженный участник
Сейчас нет на сайте
JSent, с массивом, по-моему, хорошая идея ) Можно сделать так - если число отрицательное, то также складывать, но перед каждым элементом массива отрицательного числа ставить "-". А с запятой проще - сделать отдельные массивы для целых частей и отдельные для знака после запятой, то есть всего их будет 4 штуки ) Ну и немного прикинуть на листочке - где, что и по каким правилам нужно добавлять, удачи! )

Сообщение отредактировал White9 - Пятница, 20 Декабря 2013, 00:26
vasua99Дата: Пятница, 20 Декабря 2013, 08:42 | Сообщение # 4
GNU follower
Сейчас нет на сайте
Надеюсь все понятно

Жизнь игра, и мы в ней пешки... А я кушаю пельмешки)

Сообщение отредактировал vasua99 - Пятница, 20 Декабря 2013, 08:50
JSentДата: Пятница, 20 Декабря 2013, 10:12 | Сообщение # 5
постоянный участник
Сейчас нет на сайте
Оно то понятно. Но, как я смотрю идей получше ни у кого нет.

Программист — человек, больной тяжёлой формой поражения коры головного мозга — интеллектом, который выражается в маниакально-деструктивном стремлении писать непонятные и бессмысленные наборы символов и словосочетаний.

Сообщение отредактировал JSent - Пятница, 20 Декабря 2013, 10:13
vasua99Дата: Пятница, 20 Декабря 2013, 11:09 | Сообщение # 6
GNU follower
Сейчас нет на сайте
Можно хранить знак по отдельности и в зависимости от знаков чисел и их размера определять какая операция нужна(a - b = c можно представить как -(-a + b) = c, если a < 0, b > 0 к примеру).

Жизнь игра, и мы в ней пешки... А я кушаю пельмешки)

Сообщение отредактировал vasua99 - Пятница, 20 Декабря 2013, 11:10
JSentДата: Четверг, 26 Декабря 2013, 20:13 | Сообщение # 7
постоянный участник
Сейчас нет на сайте
Собственно задача решена. Выложу, если кому интересно:
Словесное описание алгоритма:

Код
I Основная программа:
1)Введём два числа в два массива и запишем их длины.
2)Если оба числа положительны, то обратимся к алгоритму II.
3)Если оба числа отрицательные, то выведем знак "-" и обратимся к алгоритму II.
4)Если первое число положительно, а второе отрицательно, то преобразуем  
  второе число к положительному виду и обратимся к алгоритму III.
5)Если первое число отрицательно, а второе положительно, то преобразуем
  первое число к положительному виду и обратимся к алгоритму III.
6)Конец.

II Алгоритм сложения:
1)Переведём массивы из символьного типа в целочисленный.
2)Развернём эти массивы, чтобы было удобней складывать.
3)Найдём максимальную длину результата.
4)Сложим массивы столбиком, соблюдая правила арифметики.
5)Убираем лишние нолики перед числом.
6)Выведем результат с конца.
7)Конец.

III Алгоритм сравнения:
//Если одно из чисел отрицательное, то сложение заменится на вычитание.  
//А для вычитания нужно сначала сравнить эти числа.

1)Сравним длины массивов, если один длиннее другого, то это наибольшее число.
2)Если длина одинаковая, то сравним поразрядно.
3)Если числа окажутся равными (по модулю), то результат вычитания 0.
4)Если первое число больше второго, то обратимся к алгоритму IV.
5)Если второе число больше первого, то выведем  "-" и обратимся к алгоритму IV, поменяв числа местами.
6)Конец.

IV Алгоритм вычитания:
1)Переведём массивы из символьного типа в целочисленный.
2)Развернём эти массивы, чтобы было удобней вычитать.
3)Вычтем массивы столбиком, соблюдая правила арифметики. При этом результат сохраняется в 3 массив.
4)Уберём лишние нули перед числом.
5)Выведем результат с конца.
6)Конец.


И сам код:

Код
#include <stdio.h>
#include <conio.h>

//Функция сложения (II)
int sum(char num1[100], char num2[100],
  int max_num1, int max_num2)
{

  int  i, k, temp, size,
   int_num1[100], int_num2[100];

  //Обнуляем два целочисленных массива
  for (i = 0; i <= 100; i++)
  {
   int_num1[i] = 0; int_num2[i] = 0;
  }

  //Перводим их элементы из char в int
  for (i = 0; i <= max_num1; i++)
  {
   int_num1[i] = int(num1[i]) - 48;
  }

  for (i = 0; i <= max_num2; i++)
  {
   int_num2[i] = int(num2[i]) - 48;
  }

  //Разворачиваем оба массива для удобства счёта    
  for (i = 0, k = max_num1; i<k; i++, k--)
  {
   temp = int_num1[i];
   int_num1[i] = int_num1[k];
   int_num1[k] = temp;
  }

  for (i = 0, k = max_num2; i<k; i++, k--)
  {
   temp = int_num2[i];
   int_num2[i] = int_num2[k];
   int_num2[k] = temp;
  }

  //Находим максимальную длину результата    
  if (max_num1 > max_num2)
   size = max_num1 + 1;
  else
   size = max_num2 + 1;

  //Считает столбиком  
  for (i = 0; i <= size; i++)
  {
   int_num2[i] += int_num1[i];
   int_num2[i + 1] += (int_num2[i] / 10);
   int_num2[i] %= 10;
  }

  if (int_num2[size] == 0) size--;
  if (int_num2[size] == 0) size--;

  //Вывод результата
  for (i = size; i >= 0; i--)
   printf("%d", int_num2[i]);
  return 0;
}

//Функция вычитания (IV)
int dif(char num1[100], char num2[100], int size,
  int max_num1, int max_num2)
{
  int i, k, temp, rezult[100], int_num1[100], int_num2[100];

  //Обнуляем три целочисленных массива
  for (i = 0; i <= 100; i++)
  {
   int_num1[i] = 0; int_num2[i] = 0; rezult[i] = 0;
  }

  //Перводим элементы из char в int
  for (i = 0; i <= max_num1; i++)
  {
   int_num1[i] = int(num1[i]) - 48;
  }

  for (i = 0; i <= max_num2; i++)
  {
   int_num2[i] = int(num2[i]) - 48;
  }
  //Разворачиваем оба массива для удобства счёта    
  for (i = 0, k = max_num1; i<k; i++, k--)
  {
   temp = int_num1[i];
   int_num1[i] = int_num1[k];
   int_num1[k] = temp;
  }

  for (i = 0, k = max_num2; i<k; i++, k--)
  {
   temp = int_num2[i];
   int_num2[i] = int_num2[k];
   int_num2[k] = temp;
  }

  //Вычитание столбиком  
  for (i = 0; i <= size; i++)
  {
   if (int_num1[i] >= int_num2[i])
    rezult[i] = int_num1[i] - int_num2[i];
   else
   {
    rezult[i] = int_num1[i] + 10 - int_num2[i];
    int_num1[i + 1]--;
   }
  }

  if (rezult[size] == 0) size--;

  //Вывод
  for (i = size; i >= 0; i--)
   printf("%d", rezult[i]);
  return 0;
}

//Функция сравнения чисел (III)
int minus(char num1[100], char num2[100], int max_num1, int max_num2)
{
  int size, i;
  int k = 3; // если к = 3, значит числа одинаковой длинны
  size = max_num1;

  if (max_num1 > max_num2)
  {
   size = max_num1;
   k = 1; // если к = 1, значит первое число длиннее второго
  }
  else

  if (max_num2 > max_num1)
  {
   size = max_num2;
   k = 2; // если к = 2, значит второе число длиннее первого
  }
  else

   // если числа одинаковой длинны, то необходимо сравнить их  
  for (i = 0; i <= size; i++) // поразрядное сравнение весов чисел
  {
   if (num1[i] > num2[i]) // если разряд первого числа больше
   {
    k = 1;
    break;
   }

   if (num2[i] > num1[i]) // если разряд второго числа больше
   {
    k = 2;
    break;
   }
  }

  if (k == 1) dif(num1, num2, size, max_num1, max_num2);
  if (k == 2) { printf("-"); dif(num2, num1, size, max_num2, max_num1); }
  if (k == 3) printf("%d", 0); //Разность одинаковых - 0

}

//Основная программа (I)
int main()
{
  char num1[100], num2[100];
  int  max_num1 = 0, max_num2 = 0, i = -1;

  //Записываес два огромных числа в два символьных массива
  // и сохраняем максимальный индекс
  do
  {
   i++;
   scanf("%c", &num1[i]);
  }  
        while (num1[i] != 10);

  max_num1 = i - 1;

  i = -1;

   

        do
  {
   i++;
   scanf("%c", &num2[i]);
  }
        while (num2[i] != 10);

  max_num2 = i - 1;

  //Если оба числа положительны, то сложим их функцией sum()
  if (num1[0] != '-' && num2[0] != '-')
   sum(num1, num2, max_num1, max_num2);

  //Если отрицательные, то уберём минусы и сложим функцией sum()
  if (num1[0] == '-' && num2[0] == '-')
  {
   num1[0] = 48; num2[0] = 48;
   printf("-");
   sum(num1, num2, max_num1, max_num2);
  }
  //Если первое положительное, а второе отрицательное,
  // то сложим функцией minus  
  if (num1[0] != '-' && num2[0] == '-')
  {
   num2[0] = 48;
   for (i = 1; i <= max_num2; i++) { num2[i - 1] = num2[i]; }
   num2[i] = 48;
   max_num2--;
   minus(num1, num2, max_num1, max_num2);
  }

  //Если первое отрицательное, а второе положительное,
  // то сложим функцией minus  
  if (num1[0] == '-' && num2[0] != '-')
  {
   num1[0] = 48;
   for (i = 1; i <= max_num1; i++) { num1[i - 1] = num1[i]; }
   num1[i] = 48;
   max_num1--;
   minus(num2, num1, max_num2, max_num1);
  }

  _getch();
  return(0);
}



Программист — человек, больной тяжёлой формой поражения коры головного мозга — интеллектом, который выражается в маниакально-деструктивном стремлении писать непонятные и бессмысленные наборы символов и словосочетаний.
OpenGOOДата: Четверг, 26 Декабря 2013, 20:28 | Сообщение # 8
почти ветеран
Сейчас нет на сайте
У меня даже не компилируется (VC++2010)
||=== bignumbers, Debug ===|
main.c|21|error C2059: syntax error : 'type'|
main.c|26|error C2059: syntax error : 'type'|
main.c|82|error C2059: syntax error : 'type'|
main.c|87|error C2059: syntax error : 'type'|
||=== Build finished: 4 errors, 0 warnings (0 minutes, 1 seconds) ===|


Мои проекты:
- Свободный и открытый клон World Of Goo
- TrueEngine2D (2D игровой фреймворк основанный на FreeBASIC)

[GameMaker: Studio v1.4.9999]
JSentДата: Четверг, 26 Декабря 2013, 20:30 | Сообщение # 9
постоянный участник
Сейчас нет на сайте
OpenGOO, в Dev C++ и VS Express нормально компилируется sad

Программист — человек, больной тяжёлой формой поражения коры головного мозга — интеллектом, который выражается в маниакально-деструктивном стремлении писать непонятные и бессмысленные наборы символов и словосочетаний.
OpenGOOДата: Четверг, 26 Декабря 2013, 20:54 | Сообщение # 10
почти ветеран
Сейчас нет на сайте
просто убрал int из int_num1[i] = int(num1[i]) - 48; и с компилировал. Вот ещё

e:\projects\bignumbers\main.c|163|warning C4716: 'minus' : must return a value

До чего же всё таки Си толерантен к такого рода ошибкам.


Мои проекты:
- Свободный и открытый клон World Of Goo
- TrueEngine2D (2D игровой фреймворк основанный на FreeBASIC)

[GameMaker: Studio v1.4.9999]
JSentДата: Четверг, 26 Декабря 2013, 21:17 | Сообщение # 11
постоянный участник
Сейчас нет на сайте
Цитата OpenGOO ()

e:\projects\bignumbers\main.c|163|warning C4716: 'minus' : must return a value


Это капризы твоего VS. Надо в конце функции int minus() написать return 0;


Программист — человек, больной тяжёлой формой поражения коры головного мозга — интеллектом, который выражается в маниакально-деструктивном стремлении писать непонятные и бессмысленные наборы символов и словосочетаний.
OpenGOOДата: Четверг, 26 Декабря 2013, 22:30 | Сообщение # 12
почти ветеран
Сейчас нет на сайте
Это не капризы компилятора (у меня точно такой же как у тебя), надо только указать тип возвращаемого значения void, раз функция ничего не возвращает.

Мои проекты:
- Свободный и открытый клон World Of Goo
- TrueEngine2D (2D игровой фреймворк основанный на FreeBASIC)

[GameMaker: Studio v1.4.9999]
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг