Задача на перебор Turbo Pascal

[nobody_nohead]

Сообщение от Plague

Ограничения на входные данные какие?

Только одно: 4 <= n <= 1000

[Plague]

можно вставлять только +* или *+ так получается?

[nobody_nohead]

Сообщение от Plague

можно вставлять только +* или *+ так получается?

Между числами нужно вставить 2 знака умножения и все остальное - знаки сложения. Если вы это имели ввиду. Два знака умножить могут идти друг после друга, если в итоге результат будет наибольшим. Т.е например 10*2*3+5+4 имеет место быть, т.к в итоге получим 69.

[Serge_Bliznykov]

задачу с перебором я решал тут - Арифметические действия с цифрами числа

для больших N (а N=1000 - это достаточно большое количество) полный перебор будет достаточно долгим,
но, не в данном случае, в связи с тем, что нужно только позиции умножения перебирать, то это всего 999*998 вариантов, то это вполне приемлемо!


есть резон и в подходе ViktorR - найти индексы 4-х максимальных значений
и проверить (с учётом граничных значений, конечно!!!) что больше
m[max1]*m[max2] ..... + + m[max3]*m[max4]
или
m[max1-1]*m[max1]*m[max2] + + +
или
m[max1]*m[max1]*m[max2+1] + +
или
m[max3-1]*m[max2]*m[max4] + +
или
m[max3]*m[max4]*m[max4+1] + +

это всего 5 вариантов.

какой Вам способ нравится больше?

но, в любом случае - задачка не очень сложная.

я бы написал функцию Calculate(MyArray, indexMultyply1, indexMultyply2) : longint,
которая возвращает результат, если знаки умножения стоят в позициях indexMultyply1 и indexMultyply2 соответственно.
Надеюсь, это не затруднит?

Сообщение от nobody_nohead

Т.е например 10*2*3+5+4 имеет место быть, т.к в итоге получим 69.

а если поставить знаки так: 10+2+3*5*4
получается 72


--

[Plague]

Умножение двух отрицательных чисел будет положительно.

[nobody_nohead]

Сообщение от Serge_Bliznykov

а если поставить знаки так: 10+2+3*5*4
получается 72


--

Невнимательность))
После написания функции рациональным я так думаю будет сделать так:

result:= -1;
for i to n do
    for j to (n-1) do
        if Calculate(MyArray, i, j) > result then
            result:= Calcualte(MyArray, i, j);

Если что-то не так, поправьте, пожалуйста.

[Serge_Bliznykov]

Сообщение от Plague

Умножение двух отрицательных чисел будет положительно.

да, точно.
задача близка к "Дано N-целых чисел.Требуется выбрать из них три таких числа, произведение которых максимально." (на форуме - тыц, тыц, тыц)

Сообщение от nobody_nohead

После написания функции рациональным я так думаю будет сделать так:

не совсем.
первое. результат может быть отрицательным.
ну, например, расставьте знаки среди чисел: -17 1 1 1 -7
поэтому брать result -1 нельзя. надо maxResult := Calculate(MyArray, 1, 2);

ну дальше по мелочи - вычислять Calculate надо в цикле один раз (сохранять во временную переменную),
нужно сохранять не только максимальное значение, но и позиции знака умножения, при которых этот максимум был получен,
позиций для знаков на одну меньше, чем чисел, поэтому
первый цикл по позициям крутить от for i:=1 до n-2 , внутренний цикл крутить от for j:=i+1 to n-1

но в целом, да, согласен, Вы правильно поняли мою мысль.

[nobody_nohead]

Сообщение от Serge_Bliznykov

Большое спасибо, теперь стало ясно.

[Serge_Bliznykov]

пожалуйста.

функцию самостоятельно Calculate напишете? сюда готовый код выложите?
имхо, неплохо, если в теме останется готовое решение, которое может пригодиться кому-то...

[nobody_nohead]

Сообщение от Serge_Bliznykov

пожалуйста.

функцию самостоятельно Calculate напишете? сюда готовый код выложите?
имхо, неплохо, если в теме останется готовое решение, которое может пригодиться кому-то...

Да, сейчас займусь реализацией. Если получится - конечно выложу.