设为首页 加入收藏

TOP

最后一个非零数字(POJ 1604、POJ 1150、POJ 3406)(一)
2019-06-11 12:08:21 】 浏览:68
Tags:最后 一个 数字 POJ 1604 1150 3406

      POJ中有些问题给出了一个长数字序列(即序列中的数字非常多),这个长数字序列的生成有一定的规律,要求求出这个长数字序列中某个位上的数字是多少。这种问题通过分析,找出规律就容易解决。

       例如,N!是一个非常大的数,其末尾有很多个0,如何求得其最后一个非零的数字?

  • N!的最后一个非零的数字

【例1】Just the Facts (POJ 1604)

Description

The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,

 N       N!

 0       1

 1       1

 2       2

 3       6

 4      24

 5     120

For this problem, you are to write a program that can compute the last non-zero digit of any factorial for (0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce "2" because 5! = 120, and 2 is the last nonzero digit of 120.

Input

Input to the program is a series of nonnegative integers not exceeding 10000, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.

Output

For each integer input, the program should print exactly one line of output. Each line of output should contain the value N, right-justified in columns 1 through 5 with leading blanks, not leading zeroes. Columns 6 - 9 must contain " -> " (space hyphen greater space). Column 10 must contain the single last non-zero digi

t of N!.

Sample Input

1

2

125

3125

9999

Sample Output

    1 -> 1

    2 -> 2

  125 -> 8

 3125 -> 2

 9999 -> 8

      (1)编程思路1。

      将N!求出来后再求最后一个非零数字是不可取的,因为10000!是个非常大的数。

      实际上,由于问题只需求得N!的最后一个非零的数字,因此在计算过程中,乘积结果末尾的0全部舍弃不会影响最后求得的结果。因为在循环计算阶乘,将上一次的乘积乘以下一个数时,上一次乘积末尾的0会全部加在下一次乘积的后面。另外,由于并不需要求出这个阶乘的值,只需得到最后一个非零的数字。因此每次相乘时,无需将舍弃掉末尾0后的乘积结果全部用来相乘(这样很容易产生溢出),而只需截取乘积结果后面几位进行下一步运算即可。

      注意,不能只保留最后一个非零的数字进行下一步运算。给两个简单的例子,14*15=210,而4*5=20。一个结果是1,另一个是2。125*18=2250,125*8=1000,25*8=200。32位整型数据可达到10位,而阶乘计算时的下一个数最多4 位,因此乘积结果截取舍弃掉末尾0后的后5位即可。小于5位不行,读者可以自己提交程序给POJ评判。

      由于在计算N!时,(N-1)!已经求出。因此可以在计算阶乘的过程中(循环i从2~10000),不断将当前i的阶乘的最后一个非零的数字保存到ans[i]中,构造好答案表。这样,问题的求解就变成查表了。

      (2)源程序1。

#include <iostream>  

using namespace std; 

int main() 

    int i,p,num; 

    int ans[10001]; 

 

    ans[0]=ans[1]=1; 

    p=1; 

    for (i = 2; i <=10000; i++)   // 构造答案表

       { 

         p *= i; 

         while (p%10 == 0)     // 去掉乘积末尾的0

              p=p/10; 

         p %= 100000;       

         ans[i] = p % 10;       // 得出结果   

&nbs
编程开发网

首页 上一页 1 2 3 4 5 6 7 下一页 尾页 1/9/9
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Example: Getting WMI Data from .. 下一篇POJ中和质数相关的三个例题(POJ ..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }