两个算分数(比例)的小程序 [Python]

随手写的小程序 很小很实用, 尤其是在压片的时候计算sar值等方面.
第一个: 化简分数

1
2
样例输入1: 16/12
样例输出1: 4 : 3

1
2
样例输入2: 16*480/(9*704)
样例输出2: 40 : 33

恩, 简单说来, 就是化任意分数为最简分数

第二个: 小数化分数
给一个范围,用范围内的数组成分数,并使这个分数的值最接近所给的小数(如样例给的是1-100和1-1000的范围)

1
2
样例输入1: 3.1415926535897 100
样例输出1: 22 : 7

1
2
样例输入2: 3.1415926535897 1000
样例输出2: 355 : 113


以下是全部代码:
第一个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m
import sys
if len(sys.argv)<2:
    print "Enter the (num/num):",
    m = raw_input()
else:
    m = sys.argv[1]
k = m.split('/')
if len(k)<2:
    print "Input error!"
    sys.exit()
a1=eval(k[0])
a2=eval(k[1])
a3 = gcd(a1,a2)
print a1/a3,":",a2/a3

第二个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m
import sys
if len(sys.argv)<2:
    print "Enter the num and up:",
    m = raw_input()
else:
    m = " ".join(sys.argv[1:])
m=m.split()
if len(m)<2:
    print "Input error!"
    sys.exit()
b=int(m[1])
t=eval(m[0])
a1=1
a2=1
mina1=1
mina2=1
mindt=10000
while a1<b+1 and a2<b+1:
    a3=a1*1.0/a2
    if abs(a3-t)<mindt:
        mindt=abs(a3-t)
        mina1=a1
        mina2=a2
    if a3<t:
        a1+=1
    elif a3>t:
        a2+=1
    else:
        break
a3 = gcd(mina1,mina2)
print mina1/a3,":",mina2/a3

23 thoughts on “两个算分数(比例)的小程序 [Python]”

  1. 可以用 Stern-Brocot tree，除去大数运算部分复杂度是对数级的

    Reply

    1. 假设有小数 a.bcdef，可以转换为 abcdef / 100000，求gcd，可化简成 m : n，这时m和n可能不在所需范围内，然后将两数中较大的缩小到所需范围，然后另一个按比例缩小，最后取整，至多再在附近找一两个数比较一下。

      Reply

        1. 可以，就像 y = -Ax^2 + Bx + C，差不多是个倒U形，但是最高点不一定是整数，所以需要在附近取整。

          Reply

          1. 比如 0.987654321 在10000 内, 可否举例说明一下怎样寻找?
            我的程序算出来的结果应该是 80:81, 没有更接近的了

            Reply

            1. 之前的回帖好像有错，没有经过仔细考虑，是不能证明的那个方法有效的，只是通过这种方式能够以很小的代价找到比较近似的解。

              Reply

    1. 谢谢..
      Ps: 贴代码可以用<#pre lang="c"><#/pre>去掉井号这对标签
      效果类似:

      1
      2
      3
      4
      5
      6
      #include <stdio.h>
      int main(void)
      {
          printf("Hello world!\n");
          return 0;
      }

      Reply

  8. 早安。我是推特上的 @mlusa ~
    学习了……话说我python总是看得懂一些看不懂一些的呃……

    Reply

    1. 其实..我觉得py的语言特性极其简单了,看不懂的应该是逻辑结构(数据结构/算法)吧?这是所有语言通用的东西 ^_^

      Reply

Leave a Reply

Your email address will not be published.