Tagged: Головоломки

19
Апр
2020

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

Внутри поста две алгоритмические головоломки. Предложите в комментариях самое быстрое/лаконичное решение на любимом языке программирования – покажите класс!

В конце марта Библиот…

19
Фев
2020

Обыграй Сфинкса: логическая головоломка о разрезании лестниц

При каком числе квадратов в основании «лестницы» она может быть разрезана на фигуры тримино? Описание задачи подробнее – внутри поста.

Условие задачи

Вы – расхититель гробниц. Нужно пройти над пропастью по лестнице, охраняемой Сфинксом. Как водится, Сфинкс задает загадку. Решите задачу неверно – и лестница провалится в пропасть, когда вы по ней пойдете.

Условие задачи. Строительными блоками лестницы являются балки с квадратным сечением, соединенные по три таким образом, что срез имеет форму тримино (как у правой фигуры на рисунке). Для каких n можно составить лестницу из таких тройных блоков, если n – число квадратных балок в ее основании? На рисунке приведено поперечное сечение лестницы для n = 8.

Другими словами, какие лестничнообразные фигуры с основанием из n квадратов можно разрезать нацело на тримино?

Подсказка

Попробуйте решить задачу для n, равных 3, 5, 6, 9, а далее – обобщить результаты.

Идеи, ответы и программные решения можно обсудить в комментариях. Первого читателя, указавшего в комментариях под постом правильное решение, мы выделим при публикации следующей задачи (см. пример ниже).

Эта задача – пятнадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – алгоритмическую задачу о прыгающих лягушках. Ответ и новая задача будут опубликованы в 14:00 в субботу.

***

Решение алгоритмической задачи о лягушках

Если вы не решали эту задачу, прежде чем читать приведенный ниже текст, прочитайте условие и попробуйте решить самостоятельно!

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

Прыжок – единственный способ, которым лягушки противоположного вида могут преодолеть друг друга. Мы сталкивались с этим ранее в предыдущих задачах: получается, что для того, чтобы преодолеть друг друга, им необходимо совершить n2 прыжков в случае n настоящих и n виртуальных лягушек.

Сдвиг. Рассмотрим далее ситуацию для лягушек одного вида. Мы знаем, что они не могут перепрыгивать друг через друга. Первая лягушка переместится на n + 1 клеток и окажется в ячейке n + 2, вторая лягушка передвинется на n + 1 клеток до ячейки n + 3, и т. д. Чтобы оказаться в нужной позиции, вместе все лягушки одного вида должны переместиться на n (n + 1) клеток. Аналогично должны сделать их виртуальные аналоги. То есть все эти реальные и виртуальные земноводные переместятся на 2 n (n + 1) клеток. Поскольку один прыжок охватывает две ячейки, и их n2, количество сдвигов должно составить 2n (n + 1) – 2n2 = 2n.

Алгоритм. Существует два симметричных алгоритма для решения головоломки: один начинается со сдвига крайней к пустой ячейки настоящей лягушки, другой – со сдвига виртуальной. Опишем первый. Алгоритм может быть получен методом грубой силы: его ходы определены однозначно, потому что альтернативные ходы приводят к очевидным тупиковым ситуациям. В частности, когда есть выбор между сдвигом и прыжком, должен быть сделан прыжок.

Ниже приведены алгоритмы для n = 2 и n = 3 соответственно. Настоящие лягушки обозначены T, виртуальные – F.

Решение для n = 2
            1 TT_FF 
2 T_TFF
3 TFT_F
4 TFTF_ 
5 TF_FT 
6 _FTFT
7 F_TFT
8 FFT_T
. FF_TT
        
Решение для n = 3
            1  TTT_FFF
2  TT_TFFF
3  TTFT_FF
4  TTFTF_F
5  TTF_FTF
6  T_FTFTF
7  _TFTFTF
8  FT_TFTF
9  FTFT_TF
10 FTFTFT_
11 FTFTF_T
12 FTF_FTT
13 F_FTFTT
14 FF_TFTT
15 FFFT_TT
.  FFF_TTT
        

Головоломка может быть легко обобщена на случай с m и n лягушками разных видов. Общее количество необходимых ходов равно mn + m + n, из которых mn – количество прыжков, а m + n – число сдвигов.

Ответ: для 3 лягушек с каждой стороны достаточно 15 ходов.

Ответ на вопрос со звёздочккой: Для m и n лягушек достаточно mn + m + n ходов.

Как ответили читатели Библиотеки программиста? Сам ответ о числе переходов первым дал пользователь wil4, но без указания решения:

15 для n=3

Первым ответ с решением, но с чуть большим числом ходов дал пользователь mr.fantazylight:


В комментариях к решению задачи мы обсудили, откуда берутся два лишних хода.

Программное решение, находящее алгоритм для любого m и n, реализовал на С++ пользователь krotbsod. Вот пример для m = 3 и n = 5:


Автор решения krotbsod будет рад получить комментарии относительно кода: https://pastebin.com/Qm3Ru08L.

            #include <iostream>
#include <cstring>
 
using namespace std;
 
//!!! P.S. Некоторые проверки в программе не выполняются, для упрощения восприятия
 
/**
 * @brief Генерируем лягушек
 * @param frogs Указатель на массив с лягушками [m + n + 1] размерности
 * @param m T лягушек
 * @param n F лягушек
 **/
void generateFrogs(char *frogs, const int m , const int n) {
    int count = m + n + 1;
    memset(frogs, ' ', count);
 
    for(int i = 0; i < m; i++) {
        frogs[i] = 'T';
    }
    for(int i = m + 1; i < count; i++) {
        frogs[i] = 'F';
    }
}
 
/**
 * @brief Заданные шаблоны поведения лягушек возле свободной ячейки
 */
struct Patterns{
public:
 
    // T1 <-- Цифра - количество шагов
    // ^
    // |
    // Символ - тип лягушки
    /**
     * @brief Задаем шаблоны в конструкторе структуры и записываем указатели в m_list
     */
    Patterns() {
        m_list[0] = "TF FT"; // T2
        m_list[1] = "FT TF"; // F2
 
        m_list[2] = "FF FT"; // F1
        m_list[3] = "TT TF"; // F2
 
        m_list[4] = "FF TF"; // F2
        m_list[5] = "TT FT"; // T1
 
        m_list[6] = "TF FF"; // T2
        m_list[7] = "FT TT"; // T1
 
        m_list[8] = "FT FF"; // F1
        m_list[9] = "TF TT"; // T2
 
        m_list[10] = "FT FT"; // F1 or T1
        m_list[11] = "TF TF"; // lock
 
        m_list[12] = "TT FF"; // F1 or T1
 
        m_list[13] = "FF FF"; // F1;
        m_list[14] = "TT TT"; // T1;
 
        m_list[15] = "FF TT"; // done
    }
    /**
     * @brief Возвращает указатель на заданный шаблон.
     * Нужна лишь для итеративного поиска.
     * @param num Номер шаблона в m_list
     * @return Указатель на заданный шаблон
     */
    const char *pattern(const int &num) {
        // Проверку не стал делать, для упрощения восприятия
        return m_list[num];
    }
    /**
     * @brief Возвращает число шаблонов
     * @return Число шаблонов
     */
    int size() {
        return m_size;
    }
 
private:
    static const int m_size = 16;
    // Массив с указателями на массивы шаблонов
    const char *m_list[m_size];
 
} frog_patterns;
 
/**
 * @brief Получение текущего состояния (шаблона) в массиве с лягушками
 * @param currentPattern Указатель на формируемый массив для записи в него шаблона
 * @param frogs Указатель на массив с лягушками
 * @param count Размер массива с лягушками
 * @param iter Текущее положение пробела
 */
void getCurrentPattern(char *currentPattern, char *frogs, const int &count, const int &iter) {
    //Задаем шаблон текущего положения для последующего сравнения с заданными шаблонами
    memcpy(currentPattern, &frogs[iter - 2], 5); // dangerous !!! Опасно, выходим за рамки заданного массива. Но работает
 
    // Задаем МНИМЫХ лягушек в текущий шаблон для последующего сравнения с заданными шаблонами.
    // Когда символ пробела находится с краю, например: 'FF |' или '|T FF'  (где | край массива)
    // То приходим в несколько неодназначную ситуацию.
    // Проще всего этого избежать добавив МНИМЫХ лягушек в шаблон для сравнения.
    // Для конечных точек характеры следующие МНИМЫЕ лягушки:   Для начального положения(крайнего левого предела) характерна мнимая F
    //                                                          Для последнего положения(крайнего правого предела) характерна мнимая T
    // P.S. МНИМЫЕ лягушки на то и мнимые, они ни как не дополняют исходный массив, они лишь заполняют шаблон для сравнения.
 
    if(iter == 0) {
        currentPattern[0] = 'F';
        currentPattern[1] = 'F';
    }
    if(iter == 1) {
        currentPattern[0] = 'F';
    }
    if(iter == (count - 1)) {
        currentPattern[3] = 'T';
        currentPattern[4] = 'T';
    }
    if(iter == (count - 2)) {
        currentPattern[4] = 'T';
    }
}
 
/**
 * @brief Перемещение лягушки на место пустой ячейки
 * @param frogs Указатель на массив с лягушками
 * @param iter Текущее положение пробела
 * @param type Тип лягушки
 * @param step Шаг для перемещения лягушки
 */
void moveFrog(char *frogs, const int &iter, const char &type, const int &step) {
    if(type == 'F') {
        frogs[iter] = frogs[iter + step];
        frogs[iter + step] = ' ';
    }
    if(type == 'T') {
        frogs[iter] = frogs[iter - step];
        frogs[iter - step] = ' ';
    }
}
 
/**
 * @brief Основной цикл сравнения состояний
 * @param frogs Указатель на массив с лягушками
 * @param m T лягушек
 * @param n F лягушек
 * @param iter Текущее положение пробела
 * @return Возвращает 1, если перемещение всех лягушек завершено. В остальных случаях 0.
 */
int move(char *frogs, const int &m , const int &n, const int &iter) {
    int count = m + n + 1;
 
    char currentPattern[5];
    memset(currentPattern, ' ', 5);
    getCurrentPattern(currentPattern, frogs, count, iter);
 
    // Проходим по всем заданным шаблонам
    for(int i = 0; i < frog_patterns.size(); i++) {
        // Сравниваем
        int rescmp = memcmp(currentPattern, frog_patterns.pattern(i), 5);
        if(rescmp == 0) {
            // При совпадении перемещаем
            switch (i) {
            case 0:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 1:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 2:
                moveFrog(frogs, iter, 'F', 1); // F1
                break;
            case 3:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 4:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 5:
                moveFrog(frogs, iter, 'T', 1); // T1
                break;
            case 6:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 7:
                moveFrog(frogs, iter, 'T', 1); // T1
                break;
            case 8:
                moveFrog(frogs, iter, 'F', 1); // F1
                break;
            case 9:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 10:
                moveFrog(frogs, iter, 'F', 1); // F1 or T1
                break;
            case 12:
                if((m % 2) == 0) {
                    moveFrog(frogs, iter, 'T', 1);
                } else {
                    moveFrog(frogs, iter, 'F', 1);
                }
                //moveFrog(frogs, iter, 'F', 1); // F1 or T1 //if m is even use T1
                break;
            case 13:
                moveFrog(frogs, iter, 'F', 1);
                break;
            case 14:
                moveFrog(frogs, iter, 'T', 1);
                break;
            case 15:
                return 1;
                break;
            }
        }
    }
    return 0;
}
 
/**
 * @brief Запуск цикла алгоритма
 * @param m T лягушек
 * @param n F лягушек
 */
void jumpAlg(const int m , const int n) {
    int count = m + n + 1;
    char frogs[count + 1];      // +1 чтобы добавить символ \0 в конец, для корректного вывода через printf
    frogs[count] = '\0';        // тут и добавим
    generateFrogs(frogs, m, n); // Генерируем массив с лягушками
 
    int counter = 0;
    while(true) {
        printf("%s\n", frogs);
        int ret = 0;
        for(int iter = 0; iter < count; iter++) {
            // При нахождении пробела, входим в Основной цикл сравнения состояний
            if(frogs[iter] == ' ') {
                ret = move(frogs, m, n, iter);
                break;
            }
        }
        if(ret == 1) {
            printf("Count steps: %d\n", counter);
            break;
        }
        counter++;
    }
}
 
int main()
{
    //
    // T, F
    jumpAlg(3, 5);
    return 0;
}
        

Спасибо, что присылаете в комментарии свои ответы и решения!

15
Фев
2020

Прыг-прыг. Алгоритмическая головоломка о лягушках

За сколько ходов лягушки обменяются местами? Лягушки прыгают по очереди на пустую клетку, когда та рядом или через одну лягушку противоположного цвета. Подробнее – в тексте публикации.

Условие задачи

Как вы могли заметить по логотипу, Библиотеке программиста нравятся лягушки 🐸. Как настоящие (T), так и игрушечные (F). Однажды мы наблюдали такую сценку. На одномерной доске с 2n + 1 ячейками в первых n ячейках разместились n истинных лягушек в n первых ячейках и n лягушек-игрушек в последних n ячейках. По одной лягушке в ячейке, и ещё одна ячейка, разделяющая семейства. На рисунке показан случай для n = 3.

T и F делают ходы по очереди. В рамках хода лягушка прыгает на пустую клетку. Напрямик или перепрыгнув через представителя противоположного семейства. Через своих сородичей лягушки одного типа не прыгают, это считается неуважительным. Трушные лягушки двигаются только вправо, фейковые – влево. В результате перепрыгиваний они хотят обменяться местами, как на картинке.

Вопрос: сколько ходов потребуется для 3 T и 3 F? Предложите алгоритм решения задачи.

Вопрос со звёздочкой 🌟: сколько ходов нужно для m T и n F, если m и n не равны?

Программное решение✨: попробуйте реализовать визуализацию решения для общего случая (из вопроса со звёздочкой) на любимом языке программирования. Напишите функцию, которая принимает на вход числа m и n, а возвращает число ходов, а также последовательность строк, содержащих T, F и пробел для пустой ячейки. Каждая строка соответствует одном ходу.

Идеи, ответы и программы можно обсудить в комментариях. Первого читателя, указавшего в комментариях под постом правильное решение, мы выделим при публикации следующей задачи (см. пример ниже).

Эта задача – четырнадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – задачу о взломе банковского замка. Ответ и новая задача будут опубликованы в 14:00 в среду.

***

Решение задачи о взломе банковского замка

Ответ: 85.

Решение. Решим задачу в общем случае, то есть для любого числа n. Пронумеруем переключатели слева направо от 1 до n и обозначим состояния переключателя «включено» и «выключено» соответственно как 1 и 0. Чтобы помочь себе в решении общего случая головоломки, начнём с решения четырёх самых простых примеров.


Теперь рассмотрим общий пример головоломки, когда исходная строка состоит из n единиц:

111, ... , 1.

Прежде чем мы сможем выключить самый левый переключатель, переключатели должны находиться в состоянии

110, ... , 0.

Следовательно, для начала нам нужно отключить последние n – 2 переключателей и сделать это за минимальное количество ходов. Другими словами, мы должны сначала решить ту же проблему, что и для последних n – 2 переключателей. Это может быть сделано рекурсивно с использованием решений для случаев n = 1 и n = 2.

После этого мы сможем переключить первый переключатель, чтобы получить

010, ... , 0.

Теперь, прежде чем мы сможем переключить второй переключатель, нам придётся пройти через такое состояние, при котором все переключатели, следующи за ним будут «вкл». Перевести все переключатели с третьего по последний на «вкл» можно, поменяв последовательность ходов, сделанных ранее, на обратную, чтобы переключить последние n – 2 переключателей из положения «вкл» в положение «выкл». Это даст нам

011, ... , 1.

Обозначим M(n) количеством переключений, сделанных алгоритмом. Получится следующее рекуррентное выражение:

или сокращённо:

для

Решение рекуррентного уравнения по стандартной методике для линейных неоднородных рекуррентных уравнений второго порядка с постоянными коэффициентами даёт следующий необычный результат:

для

Для чётных n данная формула сводится к

Для нечётных:

Действительно: если n = 7, то M(n) = 85.

Как ответили читатели Библиотеки программиста? Алгоритмические ответы с указанием рекуррентных соотношений дали читатели lasangqwerty и maximzombi:

f(n) = f(n-1) + 2*f(n-2) + 1, f(7) = 85
Посчитаем ответ для случая с 1 и 2 тумблерами: f(1)=1 f(2) = 2 Пусть тумблеров n штук. Чтобы выключить самый левый, нужно, чтобы (n-1)-ый тумблер слева остался вкл, а остальные выкл. Чтобы выключить n-2 левых, нужно f(n-2) переключений. Также нужно переключить сам левый тумблер (т.е. еще одно переключение). Итого этими действиями мы привели тумблеры к виду: 0100…00, где 1 – вкл, 0 – выкл Чтобы выключить (n-1)-й тумблей, нужно включить все тумблеры правее него(т.е. нужно включить только (n-2)-й тумблер, но для его включения нужно включить (n-3)-й тумблей и т.д.). Чтобы включить все тумблеры правее (n-1)-го, необходимо также f(n-2) действий. Теперь тумблеры имеют вид 0111…11 Осталось перевести все тумблеры левее самого левого в режим выкл., на что понадобится f(n-1) действий. Итого получаем рекуррентную формулу: f(1)=1, f(2)=2, f(n)=f(n-2) * 2 + f(n-1) + 1 => f(7) = 85

Читатель wil4 привёл саму последовательность переключений:

1111111 1111110 1111010 1111011 1111001 1111000 1101000 1101001 1101011 1101010 1101110 1101111 1101101 1101100 1100100 1100101 1100111 1100110 1100010 1100011 1100001 1100000 0100000 0100001 0100011 0100010 0100110 0100111 0100101 0100100 0101100 0101101 0101111 0101110 0101010 0101011 0101001 0101000 0111000 0111001 0111011 0111010 0111110 0111111 0111101 0111100 0110100 0110101 0110111 0110110 0110010 0110011 0110001 0110000 0010000 0010001 0010011 0010010 0010110 0010111 0010101 0010100 0011100 0011101 0011111 0011110 0011010 0011011 0011001 0011000 0001000 0001001 0001011 0001010 0001110 0001111 0001101 0001100 0000100 0000101 0000111 0000110 0000010 0000011 0000001 0000000

Также задача подробно обсуждалась в нашем сообществе вк, там вы можете увидеть много различных подходов, в том числе ручной перебор и программные решения. Первым точное решение привёл Сергей Семёнов.

85, рекуррентно, для включения четного тумблера надо повторить все предыдущие переключения, для нечетного еще одно, a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1
12
Фев
2020

Как ограбить банк? Логическая задача

Эту задачу трудно решить аналитически… Но можно попробовать сделать это хотя бы программно. Смогли бы вы вскрыть необычный банковский замок?

Условие задачи

08
Фев
2020

Карточная головоломка Конвея

Алгоритмическая задача об одиночной карточной игре. Головоломка придумана известным британским математиком Джоном Х. Конвеем.

Условие задачи

01
Фев
2020

Задача о беглеце

Новая головоломка о спасении заключённого и подробно иллюстрированный ответ на решение задачи о шести шахматных конях.

Условие задачи о беглеце

29
Янв
2020

Задача о шести шахматных конях

Сегодня нам предстоит алгоритмическая задача с позиционным обменом двух типов объектов. Наглядно такое движение можно представить через перемещение шахматных коней.

Услов…

22
Янв
2020

Задача о часах с одинаковыми стрелками

На механических часах минутная и часовая стрелки сделаны одинаковыми. При скольких положения стрелок нельзя точно узнать время?

Эта задача – седьмой эпизод нашего сериала головол…

18
Янв
2020

Задача о прогуливающихся джентльменах

Логическая головоломка о прогулке двух джентльменов-близнецов по аллее с ответвлениями. Неизбежна ли встреча?

Эта задача – шестой эпизод нашего сериала головоломок. После описания задачи идёт ответ на преды…

14
Янв
2020

Задача о фамилии Тьюринга

Мы посвящаем следующую задачу Алану Тьюрингу (1912–1954) – английскому математику и криптографу, который, помимо других замечательных достижений, сыграл ведущую роль в развитии теоретической информатики.

Эт…

13
Янв
2020

Задача об острове хамелеонов

История о меняющих цвет ящерицах и ответ на предыдущую задачу. Кто решит первым? Следим за комментариями на сайте.

Эта задача – третий эпизод нашего сериала головоломок. После описания задачи идёт ответ на …

11
Янв
2020

Задача о двойных фамилиях

Головоломка в рамках нового формата. Практичный вопрос о вариантах новой фамилии семьи, в которой оба супруга до брака носили составные фамилии.

Новый формат. Каждый день в 14:00 будем публиковать в Библиот…