首页 > 代码库 > 带分数计算程序思路

带分数计算程序思路

思路一

      1.  将带分数用正则表达式转换成整数+一个组合数的形式。 例如:   1+3*2^2/3-2 转换成  1+3*(2+2/3)-2

      2.  直接把结果算出来

      3.  将结果的小数部分转换成分数,也就是两个整数比的形式  例如 1.23423423  提取小数部分 0.23423423 后, 设计算法找出这2个整数。

      4.  最简单的算法是双重循环, for(i=0;i<10000;i++)for(j=0;j<100000;j++) ..... 但是这样复杂度太高,  可以用每一次内循环的结果,比大小后,确定下一次内循环的范围。

例如 0.23434432 <1/2  则范围在 0/2 - 1/2   而1/2 < 2/3  分母循环到3的时候, 分子只需要遍历 1/3 比大小后确定范围在  0 - 1/3    依次类推 接下来遍历 1/4  确定范围在 0 -1/4  .....  1/5 2/5 ......  这样可以将O(N^2)的复杂度降低到近似于O(N)。

缺点:  无法确定外循环要循环多少次才能找到结果, 结果可能不精确。

优点:  设计很简单

 

思路二:

     1. 将加减乘除的操作全部封装,操作数可以为整数也可以是分数,对应4种组合  例如 1/2+1  ->  3/2   1/4 + 1/6 -> 10/24

     2. 将原表达式转换成后缀表达式,便于计算

     4. 用栈的模型计算

     3. 计算后的结果先去掉整数部分,然后约分,设定一个大概的范围,比如100000, 然后遍历 2-100000之间所有的素数,如果分子分母同时可以整数则约分,直到化成最简分数 

    

带分数计算程序思路