很多公司面试都会有一个问题,就是求N阶乘,主要是考查一些编程的基础知识如循环、类型的最大长度、递归等。
例如最简单的实现是:
public void factorial(int n){
long result = 1;
for(int i=0;i<n;i++){
result = result*i;
}
}
但是,这个简单的实现可能会出现问题, n一大就会超过long的最大值,从而导致错误。
而且随着n的增大,数会越来越大,即使是double也无法满足计算的需要。
为了解决这个问题,唯一的办法就是使用字符串,才能避免类型越界和数字大的问题,下面是基本的算法思路:
1)将数字用科学计数法表示,例如1234可以表示位1*1000+2*100+3*10+4*1
1000是10的3次方,100是10的2次方,10是10的1次方,1是10的0次方,依次类推。
2)两个多位数(10以上)相乘拆分成多次乘法,然后进行相加。
3)两个数相乘可以表示成两个数进行表示
4)用IntegerString[]数组表示一个数
程序如下:
定义类:
//表示一个数字,使用科学计数法。如500表示IntegerString(5,2)
public class IntegerString {
private int number = 0;//数字
private int length = 0;//10的length次方
/** Creates a new instance of IntegerString */
public IntegerString(int number,int length) {
this.number = number;
this.length = length;
}
public int getNumber(){
return this.number;
}
public int getLength(){
return this.length;
}
}
/**
两个数相乘,结果用两个数来表示,一个是高位,一个是低位
**/
public class MultiplyResult {
private IntegerString high;
private IntegerString low;
/** Creates a new instance of MultiplyResult */
public MultiplyResult(IntegerString a,IntegerString b) {
int result = a.getNumber()*b.getNumber();
int length = a.getLength()+b.getLength();
if(result>=10){
high = new IntegerString(result/10,length+1);
low = new IntegerString(result%10,length);
}else{
high = new IntegerString(result,length);
low = new IntegerString(0,length-1);
}
}
public String toString(){ //打印方便,以便调试
StringBuffer sb = new StringBuffer();
sb.append(high.getNumber());
sb.append(low.getNumber());
for(int i=0;i<low.getLength();i++)
sb.append("0");
return sb.toString();
}
public IntegerString getHigh(){
return high;
}
public IntegerString getLow(){
return low;
}
}
public class Factorial{
//由大到小,由高到低,将一个字符的数表示成科学计数法
private IntegerString[] getIntegerString(String str){
IntegerString[] is = new IntegerString[str.length()];
for(int i=0;i<str.length();i++){
char ch = str.charAt(i);
int number = Character.getNumericValue(ch);
is[i] = new IntegerString(number,str.length()-1-i);
}
return is;
}
//获得数的最高位
private int getMaxLength(IntegerString[] a){
int max = 0;
for(int i=0;i<a.length;i++){
if(a[i].getLength()>max)
max = a[i].getLength();
}
return max;
}
//一个数与单个数字相乘
private IntegerString[] singleMultiply(IntegerString[] old,IntegerString gene){
MultiplyResult[] mr = new MultiplyResult[old.length];
for(int i=0;i<old.length;i++){
mr[old.length-1-i] = new MultiplyResult(old[i],gene);
// System.out.println(mr[old.length-1-i]);
}
//mr是从最低位到最高位
java.util.ArrayList arrays = new java.util.ArrayList();
int carry = 0;
int maxLength = mr[mr.length-1].getHigh().getLength(); //获得最高位的长度
for(int i=0;i<=maxLength;i++){//从个位到最高位一次加,如果有进位,那么存放到carry中
int number = carry;
for(int j=0;j<mr.length;j++){
if(mr[j].getLow().getLength()==i)
{
number+=mr[j].getLow().getNumber();
}
if(mr[j].getHigh().getLength()==i){
number+=mr[j].getHigh().getNumber();
}
}
if(number>=10){ //如果有进位,取余数,如果没有,取本身
arrays.add(new IntegerString(number%10,i));
carry=1;
}else{
arrays.add(new IntegerString(number,i));
carry=0;
}
}
if(carry==1){ //如果还有进位,那么加入到最高位
arrays.add(new IntegerString(carry,maxLength+1));
}
IntegerString[] results = new IntegerString[arrays.size()];
java.util.Iterator ii = arrays.iterator();
int index=0;
while(ii.hasNext()){
results[index++] = (IntegerString)ii.next();
}
return results;
}
private void print(IntegerString[] a){
System.out.println(getNumberic(a));
}
//将数字由IntegerString[]数组转换成字符串
private String getNumberic(IntegerString[] a){
StringBuffer sb = new StringBuffer();
int max = getMaxLength(a);
for(int i=0;i<=max;i++){
boolean isFind = false;
for(int j=0;j<a.length;j++){
if(a[j].getLength()==i){
sb.insert(0,a[j].getNumber());
isFind = true;
break;
}
}
if(!isFind){
sb.insert(0,0);
}
}
return sb.toString();
}
//两个数相加
private IntegerString[] add(IntegerString[] a,IntegerString[] b){
if(a==null) return b;
if(b==null) return a;
java.util.ArrayList arrays = new java.util.ArrayList();
int aMax = getMaxLength(a);
int bMax = getMaxLength(b);
int max = aMax>bMax?aMax:bMax;
int carry = 0;
for(int i=0;i<=max;i++){
for(int j1=0;j1<a.length;j1++){
if(a[j1].getLength()==i)
carry+=a[j1].getNumber();
}
for(int j2=0;j2<b.length;j2++){
if(b[j2].getLength()==i)
carry+=b[j2].getNumber();
}
if(carry>0){
if(carry>=10){
arrays.add(new IntegerString(carry%10,i));
carry=1;
if(i==max){
arrays.add(new IntegerString(carry,i+1));
}
}else{
arrays.add(new IntegerString(carry,i));
carry=0;
}
}else{
arrays.add(new IntegerString(0,i));
carry=0;
}
}
IntegerString[] results = new IntegerString[arrays.size()];
java.util.Iterator ii = arrays.iterator();
int index=0;
while(ii.hasNext()){
results[index++] = (IntegerString)ii.next();
}
return results;
}
//两个数相乘
private String stringMultiply(String a,String b){
IntegerString[] ais = this.getIntegerString(a);
IntegerString[] bis = this.getIntegerString(b);
IntegerString[] result = null;
for(int i=0;i<bis.length;i++){
IntegerString[] tmp = this.singleMultiply(ais,bis[i]);
result = add(result,tmp);
}
return this.getNumberic(result);
}
//打印N的阶乘
public void printFactorial(int n){
String total = "1";
int n=100;
for(int i=1;i<=n;i++){
total = stringMultiply(i+"",total);
}
System.out.println(total);
}
}
使用此类计算的100的阶乘位:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
此类也可以作为两个任意数字相乘,而且不会一越界。
以上算法可能存在的问题就是:
1)字符数组是以int位最大范围,可能超出界限,改进的方法是使用动态数组ArrayList
2)涉及到的算法含有大量的字符串操作,速度不是很快,当n=1000时,需要花费大量的时间,这点需要改进
3)如果N非常大,可能会造成内存不足的情况。
分享到:
相关推荐
目录试题 基础练习 阶乘计算要点思路代码(无注释)代码(含有注释) 试题 基础练习 阶乘计算 资源限制 时间限制:1.0s 内存限制:512.0MB 问题描述 输入一个正整数n,输出n!的值。 其中n!=123*…*n。 算法描述 ...
主要介绍了 Java递归算法计算阶乘,感兴趣的朋友可以参考下
递归 阶乘 求和 用两个递归实现1!+2!+3!+。。。+n! 对新手有帮助!
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...
阶乘与排列组合算法!在各行各业都能用得到的,比较彩票业,以及复杂的生产环境预测等软件开发
Java 采取递归方法求5!的阶乘,递归方法求阶乘之和,输入要阶乘的数字,递归公式:fn=fn_1*4! 具体来看以下代码: System.out.print("输入要阶乘的数字:"); Scanner scanner = new Scanner(System.in); int n ...
但是在大数据处理问题上有绝对的速度优势 假设数据量为n 对于运行次数 (不是时间复杂度)遍历算法可能是n的n次方或者 n的阶乘 动态规划至少也是n的三次方 遗传算法大概也就几百乘 n的平方 大数据通常是亿为单位的
问题:编程实现求阶乘n! 排序 问题:实现归并排序、快速排序、插入排序、冒泡排序、选择排序 问题:编程实现O(n)时间复杂度内找到一组数据的第K大元素 二分查找、散列表、字符串处理、二叉树、堆、图、回溯、分治...
编写一个Java程序,实现冒泡排序算法对一个整数数组进行排序。 编写一个Java程序,读取一个文本文件,并统计文件中每个单词的出现次数。 编写一个Java程序,实现一个简单的计算器,可以进行加、减、乘、除运算。 ...
q19_删除链表的倒数第N个节点 q25_k个一组翻转链表 q61_旋转链表 q138_复制带随机指针的链表 q160_相交链表 q206_反转链表 双指针遍历/滑动窗口 q3_无重复字符的最长子串 q11_盛最多水的容器 q15_三数之和 q16_最...
阐述到位 算法思想、算法实现和完整示例合理搭配,相辅相成。 示例完善 示例分析精准,代码注释精确,每段代码皆可通过编译执行。 计算机技术的发展和普及不仅改变了人们的生活和娱乐方式,也改变了人们的工作方式...
【Java每日一题】 1. 末尾0的个数——滴滴笔试题 题目描述:输入一个正整数n,求n!(即阶乘)末尾有多少个0? 比如: n = 10; n! = 3628800,所以答案为2 原题链接:...
这是本人第一次写博客,嗯…目的就是想记录一下自己的学习过程。以前学习数据结构的时候写快排用的循环都是双重for循环,今天偶尔看到了运用递归来实现快速排序,所以突发... n=eval(input("请输入你要计算阶乘的数字:
谁不会看到简单的递归阶乘算法? int fact( int n ) { if ( n < 2 ) return 1; else return n * fact( n - 1 );}我认为没有必要以新的方式解释递归,你可以找到很多解释(或)。 人们常说递归慢且无效,这是事实...
99乘法表java源码 数据结构与算法 数据结构与队列 package: queue 数组模拟队列 package: sparse(表示稀疏数组) 链表 pakage: linked 栈 package: stack 哈希表(散列) hash是一种数据结构 value = hash(key) 哈希...
leetcode手册JAVA 数据结构 表中的内容 渐近符号 定义: 渐近符号是一种独立于硬件的符号,用于说明算法的时间和空间复杂度。 这意味着它是衡量算法使用多少内存或在给定输入下运行多长时间的标准化方法。 复杂性 ...
2.2.1 递归值函数:n的阶乘 49 2.2.2 箱式跟踪 52 2.3 执行动作的递归 55 2.4 递归与数组 62 2.4.1 逆置数组项 63 2.4.2 折半查找 64 2.4.3 查找数组中的最大值 68 2.4.4 查找数组中第k个最小值 69 2.5 ...
C语言 语言主讲: 主讲:邓君峰 绪 论 教学要求 – 掌握程序设计语言的基本知识 – 常用算法 – 初步的程序设计能力 学习方法 – 自主学习 – 重视上机实践 教材和参考书 The C Programming Languagem, Second Edition...
factorial(N)是N * factorial(N-1)。 脚步: 使用顶部的按钮分叉此存储库 将分叉的存储库克隆到PC 创建一个用于修改的新分支(即git branch new-user并检出git checkout new-user和git checkout -b new