USACO - 3.2.1 - Factorials

 

原创文章转载请注明出处

摘要：动态规划

一. 题目翻译

1. 描述：

你的任务是找到阶乘最后面的非零位。

举个例子: 5!=1*2*3*4*5=120所以5!的最后面的非零位是2

7!=1*2*3*4*5*6*7=5040，所以最后面的非零位是4

2. 格式：

          INPUT FORMAT:

          共一行，一个不大于4,220的正整数N

          OUTPUT FORMAT:

          共一行，输出N!最后面的非零位。

3. SAMPLE：

          SAMPLE INPUT:

7

          SAMPLE OUTPUT:

4

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

  题目可以直接模拟，与编程之美当中计算阶乘末位有几个零的题目类似。可以采用大致相同的方法。

          思路是先从输入的序列当中去除乘积为10的所有数，然后将剩余的所有数相乘，取最后一位即为答案。在进行这个计算时不必保留所有的结果，只需保留个位继续相乘就可以了。

 

2. 具体实现（具体实现过程中出现的问题）：

          计算乘积为10的所有数，主要分为两个部分，计算出是5的倍数的所有数，以及计算出是2的倍数的所有数。将这些数从数组中移除。

          令一种思路是计算出数组当中所有数含有多少个5的因数（例如5含有一个5的因数，25含有两个5的因数）并移除，然后从数组中移除相同数量的2的因数（因为2的因数的个数必然大于5的因数的个数）。   

3.  启示:

         比较巧的是刚看完编程之美就做了这道题目，编程之美当中与数字相关的一章写的比较好，大家可以参考一下。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:fact4
*/
package session_3_2_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class fact4 {

	
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
//		Scanner in = new Scanner(new BufferedReader(new FileReader(
//		"fact4.in")));
//		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
//		"fact4.out")));
		
		int size = in.nextInt();
		int[] nums = new int[size+1];
		for (int i=1;i<=size;i++){
			nums[i] = i;
		}
		//计算出所有数字当中5的因子个数，并从相应数字当中消除
		int divide5 = 0;
		for (int i=1;i<=size;i++){
			while (nums[i]%5==0){
				nums[i]/=5;
				divide5++;
			}
		}
		
		//按照5的因子的个数，从数字中消除同等的2的因子的个数
		for (int i=1;i<=size&&divide5>0;i++){
			while (nums[i]%2==0){
				nums[i]/=2;
				divide5--;
				if (divide5==0){
					break;
				}
			}
		}
		
		//计算最后一位，累乘数组中的所有数字，只需保留最后一位既可以
		int result = 1;
		for (int i=1;i<=size;i++){
			result = nums[i]*result;
			result = result%10;
		}
		
		pw.println(result);
		pw.close();
	}

}