Форум программистов, компьютерный форум CyberForum.ru

Построить стену из блоков - C++

Восстановить пароль Регистрация
 
NoBodyIsPerfect
 Аватар для NoBodyIsPerfect
46 / 29 / 1
Регистрация: 11.06.2011
Сообщений: 206
12.11.2012, 21:18     Построить стену из блоков #1
Всем привет, интересует в какую сторону думать алгоритм: есть четыре кубика длиной в 1, один длиной в 2 и один длиной в 3. Нужно построить из них стену высотой в 3 и шириной в 3, как то так:
C++
1
2
3
1 1 1
1 1 1
1 1 1
нашими строительными блоками это будет выглядеть так:
C++
1
2
3
3
1 2
1 1 1
Как можно программно проверить что хватит/не хватит данных блоков для стены 3x3?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2012, 21:18     Построить стену из блоков
Посмотрите здесь:

C++ Перестановка блоков матрицы
API Vkontakte загрузка графики на стену C++
C++ перестановка блоков матрицы
Подбор блоков в списке C++
Проверка при помощи вложенных блоков try C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Psilon
Master of Orion
 Аватар для Psilon
5743 / 4691 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
12.11.2012, 21:22     Построить стену из блоков #2
NoBodyIsPerfect, очевидно, создать вектор
C#
1
2
3
double vector[3];
for(int i = 0; i < 3; i++)
   vector[i] = 3;
в данном случае вектор
(3,3,3)T
ну а потом вычитаем. Начиная с самого большого блока. из 3 вычитаем 3 получаем 0, получаем вектор
(0,3,3)T
блоки по 3 кончились, после этого берем блоки по 2. вычитаем получаем.
(0,1,3)T
Остаются блоки по 1. Аналогично получаем
(0,0,3)T
И точно также получаем в результате (0,0,0). Если получаем - значит хватило, если не получаем - не хватило.
NoBodyIsPerfect
 Аватар для NoBodyIsPerfect
46 / 29 / 1
Регистрация: 11.06.2011
Сообщений: 206
12.11.2012, 21:37  [ТС]     Построить стену из блоков #3
а если лишние?
Psilon
Master of Orion
 Аватар для Psilon
5743 / 4691 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
12.11.2012, 21:41     Построить стену из блоков #4
NoBodyIsPerfect, ну можно проверить последний элемент массива блоков (самый мелкий), если там 0, значит более крупные точно растащили и все потратили, если не ноль - сами понимаете.
NoBodyIsPerfect
 Аватар для NoBodyIsPerfect
46 / 29 / 1
Регистрация: 11.06.2011
Сообщений: 206
12.11.2012, 21:45  [ТС]     Построить стену из блоков #5
забыл написать, еще можно расставить в разном порядке
Psilon
Master of Orion
 Аватар для Psilon
5743 / 4691 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
12.11.2012, 21:46     Построить стену из блоков #6
NoBodyIsPerfect, посчитайте возможно это или нет, если возможно, то количество комбинаций всего n!, где n - количество "этажей". Хотя если блоки вертикально тоже можно ставить, то задача сильно усложняется.
NoBodyIsPerfect
 Аватар для NoBodyIsPerfect
46 / 29 / 1
Регистрация: 11.06.2011
Сообщений: 206
12.11.2012, 22:25  [ТС]     Построить стену из блоков #7
можно ставить только горизонтально, про количество этажей не понял
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.11.2012, 22:32     Построить стену из блоков
Еще ссылки по теме:

C++ Задача с использованием функций (блоков)
Соединение двух 32 битных блоков в 64 битный и обратно C++
Арканоид. Алгоритм отбивания шара от блоков C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Psilon
Master of Orion
 Аватар для Psilon
5743 / 4691 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
12.11.2012, 22:32     Построить стену из блоков #8
NoBodyIsPerfect, ну тогда проверяете на возможность постройки, если есть такая возможность, то количество возможных вариантов (n+k)!, где n - размер вектора, k - количество комбинаций, с помощью которых можно заменить блоки исходной задачи. В данном случае k - самый сложный для подсчета параметр. Алгоритм примерно такой
1) определяем, можно ли построить
2) если можно, смотрим, остались ли лишние блоки
3) если остались, нужно посчитать их количество и количество комбинаций, по замене (то есть у нас например остался 1 блок размером 1, мы любой блок исходной задачи размером 1 можем на него поменять, значит количество комбинаций возрастает и получается равным X, где X - кол-во единичных блоков в полученной стенке.
Если же третий пункт не нужен (то есть лишних блоков никогда не остается) то все просто
1) определяем, можно ли построить
2) если можно то cout << "Количество необходимых блоков для постройки : "<< Fac(n) << endl;
Yandex
Объявления
12.11.2012, 22:32     Построить стену из блоков
Ответ Создать тему
Опции темы

Текущее время: 08:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru