Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Факториал


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

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

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

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

Автор: podval 3.11.2004, 08:58
Играясь с калькулятором, можно обнаружить следующее:

5! = 120

10! = 3628800

15! = 1307674368000

20! = 2432902008176640000

25! = 15511210043330985984000000


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

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

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

и т.д.

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

Автор: 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 3.11.2004, 11:09
Цитата(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
так что насчет "никакой рекурсии"...

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

Автор: Akina 3.11.2004, 11:11
chaos
Это Visual BASIC. На Пасквиль сам переводи.

Автор: chaos 3.11.2004, 12:29
Цитата(Akina @ 3.11.2004, 11:11)
chaos
Это Visual BASIC. На Пасквиль сам переводи.

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

Автор: podval 3.11.2004, 12:43
Akina

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

Автор: Akina 3.11.2004, 12:58
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)

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

Автор: chaos 3.11.2004, 12:58
Цитата(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 не по зубам такое число

Автор: podval 3.11.2004, 13:08
chaos
Это уже детали реализации, алгоритм тебе пояснили.

Автор: Akina 3.11.2004, 13:19
Дополнение - при ОЧЕНЬ больших числах вместо
Код

Value = Str(CurrentLastDigit * CurrentNumber)

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

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

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

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

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

Видимо правильно высказывание maxim1000
Цитата
придется реализовывать арифметику больших чисел
впрочем на algolist.manual.ru вроде исходные тексты есть...

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

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

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

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

Автор: boevik 3.11.2004, 17:08
Akina, а не загнется ли комп делая рекурсию на 10.000?

Автор: Akina 3.11.2004, 17:18
boevik
плевать... ну обвалится из-за переполнения стека - как максимум...

Автор: boevik 3.11.2004, 18:13
Цитата(Akina @ 3.11.2004, 17:18)

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

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

Автор: maxim1000 3.11.2004, 18:14
тут может подойти что-то вроде этого:
Код

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 не возникало переполнения)

Автор: 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.

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

Автор: 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.

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

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

Автор: chaos 5.11.2004, 08:35
Цитата(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.

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

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

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

Работает!!!

Автор: Akina 5.11.2004, 10:36
Проверь на больших числах - 26, 126, 626...

Автор: chaos 9.11.2004, 10:04
Цитата(Akina @ 5.11.2004, 10:36)
Проверь на больших числах - 26, 126, 626...

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

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

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

Автор: maxim1000 9.11.2004, 11:29
а мой вариант никого не интересует? smile
27->8
26->4
126->8
626->6

Автор: val 9.11.2004, 12:26
Цитата
а мой вариант никого не интересует?


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

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

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

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

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

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

Автор: 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.

Автор: Akina 12.11.2004, 19:00
GePo
Цитата
N задается в пределах от 1 до 10000

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

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

Автор: Alex101 12.11.2004, 19:01
GePo
Что-то у меня алгоритм не работает...

Автор: GePo 12.11.2004, 19:06
Akina
Цитата

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

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

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

Автор: Alex101 12.11.2004, 19:14
GePo
24
Зацикливается...

Автор: GePo 12.11.2004, 19:15
Alex101
Не понял... у меня все нормально... Где он вообще может зацклиться?

Автор: Freeman 12.11.2004, 22:09
to GePo
Цитата
И мое решение выдает ошибку при факториале 25... (Сегодня проверил)


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

Автор: GePo 13.11.2004, 00:04
Freeman
цитата не моя

Автор: Kefir 13.11.2004, 00:39
можете проверить ещё одно число
2004! -> 2

Автор: maxim1000 13.11.2004, 11:21
Цитата(Kefir @ 12.11.2004, 23:39)
можете проверить ещё одно число
2004! -> 2

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

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

Автор: maxim1000 13.11.2004, 19:30
Цитата
а сколько у тя прога считает для 2004?

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

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

на
Код
x%=10000;

то все заработает
получается 6
считает практически так же незаметно...
кстати, заметил у себя один багик (или бажик smile):
надо еще добавить
Код
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;
}

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

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

Автор: chaos 16.11.2004, 12:53
Цитата(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.

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

Автор: EKoshelev 17.11.2004, 11:25

Код

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;


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

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

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

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

Автор: maxim1000 19.11.2004, 12:03
интересна не сколько программа (хотя ее тоже тащи), сколько алгоритм (или та закономерность, о которой шла речь)

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

Автор: GePo 20.11.2004, 00:04
chaos
Цитата

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

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

Автор: EKoshelev 22.11.2004, 14:17
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. Это не верно. Просто лень было проверку писать, прога и так не маленькая (для форума).

Автор: Гость_Олег 25.11.2004, 19:37
Не знаю, как получен алгоритм выше, но вполне очевидно что оканчания будут всегда четные, т.к. двоек больше, чем пятерок
любое целое число можно представить как 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

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

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

Автор: EKoshelev 26.11.2004, 08:38
Да! Вот в этом месте

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

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

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

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

Автор: Guest 30.11.2004, 11:27
Ребята, я же написал описание алгоритма.
Цитата
иногда (когда n = 25, 125, 625...) на 2 нужно делить не один раз

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

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

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

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

Автор: EKoshelev 30.11.2004, 11:49
Олег, ты хош сказать, что перед пятёркой ты не обрезаешь. Ну допустим, когда у нас будет число кратное пяти то мы будем делить на два не однозначное а двузначное. Только это всё фигня. Когда ты залезешь до 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 и чисто интуитивно решил, что дальше тоже зациклится (хотя фактически, хрен его знает). Вот на этом принципе прога и написана.

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

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

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, то мы знаем, что последняя цифра четная, поэтому вполне достаточно хранить только одну последнюю цифру...

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

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

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

Автор: EKoshelev 1.12.2004, 09:35
maxim1000. Нет, ну это-то понятно. Просто ты сказал:
Цитата

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


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


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

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

Вот.

Автор: maxim1000 1.12.2004, 11:57
Цитата(EKoshelev @ 1.12.2004, 08:35)
Кстати, у меня возникла мысль о том, что может быть получится найти не только последнюю цифру, но и предпоследнюю и перед ней..... Как ты думаешь, maxim1000, может такое получиться?

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

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

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

Автор: ovr2000 3.12.2004, 13:01
Цитата(EKoshelev @ 30.11.2004, 11:49)
Олег, ты хош сказать, что перед пятёркой ты не обрезаешь. Ну допустим, когда у нас будет число кратное пяти то мы будем делить на два не однозначное а двузначное. Только это всё фигня. Когда ты залезешь до n=400000 (например), то тебе придётся делить на 128 и от твоего двузначного останется только нафиг никому не нужный нолик.


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

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

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

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

Автор: EKoshelev 3.12.2004, 15:46
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, 16:23
ovr2000, короче я с 400000 погорячился. Вот те факториал 25:

25! = 15511210043330985984000000

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

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

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

Автор: EKoshelev 6.12.2004, 12:52
ovr2000, ну вот, блин, я же говорил - не то.


maxim1000
Цитата

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


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


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

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

Автор: maxim1000 6.12.2004, 13:00
Цитата
Я вот подумал что получится, если десятку потом возвести в степень, равную сумме этих логарифмов?

в обычных числах не получится (результат туда не поместится)
Цитата
Можно ещё будет натуральные логарифмы использовать, чтобы по быстрее было

это практически никакого ускорения не даст
log x=ln x/ln 10
а операция деления занимает пренебрежимо малое время по сравнению с вычислением логарифма

Автор: EKoshelev 6.12.2004, 15:58
maxim1000
Цитата

это практически никакого ускорения не даст


В том смысле, что считать сумму натуральных логарифмов по всем числам, а потом экспоненту по получившемуся. Может подскажешь, как разложить в ряд натуральный логарифм??? Там можно будет покумекать с многоразрядными делами потом...
Добавлено @ 16:08
А, ну понял.
Ну всё равно подскажи, как логарифм разложить.

Автор: maxim1000 6.12.2004, 16:15
Цитата
В том смысле, что считать сумму натуральных логарифмов по всем числам, а потом экспоненту по получившемуся.

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

ряда не помню
к тому же есть разные ряды (Тейлора, Фурье)
если в Тейлора, то попробуй разложить ln(1+x) с помощью производных
кроме того, можно еще искать логарифм с помощью бисекции (правда, тогда придется реализовывать еще и операцию корня)

Автор: Aslan74 23.12.2004, 20:32
Надо выделить степени 2 и 5, встречающиеся в разложениях i = 2, n
на множители, и посчитать их степени отдельно. Потом, если степень 2 больше,
домножить на 2 в степени (степень 2 - степень 5), иначе 5 в степени (степень 5 - степень 2),
остаток пойдет в замыкающие нули.
Причем все умножения делаются только для последней цифры, без "длинной" арифметики

// отделить степени 2 и 5
// разбить число на C * 2^x2 * 5^x5
void Decompose(int& n, int& x2, int& x5)
{
for (x2 = 0; n%2 == 0; n/= 2, x2++);
for (x5 = 0; n%5 == 0; n/= 5, x5++);
}

// последняя ненулевая цифра n!
int Factorial(int n)
{
int res = 1, n2 = 0, n5 = 0;
for (int i = 2; i <= n; i++)
{
int r= i, x2, x5;
Decompose(r, x2, x5);
// отдельно домножаем степени 2 и 5, отдельно остальное
res= (res * r)%10; // взять последнюю цифру
n2+= x2;
n5+= x5;
}

// домножить на 2 или 5
if (n2 > n5)
for (int i = 0; i < n2-n5; i++)
res= (res * 2)%10; // взять последнюю цифру
else
if (n2 < n5)
for (int i = 0; i < n5-n2; i++)
res= (res * 5)%10; // взять последнюю цифру

return res;
}

P.S. Вычисляя n! для проверки обнаружил неприятный факт - в C Builder нет range checking (проверки переполнения)
Добавлено @ 20:35
Надо выделить степени 2 и 5, встречающиеся в разложениях i = 2, n
на множители, и посчитать их степени отдельно. Потом, если степень 2 больше, домножить на 2 в степени (степень 2 - степень 5), иначе 5 в степени (степень 5 - степень 2), остаток пойдет в замыкающие нули.
Причем все умножения делаются только для последней цифры, без "длинной" арифметики

// отделить степени 2 и 5
// разбить число на C * 2^x2 * 5^x5
void Decompose(int& n, int& x2, int& x5)
{
for (x2 = 0; n%2 == 0; n/= 2, x2++);
for (x5 = 0; n%5 == 0; n/= 5, x5++);
}

// последняя ненулевая цифра n!
int Factorial(int n)
{
int res = 1, n2 = 0, n5 = 0;
for (int i = 2; i <= n; i++)
{
int r= i, x2, x5;
Decompose(r, x2, x5);
// отдельно домножаем степени 2 и 5, отдельно остальное
res= (res * r)%10; // взять последнюю цифру
n2+= x2;
n5+= x5;
}

// домножить на 2 или 5
if (n2 > n5)
for (int i = 0; i < n2-n5; i++)
res= (res * 2)%10; // взять последнюю цифру
else
if (n2 < n5)
for (int i = 0; i < n5-n2; i++)
res= (res * 5)%10; // взять последнюю цифру

return res;
}

P.S. Вычисляя n! для проверки обнаружил неприятный факт - в C Builder нет range checking (проверки переполнения)

Автор: ovr2000 28.12.2004, 12:39
Зачем же так сложно.
Всего, при перемножении n! будет встречено множителей с 5-ками: целая часть(n/5) + челая часть (n/25) и т.д.
Это меньше, чем Сумма от 1 до k(k понятно количество членов получившегося ряда) (n/5^i, i=1бл), а это геометрическая прогрессия, значит сумма(Выше) равна n*((1/5-1/5^(k+1))/(1-1/5) < n/4 (это оченка количества 5 во всем числе n!)
Если мы возьмем только первые степени двойки хотя бы от трех множителей из каждого десятка (а там ведь каждый второй - четный), то это будет n*0.3>n*/4=n*0.25
Значит посчитав 5-ки, можно будет отнять только 2 от четных чисел, не считая все множители
Чтобы зря не множить на 10, сразу отнимем их количество от 5, посчитав ряд (я имею в виду точно, а не приближенно)
В результате получится только три цикла, безо всякого вложения.
Например:
Код

Dim l, n, j As Integer
Dim i, k, t As Long

   t = CLng(NF)
   'Посчитаем количество 5
   k = 0
   While t >= 5
       t = Fix(t / 5)
       k = k + t
   Wend
   'Сразу не учтем целые 10
   t = CLng(NF)
   While t >= 10
       t = Fix(t / 10)
       k = k - t
   Wend
   
   n = 1
   l = 1
   For i = 2 To CLng(NF)
       l = l + 1
       If k = 0 Then
       Select Case l
           Case 5
           Case 10
               i = i + 1
               l = 1
           Case Else
               n = (n * l) Mod 10
           End Select
       Else
           Select Case l
           Case 2
               k = k - 1
           Case 4
               k = k - 1
               i = i + 1
               l = 5
               n = (n * 2) Mod 10
           Case 6
               k = k - 1
               n = (n * 3) Mod 10
           Case 10
               i = i + 1
               l = 1
           Case Else
               n = (n * l) Mod 10
           End Select
       End If
   Next
   n = n Mod 10
   Label3.Caption = str(n)

Добавлено @ 12:42
Заметьте, все вычисления идут с типом integer, кроме самого числа, которое может быть и очень большим
Добавлено @ 12:44
Да, кстати, третий раз делить на 2 (case 6) можно ненадо, т.к. мы уже отняли десятки

Автор: EKoshelev 28.12.2004, 14:20
maxim1000, а по моему дак всё будет не только рациональным, но ещё и целым (ну или типа 123.999999934345793487), я на маленьких числах пробовал.

Aslan74 и ovr2000, я чё-то нить вашего разговора не поймал...

Автор: ovr2000 28.12.2004, 17:31
Да суть в порядке чисел, в алгоритмах не используются числа больше сотни, за исключением самого числа N
Именно это я хотел сказать, т.к. все алгоритмы, кроме последних двух , при определенных числах N уходили в переполнение

Автор: GePo 29.12.2004, 17:16
да когда ж вы читать научитесь. Я уже давно написал решение, которое не переполняется, в нем есть все "гениальные идеи", которые потом всем пришли, и вообще то с математически доказанной верностью.
Похоже кому-то влом смотреть чье-то решение, кроме своего любимого... smile

Автор: EagleThePredator 24.11.2005, 11:29
GePo
smile Спасибо за алгоритм! Мне очень помог.

Автор: sadovoya 15.10.2006, 22:00
Может, это не совсем то, что нужно, но вдруг кому-нибудь пригодится. У меня есть небольшой пример на Delphi работы с очень большими (по порядку величины) целыми числами. Демонстрируется лишь сам принцип - разделение числа на значущую часть и порядок. Адрес: http://sadovoya.narod.ru/BIG_NUMBERS.ZIP

Автор: integral 28.10.2006, 16:29
А вот пример на Java, на своей машине я смог вычеслить 100001! за 9 мин 24 сек:
private String calkFacktorial(String str)
    {
        if(str.equals("0")) return "1";
        BigInteger i = new BigInteger("1");
        BigInteger n = new BigInteger(str);
        BigInteger result = new BigInteger("1");
        
        for(; !i.equals(n); i = i.add(BigInteger.ONE))
        {
            result = result.multiply(i);
        }
        
        return result.multiply(n).toString();
    }

Автор: esperant0 28.10.2006, 21:54
Цитата(integral @ 28.10.2006,  16:29)
А вот пример на Java, на своей машине я смог вычеслить 100001! за 9 мин 24 сек:
private String calkFacktorial(String str)
    {
        if(str.equals("0")) return "1";
        BigInteger i = new BigInteger("1");
        BigInteger n = new BigInteger(str);
        BigInteger result = new BigInteger("1");
        
        for(; !i.equals(n); i = i.add(BigInteger.ONE))
        {
            result = result.multiply(i);
        }
        
        return result.multiply(n).toString();
    }

а я за своей за 12 секунд считал

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)