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

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

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

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

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

C++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
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++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
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++    
        
    Скопировано
1
2
3
4
5
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++    
        
    Скопировано
1
2
3
4
5
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++    
        
            
                
                
                
                
            
        
    Скопировано
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
#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, я и имел в виду автора задания

Новые блоги и статьи Все статьи Все блоги /
Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .

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

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

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

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

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

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

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