Принес мне тут один знакомый задачку:
Определить последнюю цифру не равную 0 при вычислении факториала N!, причем N задается в пределах от 1 до 10000

Кто что думает по этому поводу???

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

И естественно, ни какой рекурсии.

Играясь с калькулятором, можно обнаружить следующее:

5! = 120

10! = 3628800

15! = 1307674368000

20! = 2432902008176640000

25! = 15511210043330985984000000


Думаю, что есть закономерность:

факториал от 5 до 9 - 1 нуль на конце, соответственно вторая позиция справа ненулевая;

от 10 до 14 - 2 нуля;

и т.д.

Интересно, сохраняется ли эта закономерность дальше?

podval
Коню понятно что количество нулей на конце факториала = количеству сомножителей, делящихся на 5 + количеству сомножителей, делящихся на 25 + количеству сомножителей, делящихся на 125... это раз.

А вообще:

Код

Public Function LastDigit(CurrentNumber As Long, Optional CurrentLastDigit As Integer = 1) As Integer Static Value As String Static Char As Integer Value = Str(CurrentLastDigit * CurrentNumber) Do   Char = Val(Right(Value, 1))   Value = Left(Value, Len(Value) - 1) Loop While Char = 0 If CurrentNumber = 1 Then   LastDigit = Char Else   LastDigit = LastDigit(CurrentNumber - 1, Char) End If End Function Debug.Print LastDigit(100)

boevik
так что насчет "никакой рекурсии"...

Это сообщение отредактировал(а) Akina - 3.11.2004, 10:33

Цитата(Akina @ 3.11.2004, 10:04)

podval Коню понятно что количество нулей на конце факториала = количеству сомножителей, делящихся на 5 + количеству сомножителей, делящихся на 25 + количеству сомножителей, делящихся на 125... это раз. А вообще: Код Public Function LastDigit(CurrentNumber As Long, Optional CurrentLastDigit As Integer = 1) As Integer Static Value As String Static Char As Integer Value = Str(CurrentLastDigit * CurrentNumber) Do   Char = Val(Right(Value, 1))   Value = Left(Value, Len(Value) - 1) Loop While Char = 0 If CurrentNumber = 1 Then   LastDigit = Char Else   LastDigit = LastDigit(CurrentNumber - 1, Char) End If End Function Debug.Print LastDigit(100) boevik так что насчет "никакой рекурсии"...

а че это за код? на чем? А можно на паскале?

chaos
Это Visual BASIC. На Пасквиль сам переводи.

Цитата(Akina @ 3.11.2004, 11:11)

chaos Это Visual BASIC. На Пасквиль сам переводи.

ээээ
а я не знаю васик

Akina

Дал бы словесное описание алгоритма, без привязки к языку.

podval

Цитата

Дал бы словесное описание алгоритма, без привязки к языку.

Ну, эт запросто...

Код

Public Function LastDigit(CurrentNumber As Long, Optional CurrentLastDigit As Integer = 1) As Integer

Объявляем функцию, возвращающую значение (нужную нам последнюю цифирь) типа Integer и принимающую 2 параметра - число, для коего нужно сосчитать последнюю цифирь, и текущее значение последней цифири. Этот параметр необязательный, если он не задан, то он получит значение 1. Это для того чтобы не задавать его при начальном вызове, но учитывать при рекурсии.

Код

Static Value As String Static Char As Integer

Объявляем 2 временные переменные. Поскольку они не требуют сохранения при рекурсии, объявляем их статическими - т.е. общими для всех рекурсий. Можно сделать их глобальными - без разницы, просто дольше...

Код

Value = Str(CurrentLastDigit * CurrentNumber)

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

Код

Do  Char = Val(Right(Value, 1))  Value = Left(Value, Len(Value) - 1) Loop While Char = 0

Смотрим какая последняя цифирь (Char), одновременно отрезая ее от строки. Если нуль - повторяем, пока не доберемся до ненулевой цифры.

Код

If CurrentNumber = 1 Then  LastDigit = Char Else  LastDigit = LastDigit(CurrentNumber - 1, Char) End If

Если текущее значение числа не единица - вызываем рекурсивно себя, передавая новое значение последней цифры и уменьшая на 1 текущее число. Если единица - все, мы добрались до результата. Присвоим его переменной, имя которой совпадает с именем функции, для возврата в вызвавшую программу.

Код

End Function

Фунцкция кончилася...

Код

Debug.Print LastDigit(100)

А это - проверка, как функция работает...

Цитата(podval @ 3.11.2004, 12:43)

Akina Дал бы словесное описание алгоритма, без привязки к языку.

действительно!!!
Добавлено @ 13:04

Цитата(Akina @ 3.11.2004, 10:04)

podval Коню понятно что количество нулей на конце факториала = количеству сомножителей, делящихся на 5 + количеству сомножителей, делящихся на 25 + количеству сомножителей, делящихся на 125... это раз. А вообще: Код Public Function LastDigit(CurrentNumber As Long, Optional CurrentLastDigit As Integer = 1) As Integer Static Value As String Static Char As Integer Value = Str(CurrentLastDigit * CurrentNumber) Do   Char = Val(Right(Value, 1))   Value = Left(Value, Len(Value) - 1) Loop While Char = 0 If CurrentNumber = 1 Then   LastDigit = Char Else   LastDigit = LastDigit(CurrentNumber - 1, Char) End If End Function Debug.Print LastDigit(100) boevik так что насчет "никакой рекурсии"...

вот здесь вопрос воник
число у каторого мы ищем эту цифру может быть очень большое(порядка 3Е+35000)
и я вот думаю что типу LONG не по зубам такое число

chaos
Это уже детали реализации, алгоритм тебе пояснили.

Дополнение - при ОЧЕНЬ больших числах вместо

Код

Value = Str(CurrentLastDigit * CurrentNumber)

можно множить на последнюю ненулевую цифру CurrentNumber, отделяя ее тем же макаром, как и от Value. Чтобы не поиметь переполнения при перемножении...

Цитата

вот здесь вопрос воник число у каторого мы ищем эту цифру может быть очень большое(порядка 3Е+35000) и я вот думаю что типу LONG не по зубам такое число

Цитата

Это уже детали реализации, алгоритм тебе пояснили.

не совсем...
если число не поместится в LONG, придется реализовывать арифметику больших чисел
по-моему, суть задачи состоит в том, чтобы обойтись без этого
думаю, нужно отдельно обрабатывать множители, кратные 5 и не запоминать нули
тогда может хватить LONG...

Стоп. Все предыдущие коды отставить - логическая ошибка. Для 25 и более значения будут неверны.

Видимо правильно высказывание maxim1000

Цитата

придется реализовывать арифметику больших чисел

впрочем на algolist.manual.ru вроде исходные тексты есть...

так в том-то и дело, что с использованием арифметики больших чисел задача неинтересна
интереснее как-нибудь извратиться 32-битными числами

maxim1000
арифметику больших чисел не обязательно реализовывать на стрингах - я лет 15 назад кодил на АСМе работу с числами до 128 килоцифр длиной (в BCD) помнится... И работало... в высоких языках это представляется как литой массив бин-данных...

Это сообщение отредактировал(а) Akina - 3.11.2004, 14:22

Цитата

арифметику больших чисел не обязательно реализовывать на стрингах - я лет 15 назад кодил на АСМе работу с числами до 128 килоцифр длиной (в BCD) помнится... И работало... в высоких языках это представляется как литой массив бин-данных...

про арифметику больших чисел на строках я и не думал
все, что я хотел сказать, - интересной задачей является решение без использования больших чисел

Akina, а не загнется ли комп делая рекурсию на 10.000?

boevik
плевать... ну обвалится из-за переполнения стека - как максимум...

Цитата(Akina @ 3.11.2004, 17:18)

boevik плевать... ну обвалится из-за переполнения стека - как максимум...

Тогда можно и рекурсией

тут может подойти что-то вроде этого:

Код

int func(unsigned int n) {  x=1;  for(c=1;c<=n;c++)  {    int qqq=c;    while((x%2==0)&&(qqq%5==0))    {      x/=2;      qqq/=5;    }    while((x%5==0)&&(qqq%2==0))    {      x/=5;      qqq/=2;    }    x*=qqq;    x%=100000;  }  return x%10; }

Добавлено @ 18:17
только на сильно больших значениях я его не проверял
для 10 вроде работает

нули убираются как только обнаруживаются
используются последние 5 ненулевых цифр (пять выбрано для того, чтобы при умножении на число 1..10000 не возникало переполнения)


Это сообщение отредактировал(а) maxim1000 - 3.11.2004, 18:14

Код

Var i,r,x,n: Integer; Begin ReadLn(n); r:=1; for i:=1 to n do Begin x:=i; while x mod 10 = 0 do x:=x div 10; x:=x mod 100; r:=(r*x); while r mod 10 = 0 do r:=r div 10; r:=r mod 100; End; WriteLn(r mod 10); End.

Проверьте, у меня компилера нет

Цитата(Alex101 @ 4.11.2004, 22:48)

Код Var i,r,x,n: Integer; Begin ReadLn(n); r:=1; for i:=1 to n do Begin x:=i; while x mod 10 = 0 do x:=x div 10; x:=x mod 100; r:=(r*x); while r mod 10 = 0 do r:=r div 10; r:=r mod 100; End; WriteLn(r mod 10); End. Проверьте, у меня компилера нет

блин я не могу меня то же нет

Цитата(chaos @ 5.11.2004, 08:11)

Цитата(Alex101 @ 4.11.2004, 22:48) Код Var i,r,x,n: Integer; Begin ReadLn(n); r:=1; for i:=1 to n do Begin x:=i; while x mod 10 = 0 do x:=x div 10; x:=x mod 100; r:=(r*x); while r mod 10 = 0 do r:=r div 10; r:=r mod 100; End; WriteLn(r mod 10); End. Проверьте, у меня компилера нет блин я не могу меня то же нет

вспомнил!! делфей же можно компильнуть!!!

Работает!!!

Проверь на больших числах - 26, 126, 626...

Цитата(Akina @ 5.11.2004, 10:36)

Проверь на больших числах - 26, 126, 626...

для 26, а для остальных хз как проверить

chaos
Это я к тому что для чисел менее 25 достаточно просчитывать последнюю ненулевую цифирь, для чисел 26-50 - уже 2, до 75 - три, до 100 - 4, до 125 - 5, до 150 - уже 7... в общем по n-1 дополнительной хвостовой цифири для каждого множителя, делящегося на 25 (где n - кол-во пятерок средим его простых множителей)...

Я в нашем билдере до 27 могу посчитать.
27! = 10888869450418352160768000000
А так - либо "длинная арифметика" (что не очень сложно), либо Хаскел, там хоть до миллиона считай.

а мой вариант никого не интересует?
27->8
26->4
126->8
626->6

Цитата

а мой вариант никого не интересует?

Проверил, похоже тоже должен работать...

Цитата(Akina @ 9.11.2004, 07:25)

chaos Это я к тому что для чисел менее 25 достаточно просчитывать последнюю ненулевую цифирь, для чисел 26-50 - уже 2, до 75 - три, до 100 - 4, до 125 - 5, до 150 - уже 7... в общем по n-1 дополнительной хвостовой цифири для каждого множителя, делящегося на 25 (где n - кол-во пятерок средим его простых множителей)...

По-моему, надо запоминать только 2 последние ненулевые цифры, остальные просто смысла нет помнить. Ведь в формировании последней цифры участвуют всего две...

Цитата

По-моему, надо запоминать только 2 последние ненулевые цифры, остальные просто смысла нет помнить. Ведь в формировании последней цифры участвуют всего две...

действительно так, но: а вдруг эта цифра станет нулевой?
тогда последней цифрой становится другая, в формировании которой принимали участие другие цифры

maxim1000
Да, ты прав.
И мое решение выдает ошибку при факториале 25... (Сегодня проверил)

chaos:

Цитата

Определить последнюю цифру не равную 0 при вычислении факториала N!, причем N задается в пределах от 1 до 10000

Эту задачу школьники решают!
Факториал числа с некоторого номера заканчивается нулями. Нули беруться только от перемножения двоек на пятерки. Кого больше? Ясно пятерок. Поэтому, подсчитаем кол-во пятерок, входящих в n!(n div 5 + n div 25 + ....).
Теперь начнем считать нашу последнюю цифру, выкидывая все пятерки и такое же кол-во двоек:

Код

var  n, k, s, t, i, j : integer; begin  read(n);  k := n div 5;  s := 0;  while k > 0 do    begin      s := s + k;      k := k div 5    end;  t := 1;  for i := 2 to n do  begin    j := i;    while j mod 5 = 0 do      j := j div 5;    while (s > 0) and (j mod 2 = 0) do      begin        j := j div 2; s := s-1      end;    t := t*(j mod 10) mod 10  end;  write(t); end.

GePo

Цитата

N задается в пределах от 1 до 10000

Догадываешься куда пошел твой алгоритм? туда же куда и наши - в математику длинных чисел. В том виде в каком он приведен...

Однако кое-что интересное тут есть - попробую дома накидать алгоритм, поздно уже...

GePo
Что-то у меня алгоритм не работает...

Akina

Цитата

Догадываешься куда пошел твой алгоритм? туда же куда и наши - в математику длинных чисел. В том виде в каком он приведен...

ЧЕГО????? там все вычисления по модулю десять идут! до хоть n до миллиона!

Alex101
на каких примерах не работает? вообще этот алгоритм точно правильный, не только я это придумывал, но и написано это где-то. Я его сейчас просто вспомнил

GePo
24
Зацикливается...

Alex101
Не понял... у меня все нормально... Где он вообще может зацклиться?

Это сообщение отредактировал(а) GePo - 12.11.2004, 19:18

to GePo

Цитата

И мое решение выдает ошибку при факториале 25... (Сегодня проверил)

Можно спросить на чем ты проверял ?

Это сообщение отредактировал(а) Freeman - 12.11.2004, 22:40

Freeman
цитата не моя

можете проверить ещё одно число
2004! -> 2

Цитата(Kefir @ 12.11.2004, 23:39)

можете проверить ещё одно число 2004! -> 2

совпадает... а какой источник?
2005! -> 6 (это моя программа дает)

maxim1000 источник - линуксовский калькулятор (не помню как называется...)
можешь ещё проверить:
100 000! -> 6
а сколько у тя прога считает для 2004?

Цитата

а сколько у тя прога считает для 2004?

незаметно

Цитата

можешь ещё проверить: 100 000! -> 6

я рассчитывал на числа до 10 000, для больших не работает, т.к. хранятся последние цифр (если отбросить нули), а значит, умножение на число порядка 10^5 даст число порядка 10^10, что в 32 разряда не помещается
так что та программка, которую я привел не подойдет
НО:
если там изменить

Код

x%=100000;

на

Код

x%=10000;

то все заработает
получается 6
считает практически так же незаметно...
кстати, заметил у себя один багик (или бажик ):
надо еще добавить

Код

while(qqq%10==0)  qqq/=10;

а то число, которое умножается на qqq может и не делиться в данный момент на 2 или 5, правда, это влияет только на результаты для конкретных чисел (я нашел на 50000), после нескольких шагов все выравнивается, все 10-ки сокращаются
в общем, обновленная версия:

Код

int func(unsigned int n) {  unsigned int x,c;  x=1;  for(c=1;c<=n;c++)  {    int qqq=c;    if(c==50000)      c=c;    while((x%2==0)&&(qqq%5==0))    {      x/=2;      qqq/=5;    }    while((x%5==0)&&(qqq%2==0))    {      x/=5;      qqq/=2;    }    while(qqq%10==0)      qqq/=10;    x*=qqq;    x%=10000;    //cout<<"   "<<x<<"\n";  }  return x%10; }

Короче, я сам ничего не писал, мне кажется GePo чё-то по делу говорил. Я, правда, в его код не вник и сильно не пытался. На самом деле, если подумать - любое число можно представить как произведение простых множителей. Кстати, он, видать, опечатался. В произвольно взятом числе пятёрок меньше. Дак вот надо сделать так, чтобы путём выбрасывания двоек и пятёрок (по паре) в этом произведении не осталось либо пятёрок либо двоек. Надеюсь, вы поняли о чём я. Если это дело провернуть, то у числа на конце не будет ни одного нуля. Это первое.

Второе. Кто-то выше уже говорил, что на формирование последнего числа влияют только два последних от обоих множителей. Если в цикле от 2 до n у всех чисел убирать справа все нули, а слева обрезать их до двух знаков, то можно будет считать вашу задачу до тех чисел которые лезут в integer, т. е. до двух миллиардов (это в дельфе). Я код постараюсь завтра подкинуть.

Цитата(GePo @ 12.11.2004, 18:36)

chaos: Цитата Определить последнюю цифру не равную 0 при вычислении факториала N!, причем N задается в пределах от 1 до 10000 Эту задачу школьники решают! Факториал числа с некоторого номера заканчивается нулями. Нули беруться только от перемножения двоек на пятерки. Кого больше? Ясно пятерок. Поэтому, подсчитаем кол-во пятерок, входящих в n!(n div 5 + n div 25 + ....). Теперь начнем считать нашу последнюю цифру, выкидывая все пятерки и такое же кол-во двоек: Код var  n, k, s, t, i, j : integer; begin  read(n);  k := n div 5;  s := 0;  while k > 0 do    begin      s := s + k;      k := k div 5    end;  t := 1;  for i := 2 to n do  begin    j := i;    while j mod 5 = 0 do      j := j div 5;    while (s > 0) and (j mod 2 = 0) do      begin        j := j div 2; s := s-1      end;    t := t*(j mod 10) mod 10  end;  write(t); end.

че то не очень верится, что такие задачи считают в школах

Код

procedure TForm1.Button1Click(Sender: TObject); var    i, j, num, arg, q5: integer;    p: integer; begin  p := 1;  arg := SpinEdit1.Value;  q5 := 0;  j := 1;  // посчитаем количество пятёрок в множестве простых множителей  repeat    j := j * 5;    inc(q5, arg div j);  until arg div 5 < j;  for i := 2 to arg do  begin    num := i;    // Удалить все пятёрки    while num mod 5 = 0 do num := num div 5;    // Удаляем не нужные двойки    while (q5 > 0) and (num mod 2 = 0) do    begin      dec(q5);      num := num div 2;    end;    num := num mod 10; // оставляем последнюю цифру    p := p * num;    p := p mod 10; // аналогичная фигня  end; {of for}  SpinEdit2.Value := p mod 10; end;

Вот, по-моему должно работать.

И чё-то мне кажется, что если тут ещё извратнуться то можно будет работать с диапазоном вылезающим до любых пределов. Вся проблема уже будет состоять в шустродействии тачки..... Хотя что-то мне подсказывает, что я могу ошибаться...

А никто не пытался найти закономерность? Там если не считать n = 0 и 1 все результаты функции равны 2, 4, 6 или 8. Я тут покувырялся - нашёл интересное кое-чё, только вот закона не просёк ещё. И есть ли он - вопрос.

Нашёл!!! И прогу надолбил. Забыл, правда, на работу принести. Теперь только в понедельник. Короче, задаётся строка с числом и в спределах сотого порядка на 400-ом целике считает за преемлимое время (1-2 сек). Или чё, уже никому не интересно???

интересна не сколько программа (хотя ее тоже тащи), сколько алгоритм (или та закономерность, о которой шла речь)

Нет закономерности (более-менее очевидной).
Я решение этой задачи начинал как раз с ее поиска - до 50! просмотрел, что-то вроде вырисовывалось, а потом - бац!, - исключение...

chaos

Цитата

че то не очень верится, что такие задачи считают в школах

в школах и не решают, а решают на олимпиадах школьников по программированию. Эта задача как раз оттуда. И решение провереное, поэтому все-таки вникни в код, потому что он сто-процентов работающий. Можете конечно писать техническое решение, но зачем, когда есть математическое

Alex101
Более или менее очевидной нет. Абсолютно с тобой согласен. До 50 смотреть маловато будет.


maxim1000
Алгоритм писать в ломы, но если настаиваешь - напишу. Только потом. Щас не охота вааще. Кстати, он (алгоритм) не так страшен как его программа ))).

Код

type    four: array [0..3] of integer = (2, 4, 8, 6);    tabl: array [0..3, 0..4] of integer =    ((0,0,1,0,2),(0,1,3,3,2),(0,2,1,2,2),(0,3,3,1,2)); … … function TForm1.FuckLastDig3(s: string): integer; var    i, len: integer;    arr: array [0..1000] of integer; // с запасиком    digs: array of byte;    zero: boolean;  function blablabla(a, b: integer): integer;  begin    if a = -1 then result := four[b]    else    result := blablabla(a - 1, (tabl[a mod 4, arr[a]] + b) mod 4);  end;  procedure Div5;  var      i, o: integer;  begin    o := (digs[0] * 2) div 10;    zero := digs[0] = 0;    for i := 1 to len do    begin      zero := zero and (digs[i] = 0);      digs[i - 1] := (digs[i] * 2 + o) mod 10;      o := (digs[i] * 2 + o) div 10;    end;  end; begin  // для x = 0 и 1 функция работает неверно  len := Length(s);  SetLength(digs, len + 1);  for i := 1 to len do digs[len - i] := StrToInt(s[i]);  digs[len] := 0;  i := 0;  zero := false;  while not zero do  begin    arr[i] := digs[0] mod 5;    Div5;    inc(i);  end;  dec(i);  result := blablabla(i, 3); end;

Вот. Пихаете строчку с числом. Вот, собственно, и всё.

Да, обратите внимание, что для 0 и 1 возвратит 6. Это не верно. Просто лень было проверку писать, прога и так не маленькая (для форума).

Не знаю, как получен алгоритм выше, но вполне очевидно что оканчания будут всегда четные, т.к. двоек больше, чем пятерок
любое целое число можно представить как i*10 +j, где i - целое, j - цифра. Отсюда:
(k*10+n)*(p*10+l)=k*p*100+10*(p*n+l*k)+n*l
Трудности определения последней цифры могут возникнуть только тогда, когда n или l равны пяти
C учетом, что окончание факториала всегда четно (даже без учета нулей), можно упростить задачу.
А именно, если первое число факториал, то можно считать, что n - четное и. соответственно, l=5.
Получим (k*10+2*i)*(p*10+5)=k*p*100+10*(p*2*i+5*k)+2*5*k= k*p*100+10*(p*2*i+6*k), где 2*i=n
Отсюда, последняя цифра равна последней цифре от (p*2*i+6*k)=(p*n+6*k)

можно предложить такой простой алгоритм в лоб

Private Sub NF_AfterUpdate()
Dim l, n As Integer
Dim i As Long

n = 1
l = 1
For i = 2 To CInt(NF) 'переменная i используется только раз и то для ускорения цикла
If l = 3 Then 'нужно множить на 4
l = 4
n = n * 4
ElseIf l = 4 Then 'нужно множить на 5
l = 5
n = (n \ 2) Mod 10
ElseIf l = 9 Then 'нужно множить на 10, пропустим сразу и 11
l = 1
i = i + 1
Else
l = l + 1
n = (n * l) Mod 10
End If
Next
n = n Mod 10

Label20.Caption = Str(n Mod 10)
End Sub

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

Слушай, Олег, твоя прога по-моему глючить будет начиная с маленьких n. Где точно, ещё не понял.

Это сообщение отредактировал(а) EKoshelev - 26.11.2004, 08:24

Да! Вот в этом месте

ElseIf l = 4 Then 'нужно множить на 5
l = 5
n = (n \ 2) Mod 10

иногда (когда n = 25, 125, 625...) на 2 нужно делить не один раз, а по более. Поэтому начиная с 25 у тебя глючить начнёт (к вопросу об "основной ошибке"). А если будешь делить больше, то всё равно с 25 будет глюк, а со 125 вообще ноль будет возвращать. Короче, если ты основательно посидишь за этой задачкой, то придёшь к тому же результату, что и я и chaos.

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

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

Ребята, я же написал описание алгоритма.

Цитата

иногда (когда n = 25, 125, 625...) на 2 нужно делить не один раз

Согласно алгоритма умножаются только последние цифры, значит если число делится на 5,25, 125 ..., то оно оканчивается на пять, соответсвенно я множу на 5 и делю на 10 (итого делю на 2)
Дополнительно, чтобы от этой процедуры не потерять значимость, т.к. зависимость при умножении на пять существует от предыдущей цифры числа, я при умножении на 4 не обрезаю число до последней цифры.
Косвенно это подтверждается строкой

Цитата

n = n Mod 10

в конце алгоритма.

Цитата

Согласно алгоритма умножаются только последние цифры, значит если число делится на 5,25, 125 ..., то оно оканчивается на пять, соответсвенно я множу на 5 и делю на 10 (итого делю на 2)

до меня это дошло сегодня по дороге на работу

Цитата

Дополнительно, чтобы от этой процедуры не потерять значимость, т.к. зависимость при умножении на пять существует от предыдущей цифры числа

да вроде бы не зависит
дело в том, что после умножения на 5 в конце должно остаться четная цифра, так что последней цифры достаточно для умножения

Олег, ты хош сказать, что перед пятёркой ты не обрезаешь. Ну допустим, когда у нас будет число кратное пяти то мы будем делить на два не однозначное а двузначное. Только это всё фигня. Когда ты залезешь до n=400000 (например), то тебе придётся делить на 128 и от твоего двузначного останется только нафиг никому не нужный нолик.
Добавлено @ 11:59
Может я совсем тупой?????

Просто когда мы умножаем на каждое пятое число количество нулей в факториале увеличивается как минимум на 1. Когда множим на каждое 25-ое - на 2. На каждое 125 - на 3. И т. д.

Короче, по-моему, алгоритм Олега работать не будет. Проще реализовать, проверить на 400000 и сравнить с результатами других алгоритмов.




maxim1000

Теперь что касается моей проги.
Короче, я решил выяснить закономерность этих самых последних чисел. И напихал их в файл много много, начиная от n=0. Получил примерно следующее:
1126422428886828868244846448468868222428…
Начал разбираться и выяснил, что весь этот файл состоит из четырёх пятёрок:
22428
44846
88682
66264
(кроме первой пятерки, т. к. там две первых единицы).
Потом решил выяснить как располагаются эти пятёрки и сляпал файл с первыми цифрами этих пятёрок, т. е. выдиарл каждое пятое число. Там тоже получились четыре разных последовательности из пяти цифр. Потом выдирал каждое 25-ое, 125 и там тоже было по четыре последовательности из пяти цифр и в каждом случае своя. Когда я выдрал каждое 625-ое там тоже получилась последовательность и она была точь в точь как в самом первом варианте. В 3125-ых как во втором. В общем я наляпал до 5^7 и чисто интуитивно решил, что дальше тоже зациклится (хотя фактически, хрен его знает). Вот на этом принципе прога и написана.

Цитата

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

насколько я понял, не предполагается вообще хранить что-то кроме последней цифры
я тут даже набросал программку

Код

int func2(unsigned int n) {  unsigned int x,c;  x=1;  for(c=1;c<=n;c++)  {    int qqq=c;    while(qqq%5==0)    {      qqq/=5;      x/=2;      if(x%2)        x+=5;    }    x*=(qqq%10);    x%=10;  }  return x; }

умножение на 5 здесь действительно заменено на деление на 2
только при делении на два обычного числа последней цифры недостаточно (например, ***2/2 может быть ***1 или ***6)
но если делить не обычное число, а факториал, в котором просто-таки куча множителей 2, то мы знаем, что последняя цифра четная, поэтому вполне достаточно хранить только одну последнюю цифру...

кстати, мне кажется, что с помощью такого подхода можно доказать ту закономерность, котору ты выявил экспериментально

maxim1000, но ты заметь, закономерность... хитрая, короче. Не просто цикл какой-то.
Добавлено @ 16:44
Кстати, я надеюсь, в целом алгоритм понятен (без деталей)...

хитрая закономерность или нет, зависит от того, как на нее смотреть
то, что используются куски по 5 тоже закономерно
дело в том, что периодичность последней цифры - 10
т.к. x и x+5 совершенно одинаково влияют на результат, то периодичность и получается 5
а куски совсем не странные:
например 22428:
2*1=2
2*2=4
4*3=2 (последняя цифра)
2*4=8
аналогично для остальных кусков (которые просто отличаются начальной цифрой)
когда среди множителей встречается 5, происходит деление, что обеспечивает "сложную" закономерность появления кусков

maxim1000. Нет, ну это-то понятно. Просто ты сказал:

Цитата

кстати, мне кажется, что с помощью такого подхода можно доказать ту закономерность, котору ты выявил экспериментально

А я сказал:

Цитата

хитрая, короче. Не просто цикл какой-то.

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

Кстати, у меня возникла мысль о том, что может быть получится найти не только последнюю цифру, но и предпоследнюю и перед ней..... Как ты думаешь, maxim1000, может такое получиться? Просто законы по которым вываливается последняя, предпоследняя и все за ними могут быть похожи друг на друга и таким образом можно будет сляпать алгоритм нахождения любого факториала за достаточно короткое время. Только проблемка будет - как определить количество разрядов числа у n!. А ещё я подумал, что, возможно, такой алгоритм уже давно придуман и можно особо не пыжиться......

Вот.

Цитата(EKoshelev @ 1.12.2004, 08:35)

Кстати, у меня возникла мысль о том, что может быть получится найти не только последнюю цифру, но и предпоследнюю и перед ней..... Как ты думаешь, maxim1000, может такое получиться?

думаю, можно: все операци делать по остатку от деления не на 10, а на 100
единственная сложность: умножение на 5 (т.е. деление на 2)
но, думаю, и она решаема: при делении на два я использовал то, что последняя цифра должна быть четной, в этом случае, наверное, нужно будет использовать кратность какому-нибудь большему числу...

Цитата

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

сомнительно, хотя... кто его знает...

Цитата

Только проблемка будет - как определить количество разрядов числа у n!.

можно взять десятичный логарифм всех чисел и сложить
точности, может быть недостаточно, но можно округлить в бОльшую сторону...

Цитата(EKoshelev @ 30.11.2004, 11:49)

Олег, ты хош сказать, что перед пятёркой ты не обрезаешь. Ну допустим, когда у нас будет число кратное пяти то мы будем делить на два не однозначное а двузначное. Только это всё фигня. Когда ты залезешь до n=400000 (например), то тебе придётся делить на 128 и от твоего двузначного останется только нафиг никому не нужный нолик.

Повторю еще раз, я ДОКАЗАЛ правильность своего алгоритма в первом сообщении.
Там же однозначно доказано, что при умножении на пять ЕСТЬ зависимость от предыдущей цифры.
Все эти высказавания основываются на формулах, которых я давал.

Итого, в связи с тем, что я работаю с цифрами, то при любом числе , даже при СЕПТИЛИОНЕ , последняя цифра - это число от 0 до 9 и делить мне придется всегда только на 2, даже не на 4, не говоря о 128

Цитата

Там же однозначно доказано, что при умножении на пять ЕСТЬ зависимость от предыдущей цифры.

если делить делить на 2 любое число - несомненно зависит
если рассматривать такое специфическое число, как факториал - нет
используется то, что последняя ненулевая цифра всегда четная - тогда можно обойтись без знания предпоследней...

ovr2000

Цитата

(k*10+2*i)*(p*10+5)=k*p*100+10*(p*2*i+5*k)+2*5*k

Когда я учился в школе у нас за такое двойки ставили (надеюсь ошибку сам найдёшь). Это первое. Второе. Я чё-то не нашёл в твоём великом и могучем алгоритме никакой аналогии с твоим не менее великим доказательством.

Третье:

Цитата

p*n+6*k

(или какую бы ты там мудрую формулу не выдумал). Предположим:
p = 2
n = 2
k = 1
чему будет равно количество десяктов???

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

Догнал??? или нет ещё. Если нет, попробуй вписать на вход своей проги 400000 и посмотри что она выдаст.

Это сообщение отредактировал(а) EKoshelev - 3.12.2004, 15:56

ovr2000, короче я с 400000 погорячился. Вот те факториал 25:

25! = 15511210043330985984000000

А теперь на своей проге посчитай.

Верно , р - то есть вторая цифра множителя влияет на результат
мой алгоритм не верен, додумаю

Извините, но пятерки накапливаются
Алгоритм нужно менять кардинально, т.к. зависимость при умножении на 5 затрагивает не только 2-е но и более высокие порядки числа.
Нужно не перемножать пятерки а складировать, вместе с четными числами

Это сообщение отредактировал(а) ovr2000 - 4.12.2004, 11:44

ovr2000, ну вот, блин, я же говорил - не то.


maxim1000

Цитата

Цитата Только проблемка будет - как определить количество разрядов числа у n!. можно взять десятичный логарифм всех чисел и сложить точности, может быть недостаточно, но можно округлить в бОльшую сторону...

Я вот подумал что получится, если десятку потом возвести в степень, равную сумме этих логарифмов? Интересно, много времени будет жрать эта процедура? Можно ещё будет натуральные логарифмы использовать, чтобы по быстрее было. Я вот только забыл как логарифм в числовой ряд раскладывать, зато помню, что при вычислении экспоненты нужны факториалы.

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