Задача взята с сайта e-olymp.com.
Постановка задачи
В зоопарке [latex] N [/latex] клеток выстроены в ряд. В зоопарке, кроме прочих обитателей, живут две мартышки, Слава и Юра. Слава и Юра всегда были большими друзьями и сидели в соседних клетках, но теперь они поссорились и больше не хотят видеть друг друга. Смотритель уже собрался переселить их в соответствии с их желанием, однако возникла проблема. Слава и Юра — очень образованные мартышки (каждый из них закончил аж по восемь классов!), и они непременно хотят знать, сколько всего существует способов расселить их так, чтобы их клетки не были соседними, и уж конечно их клетки должны быть различными. Можно считать, что все [latex] N [/latex] клеток доступны, остальные обитатели зоопарка готовы переехать куда угодно.
Входные данные:
В первой строке входных данных находится число [latex] N [/latex] [latex](2\leq N\leq 100)[/latex] — количество клеток в зоопарке.
Выходные данные:
Выведите одно число — количество способов поселить Славу и Юру в разные клетки так, чтобы эти клетки не были соседними.
Тесты
| 4 | 6 |
| 15 | 182 |
| 30 | 812 |
| 48 | 2162 |
| 60 | 3422 |
Реализация
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int main() { int n; // количество клеток int c; //количество способов поселения cin >> n; c = (n - 1) * (n - 2); cout << c; return 0; } |
Здесь находится код в ideone.com
Решение
Рассмотрим возможные расположения клеток при условии, что одна из обезьян занимает первую клетку. Очевидно, что другая обезьяна не может занимать первую и вторую клетки, т к клетки должны быть разными и не соседними. Следовательно, существует [latex] (n — 2) [/latex] вариантов расположения второй обезьяны. Далее предположим, что первая обезьяна занимает вторую клетку. Тогда количество вариантов расположения второй обезьяны равно [latex] (n-2-1) = (n-3) [/latex] . И так далее, до тех пор пока не останется один вариант расположения второй обезьяны. Таким образом, ключ к решению задачи лежит в рассмотрении количества вариаций расположения клеток обезьян как арифметической прогрессии. Исходя из условия задачи, нам необходимо найти сумму первых [latex] n [/latex] членов прогрессии. Формула для вычислений: [latex] S=\frac{(a_1 + a_k}{2}*k [/latex], где [latex] a_1=n-2 [/latex] и [latex] a_k=1 [/latex], и [latex] k=n-2 [/latex]. Применяя математические преобразования, получаем что [latex] S=\frac{(n-1) * (n-2)}{2} [/latex]. Однако, имеет значение не только, непосредственно, какие две клетки заняты, но и какая именно из обезьян занимает определенную клетку. То есть при [latex] n=3 [/latex] мы имеем лишь пару клеток, которые можем использовать, но два способа поселения. Следовательно, полученное выражение необходимо умножить на два. Таким образом, мы вывели необходимую нам формулу.
Выполненное задание на сайте e-olimp.com здесь.
Считает правильно, но…
— Даже один символ N это уже формула. Нужен latex. Оформите везде по тексту формулы в latex.
— Вы пишите «Объявим переменную n». Не нужно пересказывать на обычном языке код программы. Это бессмысленная работа. Нужно описать ход решения, вывод формулы и т.п. Назначение переменных можно указать в комментариях прямо в коде программы.
— «Зоопарк» это не ключевое слово, а название задачи. Перечитайте свой текст и выделите важные слова.
— «щелкните здесь» звучит как-то не очень. Гиперссылка нужна, но «щелкать» на ней пользователь должен догадаться сам.
— (n-2)+(n-3)+(n-4)+…+1 это не прогрессия.
— Пояснение ни куда не годится. Нужно логически вывести формулу. Нужно объяснить как Вы считаете варианты, как получаете арифметическую прогрессию. И формула арифметической прогрессии существенно проще того, что Вы накодировали.
— «Для вопроса на выполнение…» это я вообще не понял.
Спасибо, учла замечания. Переписала объяснение решения.
Очень хорошо. Почти великолепно.
Ещё одну-две фразы уточним и будет зачтено.
0. Что Вы имеете в виду под «алгебраическая прогрессия»?
1. Не могу разобраться со стилистической и смысловой мотивацией употребления слова «оный» в данном контексте. Возможно здесь далеко не полный анализ и вы уточните свои мотивы? Нет, я догадываюсь, что это обычная референция к объекту «клетка», упоминаемому ранее в предложении. Но там не одна клетка, а две.
2. «Исходя из вышесказанного» — это снова стилистическая ошибка. Такой оборот не используют в математических текстах. Он больше характерен для официальной переписки юридической или дипломатической направленности. Математики пишут «следовательно», «тогда получаем» и т.п. Да и то, только в том случае, когда действительно имеет место логическое следование.
3. «Условие задачи смотреть здесь» — стилистически неуместное употребление императивного наклонения. Не стоит пугать читателя приказным тоном у него может не быть склонности к подчинению. Тем более условие полностью приводится тут же. Нам важно только указать на источник откуда взята задача, чтобы не нарушать авторские права. А смотреть или не смотреть этот источник дело читателя.
P.S. Понимаю, что запрещая использовать приёмы стилистического диссонанса я снижаю литературную ценность публикации, но ведь всегда остаётся proza.ru, где можно было бы опубликовать авторский вариант. Думаю, это было бы интересным новаторством — творческое литературное описание решения задачи. Но всё новое — хорошо забытое старое. Когда-то любили описывать алгоритмы в стихах.
Спасибо,очень хороший сайт. Я исправила указанные стилистические ошибки. Под алгебраической прогрессией я подразумеваю последовательность чисел, в которой каждое число, начиная со второго, получается из предыдущего добавлением к нему постоянного числа d. Надеюсь, уместно то, что я оставила эту ссылку в описании решения задачи.
Конечно уместно. Только там речь идёт об арифметической прогрессии, а не алгебраической.
Вроде бы осталось только закончить с формулами.
– Даже один символ [latex]N[/latex] это уже формула. Нужен latex. Оформите везде по тексту формулы в latex.
Спасибо, исправила.
Молодец. Зачтено.
Я правда расставил полсотни пробелов в коде программы, но это уже мой перфекционизм виноват.
UPD: У зачем Вам собственно переменная с нужна?
Спасибо, исправила код и в других своих задачах.