Старый 05.02.2015, 23:17   #1
Pashkela
 
Аватар для Pashkela
 
Регистрация: 05.07.2010
Сообщений: 1,243
По умолчанию Логика по-русски))

Есть известная задача:

Цитата:
Два математика, не достигшие пенсионного возраста, встретились после долгого перерыва. Приведем фрагмент их диалога:
- Ну, а дети у тебя есть?
- Три сына.
- А сколько им лет?
- Если перемножить, будет как раз твой возраст.
- (После размышления.) Мне этих данных недостаточно.
- Если сложить их возраст, получится сегодняшнее число.
- (Вновь после размышления.). Все еще не понимаю.
- Кстати, средний сын любит танцевать.
- Понял.
А Вы можете определить возраст каждого из сыновей?
небольшое пояснение: на момент написания задачки пенсионный возраст в России считался 60 лет

и так же есть к ней "объяснение"

Цитата:
Ответ: Математик знает произведение и сумму трех целых чисел и не может их определить. Значит, эти числа таковы, что их нельзя однозначно определить. Если переберем все натуральные числа в разумных пределах, соответствующих условию задачи, например, от 20 до 60, то убедимся, что почти во всех случаях эти числа раскладываются на произведение из трех сомножителей, имеющих разные суммы. Есть только два исключения:
36 = 1*6*6 = 2*2*9, суммы множителей равны 13,
40 = 2*2*10 = 1*5*8, суммы множителей равны 14.
Подходит лишь последний вариант, в котором есть средний сын. Итак, возраст 1 год, 5 и 8 лет.
- настолько странное с точки зрения логики, что лишь только запутывает тех, кто хочет разобраться

Так что мне пришлось поразбираться и написать, надеюсь, более понятное с точки зрения логики объяснение (в виде кода). В объяснении предусмотрены варианты когда все трое сыновей одного возраста или двое близнецов+один постарше или младший+средний+старший (не задается принудительно, дабы вы могли отследить ход мысли):

PHP код:
<pre>
<?php
$a
=array();
$i=0;
for(
$v=16;$v<60;$v++){
 for(
$d=1;$d<32;$d++){
    for(
$x=1;$x<20;$x++){
       for(
$y=1;$y<20;$y++){
         for(
$z=1;$z<20;$z++){
               if(((((
$x*$y*$z)==$v) && (($x+$y+$z)==$d)) && ($z>$y && $y>$x)) || (((($x*$y*$z)==$v) && (($x+$y+$z)==$d)) && ($z>$y && $y==$x)) || (((($x*$y*$z)==$v) && (($x+$y+$z)==$d)) && ($z==$y && $y==$x))){
                   
$i++;
                   
$a[$i]="Возраст: $v Число месяца: <b>$d</b> (Если математику $v лет и сегодня $d число и вариантов на это число больше нет - то ему не нужно спрашивать <b>третью</b> подсказку)";
                   
$a[($i+100)]="Ответ => Возраст: $v Число месяца: $d Младший: $x Средний: $y Старший $z";
               } 
                                           
}}}}}
$s=count($a);
for(
$v=1;$v<($s-1);$v++){
  if(
$a[$v]===$a[$v+1]){
    echo 
"Обнаружены варианты:<pre>";
    echo 
$a[$v+100]."<pre>";
    echo 
$a[($v+1)+100]."<pre>";
    echo 
"Но т.к. в третьей подсказке говорится, что средний сын уже танцует (да хоть поет, нам важен смысл слова 'средний' - значит есть три брата РАЗНОГО возраста: младший, средний и старший,<pre>";      
    echo 
"таким образом подходит только один ответ из двух:<pre>";      
    echo 
"<b>".$a[$v+100]."</b><pre>";
    
$v=$s
  }  
}
echo 
"==============================================================================================================<pre>";
echo 
"<< Решение (главное помнить, что математик прекрасно знает свой возраст и текущую дату, и в любой момент уже может дать ответ,<pre>"
echo 
"если не может - значит вариант не один и поэтому он требует еще подсказку) - <b>вывод, посмотреть, сколько вариантов приходится на текущую дату!</b><pre>";
echo 
"==============================================================================================================<pre>";
echo 
"Если на данный возраст (перемножить возраста сыновей) приходится только одна дата (сложить возраста сыновей) - то математематик уже дал бы ответ (т.к. он точно знает сегодняшнее число), а так он попросил еще подсказку<pre>";
echo 
"Вывод: ищите возраст математика, при котором путем сложения всех возрастов сыновей получается две одинаковые даты<pre>";
echo 
"==============================================================================================================<pre>";
print_r($a);
unset(
$a);
exit;
?>
PS: Проверять из веба, а то тут некоторые из командной строки запускают))

Последний раз редактировалось Pashkela; 06.02.2015 в 01:06..
Pashkela вне форума   Ответить с цитированием
Старый 06.02.2015, 01:01   #2
Beched
 
Регистрация: 06.07.2010
Сообщений: 400
Репутация: 118
По умолчанию

Между тем, можно решить задачу быстрее (у тебя почему-то целых 5 вложенных циклов, т.е. ты решаешь задачу за n^5 времени). Запустил, убрав лишний вывод:
Код:
$ time php /tmp/pasha.php 
1, 5, 8
real	0m1.963s
user	0m1.957s
sys	0m0.006s
Заметим, что математику не больше 59 лет. Его младшему сыну не меньше 1 года (иначе произведение было бы нулевым, а такого возраста нет). Среднему сыну не меньше 2 лет. Значит, возраст старшего сына ограничен сверху числом 59/3, а снизу -- числом 3.
Возраст среднего сына ограничен сверху корнем квадратным из 59.
При этом изначально он не знает, что есть средний сын, поэтому будем заходить за границы и учитывать близнецов.

Вот код на питоне, который вроде как работает за квадрат.
Код:
n = 60
ages = {i: [] for i in xrange(1, n)}
for z in xrange(3, n / 3): # O(n / 3)
    for y in xrange(2, min((n - 1) / z, z) + 1): # O(sqrt(n))
	for x in xrange(1, min((n - 1) / (y * z), y) + 1): # O(sqrt(n))
	    #print 'Sons', x, y, z, 'Father', x * y * z, 'Day', x + y + z
	    t, p = (x, y, z), x * y * z
	    ages[p].append(t)
	    l = [i for i in ages[p] if sum(i) == sum(t)]
	    if len(l) > 1:
		for i in l:
		    if i[0] < i[1] < i[2]:
			print i
			quit()
Перебираем старшего сына до 59/3, среднего и младшего в зависимости от старшего. Записываем все возрасты, если вдруг на каком-то шаге встретили такие два набора сыновей для конкретного возраста отца, что сумма их одинакова, выводим тот из них, который строго упорядочен. Полагаемся при этом на корректность задачи (что ответ есть, и он единственный).

Код:
$ time python /tmp/pasha.py
(1, 5, 8)

real	0m0.011s
user	0m0.008s
sys	0m0.003s

Последний раз редактировалось Beched; 06.02.2015 в 01:20..
Beched вне форума   Ответить с цитированием
Старый 06.02.2015, 01:03   #3
Pashkela
 
Аватар для Pashkela
 
Регистрация: 05.07.2010
Сообщений: 1,243
По умолчанию

ну да, я писал не на скорость, а для объяснения)
Pashkela вне форума   Ответить с цитированием
Старый 06.02.2015, 12:53   #4
mr.The
 
Аватар для mr.The
 
Регистрация: 05.07.2010
Сообщений: 73
Репутация: 16
По умолчанию

Цитата:
Два математика, не достигшие пенсионного возраста, встретились после долгого перерыва. Приведем фрагмент их диалога:
- Ну, а дети у тебя есть?
- Три сына.
- А сколько им лет?
- Если перемножить, будет как раз твой возраст.
- (После размышления.) Ты ебанутый?
- Понял.
Всегда радовало развитие сюжета в таких задачах. Извините.
--
А так-то, вот задачи более по хардкору: https://projecteuler.net/problems
__________________
Бложек mr.The. :rolleyes:
mr.The вне форума   Ответить с цитированием
Ответ

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход



Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Перевод: zCarot