首页 > 代码库 > 带分数计算程序思路
带分数计算程序思路
思路一
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之间所有的素数,如果分子分母同时可以整数则约分,直到化成最简分数
带分数计算程序思路