随手写的小程序 很小很实用, 尤其是在压片的时候计算sar值等方面.
第一个: 化简分数
样例输入1: 16/12
样例输出1: 4 : 3样例输入2: 16*480/(9*704)
样例输出2: 40 : 33恩, 简单说来, 就是化任意分数为最简分数
第二个: 小数化分数
给一个范围,用范围内的数组成分数,并使这个分数的值最接近所给的小数(如样例给的是1-100和1-1000的范围)
样例输入1: 3.1415926535897 100
样例输出1: 22 : 7样例输入2: 3.1415926535897 1000
样例输出2: 355 : 113
以下是全部代码:
第一个:
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
第二个:
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" a3<t:="" a1+="1" elif="">t:
a2+=1
else:
break
a3 = gcd(mina1,mina2)
print mina1/a3,":",mina2/a3
</b+1>
可以用 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的语言特性极其简单了,看不懂的应该是逻辑结构(数据结构/算法)吧?这是所有语言通用的东西 ^_^