Сайт підготовки до олімпіади з інформатики

Динамічне програмування

            Аналогічний приклад можна навести і на більш складніший числовий ряд чисел Фібоначі.

Задача 1. Хтось вмістив пару новонароджених кроликів в деякому місці, обгородженому з усіх боків стіною. Скільки пар кроликів народиться при цьому протягом року, якщо природа кроликів така, що кожний місяць, починаючи з третього місяця після свого народження, пара кроликів породжує іншу пару?

Спосіб 1

Кожне наступне знаходити як суму двох попередніх.

1 1 2 3 5 8 ...

k1 перше число

k2 друге число

k3:=k1+k2;

k1:=k2;

k2:=k3;

program pr4 (іnput,output);

uses crt;

var

    k1,k2,k3,n:longіnt;

begіn

clrscr;

k1:=1;k2:=1;

for n:=3 to 12 do begіn

k3:=k1+k2;

k1:=k2;

k2:=k3;

end;

wrіte('n',k3);

end.

Спосіб 2

Використаємо рекурентну формулу  чисел Фібоначі.

Кожне число Фібоначі знаходять за формулою:

n=12

program pr5;

const n=12;

var

f1,f2:real;

f:longіnt;

begіn

f1:=exp(n*ln((1+sqrt(5))/2));

f2:=(exp(n*ln(abs(1-sqrt(5))/2)));

іf odd(n) then f:=round(1/sqrt(5)*(f1-f2)) else f:=round(1/sqrt(5)*(f1+f2));

wrіteln(f);

end.

 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Приклади задач

2. Хтось вмістив пару новонароджених кроликів в деякому місці, обгородженому з всіх боків стіною. Скільки пар кроликів народиться при цьому протягом року, якщо природа кроликів така, що кожний місяць, починаючи з третього місяця після свого народження, пара кроликів породжує іншу пару?

3. Визначити кількість способів, якими можна піднятися сходами з кількістю сходинок N, якщо дозволяється підніматися по одній і через одну сходинку.

4. Визначити кількість способів, якими можна піднятися сходами з кількістю сходинок N, якщо дозволяється підніматися по одній, через одну та через дві сходинки.

5. Визначити кількість способів, якими можна прокласти залізницю заданої довжини L км, при наявності рейс довжиною 1,2,3 км.

Задача 6 «Зернинки»

Мишка збирає зернинки на шаховій дошці. Може рухатись вниз та вліво. Зібрати найбільше зернинок.

Задача 7 «ПОДАРУНОК ДЛЯ МУДРОЇ СОВИ»

П'ятачок і Вінні-Пух зібрались до Мудрої Сови на день народження. Для подарунка вирішили назбира­ти букет польових ромашок. Ромашкове поле задане прямокутною матрицею M N, у клітинках якої за­писано кількість ромашок, що ростуть на відповідно­му клаптику поля. Будь-який клаптик поля містить хоча б одну ромашку.

П'ятачок і Вінні-Пух вміють ходити лише по гори­зонталі і вертикалі, при цьому, зробивши хід на схід, уже не можна буде потім ходити на захід і навпаки, а також, зробивши хід на північ не можна буде ходити на південь і навпаки. У початковий момент гості Му­дрої Сови знаходяться в центральній клітинці поля.

Напишіть програму, що допоможе вказати напря­мок руху: NW — північний захід, NE — північний схід, SW— південний захід, SE — південний схід, та визначте при цьому найбільшу можливу кількість ромашок у букеті.

Технічні умови:

У першому рядку вхідного текстового файла owl.dat записано через пропуск два цілих непарних чи­сла: М і N (2<М, N<100).

У наступних М рядках записано по N чисел у ко­жному, розділених пропуском. Кожне з чисел не пе­ревищує 10000.

Ваша програма повинна вивести у файл owl.sol напрямок руху у вигляді: NW — північний захід, NE — північний схід, SW — південний захід, SE — південний схід. Та через пропуск у відповідному ря­дку кількість ромашок. Якщо таких напрямків буде більше одного, то вивести всі від NW за годинниковою стрілкою.

Приклад 1.

owl.dat                                owl.sol

3  3                                     NE 7

1 2 З

3 2 1

1 1 1

Приклад 2.

owl.dat                                owl.sol

3   5                                    NW 7

1  2  1  2  1                   NE    7

3   2  1  2   3                    SE    7

1 1 3  1  1                   SW  7

Алгоритм Флойда-Уоршелла

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

Запишемо сам алгоритм:

1, Визначити вершину графа k = 1, через яку буде здійснюватися перерахунок відстані між вершинами і та j.

2. Визначити вершину і = 1.
 3. Визначити вершину j = 1,

4.   Якщо величина d_{j, k} + d_k,j менша за значення d_i,j ,то замінити значення  d_i,j на d_{i, k} + d_k,і . В іншому разі залишити зна­чення  d_i,j без змін.

5.   Якщо j <= п, то перейти до наступної вершини j+ 1 і повер­нутися до п. 4.

6.   Якщо i<= п, то перейти до наступної вершини і + 1 і повернутися до п. 3.

7.   Якщо k<=n,  то перейти до наступної вершини k + 1 і повер­нутися до п. 2,

8.   Завершити алгоритм.

У результаті виконання алгоритму елементи  d_i,j будуть міс­тити найкоротшу відстань між відповідними вершинами графа і та j.

Реалізація алгоритму Флойда-Уоршелла мовою Pascal буде такою:

for k := 1 to n do

for і := 1 to n do

for j := 1 to n do

if d[i,k]+d[k,j]k]+d[k,j];

ЕТАПИ РОЗВ'ЯЗАННЯ ЗАДАЧ НА КОМП'ЮТЕРІ

Перш ніж одержати очікуваний результат роботи програми на  комп'ютері, необхідно виконати досить багато копіткої підготовчої роботи.

1.Постановка задачі. Розв'язування будь-якої задачі починається з ЇЇ постановки, викладеної мовою чітко визначених математичних понять. На першому кроці необхідно добре уявити, в чому саме полягає дана задача, які необхідні початкові дані, яку інформацію вважати результатами розв'язання.

2. Побудова математичної моделі. Побудова математичної моделі алгоритму — дуже відповідальний етап. Не завжди умова сформульованої задачі містить в собі  математичну формулу, яку можна застосувати для розробки алгоритму задачі, не завжди розв'язок задачі вдається одержати в явному вигляді, що зв'язує вхідні дані га результат. Для цього створюється інформаційна математична модель  об'єкта, що вивчається. Вибір виду моделі залежить від інформаційної сутності об'єкта, а не від його фізичної природи. Тобто, настільки важливе прикладне значення задач, як однотипність методів, якими вони розв'язуються. Наприклад, логічні моделі використовуються як для моделювання словесних міркувань, так і для опису логічних схем автоматики. Розв'язуючи задачу про рух тіла під дією прикладених до нього сил, ми перш за все записуємо рівняння його руху на основі законів механіки. Проте, крім сили тяжіння, на тіло діє і сила опору повітря. Постає питання достовірності математичної моделі і реальної картини досліджуваного об'єкта. Іноді буває неможливо врахувати всі реальні фактори, що впливають на нього. Тому дуже  важливим є вміння виділити серед усіх факторів головні і другорядні, щоб останніми можна було знехтувати. При цьому може скластися ситуація, коли наперед невідомо, якими саме факторами можна знехтувати, і тому може бути кілька математичних моделей, які описують один і той самий об'єкт з різним ступенем достовірності. Відповідність моделі реальному об'єкту перевіряється практикою, комп'ютерним експериментом. Критерій застосування практики дає можливість оцінити побудовану модель і уточнити її за необхідності. Чим достовірніше математична модель відображає реальні сторони об'єкта, тим точніші одержувані результати.

3. Побудова алгоритму. Наступним етапом є розробка алгоритму обробки інформації на основі побудованої математичної моделі.  Тепер необхідно знайти спосіб розв'язування цієї задачі. Для цього можуть бути застосовані вже відомі методи, проведена їх оцінка, аналіз, відбір або розроблені нові методи. Наприклад, вибір методу розв'язування системи рівнянь, що описує дану математичну модель. Під час створення складних алгоритмів застосовується метод покрокової розробки. Сутність цього методу полягає в тому, що алгоритм розробляється «зверху донизу». На кожному етапі приймається невелика кількість рішень, що призводить до поступової деталізації, уточнення як виконуваної, так і інформаційної структури алгоритму. Такий підхід дозволяє розбити алгоритм на окремі частини — модулі, кожний з яких розв'язує свою самостійну підзадачу. Це дає можливість сконцентрувати зусилля на розв'язуванні кожної підзадачі, що реалізується у вигляді окремої процедури. Для кожного такого модуля визначаються свої методи реалізації алгоритму та структура даних, якими він оперує. Останнім етапом у методі покрокової розробки є об'єднання окремих незалежних модулів у єдине ціле. Для цього між модулями повинні бути встановлені зв'язки, тобто узгоджена передача інформації від одних модулів до інших: результати виконання одних модулів є вхідною інформацією для інших.

Якщо поставлена задача є складним завданням, то важливість розбиття алгоритму на окремі модулі неможливо переоцінити.

4. Вибір мови програмування. Алгоритм, призначений для виконання на комп'ютері, має бути записаний мовою програмування. Різноманітність існуючих мов програмування потребує від програміста реальної оцінки складності та характеру задачі. Тільки після цього він зможе здійснити оптимальний вибір мови програмування для реалізації поставленої задачі. Враховуючи можливість розбиття всього алгоритму на окремі модулі, для кожного з них вибір мови програмування можна здійснити окремо. Процес розробки програми, як і алгоритму, може здійснюватися за принципом «зверху донизу». Це дозволяє одержати добре структуровану програму, читання і розуміння якої значно полегшене.

5. Складання програми. Цей етап потребує лише знання вибраної мови програмування. Суть його полягає в тому, щоб на основі розроблених алгоритмів і структур даних створити програму для комп'ютера.

6. Компіляція програми. Переведення програми на машинну мову здійснюється за допомогою спеціальних програм — компіляторів. Однією з їх функцій є перевірка відсутності в програмі синтаксичних помилок. Не тіште себе надією, що ваша, навіть найпростіша, програма написана бездоганно. Серед програмістів побутує прислів'я:
«Якщо програма не має помилок, це означає, що у вас поганий компілятор!!!»

7. Налагодження програми, контрольний прорахунок. Виправлення усіх синтаксичних помилок у програмі на попередньому етапі .зовсім не позбавляє вас від помилок іншого типу — змістовних, логічних. Вони з'являються під час помилкового трактування умови поставленої задачі, через недосконалість математичної моделі або недоліки у побудованому алгоритмі, що призводить до одержання помилкового результату. Такі помилки не можуть бути усунені на стадії компіляції, тому що для їх виявлення необхідна інформація про сутність самої задачі. Це може зробити лише сам розробник. Процес налагодження програми полягає втому, що готується система тестів, за допомогою якої перевіряється робота програми в різних можливих режимах. Кожний тест містить набір вхідних даних, для яких відомий результат. Для більшості програм виникає необхідність добору не одного, а серії тестів, щоби перевірити якнайбільше можливих ситуацій, які можуть виникнути в процесі роботи програми. Якщо для всіх тестів результати роботи програми збіглися з розрахунками, то можна вважати, що логічних помилок немає.

9. Експлуатація програми. Тепер програму можна тиражувати і пропонувати іншим користувачам, доповнивши її відповідною документацією для користувачів. Документація повинна містити опис виконуваної задачі, опис середовища, в якому може працювати
програма, обмеження на вхідні дані, формат вхідних та вихідних даних. Більшість розглянутих етапів розв'язування задач на комп'ютері виконуються людиною і носять творчий, евристичний характер.

Караванова Т.П., Основи алгоритмізації та програмування. 750 задач з рекомендаціями та прикладами (посібник)