Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

5–маъруза: Индикаторли тасодифий миқдор. Хизматчи ёллаш ҳақидаги масалани индикаторли тасодифий миқдорлар ёрдамида таҳлили
Режа:

1. 
   Индикаторли тасодифий миқдор;
   
2. 
   Хизматчи ёллаш ҳақидаги масалани индикаторли тасодифий миқдорлар ёрдамида таҳлили;
   
3. 
   Мавзуга доир масалалар ечиш;
   

Кўпҳадларни ҳисоблашнинг аҳамияти. Қуйидаги умумий кўпҳадларнинг турини оламиз.
р(х)=а_пх^п+a_n-1x^n-1+ а_п-2х^п-2 +… а₂х² + а₁х + а₀.
Тахмин қиламизки , . . ., нинг ҳамма коэффициэнти аниқ, доимий ва массивга ёзилган. Бу шуни англатадики кўпҳадларни хисоблаш учун ягона кирувчи маълумот сифатида х ҳисобланади, дастур натижаси эса х нуқтасидаги кўпҳадларнинг аҳамияти ҳисобланади .
Стандарт алгоритм тўғри чизиқли :
Evaluate(х)
х // кўпҳаднинг аҳамиятини ҳисоблаш нуқтаси.
result=a[0] + a[1]*х
xPower=x
for i=2 to n do
xPower=xPower*x
result=result+a[i]*xPower
end for
return result
Бу алгоритм мутлақо шаффоф ва унинг таҳлили аниқ. For циклида иккита кўпайтириш мавжуд, бунда n – 1 марта бажарилади. Бундан ташқари бир кўпайтириш циклдан олдин бажарилади. Шу сабабли кўпайтиришлар умумий сони 2n – 1. Циклда битта қўшув бажарилади. Яна битта қўшув циклдан олдин бажарилади. Шу сабабли қўшувлар умумий сони n.
Горнер схемаси.
Горнер схемаси орқали ҳисоблаш самаралироқ, бунда у мураккаблашмайди. Ушбу чизма кўпҳаднинг қуйидаги кўринишига асосланган:
р(х) = ((... ((а_пх+a_n-1)x+а_п-₂)х+…+ а₂)х+а₁)х +a₀.
Китобхон ушбу кўринишни айнан ўша кўпҳад бераётганини осон текширади. Тегишли алгоритм қуйидаги кўринишга эга :
HornersMethod(x)
х // кўпҳаднинг аҳамиятини ҳисоблаш нуқтаси.
for i=n-1down to 0 do
result=result*x
result=result+a[i]
end for
return result
Цикл n марта бажарилади, бунда цикл ичида битта кўпайтириш қўшиш берилган. Шу сабабли Горнер схемаси орқали ҳисоблаш n кўпайтиришларни талаб этади – стандарт алгоритмларга нисбатан кўпайтиришлар сони икки марта камроқ.