首页 > ACM题库 > HDU-杭电 > HDU 4814-Golden Radio Base-数学相关-[解题报告]HOJ
2015
09-18

HDU 4814-Golden Radio Base-数学相关-[解题报告]HOJ

Golden Radio Base

问题描述 :

Golden ratio base (GRB) is a non-integer positional numeral system that uses the golden ratio (the irrational number (1+√5)/2 ≈ 1.61803399 symbolized by the Greek letter φ) as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, phi-nary.

Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" �C this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ ― most notably that φ + 1 = φ 2 . For instance, 11(φ) = 100(φ). Despite using an irrational number base, when using standard form, all on-negative integers have a unique representation as a terminating (finite) base-φ expansion. The set of numbers which possess a finite base-φ representation is the ring Z[1 + √5/2]; it plays the same role in this numeral systems as dyadic rationals play in binary numbers, providing a possibility to multiply.

Other numbers have standard representations in base-φ, with rational numbers having recurring representations. These representations are unique, except that numbers (mentioned above) with a terminating expansion also have a non-terminating expansion, as they do in base-10; for example, 1=0.99999….

Coach MMM, an Computer Science Professor who is also addicted to Mathematics, is extremely interested in GRB and now ask you for help to write a converter which, given an integer N in base-10, outputs its corresponding form in base-φ.

输入:

There are multiple test cases. Each line of the input consists of one positive integer which is not larger than 10^9. The number of test cases is less than 10000. Input is terminated by end-of-file.

输出:

There are multiple test cases. Each line of the input consists of one positive integer which is not larger than 10^9. The number of test cases is less than 10000. Input is terminated by end-of-file.

样例输入:

1
2
3
6
10

样例输出:

1
10.01
100.01
1010.0001
10100.0101
Hint
Hard Code

题意:

把一个10进制数变成 x进制数  x = (1+√5)/2


思路:

比赛时候就被无理数进制吓傻了  其实完全没必要  因为 n = n * 1 = n * x^0

由于x的0次幂等于1   所以完全可以把n当成对应的x进制数的个位  现在要做的就是把这个数转化成二进制

题目给出的公式可以在两边同时乘x的若干次幂  那么这两个式子就变成了

x^(i+1) + x^i = x^(i+2)

2 * x^i = x^(i+1) + x^(i-2)

通过这两个式子不停的去变换数字  直到数字不再变了就停下来输出


代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100

int a[N*2];
int n,u,v;

int main()
{
    int i,k,flag;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        a[N]=n;
        do
        {
            flag=0;
            for(i=0;i<N*2-2;i++)
            {
                if(a[i]&&a[i+1])
                {
                    k=min(a[i],a[i+1]);
                    a[i]-=k;
                    a[i+1]-=k;
                    a[i+2]+=k;
                    flag=1;
                }
            }
            for(i=2;i<N*2-1;i++)
            {
                if(a[i]>1)
                {
                    k=a[i]/2;
                    a[i]%=2;
                    a[i-2]+=k;
                    a[i+1]+=k;
                    flag=1;
                }
            }
        }while(flag);
        for(u=2*N-1;u>N&&!a[u];u--);
        for(v=0;v<N&&!a[v];v++);
        for(i=u;i>=N;i--) printf("%d",a[i]);
        if(v!=N)
        {
            printf(".");
            for(i=N-1;i>=v;i--) printf("%d",a[i]);
        }
        printf("\n");
    }
    return 0;
}

参考:http://blog.csdn.net/houserabbit/article/details/36036903