Короче, я сам ничего не писал, мне кажется 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

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