Калькулятор - алгоритм?

Post by **Win32nipuh** » 12 Dec 2003 11:16

Коллеги, где найти алгоритм для написания калькулятора, который умеет выполнять +,-, *, / для очень больших чисел, которые видимо придется представлять как строки и с ними оперировать?

Boriskin · Post by **Boriskin** » 12 Dec 2003 15:40

Реализуйте свой собственный класс чисел произвольной точности и пользуйте любой калькулятор, например из книги Страуструпа.

Post by **Win32nipuh** » 12 Dec 2003 17:21

Boriskin wrote:Реализуйте свой собственный класс чисел произвольной точности и пользуйте любой калькулятор, например из книги Страуструпа.

Нужно реализовать операции над строками, в которых представлены большие числа, поэтому я думаю Страуструп не подходит.
Т.е., первое, что на ум приходит - это к примеру сложение реализовывать по алгоритму сложения чисел в столбец.

geek7 · Post by **geek7** » 12 Dec 2003 17:45

Win32nipuh wrote:Т.е., первое, что на ум приходит - это к примеру сложение реализовывать по алгоритму сложения чисел в столбец.

Мне кажется правильное решение, только конечно не по одной цыферке, а по слову (если конечно скорость имеет значение).
А вообще не только алгоритмы, но и библиотеки наверняка имеютя
уж на фортране точно

Zombie416 · Post by **Zombie416** » 12 Dec 2003 17:48

Если числа целые и на C++, стяните любую криптографическую библиотеку - Crypto++ например. Там есть классы для работы с длинными целыми.

Или вот это попробуйте - http://www.swox.com/gmp/ .

Самому писать - дело неблагодарное, особенно если скорость работы имеет хоть какое-то значения.

GShapiev · Post by **GShapiev** » 12 Dec 2003 18:05

Вот что у меня получилось за 5 минут с Экселем
Сложение. Жирным выделен конечный результат.
Дальше можно улучшать как захочется

IPoloz · Post by **IPoloz** » 12 Dec 2003 18:27

Подойдет?
http://www.informatik.tu-darmstadt.de/TI/LiDIA/

GShapiev · Post by **GShapiev** » 12 Dec 2003 19:04

Zombie416 · Post by **Zombie416** » 12 Dec 2003 19:11

IPoloz wrote:Подойдет?
http://www.informatik.tu-darmstadt.de/TI/LiDIA/

Она небесплатная. "LiDIA, including the point counting package, is free for non-commercial pruposes. A license fee is not required for non-commercial applications."

Boriskin · Post by **Boriskin** » 12 Dec 2003 19:31

Win32nipuh wrote:
Boriskin wrote:Реализуйте свой собственный класс чисел произвольной точности и пользуйте любой калькулятор, например из книги Страуструпа.

Нужно реализовать операции над строками, в которых представлены большие числа

Либо я не врубился в вашу задачу, либо...

реализуете нечто вроде class Number, в котором опять таки реализуете все возможные операции как то +, -, *, /. А внутри как хотите - так и храните - хоть в строках, хоть в массивах. И - вместо встроенных типов подсовываете в страуструповский калькулятор...
Попутно неплохой трениг по плюсам. :mrgreen:

Или я чего то пропустил?

Post by **Win32nipuh** » 13 Dec 2003 14:31

Boriskin wrote:
Win32nipuh wrote:
Boriskin wrote:Реализуйте свой собственный класс чисел произвольной точности и пользуйте любой калькулятор, например из книги Страуструпа.

Нужно реализовать операции над строками, в которых представлены большие числа

Либо я не врубился в вашу задачу, либо...
реализуете нечто вроде class Number, в котором опять таки реализуете все возможные операции как то +, -, *, /. А внутри как хотите - так и храните - хоть в строках, хоть в массивах. И - вместо встроенных типов подсовываете в страуструповский калькулятор...
Попутно неплохой трениг по плюсам.

Или я чего то пропустил?

Все ок, вопрос в алгоритмах реализации опреаций, хранение действительно не проблема, но скорее всего в строках. Да, пирдется видимо реализовывать пересчет в системы исчисления с большим основанием.
Идея Гриши хорошая, как частный случай.

A. Fig Lee · Post by **A. Fig Lee** » 13 Dec 2003 14:57

Еще Керниган и Ритчие в своей книжке описали классный и простой алгоритм с полиш нотацией. Без всяких деревьев и прочих комплексностей.

Post by **Win32nipuh** » 13 Dec 2003 18:55

A. Fig Lee wrote:Еще Керниган и Ритчие в своей книжке описали классный и простой алгоритм с полиш нотацией. Без всяких деревьев и прочих комплексностей.

Наверное я неправильно объяснил суть:
пример: юзер вводит две строки длиной 1000 символов (цифр), вторая длиной 500 символов (цифр) и между ними знак * (а возможны еще +, -, /)
И тот же юзер хочет получить на выходе строку-результат умножения вот таких чисел.
Уважаемый A. Fig Lee, чем тут может помочь Керниган или Ричи? :-)

, Увы...

A. Fig Lee · Post by **A. Fig Lee** » 13 Dec 2003 19:15

Win32nipuh wrote:
A. Fig Lee wrote:Еще Керниган и Ритчие в своей книжке описали классный и простой алгоритм с полиш нотацией. Без всяких деревьев и прочих комплексностей.

Наверное я неправильно объяснил суть:
пример: юзер вводит две строки длиной 1000 символов (цифр), вторая длиной 500 символов (цифр) и между ними знак * (а возможны еще +, -, /)
И тот же юзер хочет получить на выходе строку-результат умножения вот таких чисел.
Уважаемый A. Fig Lee, чем тут может помочь Керниган или Ричи? , Увы...

По мотивам Вашего предыдущего выступления с деревьями... :pain1:

Строки надо пушать на стек ясен пень.

Post by **Win32nipuh** » 13 Dec 2003 19:33

A. Fig Lee wrote:По мотивам Вашего предыдущего выступления с деревьями...
Строки надо пушать на стек ясен пень.

Да, извините, это разные задачи...

Кстати, по мотивам рпедыдущего выступления по поводу деревьев: реализовал ДНФ, красотища

, понравилось "лазить по деревьям".

A. Fig Lee · Post by **A. Fig Lee** » 13 Dec 2003 22:46

Win32nipuh wrote:
A. Fig Lee wrote:По мотивам Вашего предыдущего выступления с деревьями...
Строки надо пушать на стек ясен пень.

Да, извините, это разные задачи...

Кстати, по мотивам рпедыдущего выступления по поводу деревьев: реализовал ДНФ, красотища , понравилось "лазить по деревьям".

а чем дерево лучше?
Скорость? Меньше памяти ест? Проще? Мне кажется единственно - оно ближе к пониманию.

vaduz · Post by **vaduz** » 14 Dec 2003 00:05

А чё мучаться-то? Взять BigInteger из Java да декомпильнуть, всего делов-то.

Hamster · Post by **Hamster** » 14 Dec 2003 00:47

Или пойти на топкодер, Invitational 2001 Semifinals C+D, hardest
Правда, небольшая проблема - только одна успешная submission, и та на Яве. У меня было рабочее решение, но оно где-то потерялось. Придется искать в practice room'е.

Isaev · Post by **Isaev** » 14 Dec 2003 01:09

A. Fig Lee wrote:
Win32nipuh wrote:Кстати, по мотивам рпедыдущего выступления по поводу деревьев: реализовал ДНФ, красотища , понравилось "лазить по деревьям".

а чем дерево лучше?
Скорость? Меньше памяти ест? Проще? Мне кажется единственно - оно ближе к пониманию.

Возможности практически безграничны - можно делать практисеки все что угодно. Польская нотация позволяет только вычислять.

IA72 · Post by **IA72** » 14 Dec 2003 19:58

Hamster wrote:Или пойти на топкодер, Invitational 2001 Semifinals C+D, hardest
Правда, небольшая проблема - только одна успешная submission, и та на Яве. У меня было рабочее решение, но оно где-то потерялось. Придется искать в practice room'е.

Я когда-то, года 4 назад, делал как тестовую задачу - сложение и умножение неограниченно больших целых чисел. Скорость там не особенно играла роль, поэтому просто представил числа как строки (то есть почти неограниченно получилось

), и спокойно так их в цикле обрабатывал, зпдпнными кусками.
Работы - на несколько часов.

Post by **Win32nipuh** » 15 Dec 2003 10:04

uuid wrote:
A. Fig Lee wrote:
Win32nipuh wrote:Кстати, по мотивам рпедыдущего выступления по поводу деревьев: реализовал ДНФ, красотища , понравилось "лазить по деревьям".

а чем дерево лучше?
Скорость? Меньше памяти ест? Проще? Мне кажется единственно - оно ближе к пониманию.
Возможности практически безграничны - можно делать практисеки все что угодно. Польская нотация позволяет только вычислять.

Вот, именно так.
Я когда делал эту задачу, искал какие-нибудь готовые лексические анализаторы, так большинство из них сводится к evaluation по ходу пьесы, т.е. сразу же выполняются указанные операции.
А в моей предыдущей задаче нужно было разобрать строку, заданную юзером для поиска в базе в некоем своем "человеческом" синтаксисе, и преобразовать ее к синтаксису полнотекстового поиска SQL Server.
И в этом случае нужно было дерево разбора, по которому нужно было пройти, построить ДНФ, по пути , по поддеревьям применить правило Де Моргана, и при втором проходе построить XML.
Над строкой так не поиздеваешься :-)

Потому uuid - спасибо за отличную идею

Привет

Калькулятор - алгоритм?

Калькулятор - алгоритм?

Re: Калькулятор - алгоритм?

Re: Калькулятор - алгоритм?

Re: Калькулятор - алгоритм?

Re: Калькулятор - алгоритм?

Re: Калькулятор - алгоритм?