Алгоритмы решения задачи про китов

Задача про китов.

Океанолог Костя метит китов цветными гарпунами с флажками 5 цветов (число цветов фиксировано). Метка определяется только количеством гарпунов и сочетанием  цветов. Т.е. красная и синяя метка издали выглядит (равноценна), как синяя и красная метка. Какое минимальное количество гарпунов ему нужно, чтобы пометить разными метками N=300 китов из большого стада?

У задачи существует комбинаторное решение. Но будем исходить из того, что Костя учился на океанолога и лучше владеет гарпунами, чем комбинаторикой. И свое стадо китов Костя пометит так, чтобы не заниматься лишней работой.

Алгоритм №1

Для этого Костя  в начале будет метить первых китов  одним гарпуном:  первые  5 китов будут иметь всего по 1 гарпуну разных цветов. Затем метка будет состоять из 2-х гарпунов. Когда будут исчерпаны все цветовые комбинации из 2-х цветов,  метка будет строиться  из 3-х  цветов и т.д., пока Костя не пометит всех N китов. (Метка строится из К гарпунов, где  К=1, 2, 3, …). Помечая каждого следующего кита, Костя  будет подсчитывать, сколько гарпунов он уже поставил. При этом, главное - это обеспечить, чтобы не повторялась цветовая комбинация меток.

Хитроумный Костя делает это так:

Собирает 5-ти цветную метку из К гарпунов:

1-ый цвет может быть от 0 до числа гарпунов- К.

2-ой  цвет может быть от 0 до числа гарпунов К – число гарпунов 1 цвета.

3-ий цвет может быть от 0 до числа гарпунов К – число гарпунов 1 цвета -  число гарпунов 2 цвета.

4 цвет может быть от 0 до числа гарпунов К – число гарпунов 1 цвета -  число гарпунов 2 цвета - число гарпунов 3 цвета.

А 5-го цвета будет столько – сколько останется.

Такое последовательное построение метки из 5 цветов обеспечивает неповторимость каждой метки. При этом надо не забывать считать китов и поставленные гарпуны, и вовремя остановиться. Костя остановится, потому, что кончатся киты.

Сколько гарпунов на ките - K	Номер цвета метки
	1	2	3	4	5	Всего гарпунов
	Кол-во гарпунов данного цвета
1	0	0	0	0	1	1
	0	0	0	1	0	2
	0	0	1	0	0	3
	0	1	0	0	0	4
	1	0	0	0	0	5
2	0	0	0	0	2	7
	0	0	0	1	1	9
	0	0	0	2	0	11
	0	0	1	0	1	13
	0	0	1	1	0	15
	0	0	2	0	0	17
	и	т.	д.

Алгоритм №2

Возможен вариант алгоритм «ленивого программиста»: - меньше пишем и думаем, хотя больше перебираем.

Собираем 5-ти цветную метку из К гарпунов:

1-ый цвет может быть от 0 до числа гарпунов К.

2-ой  цвет может быть от 0 до числа гарпунов К.

 3-ий цвет может быть от 0 до числа гарпунов К

4 цвет может быть от 0 до числа гарпунов К

5-го цвета может быть от 0 до числа гарпунов К

Проверяем правильно ли собрали метку (т.е. К гарпунов или нет)

Если да, то метим кита. Считаем очередного кита и истраченные гарпуны. Как пометили все стадо запоминаем ответ (остальной перебор пусть будет работать вхолостую – зато не пишем выход из цикла. ) А потом печатаем ответ.