2 Лаборатория иши Шахсий компьютерларда маълумотларнинг таърифланиши, кодлаш

Мисол 2. a = 32, b = 12 бўлсин, унда

   НОД(32, 12) = НОД(32 – 12, 12) = НОД(20, 12) = НОД(20 – 12, 12) = НОД(8, 12) =

   = НОД(8, 12 – 8) = НОД(8, 4) = НОД(8 – 4, 4) = НОД(4, 4) = НОД(4 – 4, 4) = НОД(0, 4) = 4

Бу ҳисоблаш усули оптимал ҳисобланмайди.Масалан, НОД(1000000, 2)ни топиш учун 500000 ҳисоблаш операциясини бажариш керак бўлади. ЭУБ(НОД) ни ҳисоблашни тезроқ амалга ошириш учун айирма операциясини бўлинмадан қолган қолдиқни олишга алмаштирамиз:

Мисол 3. a = 78, b = 14. ,бўлсин, унда
НОД(78, 14) = НОД(78 mod 14, 14) = НОД(8, 14) = НОД(8, 14 mod 8) = НОД(8, 6) =

   = НОД(8 mod 6, 6) = НОД(2, 6) = НОД(2, 6 mod 2) = НОД(2, 0) = 2

Шартлар сонини иккига қисқартириш эвазига юқоридаги рекурентликни соддалаштирамиз:


Агар a < b, то НОД(a, b) = НОД(b, a mod b) = НОД(b, a), яъни функция аргументлари келтирилади. Кейинги функция чақирилишида ЭУБ(НОД) биринчи аргумент иккинчисидан катта бўлади. Фақат иккинчи аргумент b ноль бўлиши мумкин.

Мисол 4. a = 14, b = 78. бўлсин, унда

НОД(14, 78) = НОД(78, 14) = НОД(14, 8) = НОД(8, 6) = НОД(6, 2) = НОД(2, 0) = 2

Си дастурлаш тилида gcd (Greatest Common Divisor) функциясини реккурентликдан фойдаланган ҳолда ЭУБни ҳисоблашни амалга оширамиз.Бунда % белгиси Си да бўлишдан қолган қолдиқ операциясини олишни билдиради.

int gcd(int a, int b)

{

  if (b == 0) return a;

  return gcd(b, a % b);

}

Эслатиб ўтамиз, Си да шартли оператор қуйидаги синтаксисга эга :

if (<шартли ифода>) <ифода 1>; else <ифода 2>;

Агар (<шартли ифода>) рост бўлса, у ҳолда <ифода 1>; бажарилади, акс ҳолда <ифода 2>; бажарилади.

Тернар шартли оператори қуйидаги синтаксисга эга:

<шартли ифода > ? <ифода 1> : <ифода 2>;

Ва у семантик жиҳатдан оператор if..then..else дан фарқ қилади. Агар<шартли ифода > рост бўлса, у ҳолда оператор қийматни қайтаради, бунда <ифода 1> қайтади, акс ҳолда <ифода 2> қайтади.

Тернар оператордан фойдаланган ҳолда gcd функциясини қуйидагича ёзиш мумкин:

int gcd(int a, int b)

{

  return (!b) ? a : gcd(b, a % b);

}

Теорема. Иккита сони НОД ва НОК қуйидагиларни ўз ичига олади:

a · b = НОД(a, b) · НОК(a, b)

lcm (Lowest Common Multiple) ҳисоблаш функцияси НОК қуйидагиларни ўз ичига олади:

int lcm(int a, int b)

{

  return a / gcd(a, b) * b;

}

a * b / gcd(a, b) ифодасини ҳисоблашига аҳамият берсак, тўлишиш юзага келади, a / gcd(a, b) * b да эса келмайди. Бу ерда a, b и lcm(a, b) ифодаси int типининг чегарасида ётиши кўзда тутилади.

Оддий сонларнинг алгоритмини топиш

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Бу анча олдин, университетда Pascal дастурлаш тилини ўрганишга бошлаганимизда бўлган эди, уйга вазифа қилиб оддий сонларни топиш алгоритмини яратиш керак эди.

Алгоритмни Pascal тилидаги намунаси билан берамиз. Дастур фойдаланувчидан N сонини ва ҳамма содда сонларни N кирган ҳолда қидиришини сўрайди. Биринчи тестдан сўнг N= «кўп» ни киритиш умиди юзага келди. Дастур ишларди, аммо кутилгандан анча секин ишларди. Табиийки, буни сабаби кўп сонли текширишларда (N*N/2тартибида) эди, шунинг учун ортиқчаликдан халос қилинди. Натижада, бири бирига ўхшаш 5та алгоритм юзага келди ва улар бирига қараганда иккинчиси тезроқ ишларди. Буни Листинг 1 да кўрсатамиз.

# Листинг 1

# киритамиз N

n = input("n=")

# содда сонларни сақлаш учун бўш рўйхат яратамиз

lst = []

# ва k да бўлувчилар сонини сақлаймиз

k = 0

# 2 дан N гача бўлган сонларни босиб ўтамиз

for i in xrange(2, n+1):

# 2дан жорийгача бўлган сонларни босиб ўтамиз

for j in xrange(2, i):

# бўлувчилар сонини қидирамиз

if i % j == 0:

k = k + 1

# агар бўлувчи бўлмаса, сонни рўйхатга қўшамиз

if k == 0:

lst.append(i)

else:

k = 0

# рўйхатни экранга чиқарамиз

print lst

Тушунарлики, ҳар бир рақамни бўлувчисини санашга ҳеч қандай эғтиёж йўқ., шунинг учун k ўзгарувчини ўз вазифасидан озод қилиш мумкин. Ҳақиқатда, ҳеч бўлмаганда битта бўлувчи бўлса, бу рақам оддий бўлмайди.

Листинг 2 ни кўрамиз

# Листинг 2

n = input("n=")

lst = []

for i in xrange(2, n+1):

for j in xrange(2, i):

if i % j == 0:

# агар бўлувчи топилса,соддасон эмас.

break

else:

lst.append(i)

print lst

break конструкцияси ички циклни якунини ясашга ёрдам беради ва ташқи итерацияга ўтишга ёрдам беради.

Савол туғилади:” нега 4 га бўлиш керак, агар сон 2 га бўлинмаса?”. Шундай хулосага келамизки, бўлувчиларни бўлинмадан ошиб кетмайдиган содда сонлар орасидан қидириш керак.Бизнинг алгоритм Листинг 3 (га қаранг) га айланади.

# Листинг 3

n = input("n=")

lst=[]

for i in xrange(2, n+1):

# (lst) рўйхати бўйича содда сонларни босиб ўтамиз

for j in lst:

if i % j == 0:

break

else:

lst.append(i)

print lst

Сўнгра сонлар назариясини эслаймиз ва тушунамизки, шундай сонларни танлаймизки, у илдиздан ошиб кетмаслиги керак. Мисол учун, агар М сонини pi бўлувчиси бўлса, у ҳолда qi бўлувчиси бўладики, бунда pi * qi = M. Яъни, ўхшашини топиш учун, кичигини топиш керак. Ҳамма ўхшашликлар орасида, кўрилган максимал кичик ўхшашлик - pi и qi га тенг бўлган ўхшашлик, яъни pi * pi = M => pi = sqrt(M). Листинг 4 ни кўрамиз.

# Листинг 4

from math import sqrt

n = input("n=")

lst=[]

for i in xrange(2, n+1):

for j in lst:

if j > int((sqrt(i)) + 1):

lst.append(i)

break

if (i % j == 0):

break

else:

lst.append(i)

print lst

Листинг 4 коди N=10000да 1000 марта биринчи вариантга нисбатан тезроқ бажарилади.Яна ҳам тез бажариш йўли бу,фақат 1,3,7 ёки 9 га(бошқалари 2 ва 5 га бўлинадиганлари) тамом бўладиган сонларни текширишдир.Листинг 5 га қараймиз.

# Листинг 5

from math import sqrt

n = input("n=")

lst=[]

for i in xrange(2, n+1):

if (i > 10):

if (i%2==0) or (i%10==5):

continue

for j in lst:

if j > int((sqrt(i)) + 1):

lst.append(i)

break

if (i % j == 0):

break

else:

lst.append(i)

print lst

Листинг 5 даги озгина ўзгартириш эвазига тезликни оширамиз.

# Листинг 6

from math import sqrt

n = input("n=")

lst=[2]

for i in xrange(3, n+1, 2):

if (i > 10) and (i%10==5):

continue

for j in lst:

if j > int((sqrt(i)) + 1):

lst.append(i)

break

if (i % j == 0):

break

else:

lst.append(i)

print lst

Натижа: Охирги листингдаги дастур биринчи вариантга нисбатан 1300 баравар тезроқ бажарилади.Мен ўз олдимга шу масалани максимал даражада тез еча оладиган дастур тузишни мақсад қилмаган эдим, бу энди бошлаётган дастурчилар учун тўғри тузилган алгоритм сизнинг дастурларингизни оптималлаштиришда ўз ролини ўйнашини исботи эди.

P.S.
Листинг 7 камчиликларини ҳисобга олган ҳолда қуйидагиларга эга бўламиз:

# Листинг 7

n = input("n=")

lst=[2]

for i in xrange(3, n+1, 2):

if (i > 10) and (i%10==5):

continue

for j in lst:

if j*j-1 > i:

lst.append(i)

break

if (i % j == 0):

break

else:

lst.append(i)

print lst

N=10000да, вақт:

time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Решето Эратосфена:

# Листинг 8

n = input("n=")

a = range(n+1)

a[1] = 0

lst = []
i = 2

while i <= n:

if a[i] != 0:

lst.append(a[i])

for j in xrange(i, n+1, i):

a[j] = 0

i += 1

print lst

натижалар n = 1 000 000да:
time 7 = 7.088
time 8 = 1.143

Таблица 11

Функция	С++даги ёзилиши
	pow(x,y)
	sqrt(x)
	exp(x)
lg x	log10(x)
ln x	log(x)
th x	tanh(x)
ch x	cosh(x)
sh x	sinh(x)
tg x	tan(x)
cos x	cos(x)
sin x	sin(x)
arctg x	atan(x)
arcsin x	asin(x)
arccos x	acos(x)
	fabs(x)
	abs(x)
Х ни у даги қолдиғини қайтаради	fmod(x,y)
Тепасини яхлитлайди	ceil(x)
Пастини яхлитлайди	floor(x)
1,3*10^3	1.3Е3
1,3*10^-17	1.3Е-17

8 Жадвалдан мисолларни ечиш намунаси.

Масаланинг қўйилиши: Берилган а ва α қийматлар учун У нинг қийматини хисобланг




_{Матн шаклидаги алгоритмлар}
Мисолни ечиш учун қуйидаги белгилашлар киритамиз:

ва тенгламани куп содда тенгламаларга булиб ташлаймиз. Чунки 4 маротаба учратамиз , ва уни b ўрнига белгилаймиз :
1)

2)

3)

4)

5)

6)
_{Алгоритмни блок схема кўриниши }

С++ да икки усулда дастурни тузамиз.
1. усул