首页 > 代码库 > ACM学习历程——HDU4814 Golden Radio Base（数学递推） （12年成都区域赛）
ACM学习历程——HDU4814 Golden Radio Base（数学递推） （12年成都区域赛）
Description
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" ? 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-φ.
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" ? 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-φ.
Input
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.
Output
For each test case, output the required answer in a single line. Note that trailing 0s after the decimal point should be wiped. Please see the samples for more details.
Sample Input
123610
Sample Output
110.01100.011010.000110100.0101
Hint
由于φ + 1 = φ 2，两边同乘φ k,得到φ k+1+φ k=φ k+2，说明只有有两位是1，就往前进一位。此外由φ + 1 = φ 2推到的2φ 2=φ 3+1，同理可知：φ k+3+φ k=2φ k+2，说明每一位的2都可以，由它前一位和它的后两位的1构成，这样就能将所有大于2的数降成1.再配合之前的，反复模拟便可得。由于当场没有估算这个数的长度，所以采用两个数组分别存了整数部分和小数部分。整体效率不是非常高，但是在短时间内做出来还是很高兴的。
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>#include <set>#include <map>#include <vector>#include <queue>#include <string>#define inf 0x3fffffff#define esp 1e-10#define N 100using namespace std;int z[N], x[N], lenz, lenx;bool judge (){ if(z[0] && x[0]) return 0; for (int i = 0; i < lenx; ++i) if (x[i] > 1 || (x[i] && x[i+1])) return 0; for (int i = 0; i < lenz; ++i) if (z[i] > 1 ||(z[i] ==1 && z[i+1] == 1)) return 0; return 1;}void doz (int i){ if (i == lenz-1) lenz++; int up = z[i] / 2; z[i] = z[i] & 1; z[i+1] += up; if (i >= 2) z[i-2] += up; else { if (lenx < 3 - i) lenx = 3 - i; x[1-i] += up; }}void dox (int i){ if (i+3 > lenx) lenx = i + 3; int up = x[i] / 2; x[i] = x[i] & 1; x[i+2] += up; if (i == 0) z[0] += up; else x[i-1] += up;}void qt (int n){ memset (z, 0, sizeof(z)); memset (x, 0, sizeof(x)); lenz = 1; lenx = 0; z[0] = n; while (!judge ()) { for (int i = lenx-1; i >= 0; --i) { if (i == 0 && x[i] > 0 && x[i+1] > 0) { int up = min (x[i], x[i+1]); z[0] += up; x[0] -= up; x[1] -= up; continue; } else if (x[i] > 0 && x[i+1] > 0) { int up = min (x[i], x[i+1]); x[i-1] += up; x[i+1] -= up; x[i] -= up; continue; } if (x[i] > 1) { dox (i); continue; } } while(x[lenx-1] == 0) lenx--; for (int i = 0; i < lenz; ++i) { if (i == 0 && z[i] > 0 && x[0] > 0) { if (i == lenz-1) lenz++; int up = min (z[i], x[0]); z[1] += up; z[0] -= up; x[0] -= up; continue; } else if (z[i] > 0 && z[i+1] > 0) { if (i+3 > lenz) lenz = i + 3; int up = min (z[i], z[i+1]); z[i+2] += up; z[i+1] -= up; z[i] -= up; continue; } if (z[i] > 1) { doz(i); continue; } } } while(x[lenx-1] == 0) lenx--;}int main(){ //freopen ("test.txt", "r", stdin); int n; while (scanf ("%d", &n) != EOF) { qt (n); for (int i = lenz - 1; i >= 0; --i) printf ("%d", z[i]); if (lenx > 0) printf ("."); for (int i = 0; i < lenx; ++i) printf ("%d", x[i]); printf ("\n"); } return 0;}
ACM学习历程——HDU4814 Golden Radio Base（数学递推） （12年成都区域赛）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。