首页 > 试题广场 >

计算200以内正整数的阶乘

[编程题]计算200以内正整数的阶乘
  • 热度指数:2763 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
编写一段程序,用于计算200以内正整数的阶乘

要求:  不允许使用任何第三方库。



输入描述:
N为不超过200的正整数



输出描述:
如果N >= 1 并且 N <=200 ,输出N的阶乘
如果N是别的数字,输出 Error

示例1

输入

10

输出

3628800

说明

10的阶乘为  3628800 
数据量很小,直接O(n)的暴力方法就能计算,用python避免考虑溢出
n = int(input())
if 1 <= n <= 200:
    res = 1
    for num in range(1, n + 1):
        res *= num
    print(res)
else:
    print("Error")

发表于 2022-01-08 20:12:32 回复(2)
来个c语言版的,通过动态数组实现,各位可以参考
# include<stdio.h>
# include<stdlib.h>

int main()
{
	int n;
	scanf("%d", &n);
    int* res = (int*)malloc(sizeof(int));
    int current_len = 1;
    int carry = 0;
    *res = 1;
    if (n < 1 || n>200) {
        printf("Error");
    }
    else { // 用数组存放结果,超过1000000的部分会进位并放入数组的下一单元
        for (int i = 1; i < n + 1; i++) {
            int temp_len = current_len;
            for (int j = 0; j < temp_len; j++) {
                res[j] = res[j] * i + carry;
                carry = 0;
                if (res[j] >= 1000000) {
                    if (j+1 >= current_len) {
                        current_len += 1;
                        res = (int*)realloc(res, current_len * sizeof(int));
                        res[j + 1] = 0;
                        res[j+1] = res[j+1] + (int)(res[j] / 1000000);
                        res[j] = res[j] - (int)(res[j] / 1000000) * 1000000;
                    }
                    else {
                        carry = (int)(res[j] / 1000000);
                        res[j] = res[j] - (int)(res[j] / 1000000) * 1000000;
                    }
                }
            }
        }
        for (int i = current_len - 1; i >=0; i--) {
            if (res[i] == 0) {
                printf("000000");
            }
            else if (res[i] < 100000 && i != current_len - 1)
            { // 补充0
                int temp = res[i];
                int j;
                for (j = 0; temp >= 1; j++) {
                    temp = temp / 10;
                }
                for (int k = 0; k < 6 - j; k++) {
                    printf("0");
                }
                printf("%d", res[i]);
            }
            else
            {
                printf("%d", res[i]);
            }
        }
    }
    return 0;
}

编辑于 2022-04-15 16:15:27 回复(0)

动态规划思想:

状态转移方程:

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n>=1 && n<=200){
            BigInteger[] dp = new BigInteger[n];
            dp[0] = BigInteger.valueOf(1);
            dp[1] = BigInteger.valueOf(2);
            for (int i = 2; i < n; i++) {
                dp[i] = BigInteger.valueOf(i + 1).multiply(dp[i - 1]);
            }
            System.out.println(dp[n - 1]);
        }else {
            System.out.println("Error");
        }
    }
}
编辑于 2022-03-17 22:12:34 回复(0)
Java就用biginteger类解决超大数据
import java.util.*;
import java.math.*;
public class Main{
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        if(n<1||n>200){
            System.out.print("Error");
        }else{
            BigInteger result=new BigInteger("1");
        for(int i=1;i<=n;i++) {
            result=result.multiply(new BigInteger(String.valueOf(i)));
        }
            System.out.print(result);
        }
    }
}


发表于 2022-08-25 17:38:24 回复(0)
字符串相乘
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
string multi(string s, string t) {
        int l1 = s.size();
        int l2 = t.size();

        if(l1 == 0 || l2 == 0) return "0";
        bool s_is_zero = true;
        bool t_is_zero = true;
        for(int i = 0;i < l1;i++)
            if(s[i] - '0' != 0) s_is_zero = false;
        for(int i = 0;i < l2;i++)
            if(t[i] - '0' != 0) t_is_zero = false;
        if(s_is_zero || t_is_zero) return "0";
        // write code here
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());

        vector<int> tmp(l1 + l2, 0);
        for(int i = 0;i < l1;i++)
        {
            for(int j = 0;j < l2;j++)
            {
                tmp[i + j] += (s[i] - '0') * (t[j] - '0');
            }
        }
        for(int i = 0;i < l1 + l2;i++)
        {
            if(tmp[i] < 0) continue;
            int carry = tmp[i] / 10;
            tmp[i] %= 10;
            tmp[i+1] += carry;
        }
        string ret(l1 + l2, '0');
        reverse(tmp.begin(), tmp.end());
        for(int i = 0;i < l1 + l2;i++)
            ret[i] += tmp[i];
        if(ret.size() > 1 && ret[0] == '0')
            return ret.substr(1, ret.size()-1);
        if(ret.empty()) return "0";
        return ret;
}

int main()
{
    int n;
    cin >> n;
    string ret = "1";
    for(int i = 2;i <= n;i++)
    {
        ret = multi(ret, to_string(i));
    }
    cout << ret << endl;
    return 0;
}


发表于 2022-06-22 10:35:05 回复(0)
答案返回字符串就可以防止溢出
while(line = readline()){
    const n = parseInt(line)
    if( n < 1 || n > 200) print('Error')
    else fn(n)
}
function fn(n){
    let res = n.toString()
    n--
    while(n > 1){
        const ans = []
        let len = res.length - 1
        while(len >= 0){
            ans.unshift( parseInt(res[len]) * n )
            len--
        }
        res = numberString(ans)
        n--
    }
    console.log(res)
}
function numberString(ans){
    const n = ans.length
    let res = '', cur = 0
    for(let i = n-1; i >= 0; i--){
        const current = parseInt(ans[i])
        cur += current
        const c = cur % 10
        if(c == cur) cur = 0
        else cur = (cur - c)/10
        res = c + res
    }
    if(cur !== 0) res = cur + res
    return res
}



发表于 2022-02-21 16:26:30 回复(0)
n =int(input())
ns =1
fori inrange(1,n+1):
    ns =ns *i
print(ns)
发表于 2022-08-25 16:25:47 回复(0)
如果不使用第三方库的话,可以考虑使用链表来做,比如100 * 28就对应链表【0 -> 0 -> 1】 * 【8 -> 2】,用竖式计算更新链表节点得到一个新的链表。最后通过dfs从尾到头记录链表数据。
import java.io.*;
import java.math.BigDecimal;
import java.util.*;

public class Main {
    static class Node{ //链表
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n < 1 || n > 200) {
            System.out.println("Error");
        } else {
            System.out.println(fun(n));
        }
    }


    public static String fun(int n) {
        Node node = getNode(1); // 将整型转换为链表
        for (int i = 2; i <= n; i++) {
            node = mutil(node, getNode(i));
        }
        StringBuilder builder = new StringBuilder();
        dfs(node, builder);
        return builder.toString();
    }

    public static void dfs(Node node, StringBuilder builder) { // 从链表尾部记录节点值
        if (node == null) {
            return;
        }
        dfs(node.next, builder);
        builder.append(node.val);
    }

    public static Node getNode(int n) { // 将整型转换为链表,125 转换为 5 -> 2 -> 1
        Node faker = new Node(0);
        Node temp = faker;
        while (n != 0) {
            temp.next = new Node(n % 10);
            temp = temp.next;
            n /= 10;
        }
        return faker.next;
    }

    public static Node mutil(Node a, Node b) { // 链表相乘
        Node faker = new Node(0);
        Node head = faker;
        Node temp = faker;
        Node tempA = a;
        Node tempB = b;
        int c = 0;
        while (true) {
            if (tempB == null) {
                break;
            }
            while (true) {
                if (tempA == null) {
                    if (c != 0) {
                        if (temp.next == null) {
                            temp.next = new Node(c);
                        } else {
                            temp.next.val += c;
                        }
                    }
                    break;
                }
                if (temp.next == null) {
                    temp.next = new Node(0);
                }
                int t = tempA.val * tempB.val + temp.next.val + c;
                temp.next.val = t % 10;
                c = t / 10;
                tempA = tempA.next;
                temp = temp.next;
            }
            head = head.next;
            temp = head;
            tempB = tempB.next;
            tempA = a;
            c = 0;
        }
        return faker.next;
    }

}


发表于 2022-08-25 11:25:37 回复(0)
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;
import java.math.BigDecimal;
/**
 * acm模式模板
 *
 * @author Key
 * @date 2022/03/01/18:56
 **/
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 输入1.0:直接获取输入
        int n = sc.nextInt();

        if (n  200) {
            bw.write("Error\n");
            bw.flush();
        } else {
            BigDecimal res = getRes(n);

            bw.write(res.toString() + "\n");
            bw.flush();
        }

    }
    /**
     * 核心代码
     */
   private static BigDecimal getRes(int n) {
        BigDecimal nVal = new BigDecimal(n + "");
        if (n == 1) {
            return nVal;
        }
        return nVal.multiply(getRes(n - 1));
    }
}
发表于 2022-08-25 10:15:12 回复(0)
import java.util.*;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solution(n));
    }
    
    public static BigInteger solution(int n) {
        BigInteger x = BigInteger.valueOf(1);
        BigInteger y = BigInteger.valueOf(2);
        BigInteger z = BigInteger.ZERO;
        for(int i = 1; i < n ; i ++) {
            z = x.multiply(y);
            x = z;
            y = y.add(BigInteger.valueOf(1));
        }
        return x;
    }
}
提供一种新思路
编辑于 2022-08-24 23:20:49 回复(0)
import java.util.Scanner;
import  java.util.Arrays;
import java.math.BigInteger;

public class Main {
public static BigInteger memo[];
       public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        memo=new BigInteger[n+1];
        //Arrays.fill(memo,-1);

        BigInteger r=dp(n);
        System.out.println(r);




    }

    static BigInteger dp(int n){
        if(n<1){
            return BigInteger.valueOf(1);
        }
        //base case
        memo[1]=BigInteger.valueOf(1);

        // 重叠子问题
        memo[n]=BigInteger.valueOf(n).multiply(dp(n-1));
        return memo[n];

    }

}

发表于 2022-08-07 20:31:53 回复(0)
n=int(input())
ifn>=1andn<=200:
    sum_new=1
    fori inrange(1,n+1):
        sum_new=sum_new*i
    print(sum_new)
else:
    print('Error')
发表于 2022-07-19 22:48:48 回复(0)
package main

import (
	"fmt"
	"strconv"
)

func atoi(a byte) int {
	return int(a - byte('0'))
}

func itoa(a int) byte {
	return byte(a + '0')
}

func add(a, b string) string {
	if a[0] == '0' {
		return b
	}
	if b[0] == '0' {
		return a
	}
	ans := []byte{}
	n, m := len(a)-1, len(b)-1
	jinwei := 0
	for n >= 0 && m >= 0 {
		tempSum := atoi(a[n]) + atoi(b[m]) + jinwei
		curr := tempSum % 10
		jinwei = tempSum / 10
		ans = append(ans, itoa(curr))
		n--
		m--
	}
	for n >= 0 {
		tempSum := atoi(a[n]) + jinwei
		curr := tempSum % 10
		jinwei = tempSum / 10
		ans = append(ans, itoa(curr))
		n--
	}
	for m >= 0 {
		tempSum := atoi(b[m]) + jinwei
		curr := tempSum % 10
		jinwei = tempSum / 10
		ans = append(ans, itoa(curr))
		m--
	}
	if jinwei > 0 {
		ans = append(ans, itoa(jinwei))
		m--
	}

	newAns := []byte{}
	for i := len(ans) - 1; i >= 0; i-- {
		newAns = append(newAns, ans[i])
	}
	return string(newAns)

}

func mul(a, b string) string {
	if len(a) > len(b) {
		return mul(b, a)
	}
	n, m := len(a), len(b)
	ans := "0"
	for i := n - 1; i >= 0; i-- {
		jinwei := 0
		tempAns := []byte{}
		for j := m - 1; j >= 0; j-- {
			currAns := atoi(a[i])*atoi(b[j]) + jinwei
			curr := currAns % 10
			jinwei = currAns / 10
			tempAns = append(tempAns, itoa(curr))
		}
		if jinwei != 0 {
			tempAns = append(tempAns, itoa(jinwei))
		}
		newAns := []byte{}
		for k := len(tempAns) - 1; k >= 0; k-- {
			newAns = append(newAns, tempAns[k])
		}
		for k := i; k < n-1; k++ {
			newAns = append(newAns, '0')
		}
		ans = add(ans, string(newAns))
	}

	return ans
}

func calcuate(N int) (sum string) {
	var i int = 1
	sum = "1"
	for ; i <= N; i++ {
		sum = mul(sum, strconv.Itoa(i))
	}
	return
}

func main() {
	var N int = 0
	fmt.Scan(&N)
	if 1 <= N && N <= 200 {
		ans := calcuate(N)
		fmt.Println(ans)
	} else {
		fmt.Println("Error")
	}
}

发表于 2022-05-09 17:30:47 回复(0)
package main

import (
	"fmt"
	"math/big"
)

func main() {
	n := int64(0)
	fmt.Scanln(&n)
	if n < 1 || n > 200 {
		fmt.Println("Error")
		return
	}
	res := big.NewInt(1)
	for n > 0 {
		res = res.Mul(big.NewInt(n), res)
		n--
	}
	fmt.Println(res)
}

发表于 2022-04-02 15:31:38 回复(0)
利用字符串乘法解决大数溢出的问题
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int k=scanner.nextInt();
        StringBuilder ans=new StringBuilder("1");
        if(k>200){
            System.out.println("Error");
        }
        for(int i=2;i<=k;i++){
             multiply(ans,i);
        }
        System.out.println(ans);
        
    }
    static void multiply(StringBuilder ans,int k){
        int jw=0;
        for(int i=0;i<ans.length();i++){
            int tmp=(ans.charAt(ans.length()-i-1)-'0')*k;
            ans.replace(ans.length()-i-1,ans.length()-i,(""+((tmp+jw)%10)));
            if(jw+(tmp%10)>=10){
                jw=tmp/10+(jw+(tmp%10))/10;
            }else{
                jw=tmp/10;
            }
        }
        if(jw!=0){
            ans.insert(0,""+jw);
        }
    }
}
发表于 2022-03-31 16:11:07 回复(1)

GO 手写大整数乘法和打印,用int slice 分段存储

package main
import "fmt"
 
 
func main(){
    var n int
    fmt.Scanf("%d",&n)
    if n>200 || n<1{
        fmt.Println("Error")
        return
    }
    result := []int{1}
    for i:=2;i<=n;i++{
        result = times(result,i)
    }
    // fmt.Println(result)
    printNum(result)
     
}
const MAXTIMES = 100000000
func printNum(num []int){
    // 打印最高段
    fmt.Print(num[len(num)-1]);
    for i:=len(num)-2;i>-1;i--{
        fmt.Printf("%08d",num[i])
    }
 
}
func times(num []int,n int ) ( []int){
    carry :=0
    for i:=0;i<len(num);i++{
        num[i] *=n
        num[i]+=carry
        carry = num[i]/MAXTIMES
        num[i]%=MAXTIMES
    }
    if carry!=0{
        num = append(num,carry)
    }
    return num
}


发表于 2022-03-18 20:38:16 回复(0)
importjava.math.BigInteger;
importjava.util.Scanner;
 
 
publicclassMain {
 
    publicstaticvoidmain(String[] args) {
        Scanner sc = newScanner(System.in);
        inti = sc.nextInt();
        f(i);
    }
 
   
    privatestaticvoidf(inti) {
        if( i < 1|| i > 201){
            System.out.println("Error");
            return;
        }
        BigInteger sum = BigInteger.valueOf(i);
        BigInteger temp;
        for(intj = i-1; j > 1; j--) {
            temp = BigInteger.valueOf(j);
            sum = temp.multiply(sum);
        }
        System.out.println(sum.toString());
    }
}
用bigInter就可以防止溢出了,开始用int、long数字大了会溢出

发表于 2022-03-09 10:50:19 回复(0)
写的代码比较丑陋,给大伙参考下
import java.util.*;
 
public class Main{
     
    public static void main(String[] args){
         
        Scanner sc = new Scanner(System.in);
         
        int[] ans = new int[500];
        int N = sc.nextInt();
        if( N < 1 || N > 200 ){
            System.out.println("Error");
            return ;
        }
         
        ans[0]=1;
        int end = cnm(ans,N,0);
         
        StringBuilder sb = new StringBuilder();
        for(int i = end ; i >= 0 ; i--){
            sb.append(ans[i]);
        }
        System.out.println(sb.toString());
    }
     
    public static int cnm(int[] array,int x,int end){
        int aa=0;
        for(int j = 2;j <= x ; j++){
            aa=0;
            for(int i=0;i<end + 1 ;i++){
                array[i]=array[i] * j;
                array[i]+=aa;
                aa=array[i] / 10 ;
                array[i]=array[i] % 10;
            }
            array[end+1]=aa;
            while(array[end+1] != 0 ){
                end++;
                while(array[end] >= 10) {
                    array[end + 1]+=array[end] / 10 ;
                    array[end] = array[end] % 10;
                    end++;
                }
            }
        }
        return end;
    }
}

发表于 2022-02-25 03:44:06 回复(0)
from  functools import *


@lru_cache
def func(x):
    if x==1:
        return 1
    else:
        return func(x-1)*x
    
n=int(input())
print(func(n))
    

发表于 2022-01-10 15:03:25 回复(0)