РусҚаз

Евклид алгоритмі: ЕҮОБ және ЕКОЕ

Информатика · 8-сынып · Санау жүйелері · Сабақ 4 / 4

Интерактивті сабақты ашу ›Өз қолыңмен тәжірибе, дауыспен дәріс, ЖИ-тәлімгер және тест. Тегін.

Бұл не?

Сабақтың тақырыбы — «Евклид алгоритмі: ЕҮОБ және ЕКОЕ». Талдап көрейік. Ең үлкен ортақ бөлгіш — екі сан да бөлінетін ең үлкен сан, ал ең кіші ортақ еселік — екі санға да бөлінетін ең кіші сан. Тікбұрышты еденді бірдей шаршы плиткалармен қиқымсыз төсеу керек деп елестет: осындай ең үлкен плитканың қабырғасы еден қабырғаларының ең үлкен ортақ бөлгіші болады.

Евклид алгоритмі: ЕҮОБ және ЕКОЕ — Бұл не?

Бұл не үшін керек?

Евклид алгоритмі — әлі күнге дейін әрбір қорғалған байланыста жұмыс істейтін ең көне алгоритмдердің бірі: банк аударымдары мен мессенджерлердегі хабарламаларды қорғайтын криптография соған сүйенеді. Ең кіші ортақ еселік мерзімді процестерді үйлестіруге көмектеседі — көлік кестелерін, электроникадағы тактілерді, конвейердегі роботтардың жұмыс циклдерін. Жасанды интеллект мұндай кодты бір жолмен жазады, бірақ алгоритмнің неге жылдам әрі дұрыс екенін түсініп, оны өз есебіне таңдай алатын — математиканы білетін адам. Бағдарламашылар, криптографтар және инженерлер бұл түсінікті он жылдан кейін де бағалайды.

Евклид алгоритмі: ЕҮОБ және ЕКОЕ — Бұл не үшін керек?

Бұл қалай жұмыс істейді?

Евклид екі санның ортақ бөлгіші үлкенін кішісіне бөлгендегі қалдықты да бөлетінін байқады. Сондықтан сандар жұбын кішірек санмен және қалдықпен ауыстырады да, қалдық нөлге тең болғанша қайталайды; соңғы нөлге тең емес қалдық — ең үлкен ортақ бөлгіш. Геометриялық тұрғыдан бұл тіктөртбұрыштан қалдық саңылаусыз шаршылармен толғанша ең үлкен шаршыларды кесіп алғанмен бірдей. Тіпті орасан зор сандар үшін де қадам аз, өйткені әр екі қадам сайын қалдық кемінде екі есе азаяды.

Евклид алгоритмі: ЕҮОБ және ЕКОЕ — Бұл қалай жұмыс істейді?

Аздап тарих

Бұл алгоритм Евклидтің «Негіздерінде» сипатталған — шамамен жиырма үш ғасыр бұрын Александрияда жазылған ежелгі грек еңбегі. Евклид оны геометриялық түрде, екі кесіндінің ортақ өлшемін іздеу ретінде баяндаған. «Негіздер» тарихтағы ең көп басылған кітаптардың біріне айналды, ал алгоритмнің өзін әлі күнге дейін қолданылатын ең көне алгоритмдердің бірі деп санайды.

Евклид алгоритмі: ЕҮОБ және ЕКОЕ — Аздап тарих

Формула: Евклид алгоритмі

Басты ереже: а мен бэ-ның ең үлкен ортақ бөлгіші бэ мен а-ны бэ-ға бөлгендегі қалдықтың ең үлкен ортақ бөлгішіне тең. Неге? А-ны да, бэ-ны да бөлетін сан а мен бірнеше бэ-ның айырмасын да бөледі, ал бұл дәл қалдық. Мұнда а мен бэ — натурал сандар, ал қалдықты мод сөзімен белгілейді. Жұпты қалдық нөлге тең болғанша қайта-қайта ауыстырады — сонда соңғы нөлге тең емес сан жауап болады. Сандардың өлшемдері неғұрлым көп ерекшеленсе, жұп бір қадамда соғұрлым қатты кішірейеді.

  • НОД(a, b) = НОД(b, a mod b)a, b — натурал сандар, —
    a mod b — a-ны b-ға бөлгендегі қалдық, —

Формула: ЕҮОБ арқылы ЕКОЕ

Ең кіші ортақ еселікті былай табады: ол а көбейтілген бэ-ны а мен бэ-ның ең үлкен ортақ бөлгішіне бөлгенге тең. А мен бэ-ның көбейтіндісі екі санға да міндетті түрде бөлінеді, бірақ онда ортақ бөлік екі рет саналған, сондықтан оны ортақ бөлгішке бөлу арқылы алып тастайды. Мұнда а мен бэ — натурал сандар. Мысалы, екі автобус бірге шығып, әртүрлі аралықпен жүрсе, осы формула арқылы олардың неше минуттан кейін қайтадан бір мезгілде шығатынын біледі. Ортақ бөлгіш неғұрлым үлкен болса, ортақ еселік көбейтіндімен салыстырғанда соғұрлым кіші.

  • НОК(a, b) = a · b / НОД(a, b)a, b — натурал сандар, —
    НОД(a, b) — ең үлкен ортақ бөлгіш, —

Практикада не істейміз?

Ал енді практикалық тапсырманы орындап көрейік. Қазір алдыңда ең үлкен ортақ бөлгіш режимі: қырық сегізге он сегіз тіктөртбұрыш. Бір қадамда ең үлкен шаршылардың нешеуін кесіп алатыныңды таңда — қалдық шаршының қабырғасынан кіші болуы керек — және тіктөртбұрыштың барған сайын кішірейгенін қара. Қалдық саңылаусыз шаршылармен толғанда, осы шаршылардың қабырғасы жауап болады. Содан кейін уақыт сызығынан он екі мен он сегіздің ең кіші ортақ еселігін тап — әр санның еселіктерін жазып шығуға немесе ортақ бөлгіш арқылы формуланы пайдалануға болады. Бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, мен жауап беремін. Уайымдама.

Тәжірибедегі тапсырма

Тіктөртбұрыштан шаршыларды кесіп, ЕҮОБ(48, 18)-ді, ал уақыт сызығында ЕКОЕ(12, 18)-ді табыңыз.
Интерактивті сабақты ашу ›Өз қолыңмен тәжірибе, дауыспен дәріс, ЖИ-тәлімгер және тест. Тегін.

Тақырып сабақтары: Санау жүйелері

  1. Позициялық жүйелер және аудару
  2. Екілік арифметика
  3. Көлем және жіберу жылдамдығы
  4. Евклид алгоритмі: ЕҮОБ және ЕКОЕ