首页 > ACM题库 > HDU-杭电 > HDU 1141 Factstone Benchmark-动态规划-[解题报告] C++
2013
11-28

HDU 1141 Factstone Benchmark-动态规划-[解题报告] C++

Factstone Benchmark

问题描述 :

Amtel has announced that it will release a 128-bit computer chip by 2010, a 256-bit computer by 2020, and so on, continuing its strategy of doubling the word-size every ten years. (Amtel released a 64-bit computer in 2000, a 32-bit computer in 1990, a 16-bit computer in 1980, an 8-bit computer in 1970, and a 4-bit computer, its first, in 1960.)
Amtel will use a new benchmark – the Factstone – to advertise the vastly improved capacity of its new chips. The Factstone rating is defined to be the largest integer n such that n! can be represented as an unsigned integer in a computer word.Given a year 1960 ≤ y ≤ 2160, what will be the Factstone rating of Amtel’s most recently released chip?

There are several test cases. For each test case, there is one line of input containing y. A line containing 0 follows the last test case. For each test case, output a line giving the Factstone rating.

样例输入:

1960
1981
0

样例输出:

3
8

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1141

题意:atmel公司1960年发布4bits的处理器,每10年翻一番。给一个年份,问最近一次发布的处理器能运算的n!最大的n是多少。

mark:最大的处理器位数是2160年的4194304bits。要算n!的二进制表示位,直接算很难,可以变成求log2后取整加1。然后因为log2(n!) = log2(1) + log2(2)…+log2(n),所以直接O(n)就可以了。大概算到30w可以把500wbits的算出来,之后按输入二分。

代码:

# include <stdio.h>
# include <math.h>

int dp[300010] ;

void init()
{
    int i ;
    double sum = 0 ;
    for (i = 2 ; i <= 300000 ; i++)
    {
        sum += log2(i*1.0) ;
        dp[i] = ((int)sum) + 1 ;
    }
}

int main ()
{
    int n, l, r, mid ;
    init() ;
    while (~scanf ("%d", &n), n)
    {
        n = 1 << ((n-1940) / 10) ;
        l = 1, r = 300000 ; 
        while (l<r-1)
        {
            mid = (l+r)/2 ;
            if (dp[mid] < n) l = mid ;
            else r = mid ;
        }
        if (dp[r] == n) l = r ;
        printf ("%d\n", l) ;
    }
    return 0 ;
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。