Что нового

Все Первая цифра числа

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
Необходимо написать наибыстрейшую программу, которая определяет первую цифру слева (цифра наивысшего разряда) факториала любого числа в десятичном представлении. Например,
Код:
Число | Факториал | Первая цифра
------|-----------|-------------
1     | 1         | 1
2     | 2         | 2
3     | 6         | 6
4     | 24        | 2
5     | 120       | 1
6     | 720       | 7
7     | 5040      | 5
8     | 40320     | 4
9     | 362880    | 3
10    | 3628800   | 3
Программа должна принимать на входе любое число, превышающее 100, считать его факториал и выдавать одну цифру от 1 - 9 которая является первой слева. Правильность ответа можете проверить на сайте Калькулятор Факториалов.

Бонусная задача: Определить первую цифру от числа 5001!
 
Последнее редактирование модератором:

Viktor1703

AutoIT Гуру
Сообщения
1,535
Репутация
413
Не понял, вычислять факториал нужно саамому? если нет то:

Код:
Dim $aValue[10] = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

For $i = 0 To Ubound($aValue) - 1
    ConsoleWrite(Left($aValue[$i], 100) & @CRLF)
Next

Func Left($aNumber, $iLimit)
	If $aNumber >= $iLimit And $aNumber <= 5000 Then
	    If Not IsFloat($aNumber / 2) Then
	        Return StringLeft($aNumber, 1)
	    Else
            Return $aNumber	
	    EndIf
	EndIf
EndFunc


Бонусная задача: Определить первую цифру от числа 5001!

Равно 0 (нулю)
 
Автор
kaster

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
Viktor1703
моя вина, не совсем внятно изложил. поправил сообщение.
да, факториалы надо самому считать

Viktor1703 [?]
первая цифра слева. как в примере
 

Viktor1703

AutoIT Гуру
Сообщения
1,535
Репутация
413
Код:
For $i = 1 To 200
	If $i >= 100 Then
	    ConsoleWrite(Factorial($i) & @CRLF)
	EndIf	
Next	

Func Factorial($aNumber)
    Local $aRet
    If ($aNumber = 0) Or ($aNumber = 1) Then Return 1	
    For $i = 1 to $aNumber
        $aRet += Log($i) / Log(10)
    Next
    If $aNumber <= 170 Then $aRet = 10 ^ $aRet
    Return StringLeft($aRet, 1)
EndFunc


Бонусная задача: Определить первую цифру от числа 5001!

Равно 1, правдо результата ждал прилично :smile:
 
Автор
kaster

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
Viktor1703
попахивает моим давнишним кодом ;D
правда реализован неправильно.
Viktor1703 [?]
Равно 1, правдо результата ждал прилично
ответ неверен. я думаю, в следствие вышесказанного.
 

Viktor1703

AutoIT Гуру
Сообщения
1,535
Репутация
413
Честно говоря не видел Вашего кода :blink:, да и в математике я не очень, буду пробывать ещё, это же не конец света :smile:
 
Автор
kaster

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626

Zaramot

I ♥ AutoIt
Сообщения
1,160
Репутация
660
Код:
Dim $Array[10] = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

For $x = 0 To UBound($Array) - 1
	ConsoleWrite(StringMid(Factorial($Array[$x]), 1, 1) & @CRLF)
Next

Func Factorial($mfFactor)
	If Not (StringIsInt($mfFactor)) OR (Int($mfFactor) < 0) Then
		SetError(1)
		Return 0
	Else
		$mfFactor = Int($mfFactor)
	EndIf
	If $mfFactor = 0 Then Return 1
	Dim $return = 1
    For $i = $mfFactor to 1 Step - 1
        $return *= $i
    Next
	Return $return
EndFunc
 
Автор
kaster

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
Zaramot
входное число должно быть больше 100, в идеале (чтобы решить бонусную задачу) за 5000


Добавлено:
Сообщение автоматически объединено:

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

Zaramot

I ♥ AutoIt
Сообщения
1,160
Репутация
660
Код:
#include <MathEx.au3>

Dim $Array[10] = [121, 157, 189, 210, 250, 290, 310, 347, 377, 400]

For $x = 0 To UBound($Array) - 1
	ConsoleWrite(StringMid(_Factorial($Array[$x]), 2, 1) & @CRLF)
Next
 

XpycT

Скриптер
Сообщения
380
Репутация
133
Код:
#include "BigNum.au3"
$iT = TimerInit()
$iF = 1
$iN = 5001
If $iN < 0 Then Exit 99 * 0 + ConsoleWrite("Число : " & $iN & @CR & "Факториал : 0" & @CR & "Первая Цифра : 0" & @CR & "Время : " & TimerDiff($iT) & @CR)
If $iN = 0 Then Exit 99 * 0 + ConsoleWrite("Число : " & $iN & @CR & "Факториал : 1" & @CR & "Первая Цифра : 1" & @CR & "Время : " & TimerDiff($iT) & @CR)

For $i = 1 To $iN
	$iF = _BigNum_Mul($iF, $i)
Next
ConsoleWrite("Число : " & $iN & @CR & "Факториал : " & $iF & @CR & "Первая Цифра : " & StringLeft($iF, 1) & @CR & "Время : " & TimerDiff($iT) & @CR)


Первая Цифра факториал от числа 5001 : 2

BigNum.au3
 
Автор
kaster

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
Zaramot
помоему,
Код:
Time spent for 100! - 21.471751018635 secs
не очень хороший результат ;D


Добавлено:
Сообщение автоматически объединено:

XpycT
Уже лучше, но опять же 4 сек :smile:
Код:
Number : 1000
First digit : 4
Time : 4042.04109740204

Чтобы было на что ориентироваться, приведу время выполнения моего варианта
Код:
Time spent for first digit of my method for 5001 - 0.0160525988638221 secs


Добавлено:
Сообщение автоматически объединено:

XpycT [?]
Первая Цифра факториал от числа 5001 : 2
ответ верный, но я на своей машине, к сожалению не дождался результата. в любом случае, как наибыстрейший твой метод не пойдет


Добавлено:
Сообщение автоматически объединено:

таки дождался
Код:
Time : 155930.178835578
 

AZJIO

Меценат
Меценат
Сообщения
2,894
Репутация
1,196
XpycT
Если уж использовать BigNum.au3, то там есть _BigNum_Parse. Примерно так:

Код:
#include "BigNum.au3"
MsgBox(0, '', _Fl(100))

Func _Fl($n)
	$r='1'
	For $i = 2 To $n
		$r &= '*'&$i
	Next
	Return _BigNum_Parse($r)
EndFunc
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Код:
#include <Date.au3>

ConsoleWrite(" старт " & _NowTime() & @CRLF )
ConsoleWrite("первая цифра = " & StringLeft(_eshe_parocku(5001),1) & @CRLF )
ConsoleWrite(" стоп " & _NowTime() & @CRLF )

Func _eshe_parocku($aNumber)
    Local $aRet = 1
	For $i = 1 to $aNumber
        $aRet *= $i
		If $aRet > 10000000 Then $aRet = Floor($aRet / 1000)
    Next
	Return $aRet
EndFunc
 
Автор
kaster

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
C2H5OH
умно, умно :smile: экономит пару операций по сравнению с моим методом и соответственно на пару миллисекунд быстрее на числах 4000-5000. вобщем, победил, молодец :ok: к сожалению победителей нет
вот сравнительные тест двух методов
Код:
$total_my = 0
$total = 0
$NTry = 1000

For $i = 1 to $NTry
	$N = Random(4000, 5000, 1)
	$start = TimerInit()
	FirstDigit($N)
	$total_my += TimerDiff($start)
	$start = TimerInit()
	C2H5OH($N)
	$total += TimerDiff($start)
Next
ConsoleWrite('Average time of my method:' & @TAB & @TAB & $total_my/$NTry & ' msecs' & @CRLF)
ConsoleWrite('Average time of other method:' & @TAB & $total/$NTry & ' msecs' & @CRLF)

Func FirstDigit($N)
	$S = 0
	For $i = 1 to $N
		$S += Log10($i)
	Next
	Return Floor(10^Mod($S, 1))
EndFunc

Func Log10($N)
	Return Log($N)/Log(10)
EndFunc

Func C2H5OH($aNumber)
    Local $aRet = 1
    For $i = 1 to $aNumber
        $aRet *= $i
        If $aRet > 10000000 Then $aRet = Floor($aRet / 1000)
    Next
    Return StringLeft($aRet, 1)
EndFunc

на моей машине выдало следующее
Код:
Average time of my method:		12.5265294890831 msecs
Average time of other method:	9.82166783767211 msecs

Если кому интересно, я использовал свойство логарифма, что логарифм произведения равен сумме логарифмов.
pNU3fg3o.png

Старший разряд числа находится путем деления на 10 в степени этого разряда. В терминах же логарифма это разность. Если от логарифма отнять наибольший разряд, то останется лишь дробная часть. Так вот 10 этой дробной степени и есть первая цифра. Чисто математический подход.

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

Всем спасибо за участие :smile:
 

Zaramot

I ♥ AutoIt
Сообщения
1,160
Репутация
660
Первая цифра факториала числа 7000 - это 8, а его код выдает 7 :whistle:
 
Автор
kaster

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
Zaramot
Действительно. Значит аккумулируется ошибка при обрезке, которая потом дает о себе знать... Поспешил я с выводами :(
Ладно, т.к. я ответ уже дал, будем считать победивших нет :(
 

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Zaramot прав.
Мой код корректно работает для чисел до 1000.
При бОльших числах факториал растёт быстрее чем я отбрасываю младшие знаки и происходит переполнение.
Так получилось что на 5001 мой код дал правильный результат, просто совпадение.

Честно говоря особо не отлаживал код - мне настолько понравилось решение с логарифмами, что я был уверен, что оно будет победителем.

А решения с MathEx.au3 и BigNum.au3 не понравились.
Время работы кода с логарифмами - N
Время работы кода с математикой на массивах - N*log(N)
казалось бы разница небольшая, но для больших чисел......
 

AZJIO

Меценат
Меценат
Сообщения
2,894
Репутация
1,196
C2H5OH
У меня сомнения сразу были с обрезкой числа. Любая функция увеличивающаяся в некой прогрессии зависима от долей. К примеру 2 в степени 64, стоит чуть увеличить число, результат будет на несколько порядков выше. BigNum.au3 хоть и меленная но даст точный результат.
 
Верх