"Длинная" арифметика в рекурсии

@Zverit · Регистрация: 07.02.2010

Author24 — интернет-сервис помощи студентам

Как реализовать длинную арифметику в рекурсии типа N! = 1 * 2 * 3 * … * (N-1) * N. Да и вообще, не откажусь от информации в общем о длинной арифметике.

silent_1991 · 30.08.2011, 21:50

Я что-то не понял, сегодня гугл что, массовый бан устроил?
http://lmgtfy.com/?q=%D0%B4%D0... 0%BA%D0%B0
Ну, и чтобы сообщение не было спамом))
http://ru.wikipedia.org/wiki/Длинная_арифметика

@An1ka · 31.08.2011, 01:06

Сообщение от ITZver

Как реализовать длинную арифметику в рекурсии типа N! = 1 * 2 * 3 * … * (N-1) * N.

Очень просто:

C++

 unsigned int fact( unsigned int f)
{
    if ( f <= 1) return 1;
    return f * fact( f - 1);
}

Проверка на меньше либо равно 1, потому что полагают факториал от нуля равен единице.

@grizlik78 · 31.08.2011, 01:08

An1ka, а длинная арифметика где?

@Zverit · 31.08.2011, 01:39 **[ТС]**

Как я понимаю, длинная арифметика заключается в том, что длинные числа, превышающие диапазон типов, хранятся в массивах. Так?

Евгений М. · 31.08.2011, 08:09

Да. Массивы - это один из способов хранения длинных чисел.

@diagon · 31.08.2011, 08:20

Сообщение от grizlik78

An1ka, а длинная арифметика где?

А чем она от короткой отличается?
Просто перегрузить <=,*,-, и все =)

@Zverit · 31.08.2011, 09:32 **[ТС]**

Не по теме:

Сообщение от diagon

Просто перегрузить <=,*,-, и все =)

Блиин...Как сам я сам не догадался?! Спасибо!

silent_1991 · 31.08.2011, 10:43

Сообщение от diagon

А чем она от короткой отличается?

Возвращаемым и передаваемым типом unsigned int

@iama · 31.08.2011, 11:02

Легче реализовать функцию, где длинное число будем передавать по ссылке

@fasked · 31.08.2011, 11:14

Я тут когда-то начинал заниматься этим делом: https://www.cyberforum.ru/cpp-... 53284.html
но в итоге до конца дело так и не довел

Вроде бы есть только сложение, вычитание, умножение на Си. Надо реализовать деление и при желании можно все обернуть в класс.

@iama · 31.08.2011, 12:15

Тут вот очень хорошо реализовано

@Zverit · 31.08.2011, 12:22 **[ТС]**

Не по теме:

iama,
fasked, ага, уже нашел. Но все равно спасибо большое!

Добавлено через 4 минуты
iama, Только там с векторами. Хотелось бы без них. Т.к наверное на олимпиадах не разрешено пользоваться STL.

@iama · 31.08.2011, 12:23

Сообщение от ITZver

наверное на олимпиадах не разрешено пользоваться STL.

Это еще почему?

@Zverit · 31.08.2011, 12:25 **[ТС]**

Сообщение от iama

Это еще почему?

А разве можно? Вообще сомневаюсь, что можно на C++.Там ,вроде как, только на Basic и Pascal (Я о всероссийской олимпиаде по информатике)Исправьте, если не прав, просто сколько раз участвовал, писал на Pascal, а другие как то не предлагали.

@zuq · 31.08.2011, 12:30

Если можно пользоваться С++, то векторами тоже. Стандарт однако

@Zverit · 31.08.2011, 12:31 **[ТС]**

Сообщение от zuq

Если можно пользоваться С++, то векторами тоже. Стандарт однако

Согласен, но там же есть готовые алгоритмы.

@diagon · 31.08.2011, 12:35

Хм... В нашей районной олимпиаде даже на яве писать можно было, не говоря уже про STL =\
Про всероссийскую не знаю, но вряд ли там только на паскале и бейсике писать можно.

@zuq · 31.08.2011, 12:35

Так это же хорошо) Насколько я знаю, STL - можно пользоваться в полной мере.

@iama · 31.08.2011, 12:36

ITZver, дается компилятор, и ты волен совать в него какой угодно код (не взламывающий систему), лишь бы получить правильный результат. Действительно, знание STL - большой бонус на олимпиадах.

@Zverit Уничтожитель печенек 281 / 209 / 49 Регистрация: 07.02.2010 Сообщений: 724
	31.08.2011, 12:22 [ТС]	13
	Не по теме: iama, fasked, ага, уже нашел. Но все равно спасибо большое! Добавлено через 4 минуты iama, Только там с векторами. Хотелось бы без них. Т.к наверное на олимпиадах не разрешено пользоваться STL. 0

@zuq 95 / 95 / 5 Регистрация: 10.04.2011 Сообщений: 256
	31.08.2011, 12:30	16
	Если можно пользоваться С++, то векторами тоже. Стандарт однако 1

@Zverit Уничтожитель печенек 281 / 209 / 49 Регистрация: 07.02.2010 Сообщений: 724
	31.08.2011, 12:31 [ТС]	17
	Сообщение от zuq Если можно пользоваться С++, то векторами тоже. Стандарт однако Согласен, но там же есть готовые алгоритмы. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	31.08.2011, 12:35	18
	Хм... В нашей районной олимпиаде даже на яве писать можно было, не говоря уже про STL =\ Про всероссийскую не знаю, но вряд ли там только на паскале и бейсике писать можно. 1

@Zverit Уничтожитель печенек 281 / 209 / 49 Регистрация: 07.02.2010 Сообщений: 724
		1
	"Длинная" арифметика в рекурсии 30.08.2011, 21:26. Показов 1960. Ответов 23 Метки нет (Все метки) Как реализовать длинную арифметику в рекурсии типа N! = 1 * 2 * 3 * … * (N-1) * N. Да и вообще, не откажусь от информации в общем о длинной арифметике. 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	30.08.2011, 21:50	2
	Я что-то не понял, сегодня гугл что, массовый бан устроил? http://lmgtfy.com/?q=%D0%B4%D0... 0%BA%D0%B0 Ну, и чтобы сообщение не было спамом)) http://ru.wikipedia.org/wiki/Длинная_арифметика 2

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	31.08.2011, 01:08	4
	An1ka, а длинная арифметика где? 2

@Zverit Уничтожитель печенек 281 / 209 / 49 Регистрация: 07.02.2010 Сообщений: 724
	31.08.2011, 01:39 [ТС]	5
	Как я понимаю, длинная арифметика заключается в том, что длинные числа, превышающие диапазон типов, хранятся в массивах. Так? 0

Евгений М. 1080 / 1007 / 106 Регистрация: 28.02.2010 Сообщений: 2,889
	31.08.2011, 08:09	6
	Да. Массивы - это один из способов хранения длинных чисел. 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	31.08.2011, 08:20	7
	Сообщение от grizlik78 An1ka, а длинная арифметика где? А чем она от короткой отличается? Просто перегрузить <=,*,-, и все =) 1

@Zverit
	31.08.2011, 09:32 [ТС] #8
	Не по теме: Сообщение от diagon Просто перегрузить <=,*,-, и все =) Блиин...Как сам я сам не догадался?! Спасибо! 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	31.08.2011, 10:43	9
	Сообщение от diagon А чем она от короткой отличается? Возвращаемым и передаваемым типом unsigned int 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	31.08.2011, 11:02	10
	Легче реализовать функцию, где длинное число будем передавать по ссылке 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	31.08.2011, 11:14	11
	Я тут когда-то начинал заниматься этим делом: https://www.cyberforum.ru/cpp-... 53284.html но в итоге до конца дело так и не довел Вроде бы есть только сложение, вычитание, умножение на Си. Надо реализовать деление и при желании можно все обернуть в класс. 1

	31.08.2011, 12:36

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	31.08.2011, 12:15	12
	Тут вот очень хорошо реализовано 1

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	31.08.2011, 12:23	14
	Сообщение от ITZver наверное на олимпиадах не разрешено пользоваться STL. Это еще почему? 0

@Zverit Уничтожитель печенек 281 / 209 / 49 Регистрация: 07.02.2010 Сообщений: 724
	31.08.2011, 12:25 [ТС]	15
	Сообщение от iama Это еще почему? А разве можно? Вообще сомневаюсь, что можно на C++.Там ,вроде как, только на Basic и Pascal (Я о всероссийской олимпиаде по информатике)Исправьте, если не прав, просто сколько раз участвовал, писал на Pascal, а другие как то не предлагали. 0