编写一段程序,用于计算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; } }