KM31. Бумажные многоугольники

Задача

Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов r нужно сделать, чтобы среди полученных частей оказалось n k -угольников?

Входные данные:

Количество многоугольников n.
Количество углов многоугольника k.

Выходные данные:

Количество разрезов r.

Пример получения двух шестиугольников за 5 разрезов

Тесты

 Входные данные  Выходные данные
 №  n  k  r
 1  100  20  1699
 2  14  3  13
 3  1  3  1
 4  40  360  14279
 5  2  6  5

Код программы

 

Решение

При каждом разрезе количество кусков бумаги nувеличивается на 1. Общее количество вершин k будет увеличиваться в зависимости от места разреза. Таким образом при разрезе через две стороны общее количество вершин будет увеличиваться на 4. При разрезе через две вершины общее количество вершин увеличивается на 2, а при разрезе через сторону и вершину — на 3.

При k>3 сначала разделим лист на nчетырёхугольников при помощи разрезов через противоположные стороны. На это нам понадобиться n-1 разрезов. Затем можем, при помощи разрезов через соседние стороны, превращать каждый четырехугольник в k — угольник, на что понадобиться k-4 разрезов.Выходит, что на получение n k— угольников нужно сделать не меньше n(k-4)+n-1 разрезов, значит r=n(k-3)-1.

Если же k=3, то нам нужно, наоборот, уменьшить количество вершин. Тогда первый разрез сделаем через две вершины квадрата — получаем два треугольника, затем каждым разрезом через вершину и сторону увеличиваем количество треугольников на 1 пока не получим n. В таком случае r= n-1 . Исключение: если n=1, то r=1.

Ссылка на Ideone

http://ideone.com/X0D8jF

One thought on “KM31. Бумажные многоугольники

  1. — Сделайте правильные отступы в коде.
    — Вы забыли указать ключевые слова (метки).
    — Про ключевые слова снова забыли.

    У Вас одни и те же ошибки во всех работах.
    Я буду проверять остальные Ваши работы только после того, как Вы доделаете эту.
    Она самая простая.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *