9. 1B комбинаторика және жиындар теориясының элементтері: Жиын ұғымы
А Комбинаторика элементтері және ықтималдық теориясы
жүктеу/скачать 1,18 Mb.
|
Комбинаторика
- Бұл бет үшін навигация:
- Барлығы 68 І-тақырып. Комбинаториканың негізгі ұғымдары
- 2. «Бұтақтар» әдісі. «Бұтақтар» көмегімен варианттарды есептеу.
| 10.2А Комбинаторика элементтері және ықтималдық теориясы:
Пәндік жоспарлау
І-тақырып. Комбинаториканың негізгі ұғымдары 1. Комбинаторика пәні. Қайталанатын және қайталанбайтын таңдаулар. Комбинацияны құрайтын типтер Берілген жиын n әртүрлі элементтерден тұрсын. Бұл жиыннан бір элементті аламыз, содан кейін жиыннан бұл элементтен басқа екінші элемент алынады т.с.с., яғни әрбір таңдауда алынған элементтерден басқа жаңа элементтер алып отырамыз. Бұл кайталанбайтын таңдау. Берілген жиын k типті элементтерден тұратын болсын, мұнда әрбір типтің ішіндегі элементтер бірдей. Кезекті таңдауда, алдыңғы алғаннан басқа, немесе алдында алғандағыдай жаңа элемент аламыз. Бұл қайталанатын таңдау деп аталады. Қайталанатын таңдауға өзгеше сипат беруге болады. Берілген жиын әртүрлі п элементтен тұрсын. Бірінші элементті жазып алып, оны жиынға қайта қайтарамыз. Екінші элементті аламыз. Бұл жаңа немесе алдыңғы қайтарылған элемент болуы мүмкін. Мұндай таңдау қайталанатын таңдау. Жиыннан алынған элементтер таңдауларды құрайды. 2. «Бұтақтар» әдісі. «Бұтақтар» көмегімен варианттарды есептеу. Есеп шығаруда қолданылатын комбинаторикалық әдістің бірі - жалпы бір схемаға негізделген «бұтақтар» әдісі. Мүмкін таңдау саны әр қадам сайын алғашқыда қандай элемент алынғанына байланысты болатын комбинацияны құру процесін «бұтақтар» түрінде қарастырған ыңғайлы. Алдымен бір нүктеден әр түрлі неше таңдау алуға болатын бағыт көрсетіледі, яғни әрбір тармақ бір элементке сәйкес келеді. Алынған бағыттардан, екінші қадамда қанша таңдау жасауға болса, бір нүктеден сонша тармақтар (стрелка) жүргізіледі. 1-мысал. а) Теңге екі рет, б) үш рет лақтырғандағы мүмкін нәтижелердің «бұтақтарын» салып көрсет. Шешуі: а) теңгені бір рет лақтырғанда елтаңба (Е) немесе сан (С) жағымен түсетін екі жағдай болады. Сондықтан бірінші қадамда бір нүктеден шығатын 2 тармақ болады. Е С 1-қадам Е С Е С 2-қадам Теңгені екінші рет лақтырғанда да екі жағдай болады. Сонда екінші қадамда төрт нүкте аламыз, яғни теңгені екі рет лақтырғанда төрт жағдай болуы мүмкін, ЕЕ, ЕС, СЕ, СС. б) Дәл осылайша теңгені үш рет лақтырғанда ЕЕЕ, ЕЕС, ЕСЕ, ЕСС, СЕЕ, СЕС, ССЕ, ССС жағдайлар болады. Оның бұтақтары төмендегі суреттегідей. Е С 1- қадам Е С Е С 2 – қадам Е С Е С Е С Е С 3 - қадам 2-мысал. а) 2,3,4 цифрларын бір рет қана қолдану арқылы неше әдіспен үш таңбалы сан жазуға болады? б) 2 және 0 цифрларынан неше әдіспен төрттаңбалы сан жазуға болады? Шешуі: а) бұл есептің шешімін «бұтақтар» әдісі арқылы көрсетейік. Сан үштаңбалы болғандықтан, үш қадам болады. Бірінші цифр үш әдіспен таңдалады, сондықтан бірінші қадамда үш бағыт болады. Екінші цифр (цифрлар қайталанбайтын болғандықтан) қалған екеуінен таңдалады. Сонда бірінші қадамның әрбір нүктесінен екі тармақ шығады. Үшінші цифр қалған біреуінен таңдалатындықтан екінші қадамның әрбір нүктесінен бір тармақ шығады. Соңғы қадамда алты нүкте пайда болады, яғни алты үштаңбалы сан алуға болады, 234, 243, 324, 342, 423, 432. 2 3 4 1- қадам 3 4 2 4 2 3 2- қадам 4 3 4 2 3 2 3 - қадам б) 2 және 0 цифрларынан тұратын төрт таңбалы санның шығу «бұтақтарын» салайық. Суретте төрт деңгей болады. Бірінші цифр екі ғана болады, өйткені 0 цифрынан басталатын төрт таңбалы сан болмайды. Екінші, үшінші, төртінші цифрларды да екі әдіспен алуға болады. Төртінші деңгейде сегіз нүкте пайда болады, яғни сегіз төрт таңбалы сан алынды: 2000, 2002, 2020, 2022, 2200, 2202, 2220, 2222. 2 1-қадам 0 2 2- қадам 0 2 0 2 3-қадам 4-қадам 0 2 0 2 0 2 0 2 3-мысал. А, Б, В үш әрпінен дауыссыз дыбыстар қатар келмейтін барлық үш әріпті сөзді құрастыру керек. Шешуі: Шығу «бұтақтарын» көрсетейік. Бұл «бұтақтардан» 11 сөз пайда болатынын көреміз, атап айтқанда ААА, ААБ, ААВ, АБА, АВА, БАА, БАБ, БАВ, ВАА, ВАБ, ВАВ. А Б В 1-қадам А Б В А А 2-қадам А Б В А А А Б В А Б В 3 - қадам 3. Қысқа жолды табу. 4-мысал: Саудагердің жүрген жолы сызба түрінде көрсетілген. Бір пунктен екінші пунктке көрсетілген бағыт бойынша ғана жүру керек. Саудагер әрбір пункте бір рет ғана бола алады. Оның жүрген жолын «бұтақтар» әдісі арқылы көрсету керек. Бірінші пунктен оныншы пунктке дейінгі ең ұзақ және ең қысқа жолдарды табу керек. Бағыттың бойында пунктер арасындағы ара қашықтықтар көрсетілген. Шешуі: Көрнекілік үшін бірінші пунктен оныншы пунктке дейінгі барлық мүмкін болатын жолдардың «бұтақтарын» құрайық. «Бұтақтар» бойынша 1- пунктен 10 - пунктке дейінгі барлық мүмкін болатын жолдар 11. Енді барлық жолдардың ұзындықтарын табайық, мұнда соңғы пунктен бастаған ыңғайлы. Мысалы, бірінші жол 10 – 8 – 4 – 2 – 1. Бұл жолдың ұзындығы 2+8+5+2 = 17 км. Сонымен, ең қысқа жолдың ұзындығы 13 км, ал ең ұзын жол 26км тең. «Бұтақтар» әдісінің тиімділігі, барлық мүмкін болатын жол санын санауға мүмкіндік береді және барлық жолдарды бірден көре отырып, оларды салыстыруға болады. Бұл әдісті торлық графикте ең қиын жолды табуда қолданамыз. (3) (6) жүктеу/скачать 1,18 Mb. Достарыңызбен бөлісу:
|