齐肯多夫定理

/*
齐肯多夫定理表示任何正整数都可以表示成若干个不连续的斐波那契数之和。这种和式称为齐肯多夫表述法。
对于任何正整数,其齐肯多夫表述法都可以用贪心算法选出每回最大可能的斐波那契数。
*/
#include <stdio.h>
#include <memory>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <time.h>
#include <limits>
using namespace std;
#define ull unsigned long long
#define ll long long
#define N 100
ll fab[N], out[N];
int fn;
void init(){
 int i;
 ull inf = 0x7fffffffffffffff;
 ull a;
 fab[0] = 1;
 fab[1] = 2;
 for(i = 2; ; i++){
  a = fab[i-1] + fab[i-2];
  if(a > inf) break;
  fab[i] = a;
 }
 fn = i;
}
int find(ll* fab, int l, int r, ll k){
 int mid;
 while(l <= r){
  mid = (l + r) >> 1;
  if(fab[mid] <= k) l = mid + 1;
  else r = mid - 1;
 }
 return l - 1;
}
void Zeckendorf(ll a){
 if(a <= 0){
  printf("%lld=%lld\n", a, a);
  return;
 }
 ll a0 = a;
 int k = 0, i;
 while(a0 > 0){
  i = find(fab, 0, fn - 1, a0);
  out[k++] = fab[i];
  a0 -= fab[i];
 }
 printf("%lld=", a);
 for(i = 0; i < k-1; i++) printf("%lld+", out[i]);
 printf("%lld\n", out[i]);
}
int main(){
#ifndef ONLINE_JUDGE
 //freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
#endif 
 init();
 ll a;
 while(~scanf("%lld", &a)){
  Zeckendorf(a);
 }
 return 0;
}

 

 

posted on 2011-01-18 15:42 tw 阅读(336) 评论(0)  编辑 收藏 引用 所属分类: Math Theory


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿

文章分类

文章档案

搜索

最新评论