随手写的小程序 很小很实用, 尤其是在压片的时候计算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 |
可以用 Stern-Brocot tree,除去大数运算部分复杂度是对数级的
赞算法帝 我是算法白…
Python就是简练,一个eval()完事
要是C还要慢慢写个栈……
呵呵, 用Python写小工具成本特低, 挺合适的:)
第一个适合用gcd来解;第二个可以直接构造,不需要慢慢迭代
假设有小数 a.bcdef,可以转换为 abcdef / 100000,求gcd,可化简成 m : n,这时m和n可能不在所需范围内,然后将两数中较大的缩小到所需范围,然后另一个按比例缩小,最后取整,至多再在附近找一两个数比较一下。
“在附近找一两个数比较一下” 这个可以证明是最优解吗?
可以,就像 y = -Ax^2 + Bx + C,差不多是个倒U形,但是最高点不一定是整数,所以需要在附近取整。
比如 0.987654321 在10000 内, 可否举例说明一下怎样寻找?
我的程序算出来的结果应该是 80:81, 没有更接近的了
之前的回帖好像有错,没有经过仔细考虑,是不能证明的那个方法有效的,只是通过这种方式能够以很小的代价找到比较近似的解。
连分数就是对实数r作如下操作得到数列{a_n}:
a_n = [r] (取整)
r = 1/(r-a_n)
n++
谢谢..
Ps: 贴代码可以用<#pre lang="c"><#/pre>去掉井号这对标签
效果类似:
不知道对不对
int gcd(int a,int b) {
register int c;
for(;b;c=b,a=a%c,b=c)
;
return(a);
};
这个gcd还是挺启发我的:)
int gcd(int a, int b) {
return a%b==0?b:gcd(b,a%b);
}
第二个可以用连分数的吧
额,这个我不是很懂 0.0
不会也可以二分,这个+1算法算怎么回事…
不会也可以二分,这个算法算怎么回事…
只是简单实现功能了…
主要现在是用在算sar的地方,最大也就几千分之几千,也够用了
来访拉 记得回访啊! 呵呵
早安。我是推特上的 @mlusa ~
学习了……话说我python总是看得懂一些看不懂一些的呃……
其实..我觉得py的语言特性极其简单了,看不懂的应该是逻辑结构(数据结构/算法)吧?这是所有语言通用的东西 ^_^