Бесценные методические указания

Для того чтобы перебрать все возможные варианты разделения камней на две кучи и выбрать оптимальный, надо каким-то образом их генерировать. Допустим, у нас есть 8 камней. Тогда введем целочисленный массив Stones из 8 элементов и будем в него записывать 1 и 0: 1 будет указывать на принадлежность камня к первой куче, а 0 – соответственно ко второй (или наоборот – все равно). Тогда, если мы переберем все возможные сочетания 1 и 0, то мы таким образом рассмотрим и все возможные варианты разделения камней на две кучи. Но как реализовать алгоритм генерирования этих всевозможных сочетаний 1 и 0? Шерлок Холмс сказал бы так: «Элементарно, Ватсон!».

Давайте возьмем один единственный байт Byte и будем трактовать значения его бит (а это 1 или 0) как принадлежность камня к одной или другой куче. Очевидно, нам не подходит случай, когда все биты одинаковы: равны 0 или 1. Будем присваивать байту последовательно значения 1, 2, 3 и т.д., т.е. будем просто для получения нового варианта разделения камней просто прибавлять к байту значение 1:

Значения бит	Значение байта Byte
…

Теперь уже можно поступить таким образом: проверять значения бит байта Byte и, соответственно, присваивать 0 и 1 элементам массива Stones. Теперь, анализируя значения элементов массива Stones, можно подсчитать вес одной и второй кучи камней, найти их разность, сравнить ее с предыдущим вариантом и запомнить как лучшую или отвергнуть.

Кстати, вы заметили, что значение байта 254 дает тот же вариант разделения камней на две кучи, что и значение 1? Может быть это не единственная «накладка» и можно сократить число рассматриваемых вариантов?

Совсем нетрудно догадаться, что если камней не 8, а больше, то надо взять не один байт, а два, четыре или 8 (тип __int64). Если и этого мало, то придется взять массив байтов и несколько усложнить алгоритм.

В качестве подсказки посмотрите на приведенный ниже текст функции PrintVariants, которая генерирует варианты разделения камней на две кучи и выводит их для частного случая 8 камней. Если запустить эту функцию на выполнение, то она выведет 255 вариантов разделения камней на две кучи.

Задание.

Во-первых, постарайтесь понять, чем закомментированный вариант PrintVariants отличается от реализованного.

Во-вторых, проанализируйте, не генерирует ли функция повторяющихся вариантов.

В-третьих, как надо усовершенствовать функцию, чтобы она работала не только для случая 8 камней, но и для случаев меньшего и большего числа камней?

Разработайте алгоритм и программу, которая бы позволяла решать задачу о камнях путем полного перебора вариантов разделения камней.

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

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

Варианты заданий

Номер компьютера	Максимальное число камней

Дата добавления: 2014-12-26