Найти два больших числа из трех

[Gts]

Задача звучит так:

Цитата:

Определите процедуру, которая принимает в качестве аргументов три числа и возвращает сумму квадратов двух больших из них.

Это из 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 $ максимальный.

[wrest]

А можно так: $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$

[Gts]

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

[rockclimber]

Gts в сообщении #1374485 писал(а):

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

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

[wrest]

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$

О, так ещё короче, да!

[Gts]

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)$.
Но мне кажется тут есть более простой путь.

[EUgeneUS]

wrest в сообщении #1374492 писал(а):

О, так ещё короче, да!

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

-- 07.02.2019, 13:43 --

Gts в сообщении #1374485 писал(а):

опрос в том, что я не могу проследить путь мышления автора этого решения.

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

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

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

[wrest]

EUgeneUS в сообщении #1374694 писал(а):

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

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

(Оффтоп)

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

[Gts]

EUgeneUS писал(а):

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

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

(Оффтоп)

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

[mihaild]

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 века - открытие что множество вещественных чисел конечно.

[rockclimber]

mihaild в сообщении #1374736 писал(а):

но и потому что например $x^2 + y^2 + z^2 - y^2 \neq x^2 + z^2$ в общем случае.

А можно чуть подробнее? Из-за переполнения что ли?

[mihaild]

rockclimber в сообщении #1374737 писал(а):

Из-за переполнения что ли?

Сложение на самом деле не коммутативно и не ассоциативно, а математики всех веками обманывали.
Вещественные числа хранятся с конечной точностью, так что скажем $10^{-20} + 1 = 1$. И соответственно $10^{-20} + 1 - 1 = 0$.

[realeugene]

Gts в сообщении #1374485 писал(а):

Вопрос в том, что я не могу проследить путь мышления автора этого решения.

Пузырьковая сортировка + выкидывание всего лишнего.

-- 07.02.2019, 17:42 --

mihaild в сообщении #1374744 писал(а):

Вещественные числа хранятся с конечной точностью, так что скажем $10^{-20} + 1 = 1$. И соответственно $10^{-20} + 1 - 1 = 0$.

Но минимальное число из тройки при этом прибавлять и потом вычитать вполне безопасно.

[rockclimber]

mihaild в сообщении #1374744 писал(а):

Вещественные числа хранятся с конечной точностью

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

realeugene в сообщении #1374746 писал(а):

Но минимальное число из тройки при этом прибавлять и потом вычитать вполне безопасно.

Это да, но как только задача превратится в "найти сумму квадратов двух меньших чисел из трех", этот способ решения превратится в тыкву.

[mihaild]

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, который вещественный (и в итоге всех этих преобразований из интов в числа с плавающей точкой и обратно результат получится вообще случайным).