Алгоритмдер жєне деректер структурасы


Аргументті сызықты алмастыру арқылы көпмүшелікті есептеу



бет16/41
Дата05.09.2020
өлшемі0,89 Mb.
#77252
1   ...   12   13   14   15   16   17   18   19   ...   41
Байланысты:
5bacf48a-311c-11e3-8846-f6d299da70eeУМК-алг (1)

Аргументті сызықты алмастыру арқылы көпмүшелікті есептеу
полином берілсін. алмастыру жасау арқылы көпмүшелігін аламыз.

Мысалы:










т/к

формуласы тиімді. немесе

Мысалы: 10 депутаттың 5 – уін таңдау әдісі қанша?




i=10-5+1=6 дан i=10 дейін i – ді көбейту.





;

1.a,b,c[i] енгіз



2. d0 – ді табамыз:







I-этап





3. d1,d2 – ні табамыз:









егер болса, онда







Әйтпесе ц.с



Бітті



ді шығару.

Мысалы.

Мектептегі әр кластың оқушылар саны берілсін. Мектептегі жалпы оқушылар санын табу керек.

Мектепте әр класс а, б, в деп бөлінетінін ескерсек 2 өлшемді массив пайда болады.

кл [i, j] кл [1, 1] кл [2, 1] кл [3, 3]

кл [1, 2] кл [2, 2] кл [3, 3] . . .

кл [1, 3] кл [2, 3] кл [3, 3]







а

б

в

1 кл

25

20

10

2 кл

10

10

0

3 кл

15

13

11

. . .

. . .

. . .

. . .

11 кл

17

18

10


к

л [i, j] =


алг қосу (бүт таб кл [1:11,1:3], бүт S)

арг кл

нәт S
басы бүт i,j

S:=0


i:=1

әзір i≤11

цикл басы

j:=1


әзір j≤3

цикл басы

S:=S+ кл [i, j]

j:=j+1

цикл соңы
i:=i+1

цикл соңы

Соңы
4. реттелмеген массивте біртіндеп іздеу алгоритмі

Деректерге көп қолданылатын операциялардың бірі – іздеу. Іздеу мәселесі ЭЕМ-нің дамуының алғашқы жылдарынан бастап басты мәселелердің бірі болды. Аз көлемді ішкі жады мен тізбекті – лента типті құрылғыларда сақталған деректердің арасынан керекті ақпаратты іздеу ішкі жадының кеңейтілуін талап етті.

Іздеу операциясы екі нәтиже береді:

1. сәтті іздеу

2. сәтсіз іздеу.

Іздеу сәтті болса, ізделінді элементтің орналасқан жері табылады, яғни ол массивтің элементінің номерін береді.



Іздеудің бірнеше әдістері бар:

  1. белгілі бір элементті іздеу

  2. кез келген элементті іздеу т.б.

Мысалмен қарастырсақ:

Екі жиын берілсін: және . А жиыны В жиынының ішкі жиыны болатын, болмайтынын анықтау керек болсын.

Бұл есепті шешу үшін екі әдісті қолдануға болады:

1. Элементтер беттескенге дейін әрбір аi элементтерін сәйкес bi элементтерімен салыстыру

2. А және В жиындарын реттеп алып, екі жиынның элементтерін бір бірімен беттескенше салыстыру

Іздеудің бірінші нұсқасында n, m-сандары аз болғанда тиімді, ал олар өссе, онда ә-ші әдіс тиімді болады. Алгоритмнің негізгі мазмұны оның күрделілігінде.

Алгоритмнің күрделілігі итерация ұғымымен байланысты.





Достарыңызбен бөлісу:
1   ...   12   13   14   15   16   17   18   19   ...   41




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет