Нерешенная задача на максимум

echs · Регистрация: 23.10.2013

Студворк — интернет-сервис помощи студентам

Суть задачи проста. Задан ряд натуральных чисел
1, 2, 3, ... , 100
Из этого ряда должна быть построена числовая сумма
с использованием функции SIN() так, чтобы сумма
получилась максимальной (или близкой к ней)
пример построения
1) sin1 + sin2 + sin(3+4) + sin5 +sin(6+7) + ...
2) sin(1+2) + sin3 + sin(4+5) + sin(6+7) + ...
Иными словами под знаком sin может стоять одно или
сумма двух чисел (порядок четко соблюдается), но
заранее не определено - одно число или сумма

решение
1. подумал. может сначала проверить все пары и
выделить те, которые дают наибольшие значения?
2. заодно рассмотреть пары, которые дают наименьшие
значения и не использовать их?
3. разбить большой ряд на несколько меньших и провести
тотальный расчет на максимум
4. задача мне не подвластна, может кто что-нибудь подскажет?

Shersh · 23.09.2016, 13:54

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Const u = 30 '100 (если у тебя и(ли) твоей машинки есть несколько лишних лет жизни - попробуй задать U=100, я столько ждать не могу)
Dim maxSum#, MaxS$, a#(1 To u + u - 1)
 
Sub asd()
Dim i&
For i = 1 To u + u - 1
  a(i) = Sin(i)
Next i
Dim t!: t = Timer
maxSum# = 0
r 1
Debug.Print Timer - t
Debug.Print maxSum#, MaxS$
End Sub
 
Sub r(n As Integer, Optional sum#, Optional s$)
If n <= u Then
  r n + 1, a(n) + sum, s & "(" & n & ")"
  If n < u Then r n + 2, a(n + n + 1) + sum, s & "(" & n & "+" & n + 1 & ")"
Else
  If sum > maxSum Then
    maxSum = sum: MaxS = s
'    Debug.Print maxSum#, MaxS$
  End If
'  DoEvents
End If
End Sub

@volvo · 23.09.2016, 14:11

Паскаль (ну нет у меня Бейсика, чтобы проверить) :
Рекурсивно:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
{$mode objfpc}
uses sysutils, math;
const size = 25;
var
  maxsum : double = -maxint;
  maxstr : string = '';
 
  count : longint;
 
procedure p(sum : double; n : integer; s : string);
begin
  inc(count);
  if n <= size then
  begin
    p(sum + sin(n), n + 1, s + format('+sin(%d)', [n]));
    if n < size then p(sum + sin(n + n + 1), n + 2, s + format('+sin(%d+%d)', [n, n+1]));
  end
  else
  begin
    if sum > maxsum then
    begin
      maxsum := sum; maxstr := s;
    end
  end
 
end;
 
begin
  p(0.0, 1, '');
  writeln(maxstr + ' = ', maxsum:15:10);
end.

, выводит:

+sin(1)+sin(2)+sin(3)+sin(4+5)+sin(6+7)+ sin(8)+sin(9)+sin(10+11)+sin(12)+sin(13) +sin(14)+sin(15)+sin(16+17)+sin(18)+sin( 19)+sin(20)+sin(21)+sin(22)+sin(23+24)+s in(25) = 8.6175684025

за пару секунд, при увеличении size время сильно увеличивается, поэтому, чтобы не ждать часами - решаем динамическим программированием:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
{$mode objfpc}
{$h+}
uses sysutils, math;
const size = 100;
var
  arr : array[-1 .. size] of record v : double; from : integer; s : string end;
  k : integer;
  first, second : double;
  st : string = '';
 
begin
  arr[-1].v := 0.0;
  arr[ 0].v := 0.0;
  for k := 1 to size do
  begin
    first := arr[k-1].v + sin(k);
    second := arr[k-2].v + sin(k-1+k);
    if first > second then
    begin
      arr[k].v := first;
      arr[k].from := k-1;
      arr[k].s := format('sin(%d)',[k])
    end
    else
    begin
      arr[k].v := second;
      arr[k].from := k-2;
      arr[k].s := format('sin(%d+%d)',[k-1,k])
    end
  end;
  k := size;
  while k > 0 do
  begin
    st := arr[k].s + '+' + st;
    k := arr[k].from;
  end;
  writeln(arr[size].v:15:10, ' -> ', st);
end.

Выводит

8.6175684025 -> sin(0+1)+sin(2)+sin(3)+sin(4+5)+sin(6+7) +sin(8)+sin(9)+sin(10+11)+sin(12)+sin(13 )+sin(14)+sin(15)+sin(16+17)+sin(18)+sin (19)+sin(20)+sin(21)+sin(22)+sin(23+24)+ sin(25)+

мгновенно, при size = 100 результат:

35.2175510457 -> sin(0+1)+sin(2)+sin(3)+sin(4+5)+sin(6+7) +sin(8)+sin(9)+sin(10+11)+sin(12)+sin(13 )+sin(14)+sin(15)+sin(16+17)+sin(18)+sin (19)+sin(20)+sin(21)+sin(22)+sin(23+24)+ sin(25+26)+sin(27)+sin(28)+sin(29+30)+si n(31+32)+sin(33)+sin(34)+sin(35+36)+sin( 37)+sin(38)+sin(39)+sin(40)+sin(41+42)+s in(43)+sin(44)+sin(45)+sin(46)+sin(47)+s in(48+49)+sin(50+51)+sin(52)+sin(53)+sin (54+55)+sin(56)+sin(57)+sin(58)+sin(59)+ sin(60+61)+sin(62)+sin(63)+sin(64)+sin(6 5)+sin(66)+sin(67+68)+sin(69+70)+sin(71) +sin(72)+sin(73+74)+sin(75+76)+sin(77)+s in(78)+sin(79+80)+sin(81)+sin(82)+sin(83 )+sin(84)+sin(85+86)+sin(87)+sin(88)+sin (89)+sin(90)+sin(91)+sin(92+93)+sin(94+9 5)+sin(96)+sin(97)+sin(98+99)+sin(100)+

выводится моментально

@кот Бегемот · 23.09.2016, 14:56

у меня в Excel получилось 35,21755105

А вот на Бейсике, по-нашему, по-колхозному:

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
DIM max(100)
max(1) = SIN(1)
t1 = max(1) + SIN(2)
t2 = SIN(3)
IF t1 > t2 THEN max(2) = t1 ELSE max(2) = t2
FOR i = 3 TO 100
t1 = max(i - 1) + SIN(i)
t2 = max(i - 2) + SIN(2 * i - 1)
IF t1 > t2 THEN max(i) = t1 ELSE max(i) = t2
NEXT
PRINT max(100)

Зато коротко.
Ответ тот же

PS программа выдаёт ответ моментально

@m-ch · 23.09.2016, 15:10

Задача на динамическое программирование:

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DIM m(100) AS DOUBLE, t(100) AS STRING, m1 AS DOUBLE, m2 AS DOUBLE, i AS LONG, n AS LONG
n = 100
m(1) = SIN(1)
t(1) = "sin(1)"
FOR i = 2 TO n
    m1 = m(i - 1) + SIN(i)
    m2 = m(i - 2) + SIN(i - 1 + i)
    IF m1 > m2 THEN
        m(i) = m1
        t(i) = t(i - 1) + "+sin(" + LTRIM$(STR$(i)) + ")"
    ELSE
        m(i) = m2
        t(i) = t(i - 2) + "+sin(" + LTRIM$(STR$(i - 1)) + "+" + LTRIM$(STR$(i)) + ")"
    END IF
NEXT i
PRINT m(n)
PRINT t(n)

Результат:
35,21755104565
sin(1)+sin(2)+sin(3)+sin(4+5)+sin(6+7)+s in(8)+sin(9)+sin(10+11)+sin(12)+sin(13)+ sin(14)+sin(15)+sin(16+17)+sin(18)+sin(1 9)+sin(20)+sin(21)+sin(22)+sin(23+24)+si n(25+26)+sin(27)+sin(28)+sin(29+30)+sin( 31+32)+sin(33)+sin(34)+sin(35+36)+sin(37 )+sin(38)+sin(39)+sin(40)+sin(41+42)+sin (43)+sin(44)+sin(45)+sin(46)+sin(47)+sin (48+49)+sin(50+51)+sin(52)+sin(53)+sin(5 4+55)+sin(56)+sin(57)+sin(58)+sin(59)+si n(60+61)+sin(62)+sin(63)+sin(64)+sin(65) +sin(66)+sin(67+68)+sin(69+70)+sin(71)+s in(72)+sin(73+74)+sin(75+76)+sin(77)+sin (78)+sin(79+80)+sin(81)+sin(82)+sin(83)+ sin(84)+sin(85+86)+sin(87)+sin(88)+sin(8 9)+sin(90)+sin(91)+sin(92+93)+sin(94+95) +sin(96)+sin(97)+sin(98+99)+sin(100)

echs · 23.09.2016, 16:22 **[ТС]**

Ребята! БОЛЬШОЕ СПАСИБО!!
Я восхищен Вашими решениями! Более того,
я просто не мог поверить своим глазам тому, что это так!
СПАСИБО !!!

Добавлено через 48 минут
Элементарный анализ результатов показывает, что в паре
идут те числа, синус которых отрицателен. Вот это неудивительно,
чем меньше отрицательных чисел, тем больше результат.
Вывод:
Если бы позволялось объединять до четырех чисел, то в сумму
под синус пошли бы все числа, синус которых отрицательный.
А числа, синус которых положительный шли бы отдельно.
Это был бы не просто максимум, а абсолютный максимум!

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

Нерешенная задача на максимум

Решение

Решение

Решение

Решение

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8

	Нерешенная задача на максимум 23.09.2016, 10:22. Показов 1258. Ответов 5 Метки нет (Все метки) Суть задачи проста. Задан ряд натуральных чисел 1, 2, 3, ... , 100 Из этого ряда должна быть построена числовая сумма с использованием функции SIN() так, чтобы сумма получилась максимальной (или близкой к ней) пример построения 1) sin1 + sin2 + sin(3+4) + sin5 +sin(6+7) + ... 2) sin(1+2) + sin3 + sin(4+5) + sin(6+7) + ... Иными словами под знаком sin может стоять одно или сумма двух чисел (порядок четко соблюдается), но заранее не определено - одно число или сумма решение 1. подумал. может сначала проверить все пары и выделить те, которые дают наибольшие значения? 2. заодно рассмотреть пары, которые дают наименьшие значения и не использовать их? 3. разбить большой ряд на несколько меньших и провести тотальный расчет на максимум 4. задача мне не подвластна, может кто что-нибудь подскажет? 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	23.09.2016, 16:22 [ТС]
	Ребята! БОЛЬШОЕ СПАСИБО!! Я восхищен Вашими решениями! Более того, я просто не мог поверить своим глазам тому, что это так! СПАСИБО !!! Добавлено через 48 минут Элементарный анализ результатов показывает, что в паре идут те числа, синус которых отрицателен. Вот это неудивительно, чем меньше отрицательных чисел, тем больше результат. Вывод: Если бы позволялось объединять до четырех чисел, то в сумму под синус пошли бы все числа, синус которых отрицательный. А числа, синус которых положительный шли бы отдельно. Это был бы не просто максимум, а абсолютный максимум! 0