Dirichlė principo skaičiuoklė
Paskirstykite n elementų į k dėžių ir sužinokite, ką Dirichlė principas garantuoja apie pilniausią dėžę.
At least this many items must share one box (ceil(10 / 3))
- 1
Items ÷ boxes
10 ÷ 3 = 3,3333The raw average — how many items each box would hold if distributed perfectly evenly. - 2
Guaranteed minimum in fullest box
⌈10 ÷ 3⌉ = 4
Kaip veikia ši skaičiuoklė?
Dirichlė principas garantuoja, kad paskirstant n elementų į k dėžių pilniausia dėžė priverstinai turi laikyti bent ceil(n / k) elementų. Kad garantuotai kuri nors dėžė pasiektų m elementų, reikia bent k·(m − 1) + 1 elementų. Tai blogiausio atvejo tikrumai, galiojantys kiekvienam galimam išdėstymui.
Formulė
How this is calculated
Įveskite n, elementų skaičių, ir k, dėžių skaičių. Kad ir kaip gudriai paskirstytumėte elementus, pilniausia dėžė turi turėti bent ceil(n / k) elementų – tai Dirichlė (skylučių) principas. Jei skirstote tolygiai, kiekviena dėžė laiko floor(n / k), o likusios n − k·floor(n / k) dėžės gauna vieną papildomą elementą, ir būtent todėl maksimumas apvalinamas aukštyn.
Tikslinė įvestis m atsako į atvirkštinį klausimą: kiek elementų reikia padėti, kol garantuotai kuri nors dėžė laikys bent m iš jų. Blogiausiu atveju kiekviena dėžė užpildoma m − 1 elementais nepasiekiant m, iš viso k·(m − 1); dar vienas elementas, k·(m − 1) + 1, priverčia m-tąjį elementą patekti į kurią nors dėžę. Tai mažiausias skaičius, garantuojantis tikslą nepriklausomai nuo išdėstymo.
Visos įvestys traktuojamos kaip neneigiami sveikieji skaičiai ir viduje suapvalinamos žemyn, todėl trupmeniniai įvedimai apvalinami žemyn. Dėžių skaičius k turi būti bent 1, kad būtų išvengta dalybos iš nulio, o tikslas m turi būti bent 1, kad priverstinis skaičius būtų apibrėžtas. Rezultatai yra garantijos apie blogiausią atvejį, o ne tipiško ar atsitiktinio paskirstymo prognozės.
Dažnai užduodami klausimai
Jei kiekviena dėžė laikytų mažiau nei ceil(n / k) elementų, visuma būtų mažesnė už n, o tai prieštaravimas. Todėl bent viena dėžė turi pasiekti aukštyn suapvalintą vidurkį.
Reikia k·(m − 1) + 1. Blogiausiu atveju kiekvienoje dėžėje yra m − 1 elementų nepasiekiant m; vienas papildomas elementas turi priversti kurią nors dėžę pasiekti m.
Ne. Dirichlė principas yra blogiausio atvejo garantija, galiojanti bet kuriam paskirstymui, kad ir kaip elementai būtų išdėstyti.
Taip pat žinomas kaip
TG we-Calculate Editorial Team. (2026). Dirichlė principo skaičiuoklė [Online calculator]. TG we-Calculate. https://we-calculate.com/lt/calculator/pigeonhole-principle-calculator
TG we-Calculate Editorial Team. "Dirichlė principo skaičiuoklė." TG we-Calculate. 2026. https://we-calculate.com/lt/calculator/pigeonhole-principle-calculator.
TG we-Calculate Editorial Team, "Dirichlė principo skaičiuoklė," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/lt/calculator/pigeonhole-principle-calculator
@misc{wecalculate_pigeonhole_principle_calculator, title = {Dirichlė principo skaičiuoklė}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/lt/calculator/pigeonhole-principle-calculator}}, year = {2026}, note = {TG we-Calculate} }
Ar ši skaičiuoklė jums padėjo?