Пятничные задачки

← →
MBo © (2006-04-07 14:13) [0]

1. Дано предложение:
Это предложение содержит _ букв, _ слогов, _ слов
Впишите вместо прочерков числа (прописью) так, чтобы это предложение
стало правдивым.

2. Имеется двумерный массив MxN, элементы которого упорядочены по
возрастанию слева направо и сверху вниз. Необходимо за минимальное количество
операций определить, встречается ли в нем элемент, равный X.

3. В массиве длины N содержатся все целые числа от 0 до N, кроме
какого-то одного. Найти пропущенное число, если использовать
дополнительные массивы нельзя.
А что, если пропущено два числа?

4. Семеро друзей - Антонов, Борисов, Васильев, Глебов, Дмитриев, Егоров
и Иванов - по странному стечению обстоятельств имеют "совпадающие"
имена, причем ни один из них не является "тезкой" своей фамилии.
Кроме того, о них известно следующее:
- Все, кроме Антонова и Глебова, уже женаты.
- Невесте Егора очень не нравится фамилия ее жениха.
- Фамилия Глеба совпадает с именем Иванова.
- Жены Дмитриева и Ивана - родные сестры.
- Тот, чье имя совпадает с фамилией Бориса, женат, и его фамилия
совпадает с именем Егорова.
- Иван, Егор и Василий - брюнеты.
- Остальные четверо, в числе которых Иванов, Егоров и Васильев, -
блондины.
Как фамилия Василия?

5. У вас имеется 10 монет, среди которых могут быть и фальшивые.
Известно, что настоящие монеты весят одинаково, и фальшивые
(если они есть) тоже весят одинаково). Кроме того, известно, что
хотя бы одна из монет - настоящая.
Как за 3 взвешивания подтвердить или опровергнуть, что все ваши
монеты - настоящие.

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

Задачи, связанные с шахматами, в которых я не силён и достойно
проконтролировать решения не могу, однако мне они кажутся великолепными,
и кому-то может быть интересно порешать:

7. Профессор Мориарти и полковник Моран играют в шахматы по телеграфу.
Они пересылают ходы пользуясь стандартной краткой нотацией:
указывается номер хода, затем фигура, делающая ход (если ходит пешка,
то указывается только конечное поле; при взятии пешкой указывается
вертикаль, на которой она стояла, и конечное поле),
поле на которое делается ход. Также отмечаются взятия, шахи и маты.
Например: 27.Ke5 (на двадцать седьмом ходу белые сыграли конем на е5),
12...Ф:e3+ (на двенадцатом ходу черный ферзь взял белую фигуру на поле е3
и объявил шах), 42.d8Лх (белая пешка идет на d8 превращается в ладью и
объявляет мат).
Шерлок Холмс переоделся в почтальона и перехватил телеграмму с очередным ходом.
После этого, при помощи дедуктивного метода, ему удалось однозначно востановить
все предыдущие ходы в партии. Пример: Холмс перехватил ход 2...Л:a5.
Тогда вся партия была такой 1.b4 a5 2.ba5 Л:a5
Какова максимальная длина такой партии?

8. Правила, по которым ходит шахматная фигура, можно описать в виде
множества векторов всех возможных ходов. Например, для коня это множество
содержит 8 векторов:
{(1,2), (1,-2), (2,1), (2,-1), (-1,2), (-1,-2), (-2,1), (-2,-1)}
Однако можно и придумать какую-нибудь новую фигуру
с другим набором ходов. Например, {(1,1),(-1,1),(1,-1)}

Можно ли придумать такую фигуру, назовем ее "дракон", которая обладает двумя свойствами:
1) Дракон из любой клетки шахматной доски может добраться до любой другой клетки (за один или несколько ходов)
2) На шахматной доске можно расставить более 32 драконов так, чтобы они не били друг друга

Если драконов не существует, докажите это. Если существуют, то какое максимальное число драконов можно разместить на шахматной доске?

← →
Vlad Oshin © (2006-04-07 14:45) [1]

> 8. Правила, по которым ходит шахматная фигура, можно описать
> в виде
> множества векторов всех возможных ходов. Например, для коня
> это множество
> содержит 8 векторов:
> {(1,2), (1,-2), (2,1), (2,-1), (-1,2), (-1,-2), (-2,1),
> (-2,-1)}
> Однако можно и придумать какую-нибудь новую фигуру
> с другим набором ходов. Например, {(1,1),(-1,1),(1,-1)}
>
> Можно ли придумать такую фигуру, назовем ее "дракон", которая
> обладает двумя свойствами:
> 1) Дракон из любой клетки шахматной доски может добраться
> до любой другой клетки (за один или несколько ходов)
> 2) На шахматной доске можно расставить более 32 драконов
> так, чтобы они не били друг друга
>
> Если драконов не существует, докажите это. Если существуют,
> то какое максимальное число драконов можно разместить на
> шахматной доске?

Имхо, драконов не существует. Потому что, ставя дракона и назначая ему хоть один ход, на том поле, куда он пойдет автоматически не должен стоять другой дракон. Таким образом, добавляя 1 дракона, исключаем 2 поля доски.
Т.е. лучший дракон - конь. Их можно поставить 32.

← →
ferr © (2006-04-07 14:49) [2]

> В массиве длины N содержатся все целые числа от 0 до
>N, кроме
> какого-то одного. Найти пропущенное число, если
>использовать
>дополнительные массивы нельзя.
> А что, если пропущено два числа?

поясните пожалуйста...
А то очень много решений лезет за N*log(N), но ясно что так не правильно. Какая оценка?

← →
Ega23 © (2006-04-07 14:52) [3]

> Остальные четверо, в числе которых Иванов, Егоров и Васильев,
> - блондины.

Но-но! Нифига я не блондин! :о)

← →
Sandman25 © (2006-04-07 14:55) [4]

5. Весы со стрелкой?

← →
MBo © (2006-04-07 14:57) [5]

>Vlad Oshin
>Таким образом, добавляя 1 дракона, исключаем 2 поля доски.
Этого недостаточно - ведь он может стоять так, что ход будет за пределы доски.

>ferr © (07.04.06 14:49) [2]
>Какая оценка?
Ну оценка - это, думаю, в данном случае - слишком сильная подсказка.

← →
Kaban (2006-04-07 14:57) [6]

8.
Назовем драконом фигуру, которая движется на 1 клетку вправо, влево, вверх, вниз (ограниченная версия ладьи). Расставим драконов по черным (белым) клеткам.

Очевидно, что оба условия выполняются

← →
MBo © (2006-04-07 14:58) [7]

>Sandman25 © (07.04.06 14:55) [4]
>5. Весы со стрелкой?

Чашечные больше-меньше

← →
Kaban (2006-04-07 14:58) [8]

а более, сори...

← →
ferr © (2006-04-07 14:59) [9]

8) {-8, -8} {1, 0} {0, 1}
расставить как шашки

← →
MBo © (2006-04-07 14:59) [10]

>Kaban (07.04.06 14:57) [6]
второе условие - больше 32

← →
antonn © (2006-04-07 15:01) [11]

5. делим на 2 группы, по 5 штук. взвешиваем - если равны идем дальше (у нас в каждой группе минимум по 1 настоящей).
берем одну из этих групп, и в ней отбираем по 2 монеты и взвешиваем. Оставшуюся монету взвешиваем с одной из этих 4х. Если группы по 2е равны по весу и равны по весу 1 оставшаяся и одна из группы => все настоящие.

← →
ferr © (2006-04-07 15:04) [12]

глупость запостил...

← →
Kaban (2006-04-07 15:08) [13]

3.

1. Каждому числу от 0 до N поставить в соответствие N первых простых чисел

2. Во время первого прохода цикла посчитать произведение простых чисел, соответствующих элементам массива

3. Во время второго прохода цикла вычислить остаток от деления произведения на простое число соответствующее индексу массива

4. Если остаток не равен 0, искомое число найдено

5. Нужен механизм для работы с ОЧЕНЬ большими цифрами :)))

← →
MBo © (2006-04-07 15:11) [14]

>Kaban (07.04.06 15:08) [13]
Не надо больших чисел, пусть будут разумные.

>antonn © (07.04.06 15:01) [11]
А если на втором шаго попалось ФН=ФН
Как однозначно для оставшейся монеты выяснить?

← →
Sandman25 © (2006-04-07 15:18) [15]

const s = "это предложение содержит одиннадцать слов, двадцать шесть слогов, семьдесят три буквы; function Letters: integer; var I : integer; begin Result := 0; for I := 1 to length(s) do if not (s[I] in [" ", ","]) then inc(Result); end; function Slogov: integer; var i : integer; begin result := 0; for I := 1 to length(s) do if s[I] in ["à", "ÿ", "î", "¸", "è", "û", "ó", "þ", "å", "ý"] then inc(result); end; begin Caption := IntToStr(slogov) + " " + IntToStr(Letters); end;

← →
McSimm © (2006-04-07 15:24) [16]

Это предложение содержит восемьдесят пять букв, двадцать шесть слогов, одиннадцать слов
Это предложение содержит восемьдесят шесть букв, двадцать шесть слогов, одиннадцать слов
Это предложение содержит восемьдесят восемь букв, двадцать восемь слогов, одиннадцать слов

← →
antonn © (2006-04-07 15:25) [17]

MBo © (07.04.06 15:11) [14]
А если на втором шаго попалось ФН=ФН
Как однозначно для оставшейся монеты выяснить?
значит на 3ем шаге взять одну из групп ФН, а в другой группе поменять одну монету на "оставшуюся" и взвесить:)

← →
Vlad Oshin © (2006-04-07 15:30) [18]

> Vlad Oshin
> >Таким образом, добавляя 1 дракона, исключаем 2 поля доски.
>
> Этого недостаточно - ведь он может стоять так, что ход будет
> за пределы доски.

но тогда он не обойдет доску!

← →
Jeer © (2006-04-07 15:46) [19]

Kaban (07.04.06 15:08) [13]

Все проще:)
Вот неоптимальный:

1. Отсортировать массив на месте.
2. Циклом пройти до первого несовпадения индекса и значения.

> 3. В массиве длины N содержатся все целые числа от 0 до
> N, кроме
> какого-то одного. Найти пропущенное число, если использовать
> дополнительные массивы нельзя.
> А что, если пропущено два числа?

← →
McSimm © (2006-04-07 15:46) [20]

> Sandman25 © (07.04.06 15:18) [15]

неправильно :)
по условию "содержит _ букв"

> семьдесят три буквы

← →
Sandman25 © (2006-04-07 15:54) [21]

McSimm © (07.04.06 15:46) [20]

А что делать, великая русский языка :)
Вы лучше у себя число букв пересчитайте :)

← →
McSimm © (2006-04-07 15:56) [22]

> число букв пересчитайте

ой :)))

← →
MBo © (2006-04-07 16:09) [23]

>antonn © (07.04.06 15:25) [17]
>значит на 3ем шаге взять одну из групп ФН, а в другой группе поменять одну монету на "оставшуюся" и взвесить:)

Сам понимаешь - мы еще не знаем - пары ФН или другие одинаковые

>Sandman25 © (07.04.06 15:18) [15]
коварный переборщик ;)

Vlad Oshin © (07.04.06 15:30) [18]

> Vlad Oshin
>но тогда он не обойдет доску!

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

← →
Sandman25 © (2006-04-07 16:09) [24]

Если с "букв", то
этопредложениесодержитодиннадцатьсловдвадцатьсемьслоговсемьдесятчетыребукв

← →
Sandman25 © (2006-04-07 16:10) [25]

MBo © (07.04.06 16:09) [23]

Перебор был сначала уменьшен на бумаге (число слов, 10-11), потом я устал считать буковки :)

← →
McSimm © (2006-04-07 16:12) [26]

> Если с "букв", то

А если без "четыре букв" и без пробелов-запятых, то решений найти не могу :(

← →
MBo © (2006-04-07 16:22) [27]

>McSimm
73-26-11 у sandman - верное решение

← →
McSimm © (2006-04-07 16:38) [28]

Значит я неправильно понял условие.
Я полагал, что из реальной фразы спрятаны слова и их надо найти.
поэтому варианты "в этом предложении 73 букв" - исключил из рассмотрения.
Надо было добавить, что слова необходимо изменять в соответвии с грамматикой.

3.
Result := 0;
for I := 0 to N-1 do
Result := Result xor A[I];
for I := N to Next2 do
Resutt := Result xor I;
Next2(N) - ближайшее неменьшее N число, являющееся степенью двойки.
После прохождения результат покажет, какого числа нет, если отбросить старшие биты, число сохраненных бит равно log2 (Next2(N))

3. можно пройтись циклом по массиву найдя сумму чисел массива
пропущенно число: [0+1+2+...N] - CalcSum
0+1+2+...N=N(N+1)/2

MBo © (07.04.06 16:47) [31]

Однако задача по силам школьнику.

Естественно. Если под этим понимать уровень необходимых знаний. Однако хотел бы я посмотреть на этого школьника :)

MBo © (07.04.06 16:54) [35]

Уже видел, сижу пристыженный :)
Кстати, я сдаюсь насчет 5 задачи. Ответы будут в понедельник?

>насчет 5 задачи.
Она IMHO весьма сложная, так что сдаваться быстро не стоит.
Первый шаг - как antonn написал, по 5 на чашку.
На каждом шаге, если разный вес, становится ясно, что фальшивые есть, поэтому можно рассматривать только случаи одинакового веса.
Для одного взвешивания это наборы на каждой чашке
ННННН
ННННФ
НННФФ
ННФФФ
НФФФФ
Дальше пока помолчу.

<<5. У вас имеется 10 монет, среди которых могут быть и фальшивые.
Известно, что настоящие монеты весят одинаково, и фальшивые
(если они есть) тоже весят одинаково). Кроме того, известно, что
хотя бы одна из монет - настоящая.
Как за 3 взвешивания подтвердить или опровергнуть, что все ваши
монеты - настоящие>>

хорошая задача!!!

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

Есть 5 ящиков с золотом, из них один с фальшивым. Известно что фальшивое легче настоящего. Одним взвешиванием определить ящик с фальшивым золотом.

MBo © (07.04.06 16:09) [23]
Сам понимаешь - мы еще не знаем - пары ФН или другие одинаковые
угу, в 12 ночи еще не работается:)
я так понял, задача сводится к определению 2 замеров из 5 монет, где одна точно настоящая?
тогда может так (монеты - 12345):
5+2 = 3+4
1+5 = 3+4
если выполняется, значит все настоящие.

Пятничные задачки Найти похожие ветки