Почему Project Euler говорит, что я получаю № 20 неправильно?

Вот проблема, которую я пытаюсь решить: Эйлер 20 .

n! означает n ⨉ (n - 1) ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1

Например, 10! = 10 ⨉ 9 ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1 = 3628800 10! = 10 ⨉ 9 ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1 = 3628800 , а сумма цифр в 10! = 10 ⨉ 9 ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1 = 3628800 10! 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 .

Найдите сумму цифр в числе 100!

Я пробовал это:

 y = 1 #The actual number sum = 0 #The sum of its digits. def factorial(x): #Calculates the number using a recursive factorial algorithm global y y = y*x if x > 1: factorial(x-1) else: return 0 factorial(100) #Calculate 100! and the function will put it in y. def count(): #Calculates the sum. global y, sum while y > 0: currentDigit = int(y) % 10 #Find the remainder of the number gives the very last digit sum = sum + currentDigit #Add that to the total sum. y = int(y) / 10 #Divide y by 10 knocking of the 1s-digit place and putting the 10s digit in its place. return sum #return the sum. print(count()) #print the count. 

Если я делаю factorial(10) вместо 100, я получаю 27, что и говорит проблема, которую я должен получить, но я получаю 675 для factorial(100) которые, по словам программы, неверны. Что я сделал не так? Я не знаком с Python, извините, если я сделал глупую ошибку.

Проблема заключается в вашей реализации count , в частности, в строке:

  y = int(y) / 10 

Поскольку Python 3, / является истинным делением . В Python 2.2 и более поздних версиях вы можете получить поведение разделения Python 3 from __future__ import division . После выполнения вышеуказанной строки y является поплавком. Платы Python на большинстве систем содержат только около 15 значащих десятичных цифр ( sys.float_info.dig даст вам точность для вашей системы, обратите внимание, что на самом деле существует 53 бит точности, что равно 53 / log 2 (10) ≈ 15,955 ). Любая десятичная цифра, которая count выдержки после этих значительных, является результатом ошибки округления и является следствием преобразования плавающего базиса-2 в базу 10. На определенной длине средние цифры не будут влиять на сумму, вычисленную по count .

 [count(int('8' * 17 + str(k) + '0')) for k in range(1, 10)] # [130, 130, 130, 130, 130, 130, 130, 130, 130] import random [count(int('8' * 17 + ('%05d' % random.randint(1,99999)) + '0')) for k in range(1, 10)] # [146, 146, 146, 146, 146, 146, 146, 146, 146] 

Решение состоит в том, чтобы использовать // для целочисленного деления, после чего вы также можете удалить int преобразования. Пока вы на нем, вы можете также сделать y параметром для count и сделать sum локальной. В противном случае ваша глобальная переменная sum скроет встроенную функцию sum .

Что же касается устранения глобального y в factorial , довольно легко передать дополнительный аргумент:

 def factorial(x, p=1): p *= x if x > 1: return factorial(x-1, p) else: return p 

Преимущество этого заключается в том, что он рекурсивный . Стандартный интерпретатор python не реализует оптимизацию хвостового вызова, но это можно сделать с помощью декоратора. Примените такой декоратор к factorial и результат – это функция, которая не вызовет переполнение стека. Этот метод передачи накоплений может использоваться для многих других функций для создания хвостовой рекурсивной функции.

В качестве альтернативы напишите итеративную версию, которая немного более питонична.

Вот простой способ переписать функцию factorial() чтобы она больше не зависела от глобальных переменных:

 >>> def fac(x): ... if x > 1: ... return x * fac(x-1) ... else: ... return 1 ... >>> fac(10) 3628800 >>> fac(100) 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L 

Он полагается на возврат значения и рекурсивное выражение для выполнения вычисления. Конечно, вычислить 100! означает, что цепочка вызовов будет на 100 уровней глубокой, но для ясности в этой функции я думаю, что компромисс стоит того. (Могут быть более надежные способы написания этой функции – например, обработать негативы или нецелые числа).

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

Что касается фактической ошибки вашего лета, я надеюсь, что это образовательный:

 $ python3.2 -c "print (755 / 10)" 75.5 $ python2.7 -c "print (755 / 10)" 75 

Найдите сумму цифр в числе 100!

 def sumFactorial(n): factorial=str(reduce(lambda x,y:x*y, range(n,0,-1))) return sum(int(x) for x in factorial) >>> sumFactorial(10) 27 >>> sumFactorial(100) 648 >>> 
 //In c++ #include<cstdio> #include<cstring> #include<iostream> using namespace std; int main() { int a[200]; int carry=0,temp,m=1,k=0; int n; cin>>n; a[0]=1; for(int i=1;i<=n;i++) { k=0; for(int j=0;j<m;j++) { temp=a[j]*i+carry; a[j]=temp%10; carry=temp/10; } while(carry!=0) a[m++]=carry%10,carry/=10; } long long ans=0; for(int i=m-1;i>=0;i--) { ans+=a[i]; } cout<<endl; cout<<ans<<endl; } 1.Array a[200] is used to store the digits of factorial. 2.Outer loop run from 1..100 3.varible m indicates no of digits in array or factorial 4.now lets take a example take a simple multiplication 25 x 12 ------------- 5 0 2 5 ------------- 3 0 0 300- value stores in temp; by taking modulo 10 we can get the last digit it is placed array 300/10 becomes carry. в //In c++ #include<cstdio> #include<cstring> #include<iostream> using namespace std; int main() { int a[200]; int carry=0,temp,m=1,k=0; int n; cin>>n; a[0]=1; for(int i=1;i<=n;i++) { k=0; for(int j=0;j<m;j++) { temp=a[j]*i+carry; a[j]=temp%10; carry=temp/10; } while(carry!=0) a[m++]=carry%10,carry/=10; } long long ans=0; for(int i=m-1;i>=0;i--) { ans+=a[i]; } cout<<endl; cout<<ans<<endl; } 1.Array a[200] is used to store the digits of factorial. 2.Outer loop run from 1..100 3.varible m indicates no of digits in array or factorial 4.now lets take a example take a simple multiplication 25 x 12 ------------- 5 0 2 5 ------------- 3 0 0 300- value stores in temp; by taking modulo 10 we can get the last digit it is placed array 300/10 becomes carry. с //In c++ #include<cstdio> #include<cstring> #include<iostream> using namespace std; int main() { int a[200]; int carry=0,temp,m=1,k=0; int n; cin>>n; a[0]=1; for(int i=1;i<=n;i++) { k=0; for(int j=0;j<m;j++) { temp=a[j]*i+carry; a[j]=temp%10; carry=temp/10; } while(carry!=0) a[m++]=carry%10,carry/=10; } long long ans=0; for(int i=m-1;i>=0;i--) { ans+=a[i]; } cout<<endl; cout<<ans<<endl; } 1.Array a[200] is used to store the digits of factorial. 2.Outer loop run from 1..100 3.varible m indicates no of digits in array or factorial 4.now lets take a example take a simple multiplication 25 x 12 ------------- 5 0 2 5 ------------- 3 0 0 300- value stores in temp; by taking modulo 10 we can get the last digit it is placed array 300/10 becomes carry. 

Я вижу, что вы используете множество глобальных переменных.

Первое:

Я думаю, вместо использования global y вы можете использовать y в функции и вернуть значение return y .

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

Вместо написания новой факториальной функции вы могли бы импортировать факториальную функцию из math модуля .

 >>> from math import factorial 

Чтобы разбить номер на цифры, вы можете сделать следующее:

 >>> a = list(str(factorial(100))) 

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

 >>> a = [int(x) for x in a] 

Я использовал понимание списка в приведенном выше коде.

Наконец, используйте встроенную функцию суммы, чтобы получить решение.

 >>> a = sum(a) 

Надеюсь, это поможет вам решить вашу проблему / По крайней мере, мой ответ добавит некоторую ценность этому вопросу и поможет людям, имеющим аналогичную проблему. Источник: RadiusOfCirlce