Обмен

Задачка для программистов, которую любят задавать на собеседованиях. Даны две переменные, например, a=4 и b=7. Требуется поменять местами значения этих переменных (то есть должно получиться a=7 и b=4), но при этом нельзя использовать третью переменную. Нужен алгоритм, который легко реализовать на любом языке.

update

Первые - 67108864 и Roman Zhmakin.
Ответ

Есть несколько вариантов.
С помощью простых арифметических действий, например:
a = a + b;
b = a - b;
a = a - b;
С помощью функции xor (исключающее ИЛИ):
a = a XOR b;
b = a XOR b;
a = a XOR b;

И ещё - предложите самый быстрый алгоритм.

Кубок

В турнире участвуют 64 игрока. Играют по кубковой схеме, когда проигравший выбывает из турнира, а победитель поединка проходит дальше. Положение игрока в турнирной лестнице определяется жребием. Допустим, лучший игрок всегда побеждает второго по мастерству, а тот в свою очередь всегда выигрывает у всех остальных. Второе место в турнире занимает проигравший в финале. Какова вероятность, что второе место в турнире займёт второй по мастерству игрок?

update

Первым был Илья.
Ответ

32/63.
Второй по мастерству игрок может занять второе место, когда он находится в половине турнирной лестницы, не занимаемой лучшим игроком. Если в турнире всего 2^n игроков, то в половине лестницы 2^(n-1) ступеней. А число не занятых лучшим игроком начальных ступеней равно (2^n)-1. Таким образом, искомая вероятность рассчитывается как
P=(2^(n-1))/((2^n)-1)=32/63.

>34

На гранях игральной кости изображены цифры 0, 1, 2, 3, 4, 5. Кость подбрасывают, а выпавшие очки прибавляют к общей сумме. Подбрасывания продолжаются до тех пор, пока эта сумма не станет больше 34. Чему, вероятнее всего, будет равна эта сумма?

update

Первый - Илья.
Ответ

Рассмотрим предпоследний бросок. После него общая сумма может быть равной 34, 33, 32, 31 или 30. Если она равна 34, то после последнего броска равные шансы имеют итоговые значения 35, 36, 37, 38 и 39. Если сумма равна 33, то итог может быть равен 34, 35, 36, 37 или 38. И так далее. Ясно, что наиболее вероятный вариант 35.

И ещё одна задача с игральной костью.

Вид сверху

Даны две проекции объемной детали - вид спереди и вид слева. Требуется построить вид сверху. Чертёж выполнен по правилам. Если бы требовались невидимые линии, они были бы показаны пунктиром. Есть два решения.

update

Первым был ‏@arturdubro в твиттере.
Ответ
Решение №1.

Решение №2.

Похожая задача.

Верёвки

Три верёвки привязаны к трём гвоздям на доске А и запутаны между собой. Требуется привязать к свободным концам этих верёвок три новые верёвки, а концы последних закрепить гвоздями на доске В. Цель манипуляций - получить три параллельно натянутые верёвки после того, как доски А и В будут разведены в стороны. Как это можно сделать?

update

Первым правильно ответил Waleriy.
Ответ

Заодно распутайте железные дороги.

Снежный ребус

Каждая буква единственным образом представляет цифру. Математическая смекалка поможет значительно сократить перебор вариантов.

update

Первым был Дмитрий, подробное решение - Dendr.
Ответ

5169=377337/73.

Исходную дробь можно преобразовать в выражение: OXXOOX/XO = 100 + OX(10001)/XO.

Далее выясняем, что 10001=73*137. Так как 10001 - пятизначное, то XO должно делиться на один из его делителей, откуда XO=73. Остальное вычисляется просто.

Ещё два ребуса:
БАОБАБ
ГОЛОВОЛОМКА

Петля

Предлагаю нарисовать ещё одну петлю. Правила те же.

update

Первым правильно ответил Дмитрий.
Ответ

Монета

Игрок бросает десятирублёвую монету на стол, на поверхности которого нарисована сетка с ячейками в виде квадратов. Диаметр монеты 22 мм, длина стороны квадратной ячейки 40 мм. Если монета попадает внутрь любого квадрата, то игрок выигрывает, в противном случае он теряет свою монету. Считаем, что монета всегда падает на стол и вероятность падения монеты в любую точку стола одинакова, толщиной линий сетки пренебрегаем. Каковы шансы выиграть в этой игре?

update

Первым правильно ответил dbsergey.
Ответ

Игрок выигрывает в том случае, если центр монеты попадает в квадратную зону, которая отмечена оранжевым цветом. Следовательно, вероятность выигрыша будет равна отношению площадей маленького и большого квадратов: P=(18^2)/(40^2)=324/1600=0,2025

Головоломка Колумба.

Жюри

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

update

Первым правильно ответил 67108864.
Ответ

Оба типа жюри имеют одинаковую вероятность вынести правильное решение. В самом деле, два серьезных члена жюри будут голосовать за справедливое решение с вероятностью P*P = P^2, при этом результат голосования третьего члена жюри не существен. Если же эти судьи расходятся во мнениях, вероятность чего равна P(1—P) + (1—P)P = 2P(1 — P), то для нахождения вероятности правильного решения это число надо умножить на 1/2. Таким образом, полная вероятность вынесения справедливого решения жюри из трех человек равна Р^2 + Р(1 — P) = Р, что совпадает с соответствующей вероятностью для жюри из одного человека.

Другие задачи на вероятность.

Loop the loop

Всем известна игра под названием "Сапер". В одной газете нашёл головоломку по своей сути очень похожую на эту игру.
Правила довольно простые:
- соедините смежные точки вертикальными и горизонтальными линиями, образовав одну петлю (рисунок А);
- перекрещивания и ответвления не допустимы (как показано пунктирами на рисунке В);
- числа в головоломке указывают на количество линий, которые должны окружить его, в то время как пустые клетки могут быть окружены любым количеством линий;
- нельзя рисовать линии вокруг нулей;
- у головоломки есть только одно уникальное решение.
Попробуйте нарисовать эту уникальную петлю.

update

Первым правильно ответил Дмитрий.
Ответ

Ещё про точки - как соединить 13 точек и 16 точек?