JAVA特性 大数阶乘 难度系数 ★.

Presentation on theme: "JAVA特性 大数阶乘 难度系数 ★."— Presentation transcript:

1 JAVA特性 大数阶乘 难度系数 ★

2 大数阶乘 输入不超过1000的正整数n，输出 n!=1×2×3×…×n的精确结果。 样例输入：30
样例输出：

3 较小数的阶乘程序 #include <stdio.h> int main() { int i, n, product=1;
scanf("%d", &n); for(i=1; i<=n; i++) product = product * i; printf("%d\n", product); return 0; } import java.util.Scanner; public class P209_Basic { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int i, n, product=1; n = cin.nextInt(); for(i=1; i<=n; i++) product = product * i; System.out.printf("%d\n", product); }

4 从小数阶乘到大数阶乘 import java.math.BigInteger; import java.util.Scanner;
public class P209 { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int i, n = cin.nextInt(); BigInteger product = BigInteger.ONE; for (i=1; i<=n; i++) product =product.multiply(BigInteger.valueOf(i)); System.out.println(product); } import java.util.Scanner; public class P209_Basic { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int i, n, product=1; n = cin.nextInt(); for(i=1; i<=n; i++) product = product * i; System.out.printf("%d\n", product); }

5 JAVA特性 棋盘放麦子 2012年 预赛 难度系数 ★

6 棋盘放麦子 你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，问他要什么报酬，大臣说：请在第1个棋盘格放1粒麦子，在第2个棋盘格放2粒麦子，在第3个棋盘格放4粒麦子，在第4个棋盘格放8粒麦子，……后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有64格）。 国王以为他只是想要一袋麦子而已，哈哈大笑。 当时的条件下无法准确计算，但估算结果令人吃惊：即使全世界都铺满麦子也不够用！ 请你借助计算机准确地计算，到底需要多少粒麦子。

7 答案算好了吗？

8 组合数 从4个人中选2个人参加活动，一共有6种选法。从n个人中选m个人参加活动，一共有多少种选法？下面的函数实现了这个功能。
int f(int n, int m) { if(m>n) return 0; if(m==0) _______________; return f(n-1,m-1) + _____________; }

9 递归 全排列 方法 《算法竞赛入门经典》 难度系数 ★★

10 3和4的全排列 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 全排列数 f(n)=n!

11 关键：递归函数的定义 定义： void print_permutation(int n, int A[], int cur)
使用： print_permutation(6, A, 0); n个数字进行排列，结果放置在数组Ａ中。 从 cur 这个位置开始放置数字，直到n个数字全部完成排列。 1 2 3 4 5 cur

12 递归的套路 int fac(int n) /* 计算n的阶乘*/ { if(n==0||n==1) return 1;
return fac(n-1)*n; } 终止条件； 自己做点事，剩下的让别人去做吧

13 全排列的递归算法 1 2 3 4 5 cur void print_permutation(int n, int A[], int cur)
{ int i, j; if (cur==n) { // 递归边界 for (i=0; i<n; i++) printf("%d ", A[i]); printf("\n"); return; } for (i=1; i<=n; i++) { // 尝试在A[cur]中填各种整数i int ok = 1; for (j=0; j<cur; j++) if (A[j]==i) ok = 0; // 如果i已经在A[0]～A[cur-1]出现过，则不能再选 if (ok==1) { A[cur] = i; print_permutation(n, A, cur+1); 1 2 3 4 5 cur

14 数字 i 是否可以放在 cur 位置 #include <stdio.h> int main() {
int A[6] = {3,2,4,0,0,0}; int i, j, cur, ok=1; scanf("%d", &i); cur = 3; for (j=0; j<cur; j++) if (A[j]==i) ok = 0; printf((ok==1)?"Yes\n":"No\n"); return 0; } 1 2 3 4 5 cur