Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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





Доверь свою работу кандидату наук!
1500+ квалифицированных специалистов готовы вам помочь

Для того чтобы перебрать все возможные варианты разделения камней на две кучи и выбрать оптимальный, надо каким-то образом их генерировать. Допустим, у нас есть 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; Просмотров: 525; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:

  1. I. Методические рекомендации (материалы) для преподавателя
  2. II. Методические основы определения рыночной стоимости интеллектуальной собственности.
  3. II. УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ, ПРАКТИКУМЫ
  4. II. УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ, ПРАКТИКУМЫ
  5. II. УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ, ПРАКТИКУМЫ
  6. IV.УЧЕБНО-МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
  7. V. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО НАПИСАНИЮ ДИПЛОМНЫХ РАБОТ
  8. Атласы, учебно-методические пособия, практикумы
  9. В курсе для закрепления знаний по теме предусмотрено семинарское занятие по проблемам античной философии (см. методические рекомендации по семинарским занятиям)
  10. В курсе для закрепления знаний по теме предусмотрено семинарское занятие по проблемам природы человека (см. методические рекомендации по семинарским занятиям).
  11. В курсе для закрепления знаний по теме предусмотрено семинарское занятие по проблемам стратегии будущего в философии (см. методические рекомендации по семинарским занятиям).

studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.015 сек.