- PVSM.RU - https://www.pvsm.ru -
Давеча была опубликована логическая задача про Шерил [1], а в комментариях к ней хаброюзер сообщил [2] о более интересной задаче про двух мудрецов.
Собствеено, задача:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.Назовите эти числа.
Решение под катом.
Задачу я решил методом логики и подбора, видимо, иначе она не решается, во всяком случае я такого решения не встречал. Подбором просто найти первое решение, но остаётся загадкой единственно оно на заданном промежутке или нет. Мне пришла мысль написать решение с использованием ленивых коллекций и практики ради была выбрана scala. Итак начнём.
Будем двигаться по сообщениям мудрецов, смотреть, какую информацию они нам дают и писать соответствующие функции:
lazy val primes: Stream[Int] = 2 #:: Stream.from(3).filter(i => isPrime(i))
def isPrime(x: Int): Boolean = {
primes.takeWhile(i => i*i <= x).forall { k => x % k > 0}
}
Всё просто — следующее число будет простым только если оно не делится без остатка ни на одно из всех уже известных простых чисел. Дальше можно создать список всевозможных чисел для Али убрав оттуда произведения простых чисел(6, 15,...), но мы пока этого делать не будем.
//раскладываем число на сумму двух других в соотв. с условиями задачи
def expandBySum(x: Int): List[(Int, Int)] = {
@tailrec def helper(accum: List[(Int, Int)], i: Int, j: Int): List[(Int, Int)] = {
if (i < j) accum
else helper((i, j) :: accum, i - 1, j + 1)
}
helper(List.empty, x - 2, 2)
}
lazy val ValiNumbers: Stream[Int] = Stream.from(4).filter(i => !expandBySum(i).exists(expanded => isPrime(expanded._1) && isPrime(expanded._2)))
Генерируем поток чисел, которые не имеют ни одного разложения на сумму двух простых.
//раскладываем число на два множителя
def expandByProduct(x: Int): List[(Int, Int)] = {
var biggestPossibleDivision = x / 2
@tailrec def helper(accum: List[(Int, Int)], i: Int): List[(Int, Int)] = {
if (i == biggestPossibleDivision) return accum
if (x % i == 0) {
biggestPossibleDivision = if(x / i <= i) biggestPossibleDivision else x / i
helper((x / i, i) :: accum, i + 1)
}
else helper(accum, i + 1)
}
helper(List.empty, 2)
}
def inValiNumbers(x: Int): Boolean = {
ValiNumbers.takeWhile(valis => valis <= x).contains(x)
}
lazy val AliNumbers: Stream[Int] = Stream.from(4).filter(i => expandByProduct(i).count(expanded => inValiNumbers(expanded._1 + expanded._2)) == 1)
Раскладываем число на список из двух множителей и проверяем, что сумма только одно пары входит в список чисел Вали. Так мы получаем все числа, которые шейх мог шепнуть Али.
lazy val ValiNumbersWithSolution: Stream[Int] = ValiNumbers.filter(valis => expandBySum(valis).map(expanded => expanded._1 * expanded._2).count(inAliNumbers) == 1)
Ленивый список со всеми возможными парами чисел, которые мог загадать шейх:
lazy val solution: Stream[String] = ValiNumbersWithSolution.map(valis => {
val solution = expandBySum(valis).filter(expanded => inAliNumbers(expanded._1 * expanded._2)).head
"Alis number: " + solution._1 * solution._2 + "; Valis number: " + (solution._1 + solution._2) + "; solution: " + solution._1 + " & " + solution._2
})
Оказывается, в диапазона от 1 до 100 существует всего четыре пары чисел, которые бы мог загадать шейх. Иными словами, мудрецам неслабо фартануло :)
println("Vali's possible numbers: " + (ValiNumbers.take(20).toList mkString ", "))
println("Ali's possible numbers: " + (AliNumbers.take(30).toList mkString ", "))
println("Vali's numbers that give solution to Ali: " + (ValiNumbersWithSolution.take(3).toList mkString ", "))
println(solution.take(3).toList mkString "n")
"Vali's possible numbers: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87"
"Ali's possible numbers: 18, 24, 28, 50, 52, 54, 76, 92, 96, 98, 100, 112, 124, 140, 144, 148, 152, 160, 172, 176, 188, 192, 208, 212, 216, 220, 228, 232, 242, 244"
"Vali's numbers that give solution to Ali: 17, 65, 89"
"Alis number: 52; Valis number: 17; solution: 13 & 4"
"Alis number: 244; Valis number: 65; solution: 61 & 4"
"Alis number: 1168; Valis number: 89; solution: 73 & 16"
Ссылка на сорцы [3]
Автор: pronvis
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/logika/89015
Ссылки в тексте:
[1] задача про Шерил: http://geektimes.ru/post/249014/
[2] сообщил: http://geektimes.ru/post/249014/#comment_8333060
[3] Ссылка на сорцы: https://github.com/invis87/dva_mudretca
[4] Источник: http://geektimes.ru/post/249098/
Нажмите здесь для печати.