Алматыкітап баспасы

123
да цикл жұмысы 2 есе қысқарып, 50 санын жай санға тексеру үшін
25 рет жұмыс істейді. 
for j in range(1, n//2+1):
Егер сандар теориясын пайдалансақ, цикл жұмысын бұдан да 
азайтуға болады екен. 
Теорема.
Егер 
p
жай саны 
a
құрама санының ең кіші бөлгіші бол-
са, онда 
Р≤
√
а
шарты орындалады. 
Мысалы, 59 саны – жай сан, өйткені ол 
√
59-дан (
√
59≈7,6) кіші 
2, 3, 5, 7 жай сандарының ешқайсысына бөлінбейді. Олай болса, 
50 санын тексеру үшін де 2...7 арасындағы циклдің 6 рет жұмыс
істеуі жеткілікті (
√
50≈7). Бұл бастапқы жағдайдан 8 есе аз. Ал 
тексерілетін сан 1000000 болса, цикл 1000 рет жұмыс істейді.
for j in range(2, round(math.sqrt(x))):
Бір мысалға талдау жүргізе отырып, программа жазу барысын-
да тиімді алгоритмдерді білудің қаншалықты маңызды екенін көріп 
шықтық. Алгоритмдерді практикалық тұрғыдан қолдануды үйрену 
үшін, «Шарбақты бояу» есебін компьютерде орында. 
Шарбақты бояу. 
Қанат үйінің айналасындағы шарбақты 
бояуға 5 түрлі бояу алды. Ол шарбақты қандай түске бояу керектігін 
анықтау үшін, шарбаққа әр түсті бояудан жағып шықты 
(1-сурет)
. 
Нәтижесінде шарбақ түрлі түсті болды. Қанат шарбақтағы әртүрлі 
түстерді мүмкіндігінше аз күш жұмсап, бірдей түске бояғысы келе-
ді. Қанатқа көмектес. Оның шарбағындағы тақтайшалардың саны 
N
(
N
<100) және 1...5 арасындағы 5 түстің біріне боялған шарбақ 
тақтайшаларының түстері берілген. Есептің жауабы ретінде ең аз 
боялатын шарбақтар саны шығуы керек.
№

жүктеу 5,47 Mb.

Достарыңызбен бөлісу: