大数阶乘--栈
发布时间:2020-12-14 03:05:24 所属栏目:大数据 来源:网络整理
导读:http://acm.nyist.net/JudgeOnline/problem.php?pid=28 大数阶乘 时间限制: 3000 ?ms ?|? 内存限制: 65535 ?KB 难度: 3 描述 我们都知道如何计算一个数的阶乘,可是,如果这个数很大呢,我们该如何去计算它并输出它? 输入 输入一个整数m(0m=5000) 输出
http://acm.nyist.net/JudgeOnline/problem.php?pid=28 大数阶乘
时间限制:3000?ms ?|? 内存限制:65535?KB
难度:3
这道题难度为3,是一道金典的题,但是没做过类似的,比难度为4的还要难啊。。想到用顺序栈来存储数字,却没有想到如何处理进位的问题。无奈只好看讨论区,发现设计之妙,不多说,直接上码,看注释就是了
import java.util.Scanner; /* * 大数阶乘 1501 1794 */ public class Main { public static final int MAX = 50000; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int[] saveNum = new int[MAX]; int tmp = 0,sum; while (cin.hasNext()) { int n = cin.nextInt(); saveNum[0] = 1; for (int i = 2; i <= n; i++) { // 两重for循环是为了解决进位的问题 for (int j = 0; j < MAX; j++) { // 栈的后进先出,反过来存储,依靠tmp,解决进位 sum = saveNum[j] * i + tmp; // if(sum==0)break; //不可以依靠sum=0就跳出,有可能这个位置是为0的 saveNum[j] = sum % 10; //总是取个位 tmp = sum / 10; //总是取十位,个位数相乘,最大是两位而已 } } int account = MAX - 1; while (account >= 0 && saveNum[account] == 0) // 后往前找到不为0的,因为是反过来存储 account--; for (int i = account; i >= 0; i--) System.out.print(saveNum[i]); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |