Пятничные задачки. Вася Пупкин пока отдыхает ;)

← →
MBo © (2007-01-26 08:15) [0]

1. Кот ловит мышку, которая прячется в одной из пяти норок.
Норки соединены между собой таким образом 0-0-0-0-0
Процесс ловли происходит следующим образом:
Кот сует лапу в одну из норок. Если мышь там - она поймана.
Если же нет - мышь перебегает в одну из соседних норок.
За какое минимальное количество ходов кот гарантированно ловит мышь?

2. Найти закономерность:
100 -> 2
981 -> 3
657 -> 1
123 -> 0
871 -> 2
256 -> 1
752 -> 0
376 -> 1
786 -> 3
739 -> 1
689 -> ?

3. Начальник отдела спецслужбы должен срочно встретиться с 4-мя агентами.
Он отдаёт распоряжение агентам, среди которых есть Джеймс,
прийти на встречу дождливым утром в 6, 7, 8 и 9 часов утра.
Они должны прийти на явку с зонтами разных цветов.
Однако вражеская спецслужба узнала о встрече и обладает следующей информацией:
1) Уилл придёт по той дороге, справа (при отсчете от перекрестка) от которой спустя час появится агент с зелёным зонтом.
2) У агента, который придёт в 9, не будет красного зонта, и он придет не с восточной, и не с западной стороны.
3) Джо и агент с голубым зонтом придут с разницей в час и приблизятся к месту встречи с противоположных сторон,
как и два других агента которые подойдут к месту встречи с разницей в час.
4) Агент с голубым зонтом, который придёт в парк на час раньше Бена,
появится не с западной стороны, он придёт по дороге, которая находится левее
той, по которой пришёл Бен.
5) У одного из агентов жёлтый зонт.
Необходимо определить с какой стороны, во сколько, кто и с каким зонтом
придёт на место встречи.

4. За 10 часов, сменяя друг друга, три землекопа выкопали яму. Каждый из них копал столько времени, сколько потребуется двум другим при их одновременной работе (имея две лопаты), чтобы выкопать половину ямы.
За какое время смогут выкопать яму эти землекопы, если у них будет три лопаты?

5. а) Дан массив целых чисел, в котором все числа встречаются дважды,
а одно не имеет пары, например, (2,3,9,3,2)
Найти это число за линейное время с использованием лишь O(1) памяти
б) А теперь в массиве два непарных числа, например, (6,2,3,6).
Можно ли при тех же ограничениях найти оба числа?

6. N человек выстроены в круг, счет идет по кругу, выбывает каждый M-й
из оставшихся. Найти номер человека в первоначальном круге, который останется последним.

7. Числа Стирлинга 2 рода определяются так:
S(n,1) = 1
S(n,n) = 1
S(n,k) = S(n-1, k-1) + k*S(n-1,k)
По определению нетрудно составить рекурсивную функцию, но она будет довольно
медленной для больших аргументо (скажем, до миллиона). Как более эффективно вычислить S(n,k)?

8. Доказать, что в десятичной записи числа 2^99 по крайней мере 1 цифра
встречается по крайней мере 4 раза

9. Падишах решил проверить, стоит ли ему кормить своих 100 мудрецов,
или пришло время заменить. Он заказал шапки с помпончиками ста цветов,
по 200 каждого цвета, собрал мудрецов и сказал:
"У вас 3 часа на раздумье и договор. Вот вам каждому бумага, карандаш.
Завтра каждому наденут на голову шапку.
Какого цвета будет помпончик, вы знать каждый про себя не будете.
И покажут каждому всех других. И каждый должен написать,
какого цвета помпончик на нём. Если хоть один напишет правильно,
будете жить и продолжать служить. Нет - всем отрубят головы".
Могут ли мудрецы гарантированно сохранить свои головы и содержание?

10. Многие знают навскидку степени двойки до 2^32 ;)
Может, заметили, что в десятичной системе среди них ни одно число не начинается
с 7-ки. Существуют ли такие 2^N и если да, то как часто встречаются по сравнению с другими начальными цифрами.

← →
PZ (2007-01-26 08:24) [1]

2. Эта задача уже была здесь. Ответ известен.

← →
MBo © (2007-01-26 08:31) [2]

>2. Эта задача уже была здесь.
Пардон, забыл, значит...
Но наверняка найдутся те, кто не видел.

← →
PZ (2007-01-26 08:34) [3]

Я поэтому и не написал ответ

← →
MBo © (2007-01-26 08:41) [4]

Вот еще задачка на закономерность:

11. C удовольствием поменяю Новгород на Красноярск, Красноярск на Питер, Питер на Москву, Москву на Архангельск, Архангельск на Ярославль. А на что вы готовы поменять Ярославль?

← →
Брюнетка © (2007-01-26 08:43) [5]

>3.

6 часов - Джо, запад, красный зонт
7 часов - Уилл, восток, голубой
8 часов - Бен, север, зеленый
9 часов - Джеймс, юг, желтый

← →
SergP © (2007-01-26 08:59) [6]

5a ПроXORить все элементы массива и получим нужное число.

← →
Elen © (2007-01-26 09:04) [7]

> 10. Существуют ли такие 2^N, где число начинается с 7-ки.

Да. начиная с 2^46 и дальше их можно получить увеличивая степень на 6.

← →
Elen © (2007-01-26 09:04) [8]

> 10. Существуют ли такие 2^N, где число начинается с 7-ки.

Да. начиная с 2^46 и дальше их можно получить увеличивая степень на 10.

← →
Elen © (2007-01-26 09:05) [9]

От руки-крюки : [7] прошу считать опечаткой.

← →
Bless © (2007-01-26 09:13) [10]

А можно, я тоже добавлю?
Задачка для 8 класса:
пятизначное число x, деленное на произведение цифр этого числа дает 49.
Найти x

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

← →
Elen © (2007-01-26 09:29) [11]

> 8. Доказать, что в десятичной записи числа 2^99 по крайней
> мере 1 цифра
> встречается по крайней мере 4 раза

Кажись решается так : Чтобы доказать что одно число повторяется хотя бы 1 раз нужно гарантированно иметь 10+1 знак в числе, значит 4-е раза число будет повторяться в 41-значном числе. Количество знаков я могу узнать по экспоненте :

2^2=8.0E+0 1-знак
3^2=6.4E+1 2-знака
4^2=1.0E+3 4-знака
5^2=3.3E+4 5-знаков
6^2=2.1E+6 7-знаков

Значит 2^99 - 100 знаков. т.е. числа гарантированно повторяются 4-е раза

Вроде так ;)

← →
Elen © (2007-01-26 09:30) [12]

Блин опять описка :

2^2=8.0E+0 1-знак
2^3=6.4E+1 2-знака
2^4=1.0E+3 4-знака
2^5=3.3E+4 5-знаков
2^6=2.1E+6 7-знаков

← →
MBo © (2007-01-26 09:40) [13]

>Брюнетка © (26.01.07 08:43) [5] >3.

Верно. Скользкий момент с понятием право-лево может поменять север и юг

>SergP © (26.01.07 08:59) [6] >5a
Ага, это классическая задача, а вот второй пункт похитрее

>Elen
Ну через 10 степеней - это нестабильно, т.к. 1024<>1000
А как можно объяснить, что семерка редко встречается?

>100 знаков. т.е. числа гарантированно повторяются 4-е раза
В десятичной записи - не 100 цифр.

← →
Elen © (2007-01-26 09:55) [14]

> В десятичной записи - не 100 цифр.

Ну точно больше 40.

← →
Брюнетка © (2007-01-26 09:56) [15]

>11. C удовольствием поменяю Новгород на Красноярск, Красноярск на Питер, Питер на Москву, Москву на Архангельск, Архангельск на Ярославль. А на что вы готовы поменять Ярославль?

На Хабаровск -)

← →
novill © (2007-01-26 10:00) [16]

8. в числе 2^99 тридцать один знак

← →
Elen © (2007-01-26 10:02) [17]

> Ну точно больше 40.

Не вру - не может 4 раза встретится.

← →
MBo © (2007-01-26 10:03) [18]

Брюнетка © (26.01.07 09:56) [15]
>11.
На Хабаровск -)

Точно ;)

← →
Alx2 © (2007-01-26 10:04) [19]

8. в 2^99 всего 30 знаков.
Если б каждой цифры было по три, то число делилось бы на 3, чего не наблюдается. Значит какая-то цифра встречается не менее 4 раз.

← →
MBo © (2007-01-26 10:04) [20]

>novill © (26.01.07 10:00) [16]
>8. в числе 2^99 тридцать один знак

Нет

← →
Alx2 © (2007-01-26 10:05) [21]

Вдогонку: кол-во знаков считаем как trunc(ln(n)/ln(10))+1 (8-й класс, кажется)

← →
MBo © (2007-01-26 10:05) [22]

Alx2 © (26.01.07 10:04) [19]
8. в 2^99 всего 30 знаков.
Если б каждой цифры было по три, то число делилось бы на 3

Верно.

← →
Elen © (2007-01-26 10:06) [23]

> novill

Да верно :

10=1.0E+3 4-знака
20=1.0E+6 7-знаков
30=1.1E+9 10-знаков
40=1.1E+12 13-знаков
50=1.1E+15 16-знаков
60=1.2E+18 19-знаков
70=1.3E+21 22-знака
80=1.3E+24 25-знаков
90=1.3E+27 28-знаков
100=1.3E+30 31-знак

Правильно 31 знак. Ну три раза точно повтор.
А калькуляторы врут ;)

← →
Elen © (2007-01-26 10:08) [24]

Ой. Опять руки-крюки. 31 знак для 100 - в общем Mith Busted!

← →
TUser © (2007-01-26 10:48) [25]

9. А жульничать мудрецы могут? Типа один подмигивает двум другим, значит на них одинаковые шапки.

← →
$Pl@Sh © (2007-01-26 11:36) [26]

> Кот ловит мышку

Кот Васи Пупкина ловит мышку :-)

← →
начинающий © (2007-01-26 11:42) [27]

> 11. C удовольствием поменяю Новгород на Красноярск, Красноярск
> на Питер, Питер на Москву, Москву на Архангельск, Архангельск
> на Ярославль. А на что вы готовы поменять Ярославль?

и где же тут закономерность? в самих названиях?

← →
Брюнетка © (2007-01-26 11:44) [28]

>начинающий ©

Купюры разного достоинства с изображением городов.

а я, наивный, будучи в Украине пытался её осилить... :)

Хабаровск на Кудрина.

>TUser © (26.01.07 10:48) [25]
>9. А жульничать мудрецы могут? Типа один подмигивает двум другим, значит на них одинаковые шапки

Нет, только посмотреть и поразмыслить.

> мышь перебегает в одну из соседних норок.

в любую свободную или в следующую по одному направлению? т.е. из 2-й в 3-ю, потом в 4-ю - или может возвращаться в предидущую?

по поводу 1., кот сует руку в нору и высовывает? т.е. мышь может перебежать в эту же нору при своем ходе?

> Могут ли мудрецы гарантированно сохранить свои головы и
> содержание?

а только содержание? :)

кот вынимает лапу, после этого мыш непременно перебегает в соседнюю норку

> перебегает в соседнюю норку

в любом направлении?

>в любом направлении?
Да, кроме крайних норок, конечно.

1. - 8?

← →
b z (2007-01-26 13:24) [38]

1 - 10?

> 1. Кот ловит мышку, которая прячется в одной из пяти норок.
> Норки соединены между собой таким образом 0-0-0-0-0
> Процесс ловли происходит следующим образом:
> Кот сует лапу в одну из норок. Если мышь там - она поймана.
> Если же нет - мышь перебегает в одну из соседних норок.
>
> За какое минимальное количество ходов кот гарантированно
> ловит мышь?

Пока нашел вариант с 6 ходами

Пятничные задачки. Вася Пупкин пока отдыхает ;) Найти похожие ветки