Approximation of a common divisor closest to some value?
Say we have two numbers (not necessarily integers) x1 and x2 . Say, the user inputs a number y . What I want to find, is a number y' close to y so that x1 % y' and x2 % y' are very small (smaller than 0.02 , for example, but lets call this number LIMIT ). In other words, I don't need an optimal algorithm, but a good approximation.
I thank you all for your time and effort, that's really kind!
Let me explain what the problem is in my application : say, a screen size is given, with a width of screenWidth and a height of screenHeight (in pixels). I fill the screen with squares of a length y' . Say, the user wants the square size to be y . If y is not a divisor of screenWidth and/or screenHeight , there will be non-used space at the sides of the screen, not big enough to fit squares. If that non-used space is small (eg one row of pixels), it's not that bad, but if it's not, it won't look good. How can I find common divisors of screenWidth and screenHeight ?
I don't see how you can ensure that x1%y' and x2%y' are both below some value - if x1 is prime, nothing is going to be below your limit (if the limit is below 1) except x1 (or very close) and 1.
So the only answer that always works is the trivial y'=1.
If you are permitting non-integer divisors, then just pick y'=1/(x1*x2), since the remainder is always 0.
Without restricting the common divisor to integers, it can be anything, and the whole 'greatest common divisor' concept goes out the window.
x1 and x2 are not very large, so a simple brute force algorithm should be good enough.
Divide x1 and x2 to y and compute floor and ceiling of the results. This gives four numbers: x1f , x1c , y1f , y1c .
Choose one of these numbers, closest to the exact value of x1/y (for x1f , x1c ) or x2/y ( for y1f , y1c ). Let it be x1f , for example. Set y' = x1/x1f . If both x1%y' and y1%y' are not greater than limit , success ( y' is the best approximation). Otherwise add x1f - 1 to the pool of four numbers (or y1f - 1 , or x1c + 1 , or y1c + 1 ), choose another closest number and repeat.
You want to fit the maximum amount of evenly spaced squares inside a fixed area. It's possible to find the optimal solution for your problem with some simple math.
Lets say you have a region with width = W and height = H, and you are trying to fit squares with sides of length = x. The maximum number of squares horizontaly and verticaly, that I will call max_hor and max_vert respectively, are max_hor=floor(W/x) and max_vert=floor(H/x) . If you draw all the squares side by side, without any spacement, there will be a rest in each line and each column. Lets call the horizontal/vertical rests respectively by rest_w and rest_h. This case is illustrated in the figure below:
Note that rest_w=W-max_horx and rest_h=H-max_vertx.
What you want is divide rest_w and rest_h equaly, generating small horizontal and vertical spaces of sizes space_w and space_h like the figure below:
Note that space_w=rest_w/(max_hor+1) and space_h=rest_h/(max_vert+1).
Is that the number you are looking for?
链接地址: http://www.djcxy.com/p/10458.html上一篇: 初始化C结构时的术语
下一篇: 逼近一个最接近某个值的公约数？