埃及分数问题（贪心算法）

一、问题描述

把一个真分数表示成最少的埃及分数之和。

埃及分数即分子为1的分数。例如    7/8=1/2+1/3+1/24;

1.判断这个分数是不是埃及分数

2.形成1/2 1/3 1/4 ........1/n

3.fn=fn+1-1/n

4.fn==0 ?

代码

//埃及分数问题
#include
#include
struct FS{int a;int b;
};
int is_aijifs(FS* f);
FS simple(FS* f);
int gcd(FS* f);
int main(){FS f;int m=2;printf("请输入分子分母，以空格隔开！\n");scanf("%d%d",&f.a,&f.b);printf("%d/%d=",f.a,f.b);while(1){if(is_aijifs(&f)){printf("%d/%d",f.a,f.b);break;}while(1.0*f.a/f.b<1.0*1/m)   m++;printf("1/%d+",m);f.a=f.a*m-1*f.b;f.b=f.b*m;//printf("%d %d",f.a,f.b);f=simple(&f);//    printf("%d %d",f.a,f.b);}return 0;
}
int is_aijifs(FS* f){if(f->a==1) return 1;return 0;
}
FS simple(FS* f){int g=gcd(f);f->a=f->a/g;f->b=f->b/g;//printf("   %d\n",f->a);return *f;//有问题
}
int gcd(FS* f){FS f1;f1=*f;int r;while(1){r=f1.a%f1.b;f1.a=f1.b;f1.b=r;//printf("    %d\n",r);if(r==0) return f1.a;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！