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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
NoBodyIsPerfect
47 / 30 / 1
Регистрация: 11.06.2011
Сообщений: 206
#1

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

12.11.2012, 21:18. Просмотров 459. Ответов 7
Метки нет (Все метки)

Всем привет, интересует в какую сторону думать алгоритм: есть четыре кубика длиной в 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++
похоже я злостно туплю ( проблема в сабже, на сайте вконтакта есть описание процесса 1. С помощью метода wall.getPhotoUploadServer...

Нацелить пушку так, чтобы шарик ударился сначала о стену, а затем попал в цель - C++
Всем привет. Вынужден в очередной раз просить помощи. Задача В начале координат установлена пушка, стреляющая шариками для...

Пирамиду какой наибольшей высоты можно построить из набора блоков - Pascal ABC
Замечание В приведенном примере пирамида будет состоять из двух блоков: нижним будет блок с номером 3, а верхним – блок с номером 2. Блок...

Из Wordpress на стену Вконтакте - WordPress
Есть скрипт публикации записей из блога Wordpress на стену Вконтакте http://www.plati.ru/asp/pay.asp?idd=1136872 может кому пригодится.

VK API Запись на стену пользователя - PHP
Добрый день программисты, проблема такая, токен получаю делаю запрос на запись стену пользователя которй залогинился через вконтакте ...

Зачетка об стену пдыщь! - Turbo Pascal
Program p; var mas:array of integer; I:byte; sum,proizv:integer; begin for i:=1 to 5 do readln(mas); for i:=1 to 5 do...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Psilon
Master of Orion
Эксперт .NET
5888 / 4785 / 633
Регистрация: 10.07.2011
Сообщений: 14,405
Записей в блоге: 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
47 / 30 / 1
Регистрация: 11.06.2011
Сообщений: 206
12.11.2012, 21:37  [ТС] #3
а если лишние?
Psilon
Master of Orion
Эксперт .NET
5888 / 4785 / 633
Регистрация: 10.07.2011
Сообщений: 14,405
Записей в блоге: 5
Завершенные тесты: 4
12.11.2012, 21:41 #4
NoBodyIsPerfect, ну можно проверить последний элемент массива блоков (самый мелкий), если там 0, значит более крупные точно растащили и все потратили, если не ноль - сами понимаете.
NoBodyIsPerfect
47 / 30 / 1
Регистрация: 11.06.2011
Сообщений: 206
12.11.2012, 21:45  [ТС] #5
забыл написать, еще можно расставить в разном порядке
Psilon
Master of Orion
Эксперт .NET
5888 / 4785 / 633
Регистрация: 10.07.2011
Сообщений: 14,405
Записей в блоге: 5
Завершенные тесты: 4
12.11.2012, 21:46 #6
NoBodyIsPerfect, посчитайте возможно это или нет, если возможно, то количество комбинаций всего n!, где n - количество "этажей". Хотя если блоки вертикально тоже можно ставить, то задача сильно усложняется.
NoBodyIsPerfect
47 / 30 / 1
Регистрация: 11.06.2011
Сообщений: 206
12.11.2012, 22:25  [ТС] #7
можно ставить только горизонтально, про количество этажей не понял
Psilon
Master of Orion
Эксперт .NET
5888 / 4785 / 633
Регистрация: 10.07.2011
Сообщений: 14,405
Записей в блоге: 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;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.11.2012, 22:32
Привет! Вот еще темы с ответами:

Экран во всю стену - Мониторы
День добрый! В моей организации возникла необходимость установить большой экран размерами приблизительно 2х3 метра (возможно,...

Загрузить картинку на стену в VK - Visual Basic .NET
Подскажите как загрузить изображение на стену в ВК через API Приложение зарегал id получил, токен тоже 1) photos.getWallUploadServer ...

Расчёт дипломов на стену , прыжки и тд. - Pascal ABC
Ребят , я не фонтан в программирование , но азы малые знаю . Возраст у меня мал , но пытаюсь решать задачки , нужна помощь в их решении и...

Определить давление молекул на стену - Термодинамика и МКТ
На пути молекулярного пучка стоит &quot;зеркальная&quot; стенка. Определите давление, испытываемое этой стенкой, если скорость молекул в пучке V,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
12.11.2012, 22:32
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru