Тут есть хоть один толковый программист????

← →
Витёк (2005-12-27 23:01) [0]

Как же вычислить этот задолбанный факториал большого числа!!!! Парюсь уже 2 недели и никто ответить не может!! Если есть нормальный программер, подскажи как же все таки вычислить факториал к примеру числа 100!!!

← →
Кефир87 © (2005-12-27 23:11) [1]

У меня на 2ом курсе такое задание было... Но олимпиаде... 8)

← →
Piter © (2005-12-27 23:15) [2]

Витёк (27.12.05 23:01)
Тут есть хоть один толковый программист????

ответный вопрос - а тут есть хоть один нормальный вопрошающий человек? ХОТЬ ОДИН, который прежде чем задать вопрос:
"Ая-яй-яй-люди-добрые-сами-мы-не-местные-дайте-пожалуйста-код-сделай-мне-готовое-все-очень-вас-прошу-ну-что-же-вы-такие- злые-наверное-никто-не-знает-а-понтуетесь-только"

Сначала САМ подумает хоть немного? Поищет в гугле и других поисковых машинах? В общем, приложит хоть чуть-чуть энергии для решения СВОЕГО вопроса?

← →
DiamondShark © (2005-12-27 23:19) [3]

Не парься.
Попей пивка.

← →
Кручен-Верчен © (2005-12-27 23:19) [4]

Длинная арифметика. Умножай столбиком, как в 1-ом классе. Заноси каждую цифру в отдельный элемент массива.

← →
Кручен-Верчен © (2005-12-27 23:21) [5]

Удалено модератором

← →
Johnmen © (2005-12-27 23:21) [6]

>Piter © (27.12.05 23:15) [2]

Таких вопрошающих здесь во второй половине декабря и во второй половине мая практически не бывает!
:)

← →
Johnmen © (2005-12-27 23:23) [7]

>Витёк (27.12.05 23:01)
>Тут есть хоть один толковый программист????

Кстати, такое дешёвое "на слабо" здесь уже давно не проходит.

← →
Джо © (2005-12-27 23:26) [8]

Да нету толковых, нету, не нужно кричать. Все толковые уже давно написали "факториал большого числа", получили свою нобелевку и отправились жить на Багамы :)

← →
LordOfRock © (2005-12-27 23:50) [9]

Вроде отвечали уже тогда. Строки столбиком умножай. Если ты сам хоть немного "толковый программист", то сможешь сделать это.

← →
Piter © (2005-12-28 00:07) [10]

Johnmen © (27.12.05 23:23) [7]
>Тут есть хоть один толковый программист????

Кстати, такое дешёвое "на слабо" здесь уже давно не проходит

Кстати, да :)))
Тоже хотел об этом напиисать - тут есть люди - ТА-А-А-АКОЕ придумывают, чтобы оправдать себя.
Понятно, что ленивые, да хоть с фантазией. А тут стандартное - упрекание, что сидят НЕдопрограммисты, уже не цепляет :)

← →
The_scorpion © (2005-12-28 00:49) [11]

> факториал к примеру числа 100!!!

Вот так: i:=1*2*3*4*5*6*7*8*9*10*11*12...{надеюсь закономерность ясна:)))}...91*92*93*94*95*96*97*98*99*100;
Чуть не забыл: i:double;

> У меня на 2ом курсе такое задание было... Но олимпиаде..
> . 8)

Это что за олимпиада такая? Халява...:)))

← →
McSimm © (2005-12-28 00:58) [12]

> The_scorpion © (28.12.05 00:49) [11]

не все просто, что кажется простым с первого взгляда.
:)

← →
sniknik © (2005-12-28 01:39) [13]

вообще предложил бы "поправить" модуль BCD чисел, не все конечно только пяток основных нужных сдесь операций. увеличить размерность массива с 64 до 255 символов (для начала) авось хватит ;). а не хватит тогда немного более коренную переделку делать (в принципе там любая размерность числа возможна)
а саму функцию оставить "стандартной" (рекурсивной как в книжном примере по рекурсии)

... ну в общем и предложил ;о), сам это делать естественно не собираюсь.

← →
Думкин © (2005-12-28 05:45) [14]

Кстати, одна из статей Кванта в конце 80-х так и была про - как посчитать факториал 100. И Бейсиком вполне справлялись и не Бейсиком - тоже.

← →
Карелин Артем © (2005-12-28 06:02) [15]

2 минуты и готово
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272 23758251185210916864000000000000000000000000

← →
Джо © (2005-12-28 06:09) [16]

> [14] Думкин © (28.12.05 05:45)

Да, было что-то такое. То ли для "Микроши", то ли для чего...

← →
Думкин © (2005-12-28 06:22) [17]

> Джо © (28.12.05 06:09) [16]

Не помню. Я бы о Ямахе подумал(у нас Ямахи стояли), а кто-то Роботроны или Электронику или ДВК(так кажется?) вспомнил.. Хотя... тогда для школьников зоопарк большой был - и как правило, на всех Бейсик. При наличии желания этот факториал можно было бы и для МК-61 пробовать. И даже бумагу в клеточку, как и для многих задач не критичных во времени. :)
Я вот с помощью 20-разрядного бухгалтерского калькулятора(гроба потяжелее нынешнего компа) считал знаки Пи более 20 знаков.
Я вот понять не могу, неужели неинтересно такие задачки решать самому? Почему спрашивают? Именно они и дают ощущение кайфа.

← →
Джо © (2005-12-28 06:29) [18]

> [17] Думкин © (28.12.05 06:22)

Сессия-с, горю. Потому и спрашивают. Хотя мне тоже, в общем, непонятно. А особенно претензии спрашивающего. :(
Кстати, на эмкашке что-то я сомневаюсь, что вышло бы. Надо бы эмулятор нарыть, да попробовать, для мозгов зарядка изрядная.

← →
Думкин © (2005-12-28 06:38) [19]

> Джо © (28.12.05 06:29) [18]

МК как помошник только - навскидку. То есть использовать для ускорения ряда ручных операций.

← →
Гарри Поттер © (2005-12-28 06:57) [20]

Витёк (27.12.05 23:01)
Парюсь уже 2 недели и никто ответить не может!!

А может Вы в другом интернете посмотрите?(с)

← →
Ega23 © (2005-12-28 09:21) [21]

PChar рулит

← →
Rouse_ © (2005-12-28 09:27) [22]

Толковых тут куча, только они все ленивые :)
Ты им сделай чегонить и они тебя не забудут :)

← →
TUser © (2005-12-28 09:45) [23]

Кстати, столбиком уиножать длинные числа - не самый оптимальный вариант.

← →
Витёк (2005-12-28 10:50) [24]

А когда можно немного! Все советуют столбиком, а как? привидите пример!! Пожалуйста!
> факториал к примеру числа 100!!!

>Вот так: i:=1*2*3*4*5*6*7*8*9*10*11*12...{надеюсь закономерность >ясна>:)))}...91*92*93*94*95*96*97*98*99*100;
>Чуть не забыл: i:double;
А ты сам проверял как это работает?

← →
Курдль © (2005-12-28 11:09) [25]

Тут есть хоть один толковый программист????

Да ты чё, прикалываешься? Глянь в соседнюю ветку "Программеры! У кого какое образование?" - одно лоховское инженерьё! 8-/

← →
DErad (2005-12-28 11:14) [26]

Да точно, так че сдесь делаете?? Форум для программистов, а не для...

← →
Карелин Артем © (2005-12-28 11:14) [27]

> Витёк (28.12.05 10:50) [24]

> привидите пример!!

Для этого покурить кальян надо. Если ты не можешь понять что тебе в http://delphimaster.net/view/14-1135441129/, то лучше бросай нафик программирование.

← →
DErad (2005-12-28 11:18) [28]

Карелин Артем, да видел я твои коды, благодарен, только вот бы покороче, можно же сделать проще!

← →
vrem (2005-12-28 11:21) [29]

Формула Стирлинга - приближённое вычисление.

← →
The_scorpion © (2005-12-28 11:23) [30]

> McSimm © (28.12.05 00:58) [12]

Я много раз в олимпиадах участвовал, у меня глаз очень наметан...:))) это простая задача решается за 20-30 минут...

> А ты сам проверял как это работает?

Как часы...:)))...i:=1*2*3*4*5*6*7*8*9*10*11*12...{надеюсь закономерность >ясна>:)))}...91*92*93*94*95*96*97*98*99*100;
Это типа прикол был, мне не понравилось как ты задал вопрос.

Сжалюсь я над тобой...:)))
Представляй числа в стрингах, и умножай(складывай) в стрингах(забудь о других типах).Правда вот беда умножать(складывать) стринги нельзя, не предусмотрел Borland такую операцию. Но ты ведь программист. Сам создай алгоритм перемножения(сложения) стрингов.

← →
Kerk © (2005-12-28 11:24) [31]

http://kladovka.net.ru/index.cgi?pid=list&rid=53

← →
The_scorpion © (2005-12-28 11:31) [32]

> DErad (28.12.05 11:18) [28]
> Карелин Артем, да видел я твои коды, благодарен, только
> вот бы покороче, можно же сделать проще!

Согласен с господином DErad: очень много лишних действий.
ИМХО: Нужно создать константные матрицы таблицы умножения(как в школе:))) ) и таблицы сложения. И все стане проще...

← →
Думкин © (2005-12-28 11:31) [33]

> The_scorpion © (28.12.05 11:23) [30]

Можно развернуть тезис о других типах? Почему их надо забыть?

← →
DErad (2005-12-28 11:38) [34]

The_scorpion, ну напиши как это сделать, немного кода, если тебе не сложно!

← →
The_scorpion © (2005-12-28 11:40) [35]

> Можно развернуть тезис о других типах? Почему их надо забыть?

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

← →
Думкин © (2005-12-28 11:44) [36]

> The_scorpion © (28.12.05 11:40) [35]

Спасибо за развернутый ответ. Вы говорили о ТП или все-таки о Дельфи? Чем вам те же динамические массивы не угодили? Например.

← →
Igorek © (2005-12-28 12:05) [37]

> Думкин © (28.12.05 06:22) [17]
> При наличии желания этот факториал
> можно было бы и для МК-61 пробовать. И даже бумагу в клеточку,
> как и для многих задач не критичных во времени. :)

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

← →
Карелин Артем © (2005-12-28 12:30) [38]

> DErad (28.12.05 11:18) [28]

> The_scorpion © (28.12.05 11:31) [32]

Коды не мои, скачал откуда-то когда понадобилось огромные числа перемножать. Моего там 1-2 строчки.
Ну лениво было самому велик делать.

← →
The_scorpion © (2005-12-28 12:42) [39]

> DErad (28.12.05 11:38) [34]

Лови:

var
Form1: TForm1;
const slog:array ["0".."9","0".."9"] of string[2]=
(("00","01","02","03","04","05","06","07","08","09"),
("01","02","03","04","05","06","07","08","09","10"),
("02","03","04","05","06","07","08","09","10","11"),
("03","04","05","06","07","08","09","10","11","12"),
("04","05","06","07","08","09","10","11","12","13"),
("05","06","07","08","09","10","11","12","13","14"),
("06","07","08","09","10","11","12","13","14","15"),
("07","08","09","10","11","12","13","14","15","16"),
("08","09","10","11","12","13","14","15","16","17"),
("09","10","11","12","13","14","15","16","17","18"));

var str,rez1,rez2,fin,per:string;
dlin,dlin2,i:word;
str1:string="42788349583890452";
str2:string="5341237123789123789539";

implementation
{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

begin
if length(str1)>length(str2) then
begin
dlin:=length(str1);
str:=str2
end
else
begin
dlin:=length(str2);
str:=str1
end;
dlin2:=length(str);
for i:=1 to dlin-dlin2 do
str:="0"+str;
if length(str1)>length(str2) then
str2:=str
else
str1:=str;
for i:=1 to dlin do
fin:=fin+"0";
Per:="00";
for i:=dlin downto 1 do
begin
rez1:=slog[str1[i],str2[i]];
rez2:=slog[rez1[2],per[2]];
per:=slog[rez1[1],rez2[1]];
fin[i ]:=rez2[2];
end;

end;

end.

В fin хранится результат str1 и str2...это алгоритм сложение, у умножения все симметрично, сам подумаешь как переделать мой код, это очень легко.

← →
вразлет © (2005-12-28 12:47) [40]

Витёк

А что платишь?

← →
Витёк (2005-12-28 12:54) [41]

The_scorpion, спасибо!

← →
ferr © (2005-12-28 12:56) [42]

The_scorpion © (28.12.05 11:31) [32]

1 байт под одно число по меньшей мере не выгодно, а ещё и медленно.

использовать строки тоже не гуд, они должны быть константными) © C#

← →
The_scorpion © (2005-12-28 13:05) [43]

1 байт под одно число по меньшей мере не выгодно, а ещё и медленно.
Это выгодно в плане простоты и понимания, по скорости проигрыша нет, в памяти проигрыша тоже нет(256 байт это ОЧЕНЬ мало).
ИМХО: Алгоритм очень хорош

← →
ferr © (2005-12-28 13:09) [44]

The_scorpion © (28.12.05 13:05) [43]
1) log(10,2) / 8 ~= 41 %.
2) быстрее всего процессор работает с машинным словом.

← →
The_scorpion © (2005-12-28 13:09) [45]

> Спасибо за развернутый ответ. Вы говорили о ТП или все-таки
> о Дельфи? Чем вам те же динамические массивы не угодили?
> Например.

Можно и с ними...но со стрингами красивее будет...
ИМХО: Дело вкуса..:)))

← →
The_scorpion © (2005-12-28 13:12) [46]

> 1) log(10,2) / 8 ~= 41 %.

а это ты откуда взял?

> 2) быстрее всего процессор работает с машинным словом.

Ты думаешь много времени уйдет на изменение регистра кода на единицу?
К разрядам быстрее доступ будет

← →
Kerk © (2005-12-28 13:14) [47]

The_scorpion © (28.12.05 13:12) [46]
> 1) log(10,2) / 8 ~= 41 %.

а это ты откуда взял?

Ну как бы неплохо мат.часть почитывать прежде чем на олимпиады ходить.
Хотя, если ограничений по времени нет, то твой код сойдет.

← →
ferr © (2005-12-28 13:15) [48]

> а это ты откуда взял?

1 байтом код-ся 10 различных значений

← →
palva © (2005-12-28 13:24) [49]

Если нужен результат...
use Math::BigInt; $x = Math::BigInt->new(1); for($i=1; $i<=100; $i++) { $x = $x->bmul($i); } print $x; 93326215443944152681699238856266700490715968264381 62146859296389521759999322991560894146397615651828 62536979208272237582511852109168640000000000000000 00000000

← →
The_scorpion © (2005-12-28 13:33) [50]

> Ну как бы неплохо мат.часть почитывать прежде чем на олимпиады
> ходить.
> Хотя, если ограничений по времени нет, то твой код сойдет.
>

Так почитываю, иногда...:)))не понимаю откуда вы взяли это число 10,2...
Еще раз повторюсь, проигрыша по времени не будет. Советую почитывать ассемблер...:)))

> 1 байтом код-ся 10 различных значений

Это плохо?

← →
ferr © (2005-12-28 13:36) [51]

> не понимаю откуда вы взяли это число 10,2...

забавно. ln(10)/ln(2).

> Это плохо?

это 41%

← →
Kerk © (2005-12-28 13:38) [52]

The_scorpion © (28.12.05 13:33) [50]
Еще раз повторюсь, проигрыша по времени не будет.

Будет.

← →
Думкин © (2005-12-28 13:39) [53]

> The_scorpion © (28.12.05 13:33) [50]

2 isn"t fractional part but it"s a base of log.

← →
The_scorpion © (2005-12-28 13:39) [54]

> Kerk © (28.12.05 13:14) [47]

Предлагаю вам написать этот алгоритм своим способом и мы сравним их по трем параметром:1) читабельность кода 2) скорость работы 3) затрачиваемые ресурсы.
ИМХО: не люблю оторванных от реальности теоретиков...:)))

← →
The_scorpion © (2005-12-28 13:40) [55]

> ferr ©

Вам тоже...:)))

← →
Kerk © (2005-12-28 13:41) [56]

The_scorpion © (28.12.05 13:39) [54]
Предлагаю вам написать этот алгоритм своим способом и мы сравним их по трем параметром

Мой код в [31]. Не самый оптимальный, но лучше твоего. Только ты сравнивай на больших числах. 100 разрядов - не серьезно.

> не люблю оторванных от реальности теоретиков...:)))

Это ты мне? LOL

← →
The_scorpion © (2005-12-28 13:44) [57]

Давай на больших... выкладывай, оценим...:)))

← →
Kerk © (2005-12-28 13:47) [58]

123^7890 = [16490 десятичных знаков]
потрачено 265 мс

← →
palva © (2005-12-28 13:56) [59]

123^7890 на перле 25 сек (700 Мгц)

1000 операции сложения в каждой около 200 разрядах на моем Celeron 2,4 ггц получаем : Мой Алгоритм 266 мс , ваш чуть меньше 1 сек, комментарии излишни.
ИМХО тему можно закрыть.

The_scorpion © (28.12.05 14:05) [60]
1000 операции сложения в каждой около 200 разрядах на моем Celeron 2,4 ггц получаем : Мой Алгоритм 266 мс , ваш чуть меньше 1 сек, комментарии излишни.

В [58] и [59] указаны конкретные числа и результаты. У тебя что-то все "около". К чему бы это... :))

Тестовый пример 123^7890
Реализовал бы быстренько умножение через свое сложение, а затем и возведение в степень. Оно ведь не долго.

> Тестовый пример 123^7890
> Реализовал бы быстренько умножение через свое сложение,
> а затем и возведение в степень. Оно ведь не долго.

Реализую вечеро, а то зачет горит...:)))

> В [58] и [59] указаны конкретные числа и результаты. У тебя
> что-то все "около". К чему бы это... :))

К тому, что я умею ПРАВИЛЬНО тестировать...и использовал random, а его сложно предсказать(хотя и возможно).
ИМХО: если ваш алгорит слабее по скорости, то надо это просто признать, это было бы красивее и честнее.

чего стоит хотя бы вот эта строчка

for i:=1 to dlin-dlin2 do str:="0"+str;

ferr © (28.12.05 14:24) [64]

Ну да. :)
На маленьких числах прокатывает.. а когда число разрядов пойдет на тысячи, проявит себя.

вот вам и тест:

program Project2; {$APPTYPE CONSOLE} uses Windows; const Max = 100000; var str1, str2 : string; var i1,i2 : int64; i : integer; begin QueryPerformanceCounter(i1); for i:=1 to Max do str1:="0"+str1; QueryPerformanceCounter(i2); writeln(i2-i1); QueryPerformanceCounter(i1); SetLength(str2, Max); for i:=1 to Max do str2[i]:="0"; QueryPerformanceCounter(i2); writeln(i2-i1); readln; end.

> The_scorpion ©
> Kerk ©

Ваши коды ориентированы на десятичное представление чисел.
Намного быстрее будет работать в двоичной системе.

> чего стоит хотя бы вот эта строчка
>
> for i:=1 to dlin-dlin2 do
> str:="0"+str;

Что вам не нравится?

> Sha © (28.12.05 15:56) [67]

А кто спорит?
Только перевод из десятичные в двоичную займет еще минут 20-30, на олимпиадах это смертельное время.

> Что вам не нравится?

учите матчасть. серьёзно. я даже код привёл, осталось запустить.

> The_scorpion © (28.12.05 19:10) [69]
> перевод из десятичные в двоичную займет еще минут 20-30,
> на олимпиадах это смертельное время

А где написано, что ответ должен быть в десятичной системе?
Для больших чисел это обычно не требуется :)

Вот тебе "олимпиадный" вариант:

function MulString(const t, s: string): string; var i, j, j1, j2, lent, lens, len, sum: integer; begin; lent:=Length(t); lens:=Length(s); len:=lent+lens; SetLength(Result,len); sum:=0; for i:=1 to len do begin; j1:=i+1-lens; if j1<=0 then j1:=1; j2:=i; if j2>lent then j2:=lent; for j:=j1 to j2 do sum:=sum+(ord(t[j])-ord("0"))*(ord(s[i+1-j])-ord("0")); Result[i]:=chr(sum mod 10 + ord("0")); sum:=sum div 10; end; while (len>1) and (Result[len]="0") do dec(len); SetLength(Result,len); end; procedure DecString(var s: string); var i: integer; begin; for i:=1 to Length(s) do begin; if s[i]>"0" then begin; if (s[i]="1") and (i>1) and (i=Length(s)) then SetLength(s,i-1) else dec(s[i]); break; end; s[i]:="9"; end; end; function Factorial(n: cardinal): string; var s: string; begin; s:=ReverseString(IntToStr(n)); Result:="1"; while (s[1]<>"0") or (Length(s)>1) do begin; Result:=MulString(Result,s); DecString(s); end; Result:=ReverseString(Result); end;

> учите матчасть. серьёзно. я даже код привёл, осталось запустить.

Хорошо:
dlin:=dlin-dlin2;
for i:=1 to dlin do
теперь все ok

> А где написано, что ответ должен быть в десятичной системе?
>
> Для больших чисел это обычно не требуется :)

А кому нужны двоичные числа? Их только программисты и понимают...

> The_scorpion © (28.12.05 20:22) [72]
> А кому нужны двоичные числа? Их только программисты и понимают...

Есть еще кое-кто. Вернее, кое-что. Вот ему они и нужны в первую очередь.

Для справки. Число 100! записывается при помощи 159 десятичных знаков.
Не уверен, что ты его сможешь прочесть :)
А уж понять...

> Для справки. Число 100! записывается при помощи 159 десятичных
> знаков.
> Не уверен, что ты его сможешь прочесть :)
> А уж понять...

... поэтому выводы о правильности работы конкурсной программы будут составляться случайным образом :-))

> [49] palva © (28.12.05 13:24)
> Если нужен результат...
>
> use Math::BigInt;
> $x = Math::BigInt->new(1);
> for($i=1; $i<=100; $i++) {
> $x = $x->bmul($i);
> }
> print $x;

тоже самое на питоне :)
result = 1L for i in range (1L,100L): result = result*i; print result

на php
$s = "1";
for ($i=1;$i<=10000;$i++)
$s=bcmul($s, $i);
echo "(".strlen($s).") ".$s;

10000! составляет 35660 знаков :)

> Не уверен, что ты его сможешь прочесть :)
> А уж понять...

Мои возможности в понимание всего непонятного очень высоки...:)))

> Kerk © (29.12.05 00:09) [74]
> The_scorpion © (28.12.05 20:22) [72]
> теперь все ok
>
> Нет

БУ..:))))))))))))))))

> Вот тебе "олимпиадный" вариант:

На олимпиадах понятие о процедурном и модульном программирование практически отсутствует...

Все ясно. Очередной пионер. А начинал неплохо.

Attitude is not substitute for competence.

По сабжу. Есть один.
Но он сейчас клавиатуру ищет чтобы с большим комфортом под своей осью клиента для форума на своем вап сайте дописать. Обратись к нему.

> На олимпиадах понятие о процедурном и модульном программирование
> практически отсутствует...

Думаешь? Лет 8 назад был куратором на олимпиаде по информатике. Кто-то классы писал, кто-то Asm требовал.
Но кайф не в этом. А в том что на чистой математике прокололось 90% олимпидуемых.

Тут есть хоть один толковый программист???? Найти похожие ветки