Python实现阶乘的三种解法 |
您所在的位置：网站首页 › 求carry › Python实现阶乘的三种解法 |
|
Python实现阶乘的三种解法
问题描述 输入一个正整数n，输出n!的值。 其中n!=123*…*n。 算法描述 n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。 将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。 首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。 输入格式 输入包含一个正整数n，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='') 接下来我讲下思路： 首先定义一个ns数组用来存储n!的各个位数上的数值，利用for循环给ns加入10000个0值，以方便后面直接根据index对数组进行操作。 然后定义length作为 “数组的长度”（有真实数值的而非自动添加的0） 也即n!的结果的位数。 之后也必须用到for循环进行累乘，但跟解法一的直接累乘不同，这里是乘数(即i)跟各个位上的数分别相乘，若结果大于等于10则carry>0即向前进一位数值为carry，若j循环结束后carry>0则说明需要在当前ns的“长度”上进一位，所以length+1即位数+1，这里carry起的就是判断是否进位的作用，而length则代表着结果的位数。可能这么说有些抽象，下面我们通过分解运行过程来更直观的阐述上面的想法。 例如我们现在需要求5!,分五步,即i循环5次： ①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为第j位数与i相乘并加上j-1位数与i相乘后进位的值的结果 carry = int(temp/10) = 1/10 = 0 # carry=0所以不用进位 ns[j] = temp % 10 即 ns[0] = 1 % 10 =1 #只取个位数值作为第j位的值 ②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为第j位数与i相乘并加上j-1位数与i相乘后进位的值的结果 carry = int(temp/10) = 2 / 10 = 0 # carry=0所以不用进位 ns[j] = temp % 10 即 ns[0] = 2 % 10 =2 #只取个位数值作为第j位的值 #这样就已经的到2!的值了即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为第j位数与i相乘并加上j-1位数与i相乘后进位的值的结果 carry = int(temp/10) = 6 / 10 = 0 # carry=0所以不用进位 ns[j] = temp % 10 即 ns[0] = 6 % 10 =6 #只取个位数值作为第j位的值 #这样就已经的到3!的值了即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为第j位数与i相乘并加上j-1位数与i相乘后进位的值的结果 carry = int(temp/10) = 24 / 10 = 2 # carry=2>0所以需要向前进2 ns[j] = temp % 10 即 ns[0] = 24 % 10 =4 #只取个位数值作为第j位的值 j循环结束，carry>0执行while循环 while carry>0: ns[length] += carry%10 即 ns[1] += 2 % 10 = 2 #carry = 2 所以向前进2 length+=1 即 length =1+1=2 #位数加一 carry = int(carry/10) = 2 / 10 = 0 # carry = 20所以需要向前进2 ns[j] = temp % 10 即 ns[0] = 20 % 10 =0 #只取个位数值作为第j位的值 ⑵ j=1 temp = ns[j] * i + carry = ns[1] * i + carry =2*5+2=12 # temp为第j位数与i相乘并加上j-1位数与i相乘后进位的值的结果 carry = int(temp/10) = 12 / 10 = 1 # carry=1>0所以需要向前进1 ns[j] = temp % 10 即 ns[1] = 12 % 10 =2 #只取个位数值作为第j位的值 j循环结束，carry>0执行while循环 while carry>0: ns[length] += carry%10 即 ns[2] += 1 % 10 = 1 #carry = 1 所以向前进2 length+=1 即 length =2 +1 = 3 #位数加一 carry = int(carry/10) = 1 / 10 = 0 # carry = 1 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |