Написать пост

Развиваем мышление: три простые задачи на логику

Аватар Андрей Приб

Коротенькая подборка задач на логику для программистов: экспериментальная производственная линия, поиск кота и подъём по ступенькам.

Обложка поста Развиваем мышление: три простые задачи на логику

1. Экспериментальная производственная линия

Вопрос:

Новая экспериментальная производственная линия тестируется перед запуском на заводе. Линия выпускает автомобильные двигатели. В ходе тестирования выпуск продукции на линии удваивался ежедневно, и задача по выпуску продукции была выполнена за 18 дней. Сколько дней занял выпуск 25% этой продукции?

Оригинал задачи на английском

Experimental production line

Question:

A new experimental mechanized production line is being testing before delivering to the factory. The line is assembling car vehicles. The production of this line is doubled every day during the test and the production goal is completed in 18 days. How many days did it take for the to complete 25% of the testing production goal?

Answer:

16th day.

The exact number of production is unknown, so the logic steps to solve this puzzle could be the follow:
On the 18th day, the goal of the test production was completed, consequently 100% of total production was reached, i.e:

  • 18th day – 100% production.
  • As production doubled daily, it means that in the 17th day was produced only half of the output – 50%. 17th day – 50% production
  • Similarly, on the previous day, the 16th day was produced half as much, i.е. the desired 25%. 16th day – 25% production.

The testing goal was completed by 25% on the 16th day.

Решение задачи

16 дней.

Поскольку точное количество продукции неизвестно, для решения задачи можно рассуждать следующим образом:

  • На 18-ый день задача была выполнена, значит было достигнуто 100% выпуска продукции.
  • Поскольку выпуск удваивался ежедневно, значит, на 17-ый день было произведено 50% продукции.
  • Аналогично, в предыдущий, 16-ый день, было произведено ещё в 2 раза меньше, т.е. 25% продукции.

2. Найдите кота

Вопрос:

Кот прячется в одной из пяти коробок. Коробки пронумерованы от одного до пяти и расположены в ряд по порядку. Каждую ночь пугливый кот прячется в соседнюю коробку, находящуюся рядом с коробкой, в которой он прятался в предыдущий день. Каждое утро, вы можете открыть только одну коробку, чтобы проверить, есть ли там кот. Можно ли с уверенностью сказать, найдётся ли кот? Как нужно играть в эту игру, чтобы вычислить кота?

Оригинал задачи на английском

Find the cat

Question:

A cat is hiding in one of the five boxes. The boxes are numbered one to five and are all sitting in a row, lined up in order. Each night, the sneaky little cat hides in an adjacent box, exactly one box away from the box it’s in during the day. Each morning, you can open exactly one box to see if the cat is in there. Can you say with certainty that you will find the cat ? How can you go about this hide and seek game to ensure you find the cat?

Answer:

Yes, it is possible to ensure a victory in this hide and seek game. Since the cat always jumps into an adjacent box, you’ll know after opening the first box when the cat is in an odd or even numbered box.

First, consider the case when the cat started in an even numbered box, i.e., 2 or 4.

  • On day 1, check box numbered 2. If you find the cat, you win. Otherwise, the cat must have been in box numbered 4 (considering only for even number case). So, next day the cat will move to either box numbered 3 or 5.
  • On day 2, check box numbered 3. If you find the cat, you win. Otherwise, the cat must have moved to box numbered 5 and which means the cat can now only move to box numbered 4 on the next day. So, now we check box numbered 4 and we will certainly find the cat!

Now, let’s consider the case when the cat started in an odd numbered box, i.e., 1, 3 or 5.
Following the previous strategy, till day 4 cat would be in either box numbered 2 or 4 because:

  • On day 1, cat is in an odd numbered box 1 or 3 or 5.
  • On day 2, cat will be in an even numbered box 2 or 4.
  • On day 3, cat will again move to an odd numbered box.
  • And therefore on day 4, cat will be either in box numbered 2 or 4 again.

This situation is same as the previous case. We can follow the same strategy of checking boxes “2, 3 and then 4” and we will find the cat.

Hence, final solution is: 2, 3, 4, 2, 3, 4
Other solution could be: 2, 3, 4, 4, 3, 2
This puzzle can be extended for n boxes

Решение задачи

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

Для начала, предположим, что кот начал с четной коробки, 2 или 4.

  • В первый день проверяем коробку №2. Если нашли кота — выиграли. Если же нет — значит кот прыгнул в коробку №4. Следовательно, на следующий день кот прыгнет в коробку №3 или №5.
  • Во 2-й день проверяем коробку №3 и, если нашли кота — победа. В противном случае кот находится в 5-й коробке и сможет перепрыгнуть только в коробку №4.
  • На следующий день проверяем 4-ю коробку — кот определенно должен быть в ней.

Теперь предположим, что кот начал с нечетной коробки, т.е. 1-й, 3-й или 5-й. Следуем той же стратегии до 4-го дня, когда кот окажется в коробке №2 или №4:

  • В первый день – кот в коробке №1, №3 или №5.
  • Во второй день – кот в коробке №2 или №4.
  • В третий день – кот снова в нечетной коробке.
  • Следовательно, в 4-й день кот будет во 2-й или 4-й коробке.

Ситуация аналогичной предыдущем случаю – мы можем проверять коробки в порядке «2, 3 и 4» и мы найдем кота.

Итоговая последовательность: 2, 3, 4, 2, 3, 4
Другим вариантом может быть: 2, 3, 4, 4, 3, 2
Решение может быть расширено и применено для n коробок.

3. По ступенькам

Вопрос:

Вы поднимаетесь по ступенькам. До вершины n шагов. За каждый шаг вы можете переступить 1 или 2 ступеньки. Сколько у Вас есть различных вариантов подъема на вершину?

Оригинал задачи на английском

Climbing Stairs

Question:

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Answer:

A transformation of Fibonacci Number. Solve it by one dimension dynamic programming. The transition function should be:

			int climbStairs(int n)
{
    // Start typing your C/C++ solution below 
    // DO NOT write int main() function 
    int fn_2 = 1, fn_1 = 2;
    if (n == 1) return fn_2;
    if (n == 2) return fn_1;
    int fn;
    for (int i = 3; i <= n; i++)
    {
        fn = fn_2 + fn_1;
        fn_2 = fn_1;
        fn_1 = fn;
    }
    return fn;
}
		
Решение задачи

Задача решается с помощью преобразованной последовательности Фибоначчи и динамического программирования. Функция будет такой:

			int climbStairs(int n)
{
    int fn_2 = 1, fn_1 = 2;
    if (n == 1) return fn_2;
    if (n == 2) return fn_1;
    int fn;
    for (int i = 3; i <= n; i++)
    {
        fn = fn_2 + fn_1;
        fn_2 = fn_1;
        fn_1 = fn;
    }
    return fn;
}
		
Следите за новыми постами
Следите за новыми постами по любимым темам
16К открытий16К показов