1 added
1 removed
Original
2026-01-01
Modified
2026-02-21
1
<p><a>#статьи</a></p>
1
<p><a>#статьи</a></p>
2
<ul><li>6 фев 2023</li>
2
<ul><li>6 фев 2023</li>
3
<li>0</li>
3
<li>0</li>
4
</ul><h2>Задача: игра в ним</h2>
4
</ul><h2>Задача: игра в ним</h2>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня пытаемся понять, можно ли выиграть в ним с заданными условиями.</p>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня пытаемся понять, можно ли выиграть в ним с заданными условиями.</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
8
<p><strong>Условие.</strong>Вы играете с оппонентом в ним. Вот правила этой игры:</p>
8
<p><strong>Условие.</strong>Вы играете с оппонентом в ним. Вот правила этой игры:</p>
9
<ul><li>На старте перед вами лежит кучка камней.</li>
9
<ul><li>На старте перед вами лежит кучка камней.</li>
10
<li>Вы с оппонентом по очереди делаете ходы - причём первый ход всегда за вами.</li>
10
<li>Вы с оппонентом по очереди делаете ходы - причём первый ход всегда за вами.</li>
11
<li>На каждом ходу игрок убирает из кучи от одного до трёх камней на свой выбор.</li>
11
<li>На каждом ходу игрок убирает из кучи от одного до трёх камней на свой выбор.</li>
12
<li>Побеждает игрок, который уберёт последний камень.</li>
12
<li>Побеждает игрок, который уберёт последний камень.</li>
13
</ul><p>Дано число камней - n. Вернуть true, если вы сможете выиграть, учитывая, что ваш оппонент будет играть максимально рационально, иначе вернуть false.</p>
13
</ul><p>Дано число камней - n. Вернуть true, если вы сможете выиграть, учитывая, что ваш оппонент будет играть максимально рационально, иначе вернуть false.</p>
14
-
Ввод: n = 4 Вывод: false Пояснение: примерный исход игры: 1. Вы убираете 1 камень. Ваш оппонент убирает 3, включая последний камень. Ваш оппонент побеждает. 2. Вы убираете 2 камня. Ваш оппонент убирает 2 камня, включая последний. Ваш оппонент побеждает. 3. Вы убираете 3 камня. Ваш оппонент убирает последний камень. Ваш оппонент побеждает. В каждом из вариантов ваш оппонент побеждает. Ввод: n = 1 Вывод: true Ввод: n = 2 Вывод: true<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
14
+
Ввод: n = 4 Вывод: false Пояснение: примерный исход игры: 1. Вы убираете 1 камень. Ваш оппонент убирает 3, включая последний камень. Ваш оппонент побеждает. 2. Вы убираете 2 камня. Ваш оппонент убирает 2 камня, включая последний. Ваш оппонент побеждает. 3. Вы убираете 3 камня. Ваш оппонент убирает последний камень. Ваш оппонент побеждает. В каждом из вариантов ваш оппонент побеждает. Ввод: n = 1 Вывод: true Ввод: n = 2 Выво��: true<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
15
<p><strong>Решение</strong></p>
15
<p><strong>Решение</strong></p>
16
<p>Для начала мы должны понять, какие возможные исходы игровых партий существуют. Уже понятно, что если перед нашим ходом камней всего четыре, то мы проиграем.</p>
16
<p>Для начала мы должны понять, какие возможные исходы игровых партий существуют. Уже понятно, что если перед нашим ходом камней всего четыре, то мы проиграем.</p>
17
<p>Поэтому есть три сценария развития событий:</p>
17
<p>Поэтому есть три сценария развития событий:</p>
18
<ul><li>Камней меньше, чем 4, и сейчас наш ход - мы побеждаем.</li>
18
<ul><li>Камней меньше, чем 4, и сейчас наш ход - мы побеждаем.</li>
19
<li>Камней ровно 4, и сейчас наш ход - мы точно проиграли.</li>
19
<li>Камней ровно 4, и сейчас наш ход - мы точно проиграли.</li>
20
<li>Камней больше, чем 4, но при этом остаток от деления общего числа камней на 4 равен 0 - значит, мы тоже проиграем, так как по условию наш соперник будет играть честно.</li>
20
<li>Камней больше, чем 4, но при этом остаток от деления общего числа камней на 4 равен 0 - значит, мы тоже проиграем, так как по условию наш соперник будет играть честно.</li>
21
</ul>public boolean canWinNim(int n) { if (n < 4){ return true; } if (n == 4){ return false; } if (n % 4 == 0){ return false; } return true; }<p><strong>Результаты</strong></p>
21
</ul>public boolean canWinNim(int n) { if (n < 4){ return true; } if (n == 4){ return false; } if (n % 4 == 0){ return false; } return true; }<p><strong>Результаты</strong></p>
22
<p><strong>Временная сложность:</strong>O(1) - так как мы проверяем условие всего один раз.</p>
22
<p><strong>Временная сложность:</strong>O(1) - так как мы проверяем условие всего один раз.</p>
23
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти.</p>
23
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти.</p>
24
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>
24
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>