首页 > ACM题库 > HDU-杭电 > hdu 2370 Convert Kilometers to Miles-贪心[解题报告]C++
2014
01-05

hdu 2370 Convert Kilometers to Miles-贪心[解题报告]C++

Convert Kilometers to Miles

问题描述 :

This year, Bruce Force spends his vacation in Flagstaff, Arizona, where he wants to practice for his next half marathon (a race over 21 km). At his first training he runs to his friend Greedy Gonzales’ home which is 21 miles away from Flagstaff.Arriving there, he is very tired and realizes that 21 miles are much more than 21 km. Greedy Gonzales tells him that 21 km equals 13 miles. 21, 13? Bruce realizes immediately that there must be a deeper relation! Both, 13 and 21 are Fibonacci numbers!

Fibonacci numbers can be defined as follows:

F1 = 1
F2 = 2
Fn+1 = Fn+Fn-1 for n>1.

Bruce has just learned about the Fibonacci number system at his university. Each positive integer x can be written as the sum of different Fibonacci numbers, so this means that there exists numbers k and b1, b2, …, bk such that x = ∑i=1..k bi * Fi, where bk = 1 and bi (1 ≤ i < k) is either 0 or 1. In short, we can write the representation as: b(x) = (bk, bk-1, …, b1). To make the representation unique, we require that bi * bi-1 = 0 for all i > 1.

For example 21 can be represented as (1,0,0,0,0,0,0) and 13 as (1,0,0,0,0,0) in the Fibonacci system. Bruce notices that one can convert a distance x in kilometers into a corresponding distance y to miles as follows: First, write down x in its Fibonacci system representation b(x). Second, shift the bits of b(x) one position to the right (the last bit is deleted) and get b(y). Third, calculate y from b(y) by evaluating the sum given above.

For example, the number 42 written in the Fibonacci system is (1,0,0,1,0,0,0,0). In step two we would shift the bits one position to the right and get (1,0,0,1,0,0,0). In the third step, we would calculate 0*1 + 0*2 + 0*3 + 1*5 + 0*8 + 0*13 + 1*21 = 26.

Now it’s your turn to write a program for Bruce that converts kilometers into miles according to Bruce’s algorithm.

输入:

The first line of the input contains t, the number of distances Bruce wants to convert from kilometers to miles (0<t<25000). Each of the next t lines contains an integer distance x (2 < x < 25000) in kilometers.

输出:

The first line of the input contains t, the number of distances Bruce wants to convert from kilometers to miles (0<t<25000). Each of the next t lines contains an integer distance x (2 < x < 25000) in kilometers.

样例输入:

5
42
100
180
300
360

样例输出:

26
62
111
185
222


题意:一个数字可以表示成若干个fibonacci数的和。求表示成fib后“右移”1位的数字。

mark:打表前30个fib数,然后用贪心法可算出任何数字的fib数表示形式,再累加。

代码:

# include <stdio.h>
# include <string.h>


int fib[35] = {1,1} ;
int tab[35] ;


void init()
{
    int i ;
    for (i = 2 ; i <= 30 ; i++)
        fib[i] = fib[i-1]+fib[i-2] ;
}


void set (int x)
{
    int i ;
    for (i = 25 ; i>= 1 ; i--)
        if (fib[i] <= x) tab[i] = 1, x -= fib[i] ;
}


int main ()
{
    int n, x, sum, i ;
    init() ;
    scanf ("%d", &n) ;
    while (n--)
    {
        scanf ("%d", &x) ;
        memset (tab, 0, sizeof(tab)) ;
        set(x) ;
        for (i = 2, sum = 0 ; i <= 30 ; i++)
            if (tab[i]) sum += fib[i-1] ;
        printf ("%d\n", sum) ;
    }
    
    return 0 ;
}

 


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.