Властивості та сума членів арифметичної прогресії

Власне кажучи, знаючи теоретичний матеріал, що міститься в параграфі означення та формула обчислення -го члена арифметичної прогресії, можна знаходити розв'язок практично будь-якої задачі пов'язаної з арифметичною прогресією. Однак, уявіть ситуацію, що треба знайти суму арифметичної прогресії, що складається з ста елементів. Це що ж нам, один за одним додавати всі члени, з першого по останній? Зрозуміло, що такий підхід до рішення поставленої задачі є не досить зручним. В таких випадках використовується спеціальна формула, але перш ніж приступити до її виводу, розглянемо та доведемо необхідні для цього властивості арифметичної прогресії:

  1. Кожен член арифметичної прогресії дорівнює середньому арифметичному його сусідніх членів (виняток становить перший член, а у скінченній прогресії також і останній (мають тільки по одному сусідньому члену)).

    Покажемо істенність даного твердження. Отже, для члена , члени та будуть сусідніми. За означенням прогресії можемо записати наступне: . Звідси, . Взявши півсуму останніх рівностей, отримаємо , що і треба було довести.

  2. У скінченній арифметичній прогресії суми членів, рівновіддалених від її кінців, рівні між собою і дорівнюють сумі крайніх членів.

    Доведемо дане твердження також. Для цього, випишемо кілька пар членів, рівновіддалених від кінців прогресії: . Переглянувши отримані резільтати можна зробити висновок, що у кожної такої пари, сума їх номерів на одиницю більш числа членів прогресії. Таким чином, якщо на -му місці від початку прогресії знаходиться член , то на -му місці від її кінця знаходиться член . Скориставшись формулою загального члена арифметичної прогресії, знайдемо суму цих елементів:

    Звідси, виходячи з того, що , отримаємо , що і треба було довести.

Виведемо тепер формулу для суми членів скінченної арифметичної прогресії. Для прогресії, що має  членів, позначимо цю суму через . Запишемо вираз суми  двічі, один раз розташувавши члени прогресії по зростанню їх номерів, і другий раз — по спаданню:

Читати повністю

Послідовна розмальовка графа в середовищі програмування delphi

В параграфі розглядається програма, основним призначенням якої є відшукання хроматичного числа та здійснення правильної розмальовки вершин неорієнтованого графа, написана в середовищі Delphi 7. Зазначимо, що внизу сторінки міститься посилання, скориставшись якими можна завантажити delphi-проект, а в цій статті коротко опишемо елементи його головної форми.

Головне вікно проекту "Послідовна розмальовка графа"

Отже, головна форма delphi-програми ділиться на три частини і складається з панелі інструментів (компонент типу TPanel), графічного редактора (компонент типу TImage) та області виводу резільтатів (компонент типу TMemo):

Читати повністю

Означення та формула обчислення загального члена арифметичної прогресії

Арифметичною прогресією називається така послідовність чисел, кожен член якої (починаючи з другого) дорівнює сумі попереднього члена і деякого фіксованого числа , яке називається різницею або кроком арифметичної прогресії.

До прикладу натуральний ряд чисел є нескінченною арифметичною прогресією з різницею , а послідовність непарних і парних чисел — нескінченними арифметичними прогресіями, для кожної з яких різниця дорівнює числу два ().

Арифметична прогресія при являється монотонною послідовністю: якщо , то прогресія зростає, якщо , то прогресія спадає, при вона постійна. Нескінченні арифметичні прогресії, для яких різниця не дорівнює нулю, як необмежені послідовності, границі не мають. Вони відносяться до категорії розбіжних послідовностей.

Читати повністю

Алгоритм послідовної розмальовки графа

Розглядаючи задачу знаходження хроматичного числа графа (мінімальна кількість кольорів, в які можна розфарбувати його вершини) нами зазначалось, що єдиним підходом для знаходження оптимального рішення задач такого типу є перебір варіантів. До прикладу в параграфі, що міститься за посиланням вище, нами було розглянуто переборний алгоритм, результатом виконання якого є дерево варіантів, обхід якого дозволяє знайти рішення задачі. Але, як видно з прикладу, навіть для графів з мінімальним числом вершин, отримане дерево може бути достатньо громіздким, не кажучи про графи кількість верин яких перевищує число десять і більше. Таким чином, перебрний метод при знаходженні оптимального розв'язку задачі на розфарбування вершин графа вимагає великих обчислювальних затрат і, як правило, застосовується для графів, з достатньо малою кількістю вершин.

Використання алгоритму послідовної розмальовки для розв'язку задачі про розфарбування графа

Однак, якщо спростити розглядувану задачу і відмовитися від вимоги мінімальної кількості кольорів розмальовки графа, то можна побудувати алгоритми, які б працювали значно швидше, ніж алгоритм перебору варіантів. Зазначимо, що алгоритми, які швидко знаходять підходяще, але не оптимальне рішення, називаються евристичними. Прикладом раціонального евристичного алгоритму може слугувати алгоритм послідовної розмальовки графа, що базується на ідеї впорядкування вершин за будь-яким правилом (найчастіше зустрічаються приклади, де використовують степеня вершин) і послідовному присвоєнню їм кольорів, в які не були пофарбовані суміжні з ними вершини. Розглянемо даний алгоритм більш детально.

Читати повністю

Перетворення чисел з двійкової системи числення в десяткову і навпаки (реалізація в середовищі Delphi)

Delphi-програма реалізує алгоритм перетворення чисел з двійкової системи числення в десяткову і навпаки. Для цього на головній формі містяться два компоненти типу TEdit, кожен з яких призначений для вводу та виводу чисел у відповідній системі числення.

Головне вікно delphi-проекту

Логіка роботи розглядуваної delphi-програми доволі проста і полягає у наступному: при зміні значень у будь-якому з двох рядків введення («Десяткове число», «Двійкове число») відразу ж повинні бути виконані обчислення числа в новій системі числення, а результати виведені у відповідному рядку TEdit.

Отже, Запустимо програму на виконання, введемо будь-яке десяткове чи двійкове число, і таким чином, перевіримо яким чином це працює.

Читати повністю

Алгоритм Форда-Беллмана (реалізація в середовищі Delphi)

У математиці та інформатиці існує окремий розділ, який називається теорія графів. Основним предметом вивчення даного розділу є математичний об'єкт, який називається графом (об'єкт, який представляє собою множину вершин і набір ребер, які виступають в якості з'єднань між парами вершин). В рамках даного розділу ставляться і вирішуються різні задачі пов'язані з цим об'єктом. Найпоширенішшою серед них є задача про знаходження найкоротшого шляху між будь-якими двома вершинами графа. Зазначимо, що одним з найбільш використовуваних методів рішення задач такого типу являється метод Дейкстри.

Проте, виходячи з того, що delphi-проект який реалізує алгоритм методу Дейкстри нами вже неодноразово в розділі Програми на Delphi (Дослідження операцій) було розглянуто, сьогодні зосередимо свою увагу на delphi-проекті, що реалізує дещо інший алгоритм рішення задач такого типу, а саме алгоритм Беллмана-Форда.

Головне вікно проекту "Знаходження дерева мінімальної вартості за алгоритмом Беллмана-Форда"

Отже, головна форма розглядуваного проекту складається з панелі інструментів (містить кнопки «Додати вершину», «Видалити вершину», «Додати ребро», «Видалити ребро», «Видалити граф» і «Знайти дерево мінімальної вартості»), області графічного представлення, області представлення графа у вигляді матриці та області виводу результатів (компонент типу TStatusBar, призначений для виводу розв'язку у вигляді списку ребер).

Читати повністю

Розв'язок задачі про найкоротший шлях використовуючи алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда — це алгоритм, який обчислює найкоротші шляхи від однієї вихідної вершини до всіх інших вершин в зваженому орієнтованому графі. Безумовно, він являється повільнішим, ніж алгоритм Дейкстри для тієї ж задачі, але більш універсальний, оскільки здатний обробляти графи, в яких вага деяких ребер приймає від'ємного значення. Алгоритм зазвичай називають на честь двох його розробників, Річарда Беллмана і Лестера Форда, які опублікували його у 1958 та 1956 роках відповідно. Тим не менш, Едвард Форест Мур також опублікував даний алгоритм у 1957 році, і з цієї причини його також іноді називають алгоритмом Беллмана-Форда-Мура.

Різниця в кінцеваому результаті між алгоритмом Беллмана Форда та алгоритмом Дейкстри

Як уже зазначалося вище, алгоритм Беллмана-Форда підходить для роботи з графами, що мають ребра з від'ємною вагою. Однак, якщо граф містить «від'ємний цикл», тобто цикл, сума ваги ребер якого дорівнює від'ємному значенню, тоді, для даного графа, не існує дерева найкоротших шляхів (будь-який шлях такого типу може бути покращений ще одним проходом через ребра, що утворюють від'ємний цикл). В такому випадку алгоритм Беллмана-Форда може виявити цикли від'ємної довжини і повідомити про їх існування, але він не може дати правильну відповідь, тобто знайти найкоротший шлях, якщо від'ємний цикл досяжний з вершини джерела.

Читати повністю

« Попередня сторінкаНаступна сторінка »