Принес мне тут один знакомый задачку:
Определить последнюю цифру не равную 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-битными числами