编写一段程序,用于计算200以内正整数的阶乘
要求: 不允许使用任何第三方库。
# 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;
} 动态规划思想:
状态转移方程:
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");
}
}
}
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);
}
}
} #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;
} 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
} 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;
}
} 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));
}
}
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;
}
}
提供一种新思路
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];
}
}
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")
}
}
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
} 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数字大了会溢出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;
}
}