2 , де L - відстань від міста до станції, а k - якийсь коефіцієнт. Потребуєте написати програму, яка визначає мінімальні витрати компанії на установку мережі.
Вхідні дані. Під вхідному файлі записано число n (1 ≤ n ≤ 10) - кількість міст в області. Потім йдуть позитивні речові числа: k - коефіцієнт вартості кабелю і P - вартість будівлі однієї станції. Далі слід n пар дійсних чисел, які задають координати міст на площині. p> Вихідні дані. У першу рядок вихідного файлу потрібно вивести мінімальні витрати на установку мережі (з трьома знаками після десяткового дробу), в другу - кількість встановлюваних станцій. Далі вивести координати станцій (з трьома знаками після десяткової точки), а потім - список з n цілих чисел, в якому i -е число задає номер станції, до якої буде підключений i -ий місто. ( Кіровський командний турнір з програмування , 2000 р.)
Рішення . У силу слабкий розмірності ми можемо розглянути всі можливі варіанти розбиття міст на групи, маючи на увазі що для кожної групи буде встановлена ​​своя станція, причому оптимальним чином (знайти оптимальне місцезнаходження станції для однієї групи міст можна за формулою, аналогічною формулою знаходження центру мас). Потім потрібно з усіх разбиений вибрати те, для якої загальна сума витрат на встановлення мережі буде мінімальною.
В
Висновок
Перераховані підзадачі в програмуванні зазвичай розглядають для наступних комбінаторних конфігурацій: перестановки елементів множини, підмножини множини, поєднання з n елементів безлічі за k елементів ( k -елементні підмножини множини, що складається з n Ві k елементів), розміщення (впорядковані підмножини множини, тобто відрізняються не тільки складом елементів, але і порядком елементів в них), розбиття множини (Безліч розбивається на підмножини довільного розміру так, що кожен елемент вихідного безлічі міститься рівно в одному підмножині), розбиття натуральних чисел на складові, правильні дужкові послідовності (Різні правильні взаємні розташування n пар відкриваються і закриваються дужок).
Більшість зазначених конфігурацій були детально розглянуті в [1-3]. Однак при генерації різних конфігурацій використовувалися в основному нерекурсівние алгоритми. Досвідчені ж учасники олімпіад у подібних випадках при програмуванні використовують в основному саме рекурсію, за допомогою якої рішення розглянутих завдань часто можна записати більш коротко і прозоро. Тому для повноти викладу даної теми наведемо ряд рекурсивних комбінаторних алгоритмів і розглянемо особливості застосування рекурсії в комбінаториці.
В
Література
1. Окулов С.М. Перестановки. "Інформатика", № 7, 2000. p> 2. Окулов С. M . Комбінаторні задачі. "Інформатика", № 10, 13, 2000. p> 3. Усов Б.Б. Комбінаторні задачі. "Інформатика", № 39, 2000. p> 4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М.: МЦНМО, 2000. p> 5. Брудно A . Л., Каплан Л.І. Московські олімпіади з програмування. М.: Наука, 1990. p> 6. Кнут Д. Конкретна математика. Підстава інформатики. М.: "Світ", 1998. p> 7. Липський В. Комбінаторика для програмістів. М.: "Світ", 1988. p> 8. Андрєєва Є.В. Ще раз про завдання на повний перебір варіантів. "Інформатика", № 45, 2000. br/>
