Find the factorial of N
This question requires a program to compute the factorial of N.
Input Format:
The input gives a positive integer N in one line.
Output format:
Output the value of the factorial F in one line in the format "product = F", noting that there is a space to the left and right of the equal sign. The title guarantees that the result will not exceed double precision.
Input Sample:
5
Sample output:
product = 120
x = int(input())
a = 1
for i in range(1, x+1):
a = a*i
print("product = %d" % float(a))Three solutions for realizing factorials
Problem Description:
Input a positive integer n and output the value of n!
where n!=123*...*n.
Algorithm Description:
n! can be very large, and the limited range of integers that a computer can represent requires the use of high-precision computational methods. Use an array A to represent a large integer a. A[0] represents the digit of a, A[1] represents the tens digit of a, and so on.
Multiplying a by an integer k becomes multiplying each element of the array A by k. Note that the corresponding rounding is handled.
First set a to 1, then multiply by 2, multiply by 3, and when multiplied by n, you get the value of n!
Input Format:
The input contains a positive integer n, n<=1000.
Output format:
Output the exact value of n!
Sample Input:
10
Sample output:
3628800
The first two simpler solutions that come to mind when I see this problem are loops and recursion.
Solution 1: Circulation
n = int(input()) ns = 1 for i in range(1,n+1): ns = ns*i print(ns)
The idea is relatively simple, is to define a variable ns given an initial value of 1, and then use the for loop to multiply directly to get the final result.
Solution 2: Recursion
def factorial(n): if n==1: return n else: return n*factorial(n-1) n = int(input()) res = factorial(n) print(res)
Recursion is also better understood, when n == 2, return 2 * 1; n == 3, return 3 * (2 * 1); n==4, return 4 * (3 * (2 * 1)). And so on, and then just give the final result to res to print it.
Both of these methods are relatively simple, but obviously neither meets the question's requirement of "Use an array A to represent a large integer a, with A[0] denoting the digit of a and A[1] denoting the tens digit of a," so we need to figure out a way to use arrays to get the result of n!
Solution 3: Arrays
n= int(input()) ns = [0 for i in range(10000) ] length = 1 ns[0] = length = 1 if n>=2: for i in range(2,n+1): carry = 0 for j in range(length): temp = ns[j] * i + carry carry = int(temp/10) ns[j] = temp % 10 while carry>0: ns[length] += carry%10 length+=1 carry = int(carry/10) while length>0: length -=1 print(ns[length],end='')
Next I'll talk about the thought process:
First, define an ns array to store the value of each digit of n! Use a for loop to add 10,000 0 values to ns to facilitate later operations on the array directly based on index.
Then define length as the "length of the array" (the one with the real value rather than the automatically added 0) i.e. the number of bits in the result of n!
After the for loop must also be used to multiply, but with the solution of a direct multiplication of different, here is the multiplier (i) and the number of bits were multiplied, if the result is greater than or equal to 10, then carry>0 that is, to advance a value for carry, if the end of the j loop carry>0 means that you need to be at the current ns of "length "into one, so length +1 that is, the number of bits +1, here carry is to determine whether to enter the role of bits, and length represents the number of bits of the result. May be so that some abstract, the following we run through the process of decomposition to more intuitive elaboration of the above idea.
For example, we now need to ask for 5!, in five steps, i.e., i loop 5 times:
①i=1
ns[0] = length =1 , carry = 0 ∴j in range(1)
⑴ j=0
temp = ns[j] * i + carry = ns[0] * i + carry =1*1+0=1 # temp is the result of multiplying the jth digit by i and adding the value of the j-1 digit multiplied by i and rounded to the next digit carry = int(temp/10) = 1/10 = 0 # carry=0 so no rounding ns[j] = temp % 10 assume (office) ns[0] = 1 % 10 =1 #Only single-digit values are taken as the firstjvalue of a bit
②i=2
ns[0] = 1, length =1 , carry = 0 ∴j in range(1)
⑴ j=0
temp = ns[j] * i + carry = ns[0] * i + carry =1*2+0=2 # temp is the result of multiplying the jth digit by i and adding the value of the j-1 digit multiplied by i and rounded to the next digit carry = int(temp/10) = 2 / 10 = 0 # carry=0 so no rounding ns[j] = temp % 10 assume (office) ns[0] = 2 % 10 =2 # Take only the single-digit value as the value of the jth digit #That's how it's been done.2!的值了assume (office)2
③i=3
ns[0] = 2, length =1 , carry = 0 ∴j in range(1)
⑴ j=0
temp = ns[j] * i + carry = ns[0] * i + carry =2*3+0=6 # temp is the result of multiplying the jth digit by i and adding the value of the j-1 digit multiplied by i and rounded to the next digit carry = int(temp/10) = 6 / 10 = 0 # carry=0 so no rounding ns[j] = temp % 10 assume (office) ns[0] = 6 % 10 =6 # Take only the single-digit value as the value of the jth digit #That's how it's been done.3!的值了assume (office)6
④i=4
ns[0] = 6, length =1 , carry = 0 ∴j in range(1)
⑴ j=0
temp = ns[j] * i + carry = ns[0] * i + carry =6*4+0=24 # temp is the result of multiplying the jth digit by i and adding the value of the j-1 digit multiplied by i and rounded to the next digit carry = int(temp/10) = 24 / 10 = 2 # carry=2>0 so it needs to go forward 2 ns[j] = temp % 10 assume (office) ns[0] = 24 % 10 =4 #Only single-digit values are taken as the firstjvalue of a bit
j loop ends, carry>0 executes while loop
while carry>0: ns[length] += carry%10 assume (office) ns[1] += 2 % 10 = 2 #carry = 2 so go forward 2 length+=1 assume (office) length =1+1=2 #Digit plus one carry = int(carry/10) = 2 / 10 = 0 # carry = 2<10 so no need to continue rounding, while loop ends ∴length = 2 , ns[0] = 4 ,ns[1] = 2 #This gives us4!value ofns[1]*10+ns[0] assume (office) 24,The output can be printed directly upside down and thenend=''Instead of multiplying each digit by10*nadd up
⑤i=5
ns[0] = 4, ns[1] = 2 length =2 , carry = 0 ∴j in range(2)
⑴ j=0
temp = ns[j] * i + carry = ns[0] * i + carry =4*5+0=20 # temp is the result of multiplying the jth digit by i and adding the value of the j-1 digit multiplied by i and rounded to the next digit carry = int(temp/10) = 20 / 10 = 2 # carry=2>0 so it needs to go forward 2 ns[j] = temp % 10 assume (office) ns[0] = 20 % 10 =0 #Only single-digit values are taken as the firstjvalue of a bit
⑵ j=1
temp = ns[j] * i + carry = ns[1] * i + carry =2*5+2=12 # temp is the result of multiplying the jth digit by i and adding the value of the j-1 digit multiplied by i and rounded to the next digit carry = int(temp/10) = 12 / 10 = 1 # carry=1>0 so it needs to go forward 1 ns[j] = temp % 10 assume (office) ns[1] = 12 % 10 =2 #Only single-digit values are taken as the firstjvalue of a bit
j loop ends, carry>0 executes while loop
while carry>0: ns[length] += carry%10 assume (office) ns[2] += 1 % 10 = 1 #carry = 1 so go forward 2 length+=1 assume (office) length =2 +1 = 3 #digit plus one carry = int(carry/10) = 1 / 10 = 0 # carry = 1<10 so no need to continue rounding, while loop ends ∴length = 3 , ns[0] = 0 , ns[1] = 2 , ns[2] = 1 # This gives us5!value ofns[2] ns[1] ns[0]assume (office) 120
If you look at it this way, you can see that it's very similar to the vertical multiplication process you learned in elementary school, where you multiply the number of digits (ns[j],j in range(0,length)) by the number of digits (i) from the lower digit to the higher digit, and if it's greater than ten, then it goes up to the next digit (carry=temp/10>0, and if ns[length]*i+carry+10＞10, then length+1).
The above is a personal experience, I hope it can give you a reference, and I hope you can support me more.