[原创]有趣的问题：埃及分数

Mrzeng

以下是引用FantasyDR在2005-5-29 14:25:41的发言：

飘来，插个嘴：

以前看过一本叫《数学史》的书，描述各种民族的计数方法。其中就说了埃及人的这种诡异的表示分数的方法-_-b

貌似埃及数学家脑子很灵的，精通于分数的拆解。传说还有专门的计算理论，莫非就是埃及的数学教科书……

～～～飘走～～～

鬼啊..!怎么飘来飘去的..!?

我们老师也讲到这个问题,我怎么也想不通...但是看到这里了...十窍终于通了九窍啦!!!!

天若有情

埃及人运用加倍程序与单位分数概念进行计算.........................

总之用单位分数就是为了实现分数的四则运算(虽然很麻烦)

你把三分之二的求出来再说吧....()^_^

活活

关于分数运算的类,写过,不拿出来现丑了

Eastsun

问题一的代码：

1. #include<stdio.h>
   
2. void solve(int a,int b) //a/b
   
3. {
   
4. int t,tb;
   
5. printf("%d/%d=",a,b);
   
6. while(1){
   
7.   if(b%a==0) break;
   
8.   t=b/a+1;
   
9.   tb=b*t;
   
10.   a=t*a-b;
    
11.   b=tb;
    
12.   printf("1/%d+",t);
    
13. }
    
14. printf("1/%d\n",b/a);
    
15. }
    
16. int main()
    
17. {
    
18. int a,b;
    
19. scanf("%d%d",&a,&b);
    
20. if(a<b) solve(a,b);
    
21. return 0;
    
22. }

复制代码

说明：这是一个“贪心”算法。

         对于一个给定的分数a/b,如果b%a==0，这说明a/b已经可以化简为1/x的形式了。

         否则，我们先找这样的一个1/x，使它尽可能接近a/b。显然 b/a+1就是满足条件的数。

         输出1/x,再继续对a/b-1/x进行上述操作。。。

loglave

Eastsun 有没有参加acm？

jason

呵呵～Eastsun不愧是数学系的啊！呵呵～对数学这么有兴趣……

tian7

  acm  ？？？
汗啊，我看了看我们学校的acm，光是英文题目读就读不懂，还怎么编啊
[em06][em06][em06]

loglave

我也是看不懂，一般是队友看题目，然后我来写的[em07]

Eastsun

以下是引用loglave在2005-5-28 17:17:30的发言：

Eastsun 有没有参加acm？

我这个学期才知道有ACM这回事，有参加的想法，正在开始学习有关的东东。。。
ps：那些英语题目。。。我每次都拿着WQX，边看题边查单词。。。郁闷啊。。。

Eastsun

第二题的代码：

1. #include<stdio.h>
   
2. #include<string.h>
   
3. const int maxdepth=100;
   
4. int   depth=0,min,cmdepth;  //depth:当前搜索深度－1,min:以求解中最后一个分母值,cmdepth:当前最大搜索深度
   
5. int   ans[maxdepth],out[maxdepth];  //ans :temp data,out:..
   
6. void find(int a,int b,int x)  //a/b, 1/x
   
7. {
   
8. if(depth>=cmdepth||x>=min) return;  
   
9. if(b%a==0){
   
10.   b/=a;
    
11.   if(b<x||b>=min) return;
    
12.   ans[depth]=b;
    
13.   min=b;
    
14.   memcpy(out,ans,(depth+1)*sizeof(int));
    
15.   return;
    
16. }
    
17. else{
    
18.   if(depth>=cmdepth-1)  return;
    
19.   while(a*x<=b&&x<min) x++;
    
20.   while(x<min){
    
21.    if(a*x>=b*(cmdepth-depth)) break;
    
22.    ans[depth]=x;
    
23.    depth++;
    
24.    find(a*x-b,b*x,x+1);
    
25.    depth--;
    
26.    x++;
    
27.   }
    
28. }
    
29. return;
    
30. }
    
31. int main()
    
32. {
    
33. int a,b;
    
34.   scanf("%d%d",&a,&b);
    
35.   min=1000000;
    
36.         for(cmdepth=1;cmdepth<=maxdepth;cmdepth++){
    
37.    find(a,b,1);
    
38.    if(min<1000000) break;
    
39.   }
    
40.   for(int k=0;k<cmdepth-1;k++) printf("%d ",out[k]);
    
41.   printf("%d\n",out[cmdepth-1]);
    
42. return 0;
    
43. }

复制代码

用的是所谓的IDA*搜索算法。。。

FantasyDR

飘来，插个嘴：
以前看过一本叫《数学史》的书，描述各种民族的计数方法。其中就说了埃及人的这种诡异的表示分数的方法-_-b
貌似埃及数学家脑子很灵的，精通于分数的拆解。传说还有专门的计算理论，莫非就是埃及的数学教科书……
～～～飘走～～～

天若有情

终于找到数学系的同胞了
但三分之二...........

天若有情

TO 10楼：数学史就是数学的历史
传说还有专门的计算理论，莫非就是埃及的数学教科书……真幽默

Eastsun

以下是引用天若有情在2005-5-31 17:57:53的发言：

终于找到数学系的同胞了

但三分之二...........

没有弄明白你想问什么。。。
2/3=1/2+1/6

天若有情

三分之二在古埃及"不能分"为单位分数和
因为有了三分之二这个分数:总之用单位分数就是为了实现分数的四则运算
所以把三分之二的求出来就失去单位分数的本来作用了(上当了吧^_^)
活活

FantasyDR

没有看懂楼上的话……能不能写的言简意赅一些^_^b
2/3可以分的啊？

leesoft

1/3+1/4+1/12

天若有情

我并不是说三分之二不可以分.
从单位分数的起源和作用来看:
三分之二就是一个"单位分数"
因为单位分数的诞生就是为了
四则运算,而反三分之二看作
单位分数的话,运算很简单,不然
很多问题会复杂化的

FantasyDR

是啊，单位分数的提出就是为了作分数四则运算。
不过，2/3不是单位分数，因为埃及人的单位分数定义不适和2/3。
至于他们在具体运算的时候，想必肯定又很多简化的方法，不可能死板的按照这些来运算的啦～

亚森罗宾

（从地下冒出来：）
最近在研究诡辩论，搞得逻辑有些混乱了。凭良心说那些诡辩家真能牵着人的思维走。
3人去餐馆吃饭，每人出了10元，共30元。老板说今天优惠只收25，于是让服务员把5元退给三个人，服务员私自藏了2元，然后剩下的3元每人退了一元。也就是说每人出了10-1=9元，而三个人3*9+服务员私藏的2元=29元，而三个人明明出了30元啊，还有1元呢~
我看着看着想着想着就被绕进去了。
[em04]
（又钻回地下）~

FantasyDR

虽然跑题了，不过楼上的这个诡辩命题太老了。
三个人少出的钱要从老板退的钱里面算，是1.666666元不是1元啊-_-b
也就是1又2/3，又是一个2/3……