2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Найти два больших числа из трех
Сообщение06.02.2019, 16:31 


04/06/13
82
Задача звучит так:
Цитата:
Определите процедуру, которая принимает в качестве аргументов три числа и возвращает сумму квадратов двух больших из них.

Это из sicp.
Мне интересно, как искать два самых больших элемента.

Моё решение:
Используется синтаксис Lisp
#lang sicp

(define (square x)
  (* x x))
(define (sum-of-square x y)
  (+ (square x) (square y)))

(define (best-couple a b c)
  (sum-of-square (max a b c) (max (min a b) (min a c) (min b c))))
 


На всякий случай вот аналог на Си-подобном языке.
Используется синтаксис C
int bestCouple(int a, int b, int c)
{
    return pow(max(a, b, c), 2) + pow(max(min(a, b), min(a, c), min(b, c)), 2);
    // На случай, если max принимает только два аргумента: max(a, b, c) == max(max(a, b), c)
}
 


Применив max ко всем аргументам, мы получим самый максимальный аргумент, который будем использовать в качестве аргумента для функции суммы квадратов.
Применив функцию min к комбинациям пар аргументов, мы получим три минимума, в которых заведомо не будет максимального аргумента. Применив max к этим минимумам, мы получим второй по величине аргумент. Это будет вторым аргументом функции суммы квадратов.



А есть вот такое красивое решение, которе я не могу понять:
Используется синтаксис Lisp
(define (best-couple a b c)
  (sum-of-square (max a b) (max (min a b) c)))
 


Используется синтаксис C
int bestCouple(int a, int b, in c)
{
    return pow(max(a, b), 2) + pow(max(min(a, b), c), 2);
}
 

Вопрос в том, что я не могу проследить путь мышления автора этого решения. Понимаю, что вопрос тривиален, но меня хватает лишь подставить значения в набор функций и увидеть, что результат верный. Я ниже написал последовательность шагов из готового решения, но конечный результат виден только в конце. Ну не в слепую же автор перебирал варианты в данном случае. Я был бы рад увидеть ход ваших мыслей, когда вы видите эту задачу. Т.е. вопрос из серии: а как эту штуку придумали?

Для упрощения предположим, что все аргументы разные.
Возьмем минимум двух аргументов $a$ и $b$. Получим либо самый минимальный элемент, либо средний.
Далее полученный результат и третий аргумент передадим в $\max$. На выходе мы получим либо самый максимальный элемент, либо средний. Пусть $result = \max(\min(a, b), c)$

Теперь возьмём максимум аргументов $a$ и $b$. $\max$ вернет либо максимальный элемент в случае, когда $result $ средний элемент, либо средний, когда $result $ максимальный.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение06.02.2019, 16:43 


05/09/16
11467
А можно так: $s=a^2+b^2+c^2-(\min (a,b,c))^2$ ну или если как они пишут min принимает только два аргумента, то $s=a^2+b^2+c^2-(\min (\min(a,b), \min (a,c)))^2$

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение06.02.2019, 16:53 


04/06/13
82
Красиво. Только я бы вот так сделал:
$s=a^2+b^2+c^2-(\min (\min(a,b), c))^2$

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение06.02.2019, 16:54 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Gts в сообщении #1374485 писал(а):
Ну не в слепую же автор перебирал варианты в данном случае. Я был бы рад увидеть ход ваших мыслей, когда вы видите эту задачу. Т.е. вопрос из серии: а как эту штуку придумали?
Какую штуку придумали? Второе решение? Примерно так:
1. Задача эквивалентна задаче "сравнить три числа и выбрать меньшее".
2. Для этого достаточно двух сравнений.
3. Выбираем любые два числа и сравниваем.
4. Берем меньшее из них и сравниваем с третьим числом.
5. Далее все очевидно.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение06.02.2019, 16:57 


05/09/16
11467
Gts в сообщении #1374485 писал(а):
Т.е. вопрос из серии: а как эту штуку придумали?
Ну тут, как мне кажется, фишка может быть в том, что объединение подмножеств "два максимальных значения" и "минимальное значение" даёт исходное множество, поэтому можно искать первое подмножество, а можно второе подмножество.
Ну логика под return pow(max(a, b), 2) + pow(max(min(a, b), c), 2); мне кажется довольно простой. min(a,b) дает результат противоположный тому который даёт max(a,b), то если одна функция выбирает a то вторая непременно выбирает не a, то есть выбирает b, вот и всё.

-- 06.02.2019, 17:01 --

Gts в сообщении #1374490 писал(а):
Только я бы вот так сделал:
$s=a^2+b^2+c^2-(\min (\min(a,b), c))^2$
О, так ещё короче, да!

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 13:29 


04/06/13
82
wrest в сообщении #1374492 писал(а):
Ну логика под return pow(max(a, b), 2) + pow(max(min(a, b), c), 2); мне кажется довольно простой. min(a,b) дает результат противоположный тому который даёт max(a,b), то если одна функция выбирает a то вторая непременно выбирает не a, то есть выбирает b, вот и всё.

wrest, за выделенные слова отдельное спасибо. Такое описание мне больше нравится, чем то что я написал.


Цитата:
Какую штуку придумали? Второе решение? Примерно так:
1. Задача эквивалентна задаче "сравнить три числа и выбрать меньшее".
2. Для этого достаточно двух сравнений.
3. Выбираем любые два числа и сравниваем.
4. Берем меньшее из них и сравниваем с третьим числом.
5. Далее все очевидно.

rockclimber, спасибо. Не сразу, но понял почему это эквивалентная задача.

Задача "сравнить три числа и выбрать второе наибольшее число, т.е. то, которое больше минимума и меньше максимума".
За два сравнения мы не всегда можем получить второе наибольшее число. Это происходит, потому что если в первом сравнении мы можем получить максимум, а, значит, при втором сравнении этого максимума и третьего значения мы можем получить минимум.
$MIN \leqslant \min(\max(a, b), c)<MAX$

Посмотрим, что будет, если делать сравнения наоборот: $(a < b) > c$, хотя правильнее $\max(\min(a, b), c)$, потому что операторы сравнения возвращаю булевые значения, а не значение аргументов.
И снова за два сравнения мы не всегда получаем второе максимальное число, потому что если при первом сравнении мы получили минимум, то при втором сравнении этого значение и третьей величины, мы получим максимум, а не второй максимум.
$MIN < \min(\max(a, b), c) \leqslant MAX$

Но если мы откажемся от идеи получить всегда второе наибольшее число, то можем поствупить так:
возьмем вариант поиска, который дает нам либо максимум, либо второе наибольшее число. Если мы сможем получить противоположный результат этого поиска, то задача будет решена.
И вот тут не могу придумать как получить сделать заключительный шаг.
Так-то я вижу, что в $\max(\min(a, b), c)$ заключено сравнение пар $(a, c), (b, c)$ и нам надо сделать еще сравнение последней пары $(a, b)$.
Но мне кажется тут есть более простой путь.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 13:38 
Аватара пользователя


11/12/16
13195
уездный город Н
wrest в сообщении #1374492 писал(а):
О, так ещё короче, да!


Два сравнения и четыре возведения в степень короче, чем три сравнения и два возведения в степень? Хм..

-- 07.02.2019, 13:43 --

Gts в сообщении #1374485 писал(а):
опрос в том, что я не могу проследить путь мышления автора этого решения.


Путь мышления очень прост: минимум возведений в квадрат, когда минимум возведений в квадрат достигнут - минимум сравнений.

Решение понять тоже просто. Вроде объяснили выше, но повторю своими словами:

1. Берем любые два числа из трех. Среди них как минимум одно "нужное" и оно максимальное из них.
2. Найдем число из прошлой пары, которое сразу не взяли (минимум).
3. Его надо сравнить с оставшимся (на максимум).

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 13:47 


05/09/16
11467
EUgeneUS в сообщении #1374694 писал(а):
Два сравнения и четыре возведения в степень короче, чем три сравнения и два возведения в степень? Хм..

Запись короче :) Про эффективность я молчу. :oops:

(Оффтоп)

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

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 15:14 


04/06/13
82
EUgeneUS писал(а):
1. Берем любые два числа из трех. Среди них как минимум одно "нужное" и оно максимальное из них.
2. Найдем число из прошлой пары, которое сразу не взяли (минимум).
3. Его надо сравнить с оставшимся (на максимум).

Спасибо.
Всем спасибо.

(Оффтоп)

Такие простые вещи и так плохо до меня доходят. Смотрел на выделенное предложение и не мог понять, почему нужное нам число максимальное... Беда прямо-таки. Потом дошло, что мы же ищем два максимальных числа, а значит max() от двух чисел вернет либо самое максимальное число либо второе из больших чисел. А теперь нам надо взять число, которое не пропустила функция max(a, b), т.е. результат min(a, b) и третье число и найти их максимум, что опять нам вернет какое-то из наибольших чисел. Вот теперь просто, а не всё то, что я выше понаписывал.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 17:09 
Заслуженный участник
Аватара пользователя


16/07/14
8352
Цюрих
Gts в сообщении #1374490 писал(а):
Красиво. Только я бы вот так сделал:
$s=a^2+b^2+c^2-(\min (\min(a,b), c))^2$
Так делать точно не надо. И не только потому что возведение в квадрат дороже сравнения, но и потому что например $x^2 + y^2 + z^2 - y^2 \neq x^2 + z^2$ в общем случае.

(Оффтоп)

Главное достижение математики XX века - открытие что множество вещественных чисел конечно.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 17:12 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
mihaild в сообщении #1374736 писал(а):
но и потому что например $x^2 + y^2 + z^2 - y^2 \neq x^2 + z^2$ в общем случае.
:shock:
А можно чуть подробнее? Из-за переполнения что ли?

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 17:37 
Заслуженный участник
Аватара пользователя


16/07/14
8352
Цюрих
rockclimber в сообщении #1374737 писал(а):
Из-за переполнения что ли?
Сложение на самом деле не коммутативно и не ассоциативно, а математики всех веками обманывали.
Вещественные числа хранятся с конечной точностью, так что скажем $10^{-20} + 1 = 1$. И соответственно $10^{-20} + 1 - 1 = 0$.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 17:40 


27/08/16
9426
Gts в сообщении #1374485 писал(а):
Вопрос в том, что я не могу проследить путь мышления автора этого решения.
Пузырьковая сортировка + выкидывание всего лишнего.

-- 07.02.2019, 17:42 --

mihaild в сообщении #1374744 писал(а):
Вещественные числа хранятся с конечной точностью, так что скажем $10^{-20} + 1 = 1$. И соответственно $10^{-20} + 1 - 1 = 0$.
Но минимальное число из тройки при этом прибавлять и потом вычитать вполне безопасно.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 17:52 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
mihaild в сообщении #1374744 писал(а):
Вещественные числа хранятся с конечной точностью
Об этом я как-то не подумал. Наверное потому, что в стартовом посте везде стоит тип int. :wink:
realeugene в сообщении #1374746 писал(а):
Но минимальное число из тройки при этом прибавлять и потом вычитать вполне безопасно.
Это да, но как только задача превратится в "найти сумму квадратов двух меньших чисел из трех", этот способ решения превратится в тыкву.

 Профиль  
                  
 
 Re: Найти два больших числа из трех
Сообщение07.02.2019, 18:09 
Заслуженный участник
Аватара пользователя


16/07/14
8352
Цюрих
realeugene в сообщении #1374746 писал(а):
Но минимальное число из тройки при этом прибавлять и потом вычитать вполне безопасно.
Нет конечно.
>>> 16638.168860761307 + 7.9340966657975239e+19 + 1e+20 - 16638.168860761307
1.7934096665797522e+20
>>> 7.9340966657975239e+19 + 1e+20
1.7934096665797526e+20

(числа найдены перебором, поэтому кривые; думать над простейшим примером лень)

-- 07.02.2019, 18:12 --

rockclimber в сообщении #1374749 писал(а):
Наверное потому, что в стартовом посте везде стоит тип int
А еще там стоит pow, который вещественный (и в итоге всех этих преобразований из интов в числа с плавающей точкой и обратно результат получится вообще случайным).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group