c++ - 如何识别 X 的最接近值倍数？

Question

我有一个分布在区间 [0, 1[ 中的 8820 个值的列表。因此，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.0123583
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;
}

您将如何确定 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

编辑:

找到这些数字的最简单方法是在不生成任何值来填充 foo 的情况下这样做.让我们谈谈实现这一目标的数学方法。我们实际上只是想找到一个分子，我们称它为 x 超过 8820，这样分数值正好等于或大于 1/96。这让我们可以求解方程:

因为我们真正想要的是大于或等于 2280/96 的整数 x 我们可以使用 ceil 要做:ceil(2280.0 / 96.0) .当这个数字除以 2280 时，您将得到您的值。

Live Example