Умотренировочные задачки
№ 749: DmitryKulikov,
Твоё решение да, годидзе.
Твоё решение да, годидзе.
-
Убунтайкин
- Благодарил (а): 17 раз
- Поблагодарили: 53 раза
Хочу предложить такую задачу:
========================
Имеется очень длинный список натуральных чисел. Числа из списка вводятся в компьютер с клавиатуры, каждое - по одному разу.
Про этот список известно следующее:
1. В списке имеется ровно одно число, которое встречается среди чисел списка либо ровно один раз, либо нечётное количество раз.
2. Все прочие числа, входящие в этот список, встречаются в нём чётное количество раз.
3. Объём оперативной памяти и жёсткого диска компьютера во много раз меньше необходимых для размещения всего этого списка.
Задача: нужно найти с помощью компьютера то число, которое встречается в списке нечётное количество раз.
========================
Имеется очень длинный список натуральных чисел. Числа из списка вводятся в компьютер с клавиатуры, каждое - по одному разу.
Про этот список известно следующее:
1. В списке имеется ровно одно число, которое встречается среди чисел списка либо ровно один раз, либо нечётное количество раз.
2. Все прочие числа, входящие в этот список, встречаются в нём чётное количество раз.
3. Объём оперативной памяти и жёсткого диска компьютера во много раз меньше необходимых для размещения всего этого списка.
Задача: нужно найти с помощью компьютера то число, которое встречается в списке нечётное количество раз.
И куда эти числа вводятся?Убунтайкин писал(а) ↑ 04 ноя 2021 16:52: Объём оперативной памяти и жёсткого диска компьютера во много раз меньше необходимых для размещения всего этого списка
-
Убунтайкин
- Благодарил (а): 17 раз
- Поблагодарили: 53 раза
Компьютер считывает их из входного потока. Он должен все эти числа прочитать (не имея возможности запомнить) и выдать нужное. Этой задачей поделился со мной один знакомый программист.Злец писал(а) ↑ 04 ноя 2021 18:46: И куда эти числа вводятся?
-
Убунтайкин
- Благодарил (а): 17 раз
- Поблагодарили: 53 раза
Вот вам другая задача, взятая из сборника "Московские математические олимпиады".
================
Али-Баба пытается проникнуть в пещеру. У входа в неё стоит барабан с четырьмя отверстиями по бокам. Около каждого отверстия внутри поставлен переключатель, имеющий два положения - "верх", "низ". Разрешается засунуть руки в какие-либо два отверстия, пощупать, как стоят переключатели, и переключить их произвольным образом (в частности, можно не переключать). После этого барабан приходит в быстрое вращение, так что после его остановки уже нельзя установить, какие именно переключатели трогали в прошлый раз. Разрешается повторить эту операцию до десяти раз. Дверь в пещеру открывается в тот момент, когда все переключатели стоят в одинаковом положении. Докажите, что Али-Баба сумеет попасть в пещеру.
================
Али-Баба пытается проникнуть в пещеру. У входа в неё стоит барабан с четырьмя отверстиями по бокам. Около каждого отверстия внутри поставлен переключатель, имеющий два положения - "верх", "низ". Разрешается засунуть руки в какие-либо два отверстия, пощупать, как стоят переключатели, и переключить их произвольным образом (в частности, можно не переключать). После этого барабан приходит в быстрое вращение, так что после его остановки уже нельзя установить, какие именно переключатели трогали в прошлый раз. Разрешается повторить эту операцию до десяти раз. Дверь в пещеру открывается в тот момент, когда все переключатели стоят в одинаковом положении. Докажите, что Али-Баба сумеет попасть в пещеру.
Тогда, очевидно, XOR ко всем входящим.Убунтайкин писал(а) ↑ 04 ноя 2021 19:39: Компьютер считывает их из входного потока. Он должен все эти числа прочитать (не имея возможности запомнить) и выдать нужное
-
Убунтайкин
- Благодарил (а): 17 раз
- Поблагодарили: 53 раза
Тогда вот вам усложнённый вариант: всё, как в первой задаче, но чисел, которые встречаются нечётное количество раз, ровно два. Признаться, решение мне неизвестно - пробовал решить, но потом забросил.Злец писал(а) ↑ 04 ноя 2021 20:18: Тогда, очевидно, XOR ко всем входящим.
Многие полезут в гугл, но зачем, если можно испытать оргазм, решив самому.
Задача чисто развлекательная.
Есть вот такие ряды:
0 0 0 = 6
1 1 1 = 6
2 2 2 = 6
3 3 3 = 6
4 4 4 = 6
5 5 5 = 6
6 6 6 = 6
7 7 7 = 6
8 8 8 = 6
9 9 9 = 6
10 10 10 = 6
Необходимо расставить любые математические символы действий над числами, любые, применять любые математические способы, дабы все уравнения привести в порядок.
Ограничение ровно одно: ни одной дополнительной цифры вводить нельзя, а так, хоть интегралами считайте.
В некоторых случаях есть больше одного варианта ответа, т.е. скомпоновать можно по-разному. И здесь не только плюс, минус, умножить и разделить. Математических операций гораздо больше!
Сумеете выстроить все уравнения?
P.S. И еще у меня сейчас задачка по терверу на теорию игр, весь мозг сломал, не выходит каменный цветок, потом здесь напишу.
Задача чисто развлекательная.
Есть вот такие ряды:
0 0 0 = 6
1 1 1 = 6
2 2 2 = 6
3 3 3 = 6
4 4 4 = 6
5 5 5 = 6
6 6 6 = 6
7 7 7 = 6
8 8 8 = 6
9 9 9 = 6
10 10 10 = 6
Необходимо расставить любые математические символы действий над числами, любые, применять любые математические способы, дабы все уравнения привести в порядок.
Ограничение ровно одно: ни одной дополнительной цифры вводить нельзя, а так, хоть интегралами считайте.
В некоторых случаях есть больше одного варианта ответа, т.е. скомпоновать можно по-разному. И здесь не только плюс, минус, умножить и разделить. Математических операций гораздо больше!
Сумеете выстроить все уравнения?
P.S. И еще у меня сейчас задачка по терверу на теорию игр, весь мозг сломал, не выходит каменный цветок, потом здесь напишу.
0+0+0=6' (ну типа производная от константы) - так можно?
системы счисления и логаримы по основаниям можно?
системы счисления и логаримы по основаниям можно?
Ну, как вариант, у меня был другой способ. Как и говорил, в каждом случае наверняка можно придумать больше одного варианта.Дрыныч писал(а) ↑ 05 фев 2022 07:32: 0+0+0=6' (ну типа производная от константы) - так можно?
Логарифмы - почему нет, можно, но с выполнением условия, что никаких дополнительных цифр появляться не должно. Но ведь есть логарифмы, где основание цифрой не обозначается.системы счисления и логаримы по основаниям можно?
Системы счисления - нет, считаем в десятичной.
ну то есть lg, ln - ОК, а log только используя одну из цифр?
и наскольк широко можно математичские нотации применять? Четкое ТЗ есть?)
А то я ведь могу взять функцию AlwaysSix(x,y,z) - ни одной цифры, но по сигнатуре понятно что она делает)
и наскольк широко можно математичские нотации применять? Четкое ТЗ есть?)
А то я ведь могу взять функцию AlwaysSix(x,y,z) - ни одной цифры, но по сигнатуре понятно что она делает)
Только то, что я транслировал выше, других уточнений у меня нет.Дрыныч писал(а) ↑ 05 фев 2022 13:44: и наскольк широко можно математичские нотации применять? Четкое ТЗ есть?)
Но это задача для школьной программы, интегралы и производные в школах изучают.
И все примеры решаются исключительно в рамках школьной программы обычной общеобразовательной математики.
Да, вполне.ну то есть lg, ln - ОК
Последний раз редактировалось Splinter 05 фев 2022 15:22, всего редактировалось 1 раз.
№ 760: Дрыныч,
[неуклюже помогает]
[неуклюже помогает]
Код: Выделить всё
function AlwaysSix(int $x, int $y, int $z) :int {
return 6;
}
ну то есть я могу спокойно брать число пи, число е, операции округления пол-потолок, знак бесконечсности, ряды?Splinter писал(а) ↑ 05 фев 2022 15:22: Только то, что я транслировал выше, других уточнений у меня нет.
Но это задача для школьной программы, интегралы и производные в школах изучают.
И все примеры решаются исключительно в рамках школьной программы обычной общеобразовательной математики.
Можешь, конечно, в рамки условий укладывается.Дрыныч писал(а) ↑ 05 фев 2022 16:02: ну то есть я могу спокойно брать число пи, число е, операции округления пол-потолок, знак бесконечсности, ряды?
Но давай постараемся не просто решить, а решить проще.
Это не требование по условиям - тут ограничений нет, кроме вышеозвученных - но чтобы школьнику понятно было.
Более того, в одном случае пи применить придется, правилами это не запрещено, на ринг выйдет тригонометрия.
Если кто найдет иные варианты, то я только рад буду: математика крайне изящная наука.
Да, с единицами сложнее всего было...Splinter писал(а) ↑ 05 фев 2022 16:22:Более того
Остальные за пару минут сделал.
Попробую с единицами, можно ли проще.
P.S. Думаю, не очень сильно подскажу, что некоторые приводятся к единицам.
Но это некрасиво, попробую все таки еще.
В смысле решить красиво?Splinter писал(а) ↑ 05 фев 2022 16:22: Но давай постараемся не просто решить, а решить проще.
Просто так-то с помощью пи/пи = 1 мы можем добить до какого угодно результата.
Какой из этих примеров самый сложный? Над всеми думать лениво:)
уж лучше тогда ln(e)Дрыныч писал(а) ↑ 05 фев 2022 17:16: с помощью пи/пи = 1
А с помощью пи, е и округления можно вообще творить чудеса.
Слева поставить плюсы, знаки равно позачеркивать нафик! Кроме третьего.
[Ныряет в подвал]
[Ныряет в подвал]
- bullshizer
- Благодарил (а): 568 раз
- Поблагодарили: 66 раз
Нууу, это кому как. Дольше всего ломали голову над нулями и единицами, причем, решив пример с единицами, дальше легко уже можно было решить с нулями, ибо единицу перевести в ноль проблем нет.Дрыныч писал(а) ↑ 05 фев 2022 17:16: Какой из этих примеров самый сложный?
А, с семерками еще поскрипеть пришлось.
Началооось!!!Над всеми думать лениво:)
Всем "лениво", а вот возьми и подумай!
Мне подобного рода задачки помогают малость встряхнуться, интересно становится: "нет, я смогу, я сумею, сам".
Вот, повторюсь, по терверу человек подкинул задачу, с четверга бьюсь, пока неудачно, но азарт есть.
дык получается, что задачи решаются очень примитивно по допустимым условиям, а думать над красотой уже зная решение уже не для инжерной натуры)Splinter писал(а) ↑ 05 фев 2022 23:21: Всем "лениво", а вот возьми и подумай!
что там про терверную задачку?)
Я ещё завтра, выходной, поковыряюсь сам, потом расскажу. Никак у меня там вероятность больше 1/6 не получается, а должно быть больше!Дрыныч писал(а) ↑ 05 фев 2022 23:32: что там про терверную задачку?)
Интрига
Возможно, мне даже будет стыдно после этого, что так долго мыкался с ней.
Если интересно про тервер, то вот еще классическая задача по теории игр.
Сразу говорю: ответ гуглится запросто, если вам надо, но теряется интерес.
Некоторое число респондентов независимо друг от друга равновероятно выбирают произвольное число от 0 до 100.
Победителем становится тот, чье число будет ближе всех к 2/3 от среднего арифметического всех чисел, предложенных всеми остальными участниками.
Произвольный участник не знает что предлагали остальные, может только предполагать.
Какое число выбрали бы вы, чтобы с наибольшей вероятностью стать победителем?
P.S. Эту задачу проверяли на практике в 1997 году среди читателей одной газеты.
Сразу говорю: ответ гуглится запросто, если вам надо, но теряется интерес.
Некоторое число респондентов независимо друг от друга равновероятно выбирают произвольное число от 0 до 100.
Победителем становится тот, чье число будет ближе всех к 2/3 от среднего арифметического всех чисел, предложенных всеми остальными участниками.
Произвольный участник не знает что предлагали остальные, может только предполагать.
Какое число выбрали бы вы, чтобы с наибольшей вероятностью стать победителем?
P.S. Эту задачу проверяли на практике в 1997 году среди читателей одной газеты.
условие же некорректное - тут либо выбирают равномерно либо стараются попасть в 2\3 от среднего арифмитическогоSplinter писал(а) ↑ 06 фев 2022 01:49: Некоторое число респондентов независимо друг от друга равновероятно выбирают произвольное число от 0 до 100.
Победителем становится тот, чье число будет ближе всех к 2/3 от среднего арифметического всех чисел, предложенных всеми остальными участниками.
если второе - то 0 что ли в силу симметрии?
ОК, согласен, условие писал по памяти, сейчас скачал источник, прочитал формулировку еще раз.
Читатели газеты выбирают любое целое число от 0 до 100. Победителем становится тот, чье число ближе всех к 2/3 от среднего арифметического всех чисел, участвующих в конкурсе.
Вот так сформулировано условие у Талера было.
Можно представить в виде газетного объявления.
Читатели газеты выбирают любое целое число от 0 до 100. Победителем становится тот, чье число ближе всех к 2/3 от среднего арифметического всех чисел, участвующих в конкурсе.
Вот так сформулировано условие у Талера было.
Можно представить в виде газетного объявления.
Внимание! Конкурс!
Пришлите в редакцию любое число от 0 до 100. Если ваше число окажется наиболее близко к 2/3 от среднего арифметического среди всех присланных чисел, то вы станете победителем!
Приз редакции - пирожок с полки!
№ 775: Splinter, Да вроде всё просто. Если взять равномерное распределение, т.е. среднее арифметическое будет 50. А 2/3 от 50, это 33,(3). Но раз мы тут про теорию игр, то надо сделать ещё шажок и взять 2/3 от 33, т.е. 22.
0 и 1 - решения устойчивые по Нэшу
0 сильнее
в реальности нужно строить гипотезы об участниках - например можно прикинуть что у 50% интеллекта хватит лишь на вывод что надо выбирать 2/3 от 50
25% может посчитать что больше 50 вообще глупо выбирать, соот-но средняя будети 25, а 2/3 от нее - 16
10% сообразит на вторую итерацию, т.е что надо брать 2/3 от 33 - 22 то бишь
5% сообразит что итерации можно продолжать и выберути 0 или 1
оставшиеся пусть выберут случайно, можно им какое-то рапределение придумать:)
ну и посчитать по таким примерным прикидкам сколько средняя получается, от нее 2/3...
я бы пожалуй в подобном конкурсе если бы проводили среди россиян, назвал бы 12
0 сильнее
в реальности нужно строить гипотезы об участниках - например можно прикинуть что у 50% интеллекта хватит лишь на вывод что надо выбирать 2/3 от 50
25% может посчитать что больше 50 вообще глупо выбирать, соот-но средняя будети 25, а 2/3 от нее - 16
10% сообразит на вторую итерацию, т.е что надо брать 2/3 от 33 - 22 то бишь
5% сообразит что итерации можно продолжать и выберути 0 или 1
оставшиеся пусть выберут случайно, можно им какое-то рапределение придумать:)
ну и посчитать по таким примерным прикидкам сколько средняя получается, от нее 2/3...
я бы пожалуй в подобном конкурсе если бы проводили среди россиян, назвал бы 12
№ 776: TheJudge, вот в твоей соображалке я никогда не сомневался, все верно.
Только люди пошли еще дальше.
Только люди пошли еще дальше.
Тем не менее ноль не оказался выигрышным числом в этом эксперименте в Financial Times. Средним арифметическим было число 19, поэтому победило число 13.
И здесь почти в точку.Дрыныч писал(а) ↑ 06 фев 2022 10:57: я бы пожалуй в подобном конкурсе если бы проводили среди россиян, назвал бы 12
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 18 гостей