Найти максимальное частное двух чисел массива

@OlegRuno · Регистрация: 28.05.2012

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

Среди набора целых чисел необходимо выбрать два таких числа, чтобы их частное было максимальным.

Формат входного файла:

В первой строке входного файла input.txt записано число - количество чисел в наборе. Во второй строке записаны сами числа через один пробел. Количество чисел в наборе не превосходит 100000. Числа в наборе нумеруются с 1. Значения всех чисел целые и по модулю не превосходят 2147483647. Гарантируется, что для предложенного набора чисел результат всегда существует. Каждая строка заканчивается переходом на новую строку.
Формат выходного файла:

В первую строку выходного файла output.txt необходимо вывести без пробелов номер числа в наборе, которое выбрано числителем дроби.
Во вторую строку - без пробелов номер числа в наборе, которое выбрано знаменателем дроби.

Пример ввода:

4
1 -2 8 3
Пример вывода:

3
1

Вот мой код, однако сложность алгоритма Q(n^2), необходимо Q(n).(Проблема в 2х вложенных циклах for)

Java
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
41
package laba1;
 
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
 
public class zadanie32 {
    
    public static void main(String[] args){
        int n=0;
        int [] mass = new int [10000000];
        try{
            Scanner sc = new Scanner(new File("input.txt"));
            while(sc.hasNext()){
            n=sc.nextInt();
            for(int i=0; i<n; i++)
              {mass[i]=sc.nextInt();}           
            }
            sc.close();
            }catch(FileNotFoundException e){}
        
        int imax=0, imin=0;
        float max=0;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if((i!=j)&(mass[j]!=0)){
                    if((((float)mass[i]/mass[j]>=max))){
                        max=(float)(mass[i]/mass[j]);
                        imax=i; imin=j;
                    }
        try{
            PrintWriter pw = new PrintWriter(new File("output.txt"));
            pw.println(imax+1);
            pw.println(imin+1);
            pw.close();}catch(Exception e){}
            
        }
    }
 
}

@turbanoff · 11.09.2012, 10:28

Предлагаю вам найти, сначала четыре таких числа:
1. минимальное по модулю отрицательное число - minNegative
2. максимальное по модулю отрицательное число - maxNegative
3. минимальное по модулю положителное число - minPositive
4. максимальное по модулю положительное число - maxPositive

После чего сравнить следующие пары чисел
a. maxNegative / minNegative
b. maxPositive / minPositive

Я уверен, что нужная вам пара будет одной из приведенных.
Поиск минимальных/максимальных значений можно осуществить за один проход O(n).

PS. И не забудьте обработать крайние случаи: массив пуст, в массиве нет отрицательных элементов, в массиве нет положительных элементов, одно из чисел = 0.

@OlegRuno · 11.09.2012, 12:04 **[ТС]**

допустим у нас условие 0 3
мы же ищем макс и мин, и получается он захочет делить 3 на 0, нужен какой то общий вариант

@turbanoff · 11.09.2012, 12:39

Перечитайте внимательней мое сообщение - я указал крайние случаи, которые необходимо обработать особо.

@Skipy · 11.09.2012, 12:40

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

допустим у нас условие 0 3
мы же ищем макс и мин, и получается он захочет делить 3 на 0, нужен какой то общий вариант

максимальное - бесконечность (3/0), минимальное - ноль (0/3).

@turbanoff · 12.09.2012, 11:46

Вот, получилось довольно длинно.

сalcMaxQuotient

Java
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
    public static void calcMaxQuotient(int[] arr) {
        if (arr == null || arr.length < 2) {
            System.out.println("В массиве должно быть как минимум два числа");
            return;
        }
 
        boolean allZeros = true;
        boolean zeroFind = false;
        int zeroIndex = 0;
 
        boolean minPositiveFind = false;
        boolean maxPositiveFind = false;
        boolean minNegativeFind = false;
        boolean maxNegativeFind = false;
 
        int minPositive = 0;
        int maxPositive = 0;
        int minNegative = 0;
        int maxNegative = 0;
 
        int minPositiveIndex = 0;
        int maxPositiveIndex = 0;
        int minNegativeIndex = 0;
        int maxNegativeIndex = 0;
 
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) {
                if (!minPositiveFind || (minPositive > arr[i])) {
                    minPositiveFind = true;
                    minPositive = arr[i];
                    minPositiveIndex = i;
                }
                if (!maxPositiveFind || (maxPositive <= arr[i])) {
                    maxPositiveFind = true;
                    maxPositive = arr[i];
                    maxPositiveIndex = i;
                }
                allZeros = false;
            } else if (arr[i] < 0) {
                if (!minNegativeFind || (minNegative < arr[i])) {
                    minNegativeFind = true;
                    minNegative = arr[i];
                    minNegativeIndex = i;
                }
                if (!maxNegativeFind || (maxNegative >= arr[i])) {
                    maxNegativeFind = true;
                    maxNegative = arr[i];
                    maxNegativeIndex = i;
                }
                allZeros = false;
            } else {
                zeroFind = true;
                zeroIndex = i;
            }
        }
 
        if (allZeros) {
            System.out.println("В массиве все числа равны 0");
            return;
        }
 
        System.out.println("maxPositive " + maxPositiveFind + ", " + maxPositive + " = arr["  + maxPositiveIndex + "]");
        System.out.println("minPositive " + minPositiveFind + ", " + minPositive + " = arr["  + minPositiveIndex + "]");
        System.out.println("maxNegative " + maxNegativeFind + ", " + maxNegative + " = arr["  + maxNegativeIndex + "]");
        System.out.println("minNegative " + minNegativeFind + ", " + minNegative + " = arr["  + minNegativeIndex + "]");
 
        double resultFromPositive = Double.NEGATIVE_INFINITY;
        if (minPositiveFind && maxPositiveFind && (minPositiveIndex != maxPositiveIndex))
            resultFromPositive = ((double)maxPositive) / minPositive;
 
        double resultFromNegative = Double.NEGATIVE_INFINITY;
        if (minNegativeFind && maxNegativeFind && (minNegativeIndex != maxNegativeIndex))
            resultFromNegative = ((double)maxNegative) / minNegative;
 
        double zeroResult = Double.NEGATIVE_INFINITY;
        if (zeroFind)
            zeroResult = 0;
 
        System.out.println();
        System.out.println("resultFromPositive = " + resultFromPositive);
        System.out.println("resultFromNegative = " + resultFromNegative);
        System.out.println("zeroResult = " + zeroResult);
 
        System.out.println();
        if (arr.length == 2 && minPositiveFind && minNegativeFind) //два разнознаковых числа
            if (Math.abs(arr[0]) > Math.abs(arr[1]))
                System.out.println("arr[1] / arr[0] = " + ((double) arr[1]) / arr[0]);
            else
                System.out.println("arr[0] / arr[1] = " + ((double) arr[0]) / arr[1]);
        else if (resultFromPositive >= resultFromNegative && resultFromPositive >= zeroResult) //положительные числа
            System.out.println("arr[" + maxPositiveIndex +"] / arr[" + minPositiveIndex + "] = " + resultFromPositive);
        else if (resultFromNegative >= resultFromPositive && resultFromNegative >= zeroResult) //отрицательные
            System.out.println("arr[" + maxNegativeIndex +"] / arr[" + minNegativeIndex + "] = " + resultFromNegative);
        else { //победил ноль
            int nonZeroIndex = minPositiveFind ? minPositiveIndex : minNegativeIndex;
            System.out.println("arr[" + zeroIndex +"] / arr[" + nonZeroIndex + "] = 0");
        }
    }

Проверка - http://ideone.com/b7kEk

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@turbanoff 4094 / 3828 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 12
	11.09.2012, 10:28
	Предлагаю вам найти, сначала четыре таких числа: 1. минимальное по модулю отрицательное число - minNegative 2. максимальное по модулю отрицательное число - maxNegative 3. минимальное по модулю положителное число - minPositive 4. максимальное по модулю положительное число - maxPositive После чего сравнить следующие пары чисел a. maxNegative / minNegative b. maxPositive / minPositive Я уверен, что нужная вам пара будет одной из приведенных. Поиск минимальных/максимальных значений можно осуществить за один проход O(n). PS. И не забудьте обработать крайние случаи: массив пуст, в массиве нет отрицательных элементов, в массиве нет положительных элементов, одно из чисел = 0. 0

@OlegRuno 2 / 2 / 0 Регистрация: 28.05.2012 Сообщений: 38
	11.09.2012, 12:04 [ТС]
	допустим у нас условие 0 3 мы же ищем макс и мин, и получается он захочет делить 3 на 0, нужен какой то общий вариант 0

@turbanoff 4094 / 3828 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 12
	11.09.2012, 12:39
	Перечитайте внимательней мое сообщение - я указал крайние случаи, которые необходимо обработать особо. 0