Оптимизация алгоритма нахождения максимального элемента

@vterkin · Регистрация: 23.06.2019

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

Дорогие форумчане, второй день ломаю голову над лабораторной, если у кого есть готовые варианты или хотя бы предполагает в какую сторону двигаться, подскажите. Буду при много благодарен.
Задание:
В соответствии с вариантом задания, реализовать алгоритмы так, чтобы их временная сложность соответствовала требуемой в постановке задачи или были проведены иные оптимизации (см. табл. 2). Решения представить в виде работающих программ на C++

1. Поиск номера максимального элемента в массиве a[n]

C++

int max=a[0], imax=0;
for (int i=1; i<n; i++) 
   if (a[i]>max) {
      max = a[i]; imax=i; 
 }

реализовать алгоритм без применения 2 дополнит. переменных)

2. Получение четырёхзначного натурального числа из пары двузначных

C++

int a=12,b=34;
char buf[4];
itoa(a,buf,10);
itoa(b, &buf[2], 10);
cout << buf;

устранить использование дополнительного строкового буфера

@FFPowerMan · 03.05.2020, 18:59

2

C++

1
2
3

int a=12, b=34, buf;
buf = 12*100 + b;
cout << buf;

@vterkin · 03.05.2020, 19:00 **[ТС]**

Тоже приходил к этому решению, наверное на нём и остановлюсь. Спасибо

@FFPowerMan · 03.05.2020, 19:02

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

реализовать алгоритм без применения 2 дополнит. переменных)

- это значит...
без применения двух дополнительных переменных?
без применения второй дополнительной переменной?

@vterkin · 03.05.2020, 19:04 **[ТС]**

без применения двух дополнительных переменных

@FFPowerMan · 03.05.2020, 19:09

1 оставить можно?

Добавлено через 32 секунды

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

C++

1	int max=a[0], imax=0;

- т.е. из вот этих двух, одну убрать, а одну оставить?

@vterkin · 03.05.2020, 19:11 **[ТС]**

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

1 оставить можно?

Добавлено через 32 секунды
- т.е. из вот этих двух, одну убрать, а одну оставить?

Нет, нужно обе убрать

@FFPowerMan · 03.05.2020, 19:13

1) просто sort применить и взять последний элемент.

Добавлено через 1 минуту
Какие Ваши варианты?

@vterkin · 03.05.2020, 19:13 **[ТС]**

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

1) просто sort применить и взять последний элемент.

Добавлено через 1 минуту
Какие Ваши варианты?

Это увеличит время работы алгоритма, соответственно возрастёт трудоемкость. А здесь задача оптимизировать данный алгоритм.

@Yetty · 03.05.2020, 19:14

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

1. Поиск номера максимального элемента в массиве a[n]

C++

imax=0;
for (int i=1; i<n; i++)
if (a[i]>a[imax]) imax=i;
 
cout << "number=" << imax+1 << "\n";

@vterkin · 03.05.2020, 19:16 **[ТС]**

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

1) просто sort применить и взять последний элемент.

Добавлено через 1 минуту
Какие Ваши варианты?

На данный момент вариантов пока не имею(

Таких задач 10, если интересно про них тут написано http://blog.kislenko.net/show.php?id=2000

Добавлено через 1 минуту

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

C++

imax=0;
for (int i=1; i<n; i++)
if (a[i]>a[imax]) imax=i;
 
cout << "number=" << imax+1 << "\n";

реализовать алгоритм без применения 2-х дополнительных переменных

@Yetty · 03.05.2020, 19:28

vterkin, в варианте который сбросил нет

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

2-х дополнительных переменных

при желании можно и imax убрать учитывая что number_max=imax+1

C++

1
2
3

    number_max=1;
    for (int i=1; i<n; i++)
    if (a[i]>a[number_max-1]) number_max=i+1;

@vterkin · 03.05.2020, 19:40 **[ТС]**

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

vterkin, в варианте который сбросил нет

при желании можно и imax убрать учитывая что number_max=imax+1

C++

1
2
3

    number_max=1;
    for (int i=1; i<n; i++)
    if (a[i]>a[number_max-1]) number_max=i+1;

Благодарю за ответ, но суть немного другая, вообще не использую дополнительных переменных (вообще никаких, number_max и imax тоже) найти номер максимального элемента массива.

@Yetty · 03.05.2020, 19:53

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

но суть немного другая

неправильно понимаете. в Вашем первоначальном коде: max и imax это две дополнительные переменные. в ответ выводится номер: объявляется переменная number_max и ей присваивается значение второй дополнительной переменной +1:

C++

1
2
3

int number_max;
number_max=imax+1; 
cout << number_max << "\n"; // это и будет ответ

в том варианте что я Вам сбросил в сообщении №12 вообще нет дополнительных переменных (только одна основная)

@FFPowerMan · 03.05.2020, 20:36

1

C++

#include <iostream>
using namespace std;
#define n 5
 
int main()
{
    int i, a[n];
    
    a[0] = 0; //Debug
    a[1] = 5;
    a[2] = 1;
    a[3] = 2;
    a[4] = 0;
        
    for(i = 1; i < n; i++)
    {
        if(a[i] > a[i >> 16])
        {
            i &= 0xFFFF;
            i |= (i&0xFFFF) << 16;
        }
            
    } 
    cout << "number = " << (i >> 16) << "\n";
    
    return 0;
}

@Kuzia domovenok · 04.05.2020, 00:05

по-моему, на своих оптимизациях автор совсем повернулся - оптимизирует даже количество строчек, похоже на то

C++

1	for (int i = 0; i < n; i++) if (a[i] > a[imax]) imax = i;

@vterkin · 04.05.2020, 10:47 **[ТС]**

Сообщение от Kuzia domovenok

по-моему, на своих оптимизациях автор совсем повернулся - оптимизирует даже количество строчек, похоже на то

C++

1	for (int i = 0; i < n; i++) if (a[i] > a[imax]) imax = i;

Это не в авторе дело, это задание лабораторной работы по теме Оптимизация временной сложности алгоритма. А мне её нужно решить, вот и спросил совет.

@Kuzia domovenok · 04.05.2020, 11:17

vterkin, я и имел в виду автора задания

@vterkin 0 / 0 / 0 Регистрация: 23.06.2019 Сообщений: 8
	03.05.2020, 19:00 [ТС]	3
	Тоже приходил к этому решению, наверное на нём и остановлюсь. Спасибо 0

@FFPowerMan 2128 / 1211 / 503 Регистрация: 11.10.2018 Сообщений: 6,107
	03.05.2020, 19:02	4
	Сообщение от vterkin реализовать алгоритм без применения 2 дополнит. переменных) - это значит... без применения двух дополнительных переменных? без применения второй дополнительной переменной? 0

@vterkin 0 / 0 / 0 Регистрация: 23.06.2019 Сообщений: 8
	03.05.2020, 19:04 [ТС]	5
	без применения двух дополнительных переменных 0

@vterkin 0 / 0 / 0 Регистрация: 23.06.2019 Сообщений: 8
	03.05.2020, 19:11 [ТС]	7
	Сообщение от FFPowerMan 1 оставить можно? Добавлено через 32 секунды - т.е. из вот этих двух, одну убрать, а одну оставить? Нет, нужно обе убрать 0

@FFPowerMan 2128 / 1211 / 503 Регистрация: 11.10.2018 Сообщений: 6,107
	03.05.2020, 19:13	8
	1) просто sort применить и взять последний элемент. Добавлено через 1 минуту Какие Ваши варианты? 0

@vterkin 0 / 0 / 0 Регистрация: 23.06.2019 Сообщений: 8
	03.05.2020, 19:13 [ТС]	9
	Сообщение от FFPowerMan 1) просто sort применить и взять последний элемент. Добавлено через 1 минуту Какие Ваши варианты? Это увеличит время работы алгоритма, соответственно возрастёт трудоемкость. А здесь задача оптимизировать данный алгоритм. 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	04.05.2020, 11:17	18
	vterkin, я и имел в виду автора задания 0