Как определить самые близкие значения, кратные X?

Question

У меня есть список значений 8820, распространяемых в интервале [0, 1[. Таким образом, 1/8820 * t, с t [0,8820[. Список первых 500 значений будет:

0 0 
1 0.000113379 
2 0.000226757 
3 0.000340136 
4 0.000453515 
5 0.000566893 
6 0.000680272 
7 0.000793651 
8 0.000907029 
9 0.00102041 
10 0.00113379 
11 0.00124717 
12 0.00136054 
13 0.00147392 
14 0.0015873 
15 0.00170068 
16 0.00181406 
17 0.00192744 
18 0.00204082 
19 0.0021542 
20 0.00226757 
21 0.00238095 
22 0.00249433 
23 0.00260771 
24 0.00272109 
25 0.00283447 
26 0.00294785 
27 0.00306122 
28 0.0031746 
29 0.00328798 
30 0.00340136 
31 0.00351474 
32 0.00362812 
33 0.0037415 
34 0.00385488 
35 0.00396825 
36 0.00408163 
37 0.00419501 
38 0.00430839 
39 0.00442177 
40 0.00453515 
41 0.00464853 
42 0.0047619 
43 0.00487528 
44 0.00498866 
45 0.00510204 
46 0.00521542 
47 0.0053288 
48 0.00544218 
49 0.00555556 
50 0.00566893 
51 0.00578231 
52 0.00589569 
53 0.00600907 
54 0.00612245 
55 0.00623583 
56 0.00634921 
57 0.00646259 
58 0.00657596 
59 0.00668934 
60 0.00680272 
61 0.0069161 
62 0.00702948 
63 0.00714286 
64 0.00725624 
65 0.00736961 
66 0.00748299 
67 0.00759637 
68 0.00770975 
69 0.00782313 
70 0.00793651 
71 0.00804989 
72 0.00816327 
73 0.00827664 
74 0.00839002 
75 0.0085034 
76 0.00861678 
77 0.00873016 
78 0.00884354 
79 0.00895692 
80 0.00907029 
81 0.00918367 
82 0.00929705 
83 0.00941043 
84 0.00952381 
85 0.00963719 
86 0.00975057 
87 0.00986395 
88 0.00997732 
89 0.0100907 
90 0.0102041 
91 0.0103175 
92 0.0104308 
93 0.0105442 
94 0.0106576 
95 0.010771 
96 0.0108844 
97 0.0109977 
98 0.0111111 
99 0.0112245 
100 0.0113379 
101 0.0114512 
102 0.0115646 
103 0.011678 
104 0.0117914 
105 0.0119048 
106 0.0120181 
107 0.0121315 
108 0.0122449 
109 0.
110 0.0124717 
111 0.012585 
112 0.0126984 
113 0.0128118 
114 0.0129252 
115 0.0130385 
116 0.0131519 
117 0.0132653 
118 0.0133787 
119 0.0134921 
120 0.0136054 
121 0.0137188 
122 0.0138322 
123 0.0139456 
124 0.014059 
125 0.0141723 
126 0.0142857 
127 0.0143991 
128 0.0145125 
129 0.0146259 
130 0.0147392 
131 0.0148526 
132 0.014966 
133 0.0150794 
134 0.0151927 
135 0.0153061 
136 0.0154195 
137 0.0155329 
138 0.0156463 
139 0.0157596 
140 0.015873 
141 0.0159864 
142 0.0160998 
143 0.0162132 
144 0.0163265 
145 0.0164399 
146 0.0165533 
147 0.0166667 
148 0.01678 
149 0.0168934 
150 0.0170068 
151 0.0171202 
152 0.0172336 
153 0.0173469 
154 0.0174603 
155 0.0175737 
156 0.0176871 
157 0.0178005 
158 0.0179138 
159 0.0180272 
160 0.0181406 
161 0.018254 
162 0.0183673 
163 0.0184807 
164 0.0185941 
165 0.0187075 
166 0.0188209 
167 0.0189342 
168 0.0190476 
169 0.019161 
170 0.0192744 
171 0.0193878 
172 0.0195011 
173 0.0196145 
174 0.0197279 
175 0.0198413 
176 0.0199546 
177 0.020068 
178 0.0201814 
179 0.0202948 
180 0.0204082 
181 0.0205215 
182 0.0206349 
183 0.0207483 
184 0.0208617 
185 0.0209751 
186 0.0210884 
187 0.0212018 
188 0.0213152 
189 0.0214286 
190 0.021542 
191 0.0216553 
192 0.0217687 
193 0.0218821 
194 0.0219955 
195 0.0221088 
196 0.0222222 
197 0.0223356 
198 0.022449 
199 0.0225624 
200 0.0226757 
201 0.0227891 
202 0.0229025 
203 0.0230159 
204 0.0231293 
205 0.0232426 
206 0.023356 
207 0.0234694 
208 0.0235828 
209 0.0236961 
210 0.0238095 
211 0.0239229 
212 0.0240363 
213 0.0241497 
214 0.024263 
215 0.0243764 
216 0.0244898 
217 0.0246032 
218 0.0247166 
219 0.0248299 
220 0.0249433 
221 0.0250567 
222 0.0251701 
223 0.0252834 
224 0.0253968 
225 0.0255102 
226 0.0256236 
227 0.025737 
228 0.0258503 
229 0.0259637 
230 0.0260771 
231 0.0261905 
232 0.0263039 
233 0.0264172 
234 0.0265306 
235 0.026644 
236 0.0267574 
237 0.0268707 
238 0.0269841 
239 0.0270975 
240 0.0272109 
241 0.0273243 
242 0.0274376 
243 0.027551 
244 0.0276644 
245 0.0277778 
246 0.0278912 
247 0.0280045 
248 0.0281179 
249 0.0282313 
250 0.0283447 
251 0.028458 
252 0.0285714 
253 0.0286848 
254 0.0287982 
255 0.0289116 
256 0.0290249 
257 0.0291383 
258 0.0292517 
259 0.0293651 
260 0.0294785 
261 0.0295918 
262 0.0297052 
263 0.0298186 
264 0.029932 
265 0.0300454 
266 0.0301587 
267 0.0302721 
268 0.0303855 
269 0.0304989 
270 0.0306122 
271 0.0307256 
272 0.030839 
273 0.0309524 
274 0.0310658 
275 0.0311791 
276 0.0312925 
277 0.0314059 
278 0.0315193 
279 0.0316327 
280 0.031746 
281 0.0318594 
282 0.0319728 
283 0.0320862 
284 0.0321995 
285 0.0323129 
286 0.0324263 
287 0.0325397 
288 0.0326531 
289 0.0327664 
290 0.0328798 
291 0.0329932 
292 0.0331066 
293 0.03322 
294 0.0333333 
295 0.0334467 
296 0.0335601 
297 0.0336735 
298 0.0337868 
299 0.0339002 
300 0.0340136 
301 0.034127 
302 0.0342404 
303 0.0343537 
304 0.0344671 
305 0.0345805 
306 0.0346939 
307 0.0348073 
308 0.0349206 
309 0.035034 
310 0.0351474 
311 0.0352608 
312 0.0353741 
313 0.0354875 
314 0.0356009 
315 0.0357143 
316 0.0358277 
317 0.035941 
318 0.0360544 
319 0.0361678 
320 0.0362812 
321 0.0363946 
322 0.0365079 
323 0.0366213 
324 0.0367347 
325 0.0368481 
326 0.0369615 
327 0.0370748 
328 0.0371882 
329 0.0373016 
330 0.037415 
331 0.0375283 
332 0.0376417 
333 0.0377551 
334 0.0378685 
335 0.0379819 
336 0.0380952 
337 0.0382086 
338 0.038322 
339 0.0384354 
340 0.0385488 
341 0.0386621 
342 0.0387755 
343 0.0388889 
344 0.0390023 
345 0.0391156 
346 0.039229 
347 0.0393424 
348 0.0394558 
349 0.0395692 
350 0.0396825 
351 0.0397959 
352 0.0399093 
353 0.0400227 
354 0.0401361 
355 0.0402494 
356 0.0403628 
357 0.0404762 
358 0.0405896 
359 0.0407029 
360 0.0408163 
361 0.0409297 
362 0.0410431 
363 0.0411565 
364 0.0412698 
365 0.0413832 
366 0.0414966 
367 0.04161 
368 0.0417234 
369 0.0418367 
370 0.0419501 
371 0.0420635 
372 0.0421769 
373 0.0422902 
374 0.0424036 
375 0.042517 
376 0.0426304 
377 0.0427438 
378 0.0428571 
379 0.0429705 
380 0.0430839 
381 0.0431973 
382 0.0433107 
383 0.043424 
384 0.0435374 
385 0.0436508 
386 0.0437642 
387 0.0438776 
388 0.0439909 
389 0.0441043 
390 0.0442177 
391 0.0443311 
392 0.0444444 
393 0.0445578 
394 0.0446712 
395 0.0447846 
396 0.044898 
397 0.0450113 
398 0.0451247 
399 0.0452381 
400 0.0453515 
401 0.0454649 
402 0.0455782 
403 0.0456916 
404 0.045805 
405 0.0459184 
406 0.0460317 
407 0.0461451 
408 0.0462585 
409 0.0463719 
410 0.0464853 
411 0.0465986 
412 0.046712 
413 0.0468254 
414 0.0469388 
415 0.0470522 
416 0.0471655 
417 0.0472789 
418 0.0473923 
419 0.0475057 
420 0.047619 
421 0.0477324 
422 0.0478458 
423 0.0479592 
424 0.0480726 
425 0.0481859 
426 0.0482993 
427 0.0484127 
428 0.0485261 
429 0.0486395 
430 0.0487528 
431 0.0488662 
432 0.0489796 
433 0.049093 
434 0.0492063 
435 0.0493197 
436 0.0494331 
437 0.0495465 
438 0.0496599 
439 0.0497732 
440 0.0498866 
441 0.05 
442 0.0501134 
443 0.0502268 
444 0.0503401 
445 0.0504535 
446 0.0505669 
447 0.0506803 
448 0.0507937 
449 0.050907 
450 0.0510204 
451 0.0511338 
452 0.0512472 
453 0.0513605 
454 0.0514739 
455 0.0515873 
456 0.0517007 
457 0.0518141 
458 0.0519274 
459 0.0520408 
460 0.0521542 
461 0.0522676 
462 0.052381 
463 0.0524943 
464 0.0526077 
465 0.0527211 
466 0.0528345 
467 0.0529478 
468 0.0530612 
469 0.0531746 
470 0.053288 
471 0.0534014 
472 0.0535147 
473 0.0536281 
474 0.0537415 
475 0.0538549 
476 0.0539683 
477 0.0540816 
478 0.054195 
479 0.0543084 
480 0.0544218 
481 0.0545351 
482 0.0546485 
483 0.0547619 
484 0.0548753 
485 0.0549887 
486 0.055102 
487 0.0552154 
488 0.0553288 
489 0.0554422 
490 0.0555556 
491 0.0556689 
492 0.0557823 
493 0.0558957 
494 0.0560091 
495 0.0561224 
496 0.0562358 
497 0.0563492 
498 0.0564626 
499 0.056576  
... 

(это просто code, порождающие этот список):

double tick8820 = 1/8820.; 
double counter = 0.; 

for(int i = 0; i < 8820; i++) { 
    cout << i << " " << counter << endl; 

    counter += tick8820; 
} 

как бы вы identificate в ближайшие значения кратные 1/96? Например, первые 6 множественным будет перехвачена на:

0 0 
92 0.0104308 
184 0.0208617 
276 0.0312925 
368 0.0417234 
459 0.0520408 

Обратите внимание, что выбирает 459, а не 460, так как:

459: 0.0520408 // closest 
5/96: 0.0520833 
460: 0.0521542 

Я получил эти значения один за другим (и я знаю, что следующий будет при t + 1/8820), поэтому мне нужно проверить, является ли текущий кандидат правильным или нет при его обработке.

Answer 1

Это зависит от вашего приложения. Если вы собираетесь использовать эти сгенерированные значения, тогда подход грубой силы будет следующим: Ввод всех ваших значений 8821 в отсортированный array и использование на нем lower_bound.

Например, если вы положили все свои ценности в array<double, 8821> foo то ваш элемент, содержащий ваш результат в: lower_bound(cbegin(foo), cend(foo), 1.0/96.0) Вы можете увидеть живой пример этого здесь: http://ideone.com/4Y8bWg

EDIT:

Самый простой способ найти эти числа - сделать это, не генерируя ни одного из значений для заполнения foo. Давайте поговорим об математическом способе, которым это может быть достигнуто. Мы просто пытаемся найти числитель, назовем его x более 8820, так что значение фракции в точности равно или больше 1/96. Это позволяет нам решить уравнение:

Так что мы действительно хотим является неотъемлемой х больше или равна 2280/96 мы можем использовать ceil сделать: ceil(2280.0/96.0). Когда это число будет разделено на 2280, вы получите свою ценность.

Live Example