Форум 'Этюды для программистов' на RSDN

Игра Мельница и хитрый знахарь

Sat, 15 Nov 2025 09:34:34 GMT

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

Вот такая доска, второй вариант (B) — ходить можно по линиям:

Фишки уже стоят в начальных позициях как в шашках, пусть красные и белые, типа так:

W W W
* * *
R R R

Знахарь предлагает попробовать за "пол туалета" (т.е. 50% от стоимости общественного туалета). При этом если я выигрываю — дает денег в 40 раз больше, т.е. уже на 20 туалетов.

И он же любезно предлагает тебе ходить первым... А так же добавляет правило — запрет обратного хода, чтобы игра не длилась вечно.

В общем, проиграл я таки "пол туалета".

И тут вопрос — жульничал ли знахарь? Вроде получается что кто ходит первым — всегда проигрывает, при любом раскладе. Но это не точно, нужно бы перебрать варианты. Или же все честно и в игру можно играть вечно?

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

Задачка для 8го класса на логику

Wed, 12 Nov 2025 18:10:51 GMT

Здравствуйте!

Квадрат по четырём точкам

Sat, 23 Aug 2025 18:18:39 GMT

Попалась на ютубе задачка на геометрическое построение, понравилась.

Даны четыре точки, принадлежащие разным сторонам одного квадрата. Нужно при помощи циркуля и линейки построить этот квадрат.

Чтоб не распыляться, можно рассмотреть только те случаи, когда решение существует и является единственным.

Необычная задача на измерения (два типа шариков)

Mon, 07 Apr 2025 16:31:13 GMT

Попадалась ли вам такая задача:

Есть два типа шариков — шарики типа А и шарики типа Б. Так же есть специальное устройство — в него можно поместить множество шариков — устройство скажет сколько процентов шариков типа А.
Сколько нужно измерений, чтобы разделить на 2 кучи 1 миллион шариков (в одной куче только А, в другой гарантированно только Б)?

Можно чуть изменить:

Есть один миллион яиц, среди которых часть тухлых а часть нормальных. Нужно отобрать все тухлые яйца. При этом есть прибор, в который можно поместить все яйца и получить количество тухлых — в лбом количестве. Сколько минимум измерений этим прибором нужно сделать, чтобы отобрать все тухлые яйца?

deepseek говорит что нужно 1 млн. измерений.
gpt o1 точно не знает, говорит что около ≈50000 измерений.

Нули и единицы

Fri, 04 Apr 2025 19:43:19 GMT

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

// Максимальное количество последовательных единиц

// Дан массив nums содержащий только 0 (нули) и 1 (единицы),
// и целое число k. Верните максимальное количество последовательных
// единиц в массиве, если вы можете заменить не более k нулей на единицы.

// Пример 1:
// nums = [1,1,1,0,0, 0, 1,1,1,1, 0], k = 2
// Ответ: 6
// Замена: [1,1,1,0,0,<1>,1,1,1,1,<1>]
// ---------------
// Выделенные скобками (< >) числа были заменены с 0 на 1.
// Самый длинный подмассив подчеркнут.

// Пример 2:
// nums = [0,0,1,1 ,0, 0, 1,1,1, 0, 1,1,0,0,0,1,1,1,1], k = 3
// nums = [0,1,1,1 ,1, 1, 1,1,1, 0, 1,1,0,0,0,1,1,1,1]
// Ответ: 10
// Объяснение: [0,0,1,1,<1>,<1>,1,1,1,<1>,1,1,0,0,0,1,1,1,1]
// -------------------------
// Выделенные скобками (< >) числа были заменены с 0 на 1.
// Самый длинный подмассив подчеркнут.

// Ограничения:
// 1 <= nums.length <= 105
// nums[i] = 0 или 1.
// 0 <= k <= nums.length

Мой код (не завершен и не работает):

#include <stdio.h>

#define MAX_NUMBER_COUNT 105

int get_max_one_sequences(int nums[], int length, int k) {
    int i, start_index, current_count, max_count;
    if (!nums || length <= 0 || k < 0 || k >= length) return 0;
    if (length > MAX_NUMBER_COUNT) return 0;
    max_count = 0;
    current_count = -1;
    start_index = -1;
    for (i = 0; i < length; i++) {
        if (nums[i] == 1) {
            if (current_count < 0) { start_index = i; }
            current_count++;
        } else {
            if (max_count < current_count) { max_count = current_count; }
            current_count = -1;
        }
    }
    return max_count;
}

void print_array(int nums[], int length) {
    int i;
    if (!nums || length <= 0) return;
    for (i = 0; i < length; i++) {
        printf(i > 0 ? ", %d" : "%d", nums[i]);
    }
    putchar('\n');
}

#define ANSWER 6

int nums[] = { 1,1,1,0,0, 0, 1,1,1,1, 0 };

/**********************************************************************
1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0
k = 2
Result: 3 (must be: 6)
**********************************************************************/
int main(int argc, char *argv[]) {
    int length, k;
    k = 2;
    length = sizeof(nums) / sizeof(nums[0]);
    print_array(nums, length);
    printf("k = %d\n", k);
    printf("Result: %d (must be: %d)\n",
        get_max_one_sequences(nums, length, k), ANSWER);
    return 0;
}

[offtop] nikov - легенда!

Tue, 18 Feb 2025 17:37:41 GMT

Всем привет,

я просто листал телеграм канал с приколами и увидел там это https://t.me/dev_meme/6538

Так как он сам признал это, то думаю не будет деанонимизацией написать здесь, что легендарная Cleo c math.stackexchange.com и nikov — это один и тот же человек. Просто взрыв мозга, как тесен мир

Если что, я точно не nikov

Задача о проносе трубы через коридоры

Sun, 15 Dec 2024 11:28:04 GMT

Доброго времени суток!

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

	Ролик с ютуба
	https://www.youtube.com/watch?v=ARobW6kXk_8&t=182s

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

Катеты треугольника перпендикулярны линиям контура коридоров;
Концы гипотенузы лежат на линиях внешнего контура коридоров;
Гипотенуза пересекается с вершиной выступающего угла коридоров;
Высота, опущенная к гипотенузе, попадает в точку пересечения гипотенузы с выступающим углом.

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

А вот теперь вопрос: можно ли, имея лишь план стен, пользуясь лишь циркулем и линейкой, построить данный прямоугольный треугольник?

Обратное построение выполняется легко. Т.е. имея треугольник, достроить линии стен не составит труда: опускаем высоту на гипотенузу и из точки пересечения проводим перпендикуляры к катетам — внутренний контур коридоров готов. Потом через концы гипотенузы проводим две линии, параллельные линиям внутреннего контура и получаем полный план коридоров. А вот можно ли по линиям коридора построить треугольник?

Цепочки сумм-квадратов

Wed, 11 Sep 2024 14:48:50 GMT

Немножко оживлю форум задачкой для программистов. На подумать над алгоритмом и на покодировать на любимом языке.

https://habr.com/ru/articles/842246/

Дано натуральное число n.
Нужно вывести все цепочки неповторяющихся натуральных чисел в диапазоне от 1 до n, такие, что каждая пара смежных чисел в цепочке является квадратом натурального числа.

Например, цепочка 10, 6, 3, 1, 8 — там суммы 16, 9, 4, 9.

Автор статьи на хабре привёл какое-то довольно громоздкое и неоптимальное решение на скале. Вот, разомнитесь и превзойдите его, что ли

UPD. Невнимательно прочитал условие. Автор хочет все перестановки чисел от 1 до n. Но очевидно, что решения существуют только для некоторых n. Например, для n=10 таких перестановок в принципе нет.
Поэтому предлагаю решать и в моей постановке тоже.

Поскольку если какая-то цепочка является решением, то любая подцепочка и её отражение также являются решением.
Поэтому надо вывести все уникальные наибольшие цепочки.

Задача для детей 7 лет

Thu, 23 May 2024 19:41:18 GMT

Текст прямо из книжки

Как далеко медведь может убежать в лес если он не знает насколько этот лес большой?

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

Задача про 1 кг пуха

Tue, 21 May 2024 12:00:13 GMT

1 кг пуха сожгли, если сравнить с 1 кг гвоздей — что тяжелее? И почему?

⸻
^{❧ “Keep a little fire burning; however small, however hidden.” ― Cormac McCarthy}

100 арестантов

Fri, 03 May 2024 18:38:35 GMT

Есть 100 арестантов, каждому из них присвоен номер от 1 до 100

Руководство тюрьмы предложило им вариант освобождения:
В закрытой комнате стоит 100 коробок с номерами от 1 до 100 и в каждой лежит номер от 1 до 100. Номера перемешаны случайным образом.

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

Заключенные могут выработать стратегию заранее, но никто из тех кто заходил в комнату не может передавать никакую информацию ожидающим.

Есть ли стратегия с вероятностью освобождения больше чем 2^-100?

Суд

Sun, 03 Mar 2024 03:18:13 GMT

Задачка довольно простая для решения в лоб.
Но ответ как бы намекает, что должно быть красивое решение.
Я красивого решения пока не придумал.

Вот задача:

У подсудимого есть две опции:
1) Один судья, который вынесет оправдательный приговор с вероятностью p.
2) Суд из трех присяжных: первый вынесет оправдательный приговор с вероятностью p, второй тоже с вероятностью p, а третий с вероятностью 1/2. Подсудимый оправдал, если как минимум двое из трех судей вынесут оправдательный приговор (спасибо andy за замечание).

Какая опция предпочтительней для подсудимого?

часы

Sat, 02 Mar 2024 16:21:19 GMT

На досуге этюд сочинил.
У вас есть по два экземпляра часов двух разных моделей. Как определить часы какой модели являются более точными? Другими устройствами измерения времени кроме этих часов пользоваться нельзя.

Макароны на тарелке

Fri, 01 Mar 2024 15:10:51 GMT

На тарелке лежит N макарон. Мы случайно выбираем и связываем два кончика. Продолжаем это делать пока не свяжем все макароны.
Найти мат ожидание количества получившихся макаронных колец.

Сумма всех натуральных чисел равна -1/12 ?

Thu, 04 Jan 2024 21:23:05 GMT

Привет всем.

В этом ролике выводится сумма бесконечного ряда всех натуральных чисел и в результате получается дробное отрицательное число, по модулю меньшее единицы (-1/12). В чем подвох?

https://www.youtube.com/watch?v=YQpkcYmvChQ

Задачка про два целых числа

Fri, 15 Dec 2023 19:38:58 GMT

Два целых числа x и y выбираются так, где 1 < x ≤ y < 100.

Игроку А дается произведение x⋅y, а игроку B — сумма x+y.

Происходит следующий диалог¹:

A: Я не знаю значений x и y.
Б: Я знал, что ты не знаешь. Я их тоже не знаю.
A: Теперь я знаю x и y.
Б: Теперь я тоже их знаю.

Чему равны x и y?

⸻
¹ диалог между A и B подразумевает, что A знает, что B была дана сумма x+y, и что B знает, что A была дана произведение x⋅y.

...<< Dementor ^1.5.2 ✪ Lets Play a Game ⚀⚁⚂⚅⚅>>

Задача китайской средней школы

Thu, 14 Dec 2023 21:51:39 GMT

Показалась занимательной и достойной, чтобы опубликовать ее здесь:

Имеется квадрат ABCD. Длина стороны квадрата равна 4. Постройте четверть окружности с центром в точке B, которая соединяет точки A и C. Затем постройте полукруг с диаметром, равным AD. Четверть окружности и полукруг пересекаются.

Чему равна площадь пересечения этих двух фигур?

...<< Dementor ^1.5.2 ✪ Lets Play a Game ⚀⚀⚁⚂⚄>>

Сборник задач по индуктивным функциям

Mon, 28 Aug 2023 18:14:32 GMT

Может быть, кому-то покажется интересным: https://algodrom.ru/
Пока задачек немного, потому что я не уверен, что такой формат задач "пойдет",
так что буду благодарен вашим мнениям и предложениям.

Коллац на Фрактране

Fri, 07 Jul 2023 17:08:49 GMT

А вот вам этюд для труъ программистов!

"Я хочу сыграть с вами в одну игру..." (Джон Конвей, про свою игру "Жизнь")

Вы задаёте список положительных дробей.
Берём некое натуральное число.
И пытаемся умножить его на первую дробь. Если результат дробный — отменяем, пытаемся умножить на вторую дробь. И так далее...
Короче говоря, находим в списке первую дробь, которая при умножении на число даёт натуральное число.
Повторяем эту процедуру для результата умножения. (Каждый раз начинаем поиск от начала списка).
Ну и так далее.
Если ни одна из дробей не подошла, то процедура останавливается.

Этот список дробей является программой на эзотерическом языке Fractran.

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

Пример кода, который делит число с остатком: <x,0,0> --> <0,x/2,x%2>
то есть, на вход подаём 2^x, а в итоге хотим получить 3^d * 5^r

1) < -2, +1, 0 > = 2^-2 * 3 = 3/4
2) < -1, 0, +1 > = 2^-1 * 5 = 5/2

Машина работает так:
— если x >= 2, делаем x-=2, d+=1 — и повторяем
— если x >= 1, делаем x-=1, r+=1 — и тут уже повторять не получится
— на этом и останавливаемся.

А вот пример машины, которая бесконечно прыгает между тремя состояниями
1) < -1, +1, 0 > = 3/2
2) < 0, -1, +1 > = 5/3
3) < +1, 0, -1 > = 2/5
Подаём на вход <1,0,0> = 2 и всё заверте

Предлагаю маленький конкурс: написать программу, реализующую последовательность Коллаца (3x+1).

На входе — некое число, символизирующее x. (Например, 2^x)
На выходе — некое число, символизирующее количество итераций до значения 1. (Например, 3^t)
(Примем за постулат, что 3x+1 всегда сходится к циклу 1-4-2-1).

Чем короче будет программа, тем лучше.

Только давайте сразу договоримся, что код публиковать в виде векторов, а не в виде дробей. Потому что какое-нибудь 1234/567 воспринимать тяжело, это же надо факторизовывать (2^1 * 617^1) / (3^4 * 7^1)

задачка попалась

Thu, 15 Jun 2023 10:54:54 GMT

На C#.
идеи есть? в принципе ни слова не сказано про нативный код, но может и управляемым можно как-то изгольнуться?

We declared 2 string constants in the program, they both have the same text, "12". How can we change the text to "13" in the first string? Do not create a new variable/const, just mutate the original string.