hdu4814 模拟（黄金分割进制转换）

题意：

给你一个十进制数，让你把他转化成Q进制数，Q是黄金分割比 = (1+√5)/2.

思路：

首先要明确的就是虽然q是实数，但是依然可以转换成q进制数，因为任何数num,都有 num = num * 1 => num = num * q^0,先把所有的数字都放在各位，然后在根据题目的要求吧他转化成所有的数字都是0或者1，不能有两个连续的1，首先题目给了我们两个式子，经过简单转化就能得到这两个式子

Q^n = Q^(n-1) + Q^(n-2)

2*Q^n = Q^(n+1) + Q^(n-2)

这样对于全都转换成0，1，我们可以先把所有的数字num都放在个位，然后在根据

2*Q^n = Q^(n+1) + Q^(n-2)把大于1的数字分解，一直分解到所有数字小于等于1

对于连续的11我们可以Q^n = Q^(n-1) + Q^(n-2)分解连续的1，有一点要注意的就是这两个处理要同时做，因为分解11可能会产生大于1的数字，所以两个一起弄（一起的意思就是while(!ok){处理问题1;处理问题2;}），直到所有的都满足条件就行了。

#include<stdio.h>

#include<string.h>



int main ()

{

   int ans[105] ,i ,j;

   int n;

   while(~scanf("%d" ,&n))

   {

      memset(ans ,0 ,sizeof(ans));

      ans[50] = n;

      int mk = 1;

      while(mk)

      {

         mk = 0;

         for(i = 2 ;i <= 100 ;i ++)

         {

            if(ans[i] > 1)

            {

               ans[i+1] += ans[i] / 2;

               ans[i-2] += ans[i] / 2;

               ans[i] %= 2;

               mk = 1;

            }

         }

         for(i = 1 ;i <= 100 ;i ++)

         if(ans[i] && ans[i+1])

         {

            int tmp = ans[i] < ans[i+1] ? ans[i] : ans[i+1];

            ans[i] -= tmp;

            ans[i+1] -= tmp;

            ans[i+2] += tmp;

         }

      }

      int st ,et;

      for(i = 100 ;i >= 1 ;i --)

      if(ans[i]) {st = i;break;}

      for(i = 1 ;i <= 100 ;i ++)

      if(ans[i]) {et = i ;break;}

      for(i = st ;i >= et ;i --)

      {

         if(i == 49)printf(".");

         printf("%d" ,ans[i]);

      }

      puts("");

   }

   return 0;

}

巴特西

hdu4814 模拟（黄金分割进制转换）

最新文章

热门文章