Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.84/25: Рейтинг темы: голосов - 25, средняя оценка - 4.84
0 / 0 / 0
Регистрация: 05.04.2022
Сообщений: 20

Выбрать в заданном массиве два элемента ai и aj, такие что i<j, и отношение aj ai — максимально и больше 1

28.07.2022, 12:19. Показов 5432. Ответов 36
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Отношение
Дан массив a1,a2,...an. Необходимо выбрать в нём два элемента ai и aj, такие что i<j, и отношение aj ai — максимально и больше 1.

Входные данные
В первой строке задано целое число 2 ⩽n⩽ 100 000 — количество элементов в массиве.
Во второй строке заданы n целых положительных чисел ai(1 ⩽i⩽n, 1 ⩽ai⩽ 5000).

Выходные данные
Выведите два числа — индексы элементов i и j. Если ответов несколько, то выведите любой из них.
Если ответа нет, то выведите два нуля, разделённых пробелом.

помогите решить на с++ пожалуста
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
28.07.2022, 12:19
Ответы с готовыми решениями:

Выбрать в массиве два элемента ai и aj, такие что i<j, и отношение aj ai — максимально и больше 1
Дан массив a1,a2,…an. Необходимо выбрать в нём два элемента ai и aj, такие что i&lt;j, и отношение aj/ai — максимально и больше 1. ...

Необходимо выбрать в массиве два элемента ai и aj, такие что i<j, и отношение aj/ai — максимально и больше 1
Дан массив a1,a2,…an. Необходимо выбрать в нём два элемента ai и aj, такие что i&lt;j, и отношение aj/ai — максимально и больше 1. ...

В упорядоченном массиве, найти такие два элемента, произведение которых максимально
Одномерный массив.В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально). Двумерный массив....

36
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
01.08.2022, 17:35
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Valentin000000 Посмотреть сообщение
нужно ведь еще, что бы отношение было больше 1
Этого можно достичь строгим сравнением, а можно еще и в конце проверить.
Если a > b, то a / b > 1.
0
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
01.08.2022, 17:43
Valentin000000, сначала ищется максимальное возможное отношение. Перед выводом полученных результатов на экран можно сделать проверку, мол больше ли оно 1, если да, то выводим, если нет то "0 0"

Добавлено через 3 минуты
к слову отношение полученных элементов может быть <= 1 только в двух случаях:
1) если все элементы равны (==1)
2) если размер ряда = 2 и если первый элемент поделить на второй будет значение <=1
0
 Аватар для zayats80888
6353 / 3524 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
01.08.2022, 17:58
Если O(n), то на скидку можно поробовать так:
первый проход по массиву слева направо ищем минимальный элемент, но кэшируем "промежуточные" индексы в стек(вектор);
второй проход аналогичный, только справа налево и поиск максимума;
третий проход "парный" по полученным "стекам" (в любом направлении, с учетом корректности индексов, разумеется), вибирая пару с макс. отношением.
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
01.08.2022, 18:35
Цитата Сообщение от Valentin000000 Посмотреть сообщение
нужно ведь еще, что бы отношение было больше 1
Вот про эту "рукожопость" я и говорю.
Мозг атрофирован до костей. Проверку сделать не в силах. Подогнать вывод не в силах.
Зачем садится за компьютер, который умнее тебя, и мучать себя.
Как делали двоешники раньше. Ничего не делали, приходят.
- Почему не сделал домашнее задание ?
- Я не понимаю.
- Что не понимаешь?
- Все.
Ставят двойку и свободный.

Цитата Сообщение от lemegeton Посмотреть сообщение
А ещё лучше вычитание.
if (a[j] - a[imin] > a[jbest] - a[ibest])
Емм, а чем оно тут поможет ? Разница не тоже самое что отношение.
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
01.08.2022, 19:11
Цитата Сообщение от SmallEvil Посмотреть сообщение
Емм, а чем оно тут поможет ? Разница не тоже самое что отношение.
Да, действительно. Надо делить. Ну или умножать.
1
0 / 0 / 0
Регистрация: 05.04.2022
Сообщений: 20
01.08.2022, 20:12  [ТС]
решил, нужно было всего лишь добавить double в if
#i
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
28
29
30
31
32
33
nclude <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a;
int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int imin = 0;
    int ibest = 0;
    int jbest = 1;
    for (int j = 2; j < n; ++j)
    {
        if (a[j - 1] < a[imin])
            imin = j - 1;
        if (double(a[j]) / double(a[imin]) > double(a[jbest]) / double(a[ibest]))
        {
            jbest = j;
            ibest = imin;
        }
    }
    if (a[jbest] / a[ibest] > 1) {
        cout << ibest+1 << " " << jbest+1 << endl;
    }
    else {
        cout << "0 0";
    }
    
 
  
    return 0;
}
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
01.08.2022, 21:16
Цитата Сообщение от Valentin000000 Посмотреть сообщение
решил, нужно было всего лишь добавить double в if
Решил он, пфф.
Хорошо хоть читать умеет, по ссылкам которые я дал

Цитата Сообщение от Valentin000000 Посмотреть сообщение
if (a[jbest] / a[ibest] > 1)
А тут не нужно уже, и так сойдет ?
1
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
01.08.2022, 21:49
Цитата Сообщение от Valentin000000 Посмотреть сообщение
добавить double
или перейти к умножению)
1
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
01.08.2022, 21:58
Цитата Сообщение от programmer_08 Посмотреть сообщение
или перейти к умножению)
и получить переполнение...

Добавлено через 31 секунду
если бы чуток большие числа были...
0
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
01.08.2022, 22:40
Цитата Сообщение от lemegeton Посмотреть сообщение
нужно ведь еще, что бы отношение было больше 1
используем свойство логарифмов log10(a/b)=log10(a)-log10(b). отрицательное значение: a/b<1.
Равное нулю a/b=1. Больше нуля a/b>1. Индексы ищем сравнивая значения разности логарифмов a и b.
0
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
02.08.2022, 00:57
повар1, это юмор такой?
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,320
02.08.2022, 02:27
Возможно я что-то упускаю, но

1. Инициализация: текущий минимум и текущий максимум устанавливается в первый элемент последовательности

2. Просматриваем последовательность слева направо

2.1. Если мы встречаем новым максимум, то мы обновляем рекорд максимум/минимум (если он превосходит ранее найденный рекорд).

2.2. Если мы встречаем новым минимум, то сразу прекращаем просмотр и перезапускаем алгоритм: переходим на шаг 1 для оставшейся части последовательности.

Все. Ничего сортировать не нужно.

Ключевой момент алгоритма: нахождение нового минимума перезапускает поиск отношения.

Добавлено через 8 минут
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
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <utility>
#include <iostream>
 
int main() 
{
  unsigned n = 0;
  std::cin >> n;
 
  double best_ratio = 1;
  std::pair<unsigned, unsigned> best_ij = { 0, 0 };
 
  std::pair<unsigned, unsigned> ij;
  std::pair<unsigned, unsigned> ai_aj = { -1u, -1u };
 
  for (unsigned i = 0; i < n; ++i)
  {
    unsigned a = 0;
    std::cin >> a;
 
    if (a > ai_aj.second)
    {
      ij.second = i;
      ai_aj.second = a;
 
      double ratio = (double) ai_aj.second / ai_aj.first;
      if (ratio > best_ratio)
      {
        best_ratio = ratio;
        best_ij = ij;
      }
    }
    else if (a < ai_aj.first)
    {
      ij = { i, i };
      ai_aj = { a, a };
    }
  }
 
  std::cout << best_ij.first << " " << best_ij.second << std::endl;
}
Добавлено через 5 минут
А, вижу, уже решили... Не ясно только, зачем вектор понадобился.
0
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
02.08.2022, 09:01
Цитата Сообщение от programmer_08 Посмотреть сообщение
повар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
#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    int m[4]={3, 1, 7, 2};
    int index_i,index_j;
    double max=0;
 
    for(int i=0;i<3;i++)
     for(int j=i+1;j<4;j++){
        double d=log10(m[j]*1.)-log10(m[i]*1.);
        //cout<<i<<"  "<<j<<"  " <<d<<"\n";
        if(d>0)
          if( max-d<0){
                index_i=i;
                index_j=j;
                max=d;
         }
      }
     if(max>0) cout<<index_i<<"  "<<index_j;
     if(max==0) cout<<"0 0";
     return 0;
}
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
02.08.2022, 13:26
Цитата Сообщение от повар1 Посмотреть сообщение
double d=log10(m[j]*1.)-log10(m[i]*1.);
Умножение аргументов функции log10 на 1. с целью преобразования в double лишняя операция, не представляющая никакого смысла. Данная функция перегружена и принимает любой целочисленный тип, при этом функция будет возвращать double.
0
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
02.08.2022, 14:07
Цитата Сообщение от Royal_X Посмотреть сообщение
лишняя операция,
не все так просто
Миниатюры
Выбрать в заданном массиве два элемента ai и aj, такие что i<j, и отношение aj ai — максимально и больше 1  
0
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
02.08.2022, 14:16
Цитата Сообщение от повар1 Посмотреть сообщение
не все так просто
у меня на g++ с включенными -Wall -Wextra -Wpedantic такого предупреждения нет. Не знаю, как вы там у себя настраивали. Считаю, что у меня настроено и так максимально требовательно к стандарту.
0
848 / 651 / 323
Регистрация: 24.02.2017
Сообщений: 2,297
02.08.2022, 14:20
Цитата Сообщение от Royal_X Посмотреть сообщение
у меня на g++
у меня другой

Добавлено через 1 минуту
Это ловля блох. Главное показать как можно выполнить задание
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
02.08.2022, 14:20

В упорядоченном массиве, найти такие два элемента, произведение которых максимально
В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально).

В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально)
В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально) Решить: Одномерным, двумерным,...

В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально)
В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально). Другими словами, необходимо просто...

В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально)
В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально) Решить: Одномерным, двумерным,...

В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально)
В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально). Составить обычную программу и через...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
37
Ответ Создать тему
Новые блоги и статьи
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru