Вычислить максимум необычной суммы?

iks2 · 24.10.2016, 16:34

Задача
дано 100 чисел: sin1, sin2, ... , sin100
Эти числа разбиваются на пары и перемножаются. Получается 50 чисел, которые и складываются.
Требуется всё это проделать так, чтобы получить максимальную сумму.

решение
1. числа загоняются в массив
2. массив сортируется
3. рядом стоящие элементы перемножаются и все суммируется

Вопрос. Будет ли это Истинный максимум?

Код:

REM
REM  SUMMA = 25.11266
REM

CLS
CONST n = 100
DIM x(1 TO n)

FOR i = 1 TO n
   x(i) = SIN(i)
NEXT

FOR i = 1 TO n - 1
FOR j = i + 1 TO n
   IF x(i) > x(j) THEN SWAP x(i), x(j)
NEXT j, i

FOR i = 1 TO n - 1 STEP 2
   S = S + x(i) * x(i + 1)
NEXT

PRINT "SUMMA ="; S
END

Николай_С · 24.10.2016, 17:31

Странно что в квадрат при этом не возводятся, а то была бы единица.

Цитата:

Вопрос. Будет ли это Истинный максимум?

Конечно же нет. А как быть с отрицательными числами?

P.s. Метод сортировки примитивен. Что-нибудь слышали про пузырьковый метод?

Vladimir_S · 24.10.2016, 19:02

Цитата:

Сообщение от Николай_С

P.s. Метод сортировки примитивен. Что-нибудь слышали про пузырьковый метод?

Да ладно, Коля, - какая разница? Методов сортировки много, и тут уж кому что нравится.

iks2 · 24.10.2016, 19:44

Николай_С
Понимаете, после сортировки, мы имеем последовательность от самого меньшего числа, до самого большего. Далее все числа, пары, перемножаются. Иными словами умножение двух отрицательных чисел дает положительное число. В случае если число отрицательных чисел нечетно, то
это будет самое маленькое по модулю отрицательное число и умножится оно на самое маленькое по модулю положительное число. То есть мы получим (в данном случае) самое малое по модулю отрицательное число. Понимаете, меньше Не существует. Ну а что с остальными числами?
Приведу вам пример для двух пар чисел. Дано A, B, C, D - четыре числа в порядке возрастания. И надо доказать, что AB + CD - Абсолютный максимум. Итак у нас 2 варианта. Докажем оба
1. (AB + CD) > (AC + BD)
2. (AB + CD) > (AD + BC)
...
1. (AB + CD) - (AC + BD) > 0 ?
A(B - C) + D(C - B) = (A - D)(B - C) > 0 (доказано)

2. (AB + CD) - (AD + BC) > 0 ?
A(B - D) + C(D - B) = (A - C)(B - D) > 0 (доказано)

Надо полагать, что далее может помочь математическая индукция (это я не проверял)
Как вы считаете, этого недостаточно?

24.10.2016, 16:34	#1 (permalink)
iks2 Member Регистрация: 22.10.2016 Сообщений: 62 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Вычислить максимум необычной суммы? Задача дано 100 чисел: sin1, sin2, ... , sin100 Эти числа разбиваются на пары и перемножаются. Получается 50 чисел, которые и складываются. Требуется всё это проделать так, чтобы получить максимальную сумму. решение 1. числа загоняются в массив 2. массив сортируется 3. рядом стоящие элементы перемножаются и все суммируется Вопрос. Будет ли это Истинный максимум? Код: REM REM SUMMA = 25.11266 REM CLS CONST n = 100 DIM x(1 TO n) FOR i = 1 TO n x(i) = SIN(i) NEXT FOR i = 1 TO n - 1 FOR j = i + 1 TO n IF x(i) > x(j) THEN SWAP x(i), x(j) NEXT j, i FOR i = 1 TO n - 1 STEP 2 S = S + x(i) * x(i + 1) NEXT PRINT "SUMMA ="; S END

Опции темы
Версия для печати Отправить по электронной почте
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид

24.10.2016, 19:44	#4 (permalink)
iks2 Member Регистрация: 22.10.2016 Сообщений: 62 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Николай_С Понимаете, после сортировки, мы имеем последовательность от самого меньшего числа, до самого большего. Далее все числа, пары, перемножаются. Иными словами умножение двух отрицательных чисел дает положительное число. В случае если число отрицательных чисел нечетно, то это будет самое маленькое по модулю отрицательное число и умножится оно на самое маленькое по модулю положительное число. То есть мы получим (в данном случае) самое малое по модулю отрицательное число. Понимаете, меньше Не существует. Ну а что с остальными числами? Приведу вам пример для двух пар чисел. Дано A, B, C, D - четыре числа в порядке возрастания. И надо доказать, что AB + CD - Абсолютный максимум. Итак у нас 2 варианта. Докажем оба 1. (AB + CD) > (AC + BD) 2. (AB + CD) > (AD + BC) ... 1. (AB + CD) - (AC + BD) > 0 ? A(B - C) + D(C - B) = (A - D)(B - C) > 0 (доказано) 2. (AB + CD) - (AD + BC) > 0 ? A(B - D) + C(D - B) = (A - C)(B - D) > 0 (доказано) Надо полагать, что далее может помочь математическая индукция (это я не проверял) Как вы считаете, этого недостаточно?

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070