面试题 -算法？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

面试题 -算法？

面试题 -算法？# Programming - 葵花宝典

N*Y2007-07-17 07:07

1 楼

面试题 - 算法？
input 4 positive integers p1, q1, p2, q2, where p1/q1 < p2/q2
output, positive integers p0 and q0
s.t. p1/q1 < p0/q0 and for any positive integer q, 0 < q < q0 and any integer p
either p/q < p1/q1 or p2/q2 < p/q

k*f2007-07-17 07:07

2 楼

先定出q0，
q0是满足1/q0 > p2/q2-p1/q1的最大的一个。
然后p0就是 p1/q1*q0 和 p2/q2*q0中唯一的整数。

【在 N*******Y 的大作中提到】

: 面试题 - 算法？
: input 4 positive integers p1, q1, p2, q2, where p1/q1 < p2/q2
: output, positive integers p0 and q0
: s.t. p1/q1 < p0/q0 : and for any positive integer q, 0 < q < q0 and any integer p
: either p/q < p1/q1 or p2/q2 < p/q

N*Y2007-07-17 07:07

3 楼

how ?
why?
若p1=99, q1=200, p2=101, q2=200
你的意思是
q0是99？
若p1=99, q1=200, p2=101, q2=200
q0=99
p1/q1*q0 = 49.005
p2/q2*q0 = 49.995
p1/q1*q0 和 p2/q2*q0中没有整数?

【在 k****f 的大作中提到】

: 先定出q0，
: q0是满足1/q0 > p2/q2-p1/q1的最大的一个。
: 然后p0就是 p1/q1*q0 和 p2/q2*q0中唯一的整数。