Задача тижня 06.02.12 – 12.02.12
Стовпчикова огорожа
Подвір’я дідуся однією стороною, довжина якої 100 метрів, виходить до лісу. Дідусь вирішив відгородити свій двір від лісу, але не капітальною огорожею, а тільки окремими стовпчиками. Він установив перший стовпчик на краю межі й доручив своїм онукам кожного разу, повертаючись з прогулянки в лісі, приносити дерев’яні стовпчики й додавати їх до огорожі – хто куди захоче. Так з часом і почала утворюватися стовпчикова огорожа.
1. Створіть програму знаходження найбільшої відстані між сусідніми стовпчиками:
Вхідні дані
Значення К – ціле число від 1 до 5000 (кількість стовпців, установлених онуками), вводиться з клавіатури або задається як константа;
значення Ri (i = 1, 2, …, К) – цілі числа від 10 до 10000 (значення відстаней (у сантиметрах) від дідова стовпчика до онукових стовпців у порядку їх установлення), вводяться з клавіатури або з файлу.
Вихідні дані (виводяться на екран)
Значення Rmax – найбільша відстань між сусідніми стовпчиками (у сантиметрах).
2. Заповніть тестову таблицю за результатами роботи програми:
| № | К | Ri (i = 1, 2, …, К) | Rmax |
| 1 | 1 | 20 | 20 |
| 2 | 3 | 100 70 15 | 55 |
| 3 | 5 | 100 45 10 65 90 | |
| 4 | 6 | 80 30 160 105 200 190 | |
| 5 | 9 | 10 580 850 1000 140 350 200 710 950 | |
| 6 | 20 | 10000 450 6000 10 900 8000 1500 3450 2400 9600 6900 4800 100 5510 1100 1900 9100 7300 3900 8100 |
Аналіз розв’язку задачі «Стовпчикова огорожа»
Варіант 1.
Оскільки вхідні значення Ri невпорядковані, їх слід зберегти у масиві R для того, щоб відсортувати за зростанням. Після сортування потрібно, використовуючи цикл, знайти Rmax як максимальну різницю між сусідніми елементами масиву:
Варіант 2.
Цей варіант розроблений за мотивами рішення одного з учасників задачного марафону. На жаль, автор припустився помилки, але оригінальність ідеї була оцінена одним додатковим балом.
Ідея розв’язку не спирається на упорядкування масиву R. Для кожного онукова стовпчика (зовнішній цикл по i від 1 до K) визначаються його відстані до найближчого стовпчика «зліва» (poz) і «справа» (otr). Це реалізується в результаті виконання внутрішнього циклу по j, знову ж таки від 1 до K, де ситуація i = j пропускається. Знайдені значення відстаней poz і otr порівнюються із поточним значенням Rmax (шукана максимальна відстань між стовпчиками), і найбільше з них стає значенням Rmax.
Звернемо увагу на те, що для «запуску» внутрішнього циклу, змінним poz і otr необхідно надати початкові значення, які б напевно перевищували будь-яку різницю R[i]-R[j]. Ми скористалися системною константою maxint – найбільшим значенням цілої типу integer.
Залишається подбати про перший стовпчик, який поставив дідусь, і перевірити його відстань до найближчого онукова стовпчика R0. Цю перевірку доречно здійснити в рамках зовнішнього циклу.
Після виходу із зовнішнього циклу залишається порівняти значення R0 і Rmax, щоб більше з них надати змінній Rmax і вивести відповідь на екран.
Зауваження 1. Зазначимо, що не можна уникнути пошуку двох значень – poz і otr та спростити задачу пошуком однієї відстані, наприклад, d = abs (R[i]-R[j]), оскільки нас цікавить найбільше значення з двох відстаней до найближчих стовпчиків.
Зауваження 2. Можна перевірку дідова стовпчика здійснювати не окремо, а разом з онуковими. Для цього слід збільшити масив R на 1 елемент з нульовим значенням і, відповідно, цикли виконувати від 1 до K+1.
Таблиця за результатами роботи програми:
| № | К | Ri (i = 1, 2, …, К) | Rmax |
| 1 | 1 | 20 | 20 |
| 2 | 3 | 100 70 15 | 55 |
| 3 | 5 | 100 45 10 65 90 | 35 |
| 4 | 6 | 80 30 160 105 200 190 | 55 |
| 5 | 9 | 10 580 850 1000 140 350 200 710 950 | 230 |
| 6 | 20 | 10000 450 6000 10 900 8000 1500 3450 2400 9600 6900 4800 100 5510 1100 1900 9100 7300 3900 8100 | 1050 |
Журі оцінило надіслані розв’язки наступним чином:
| № | Учасник | Кількість балів |
| 1 | RomaN | 4 |
| 2 | SERGEY | 1 |
| 3 | forsh3 | 4 |
| 4 | Юрий Дончик | 4 |
| 5 | ALEX Z | 4 |
| 6 | Kolgatin Andrey | 4 |
