Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
1

Методом "разделяй и властвуй" построить башни

18.06.2018, 18:15. Просмотров 1040. Ответов 13
Метки нет (Все метки)

Всем привет, последняя задачу которую нужно решить)

Есть бесконечное количество блоков размера 2x1x1.
Сколько разных блоков (башен) заданной высоты в форме кубоида у которых площадь нижней грани равна 2x2 можно сделать? Отражения и повороты также считаются.
Ввод: натуральное число. Рассматриваемая высота будет 2^n
Примеры:
1 Пример:
Ввод:
0
Вывод:
2
2 Пример:
Ввод
1
Вывод
9
3 Пример:
Ввод
7
Вывод
5409

1 Пример:
Название: q.jpg
Просмотров: 50

Размер: 7.4 Кб

Высота тут 1, в 3Д не смог нарисовать

Для начала подойдёт просто алгоритм без "разделяй и властвуй". У кого будет алгоритм решения, прошу не писать его сразу, хочу попытаться сам додуматься с помощью подсказок.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.06.2018, 18:15
Ответы с готовыми решениями:

Поиск максимального элемента в массиве методом "разделяй и властвуй"
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его...

Методом "разделяй и властвуй" посчитать задания
Тема больше не актуальна Всем привет, снова мучаюсь с задачей вот уже пару дней. Ввод: ...

В каких случаях лучше использовать алгоритм "разделяй и властвуй"?
Подскажите, в каких случаях лучше использовать алгоритм разделяй и властвуй? Как оформить этот...

Разделяй и властвуй: сумма произведений попарных элементов массивов
Всем привет. Есть задача. Дан массив А из 150 чисел, который начинается с 2 и каждый следующий...

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле...

13
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
18.06.2018, 18:32  [ТС] 2
Все блоки одинаковые
Возможно рисунок не правильный
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
18.06.2018, 18:40  [ТС] 3
Возможно это только 1 вариант на картинке. Второй будет с 4 блоками которые все "вытянутые" вверх"

Добавлено через 6 минут
Ах нет, высота ведь 1, запутался немного, значит картинка правильная должна быть
Название: x2zqAFf.jpg
Просмотров: 43

Размер: 5.0 Кб
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
18.06.2018, 21:54  [ТС] 4
Высота 2.

Методом "разделяй и властвуй" построить башни


Красные просто потому что там все лежат плашмя так сказать, чтоб их отделить, может в этом есть какой то смысл
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
20.06.2018, 19:58  [ТС] 5
Скорее всего нужно найти рекурсивную функцию или рекуррентное соотношение. кое как, не уверен что правильно, для высоты равной 4 нашел 81 кубоид

Добавлено через 19 часов 14 минут
Из за того что числа быстро возрастают ответ будет mod 10^5 (для 7 уже сделано)
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
20.06.2018, 20:20 6
не знаю, как описать этот подход, не рассказав все.
вроде достаточно знать высоту уже построенной целиком части башни (не имеющей пробелов, имеющей объем 4*эту самую высоту) и маску из восьми битов, описывающую присутствие/отсутствие кубика в данной позиции. 8 позиций - это четыре позиции в верхнем слое и в предыдущем. на этих состояниях вроде можно написать динамику.
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
21.06.2018, 16:02  [ТС] 7
Цитата Сообщение от salam Посмотреть сообщение
не знаю, как описать этот подход, не рассказав все.
вроде достаточно знать высоту уже построенной целиком части башни (не имеющей пробелов, имеющей объем 4*эту самую высоту) и маску из восьми битов, описывающую присутствие/отсутствие кубика в данной позиции. 8 позиций - это четыре позиции в верхнем слое и в предыдущем. на этих состояниях вроде можно написать динамику.
Близится дедлайн так что хочу быстрей уже решить
Почему кубик может отсутствовать если башня построена целиком?

На SO есть ответ но не понятно как это в код переписать и вообще "разделяй и властвуй" это или нет, надеюсь за это не будут ругать не ссылка все таки: possibilities-to-construct-2n-height-tower-with-2x2-base-of-2x1x1-blocks
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
22.06.2018, 12:36 8
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Почему кубик может отсутствовать если башня построена целиком?
Целиком построена часть башни. А в двух верхних слоях могут быть пропуски.

Добавлено через 19 часов 6 минут
Когда мы делим башню пополам, то на месте среза возможны случаи:
1. Срез не пересекает ни одну деталь
2. Срез пересекает 2 детали (4 варианта)
3. Срез пересекает 4 детали

Для каждого из этих случаев нужно посчитать варианты для получающихся подбашен и перемножить.
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
22.06.2018, 20:55  [ТС] 9
Цитата Сообщение от Shamil1 Посмотреть сообщение
Целиком построена часть башни. А в двух верхних слоях могут быть пропуски.
Этого я не понимаю, какие могут отсутствовать?

Название: 5x8hUyV.jpg
Просмотров: 25

Размер: 6.2 Кб

Это два верхних слоя в которых не хватает 2 вариантов?
Первый: два горизонтально
Второй: два вертикально
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
23.06.2018, 02:45 10
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Это два верхних слоя в которых не хватает 2 вариантов?
Это два верхних слоя, в которых пустые 4 места.
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
23.06.2018, 15:56  [ТС] 11
Цитата Сообщение от Shamil1 Посмотреть сообщение
Когда мы делим башню пополам, то на месте среза возможны случаи:
1. Срез не пересекает ни одну деталь
2. Срез пересекает 2 детали (4 варианта)
3. Срез пересекает 4 детали
Для каждого из этих случаев нужно посчитать варианты для получающихся подбашен и перемножить.
Для первого получается: 2 варианта
Для второго получается: 4 варианта
Для 3 получается: 1 вариант

И как теперь делать рекурсию?

C
1
2
3
4
5
6
7
8
9
10
11
12
int divide(int n) {
    if (n == 1) {
        return 2;
    }
    if (n == 2) {
        return 9;
    }
 
//ни одну деталь, 2, 4
    return 2*divide(n-1)+4*divide(n-1)+1*divide(n-2);//когда нужно n-1 или n-2?
 
}
Программу написали (немного другую), осталось мне понять как это работает)
Для высот 4, 8 получилось 121, 23409 соответственно

Добавлено через 19 минут
Цитата Сообщение от Shamil1 Посмотреть сообщение
Для каждого из этих случаев нужно посчитать варианты для получающихся подбашен и перемножить.
Для этого ведь рекурсивные вызовы нужны? Что б подсчитать получающиеся подбашни
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
24.06.2018, 12:03 12
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Для первого получается: 2 варианта
Для первого случая всего 1 вариант - ровный, гладкий разрез.

Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Для 3 получается: 1 вариант
Да, но для него не нужна отдельная функция/опция. Просто вместо эн/2 будет эн/2 - 1.

Цитата Сообщение от Dimitrij1 Посмотреть сообщение
И как теперь делать рекурсию?
У кусочков башни будет по два разреза - снизу и сверху. Итого получается 5*5 = 25 разных вариантов. Но можно сократить с учётом симметрии.
На первый взгляд варианты:
1. с обеих сторон плоско
2. с одной стороны плоско
3. с двух сторон выступы у одной грани
4. с двух сторон выступы у соседних гранях
5. с двух сторон выступы у противоположных гранях

Итого получается 5 рекурсивных функций, принимающих эн = количество полных слоёв. Если эн меньше 2, то сразу возвращают ответ (посчитать вручную количество вариантов).

Добавлено через 18 часов 23 минуты
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
3 Пример:
Ввод
7
Вывод
5409
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Для высот 4, 8 получилось 121, 23409 соответственно
Что-то тут не сходится. Для высоты 128 не может быть так мало.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
24.06.2018, 12:57 13
Лучший ответ Сообщение было отмечено Dimitrij1 как решение

Решение

Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Программу написали (немного другую), осталось мне понять как это работает)
Для высот 4, 8 получилось 121, 23409 соответственно
У меня получилось 2, 9, 121, 23409, 880961761.
Для ввода 7 (высота 128) у меня получается 10071226920676852384094815383518119205428915344776495246434549617720305409. Это несколько отличается от 5409 из условия.


C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
void Main()
{
    int n = 3;
    BigInteger res = Solve(n);
    Console.WriteLine(res);
}
 
BigInteger Solve(int k)
{
    int n = (int)Math.Pow(2, k);
    return BothFlat(n);
}
 
BigInteger BothFlat(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 2;
    
    int n1 = (n - 2)/2;
    int n2 = n - 2 - n1;
    
    return BothFlat(n1 + 1) * BothFlat(n2 + 1)
         + BothFlat(n1) * BothFlat(n2)
         + OneFlat(n1) * OneFlat(n2) * 4;
}
 
BigInteger OneFlat(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 3;
 
    int n1 = (n - 2) / 2;
    int n2 = n - 2 - n1;
 
    return BothFlat(n1 + 1) * OneFlat(n2 + 1)
         + BothFlat(n1) * OneFlat(n2)
         + OneFlat(n1) * AdjacentSide(n2) * 2
         + OneFlat(n1) * SameSide(n2)
         + OneFlat(n1) * OppositeSide(n2);
}
 
BigInteger SameSide(int n)
{
    if (n == 0) return 2;
    if (n == 1) return 4;
 
    int n1 = (n - 2) / 2;
    int n2 = n - 2 - n1;
 
    return OneFlat(n1 + 1) * OneFlat(n2 + 1)
         + OneFlat(n1) * OneFlat(n2)
         + AdjacentSide(n1) * AdjacentSide(n2) * 2
         + SameSide(n1) * OppositeSide(n2)
         + OppositeSide(n1) * SameSide(n2);
}
 
BigInteger AdjacentSide(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 4;
 
    int n1 = (n - 2) / 2;
    int n2 = n - 2 - n1;
 
    return OneFlat(n1 + 1) * OneFlat(n2 + 1)
         + OneFlat(n1) * OneFlat(n2)
         + AdjacentSide(n1) * OppositeSide(n2)
         + AdjacentSide(n1) * SameSide(n2)
         + SameSide(n1) * AdjacentSide(n2)
         + OppositeSide(n1) * AdjacentSide(n2);
}
 
BigInteger OppositeSide(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 5;
 
    int n1 = (n - 2) / 2;
    int n2 = n - 2 - n1;
 
    return OneFlat(n1 + 1) * OneFlat(n2 + 1)
         + OneFlat(n1) * OneFlat(n2)
         + AdjacentSide(n1) * AdjacentSide(n2) * 2
         + SameSide(n1) * SameSide(n2)
         + OppositeSide(n1) * OppositeSide(n2);
}

Не по теме:

з.ы. Давно я в трёхмерный тетрис не играл :).



Добавлено через 21 минуту
Цитата Сообщение от Shamil1 Посмотреть сообщение
Это несколько отличается от 5409 из условия.
Видимо, нужно вывести последние 4 или 5 цифр ответа. То есть, в моём коде BigInteger надо заменить на int и ответ возвращать по модулю.
1
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
24.06.2018, 13:52 14
Вариант с сохранением промежуточных результатов в словаре, чтобы не считать одно и то же несколько раз:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
void Main()
{
    Console.WriteLine(Solve(7));
}
 
enum Tower { BothFlat, OneFlat, SameSide, AdjSide, OppSide }
 
int Solve(int k)
{
    const int mod = 10_000;
    Dictionary<(int, Tower), int> dic = new Dictionary<(int, Tower), int>()
    {
        {(0, Tower.BothFlat), 1}, {(1, Tower.BothFlat), 2},
        {(0, Tower.OneFlat), 1}, {(1, Tower.OneFlat), 3},
        {(0, Tower.SameSide), 2}, {(1, Tower.SameSide), 4},
        {(0, Tower.AdjSide), 1}, {(1, Tower.AdjSide), 4},
        {(0, Tower.OppSide), 1}, {(1, Tower.OppSide), 5},
    };
 
    int loop(int n, Tower type)
    {
        if (!dic.TryGetValue((n, type), out int res))
        {
            int n1 = (n - 2) / 2;
            int n2 = n - 2 - n1;
 
            switch(type)
            {
                case Tower.BothFlat:
                    res = loop(n1 + 1, Tower.BothFlat) * loop(n2 + 1, Tower.BothFlat)
                        + loop(n1, Tower.BothFlat) * loop(n2, Tower.BothFlat)
                        + loop(n1, Tower.OneFlat) * loop(n2, Tower.OneFlat) * 4;
                    break;
                case Tower.OneFlat:
                    res = loop(n1 + 1, Tower.BothFlat) * loop(n2 + 1, Tower.OneFlat)
                        + loop(n1, Tower.BothFlat) * loop(n2, Tower.OneFlat)
                        + loop(n1, Tower.OneFlat) * loop(n2, Tower.AdjSide) * 2
                        + loop(n1, Tower.OneFlat) * loop(n2, Tower.SameSide)
                        + loop(n1, Tower.OneFlat) * loop(n2, Tower.OppSide);
                    break;
                case Tower.SameSide:
                    res = loop(n1 + 1, Tower.OneFlat) * loop(n2 + 1, Tower.OneFlat)
                        + loop(n1, Tower.OneFlat) * loop(n2, Tower.OneFlat)
                        + loop(n1, Tower.AdjSide) * loop(n2, Tower.AdjSide) * 2
                        + loop(n1, Tower.OppSide) * loop(n2, Tower.SameSide)
                        + loop(n1, Tower.SameSide) * loop(n2, Tower.OppSide);
                    break;
                case Tower.AdjSide:
                    res = loop(n1 + 1, Tower.OneFlat) * loop(n2 + 1, Tower.OneFlat)
                        + loop(n1, Tower.OneFlat) * loop(n2, Tower.OneFlat)
                        + loop(n1, Tower.AdjSide) * loop(n2, Tower.OppSide)
                        + loop(n1, Tower.AdjSide) * loop(n2, Tower.SameSide)
                        + loop(n1, Tower.OppSide) * loop(n2, Tower.AdjSide)
                        + loop(n1, Tower.SameSide) * loop(n2, Tower.AdjSide);
                    break;
                case Tower.OppSide:
                    res = loop(n1 + 1, Tower.OneFlat) * loop(n2 + 1, Tower.OneFlat)
                        + loop(n1, Tower.OneFlat) * loop(n2, Tower.OneFlat)
                        + loop(n1, Tower.AdjSide) * loop(n2, Tower.AdjSide) * 2
                        + loop(n1, Tower.SameSide) * loop(n2, Tower.SameSide)
                        + loop(n1, Tower.OppSide) * loop(n2, Tower.OppSide);
                    break;
            }
            res %= mod;
            dic.Add((n, type), res);
        }
        return res;
    }
    
    return loop(1 << k, Tower.BothFlat);
}
Ответ считаю по модулю 10,000 (последние 4 цифры), так как для 100,000 int переполняется.

Добавлено через 10 минут
Возведение в степень можно (нужно!) заменить на сдвиг.
0
24.06.2018, 13:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.06.2018, 13:52

"Магический квадрат" - построить алгоритм заполнения в виде блок схемы
Подскажите пожалуйста как это осуществить. С конкретным числом легко. А когда вводится случайное,...

Алгоритм роста "квадрата" или как работает "черный ящик"
Хочу спросить совета по нахождению формулы для &quot;черного ящика&quot;, который на входе принимает 2...

Из пункта "А" приехать в пункт "Б" и показать возможные траектории движения
Задача вот такая: надо из пункта &quot;А&quot; приехать в пункт &quot;Б&quot; и показать возможные траектории движения....


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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