Форум программистов, компьютерный форум, киберфорум
QBasic
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
196 / 8 / 3
Регистрация: 30.04.2016
Сообщений: 733
1

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

14.10.2018, 11:06. Показов 947. Ответов 16
Метки нет (Все метки)

Дан массив из 10 чисел. Найти сумму трёх
максимальных из них.
Вариант с тремя числами подряд:
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
CLS
DIM A(10)
DATA 12, 16, 21, 25, 30, 34, 36, 42, 10, 15
   FOR i = 1 TO 10
     READ A(i)
     PRINT A(i);
    NEXT i
 FOR i = 6 TO 8
   S = S ++ A(i)
    LOCATE 2, 1
   NEXT i
PRINT “ Сумма 3-х  максимальных чисел: “;  S
На выходе имеем:
QBasic/QuickBASIC
1
2
  12   16   21   25   30   34   36   42   10   15
Сумма трёх максимальных чисел:   112
Это решение, конечно, примитивное. А как
действительно найти сумму трёх максимальных
чисел в случайном массиве.
0

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

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.10.2018, 11:06
Ответы с готовыми решениями:

Найти сумму трёх максимальных из этих чисел
Дан массив из 10 чисел. Найти сумму трёх максимальных из этих чисел. Во как-то так:...

Найти сумму трёх максимальных из этих чисел
Дан массив из 10 чисел. Найти сумму трёх максимальных из этих чисел. CLS DIM A(10) FOR i = 1 TO...

Дан массив из 10 чисел. Найти сумму трёх максимальных из этих чисел
. Дан массив из 10 чисел. Найти сумму трёх максимальных из этих чисел. CLS DIM A(10) FOR i = 1...

В случайном массиве 100 реальных чисел от 0 до 1 найти минимум и максимум суммы трех элементов.
Помогите решить задачку: В случайном массиве 100 реальных чисел от 0 до 1 найти минимум и...

16
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5754 / 3458 / 2449
Регистрация: 22.11.2013
Сообщений: 9,714
Записей в блоге: 1
14.10.2018, 11:39 2
Например, так:
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
CONST n = 10, k = 3
DIM a(n), m(k + 1)
DATA 12, 16, 21, 25, 30, 34, 36, 42, 10, 15
FOR i = 1 TO n
  READ a(i)
  PRINT a(i);
NEXT
PRINT
FOR i = 1 TO k
  m(i) = a(i)
  FOR j = i - 1 TO 1 STEP -1
    IF m(j + 1) > m(j) THEN SWAP m(j + 1), m(j) ELSE EXIT FOR
NEXT j, i
FOR i = k + 1 TO n
  m(k + 1) = a(i)
  FOR j = k TO 1 STEP -1
    IF m(j + 1) > m(j) THEN SWAP m(j + 1), m(j) ELSE EXIT FOR
NEXT j, i
FOR i = 1 TO k
  s = s + m(i)
NEXT
PRINT "Сумма 3-х максимальных: "; s
Или просто сортируем и берем 3 первых:
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
CONST n = 10, k = 3
DIM a(n)
DATA 12, 16, 21, 25, 30, 34, 36, 42, 10, 15
FOR i = 1 TO n
  READ a(i)
  PRINT a(i);
NEXT
PRINT
t = n
DO
  i = t: t = 1
  FOR j = 1 TO i - 1
    IF a(j + 1) > a(j) THEN
      SWAP a(j + 1), a(j)
      t = j
    END IF
  NEXT
LOOP UNTIL t = 1
FOR i = 1 TO k
  s = s + a(i)
NEXT
PRINT "Сумма 3-х максимальных: "; s
0
615 / 411 / 22
Регистрация: 05.07.2018
Сообщений: 1,631
Записей в блоге: 7
14.10.2018, 15:37 3
Алгоритм
1. находим максимальное число, которое и идет в сумму.
2. в массиве это число заменяется на число, которое меньше всех чисел массива
3. повторить всего три раза
4. вывести результат на экран

QBasic/QuickBASIC
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
CLS
DIM A(10)
CONST X = -100000
DATA 12, 16, 21, 25, 30, 34, 36, 42, 10, 15
 
FOR i = 1 TO 10
   READ A(i)
   PRINT A(i);
NEXT
 
PRINT
max = X
 
FOR k = 1 TO 3
   FOR i = 1 TO 10
      IF max < A(i) THEN
         max = A(i)
         imax = i
      END IF
   NEXT i
 
   SUM = SUM + max
   max = X
   A(imax) = X
NEXT k
PRINT "SUM ="; SUM
END
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5754 / 3458 / 2449
Регистрация: 22.11.2013
Сообщений: 9,714
Записей в блоге: 1
14.10.2018, 19:19 4
А еще можно сделать 3 прохода сортировки пузырьком:
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
CONST n = 10, k = 3
DIM a(n)
DATA 12, 16, 21, 25, 30, 34, 36, 42, 10, 15
FOR i = 1 TO n
  READ a(i)
  PRINT a(i);
NEXT
PRINT
t = n
DO
  i = t: t = 1
  FOR j = 1 TO i - 1
    IF a(j) > a(j + 1) THEN  ' "тяжелые" "тонут" за 1 проход
      SWAP a(j + 1), a(j)
      t = j
    END IF
  NEXT
LOOP UNTIL t <= n - k
FOR i = n - k + 1 TO n
  s = s + a(i)
NEXT
PRINT "Сумма 3-х максимальных: "; s
0
6136 / 903 / 305
Регистрация: 25.02.2011
Сообщений: 1,288
Записей в блоге: 1
15.10.2018, 12:06 5
как бы тоже самое, что и в предыдущем сообщении, но немного другая сортировка:
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
CONST n = 10, k = 3
DIM a(1 TO n) AS LONG
DIM i AS LONG, j AS LONG, s AS LONG
DATA 12, 16, 21, 25, 30, 34, 36, 42, 10, 15
FOR i = 1 TO n
  READ a(i)
  PRINT a(i);
NEXT i
PRINT
FOR i = 1 TO k
  FOR j = i + 1 TO n
    IF a(i) < a(j) THEN SWAP a(i), a(j)
  NEXT j
  s = s + a(i)
NEXT i
PRINT "Sum max 1-3 ="; s
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5754 / 3458 / 2449
Регистрация: 22.11.2013
Сообщений: 9,714
Записей в блоге: 1
15.10.2018, 13:12 6
Цитата Сообщение от m-ch Посмотреть сообщение
как бы тоже самое
то, да не то...
Кроме типа сортировки разница еще в "не более трех проходов" против "всегда три прохода".
Но для 10 элементов разница действительно несущественна.
0
6136 / 903 / 305
Регистрация: 25.02.2011
Сообщений: 1,288
Записей в блоге: 1
15.10.2018, 15:03 7
Цитата Сообщение от bormant Посмотреть сообщение
Кроме типа сортировки разница еще в "не более трех проходов" против "всегда три прохода".
в "пузырьковой сортировке" количество операций Swap может быть существенно больше
Это хорошо видно, если взять массив не на 10 элементов, а например на 1000
Сделал три различных варианта на случайных данных, с указанием количества операций обмена и сравнения
QBasic/QuickBASIC
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
CONST n = 1000, k = 100
DIM a(1 TO n) AS LONG, b(1 TO n) AS LONG
DIM i AS LONG, j AS LONG, x AS LONG, l AS LONG, r AS LONG, s AS LONG, cnt AS LONG, cnt2 AS LONG
 
RANDOMIZE 123
FOR i = 1 TO n
        b(i) = INT(RND * 1000 + 1)
NEXT i
 
'test1
FOR i = 1 TO n
    a(i) = b(i)
NEXT i
s = 0
cnt = 0
cnt2 = 0
l = 1
r = n
WHILE l < r - 1
    x = a(k)
    i = l
    j = r
    DO
        WHILE a(i) > x
            i = i + 1
            cnt2 = cnt2 + 1
        WEND
        WHILE a(j) < x
            j = j - 1
            cnt2 = cnt2 + 1
        WEND
        IF i <= j THEN
            cnt = cnt + 1
            SWAP a(i), a(j)
            i = i + 1
            j = j - 1
        END IF
    LOOP UNTIL i > j
    IF j < k THEN l = i
    IF i > k THEN r = j
WEND
FOR i = 1 TO k
    s = s + a(i)
NEXT i
PRINT "Sum ="; s, "Swap ="; cnt, "Compare ="; cnt2
 
'test2
FOR i = 1 TO n
    a(i) = b(i)
NEXT i
s = 0
cnt = 0
cnt2 = 0
FOR i = 1 TO k
    'FOR j = i + 1 TO n
    FOR j = n TO i + 1 STEP -1
        cnt2 = cnt2 + 1
        IF a(i) < a(j) THEN
            cnt = cnt + 1
            SWAP a(i), a(j)
        END IF
    NEXT j
    s = s + a(i)
NEXT i
PRINT "Sum ="; s, "Swap ="; cnt, "Compare ="; cnt2
 
'test3
FOR i = 1 TO n
    a(i) = b(i)
NEXT i
s = 0
cnt = 0
cnt2 = 0
t = n
DO
    i = t: t = 1
    FOR j = 1 TO i - 1
        cnt2 = cnt2 + 1
        IF a(j) > a(j + 1) THEN
            cnt = cnt + 1
            SWAP a(j + 1), a(j)
            t = j
        END IF
    NEXT
LOOP UNTIL t <= n - k
FOR i = n - k + 1 TO n
  s = s + a(i)
NEXT
PRINT "Sum ="; s, "Swap ="; cnt, "Compare ="; cnt2
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5754 / 3458 / 2449
Регистрация: 22.11.2013
Сообщений: 9,714
Записей в блоге: 1
15.10.2018, 16:18 8
Цитата Сообщение от m-ch Посмотреть сообщение
в "пузырьковой сортировке" количество операций Swap может быть существенно больше
... например возьмем упорядоченный по возрастанию массив из 1000 элементов :-) Пузырёк -- один проход и ни одной замены, выбор -- 3 прохода и примерно 1996 замен.
Признавайтесь, RANDOMIZE 123 специально искали? ;-)

Но в целом ожидаемо, квадрат супротив логарифма в среднем случае не сыграет...

Можно было еще первый из #2 в сравнение добавить, слегка модифицировав:
QBasic/QuickBASIC
14
15
16
17
18
19
20
21
22
FOR i = k + 1 TO n
  IF m(k) < a(i) THEN
    m(k) = a(i): j = k - 1
    WHILE j > 0 AND m(j + 1) > m(j)
      SWAP m(j + 1), m(j)
      j = i - 1
    WEND
  END IF
NEXT
Но принципиальной разницы с выбором все-равно быть не должно.
0
6136 / 903 / 305
Регистрация: 25.02.2011
Сообщений: 1,288
Записей в блоге: 1
15.10.2018, 17:11 9
Цитата Сообщение от bormant Посмотреть сообщение
Признавайтесь, RANDOMIZE 123 специально искали? ;-)
нет, поставил "123" для воспроизводимости расчетов, поставьте Randomize Timer, результат на случайных данных будет тем же.
Можно использовать простые варианты сортировок, такие как "пузырек", "выбором", "вставками" и др.
Для малых значений n это не принципиально, даже может быть показан результат лучше, чем в "продвинутых" алгоритмах.
Здесь плюсы и минусы такие же как и в самих алгоритмах сортировок.

В своем коде из #7 в "test1" использовал элемент алгоритма быстрой сортировки, который показывает практически независимый результат для любого k, на случайных данных. Так для малых k данный алгоритм будет уступать примитивным сортировкам

Добавлено через 19 минут
Цитата Сообщение от bormant Посмотреть сообщение
... например возьмем упорядоченный по возрастанию массив из 1000 элементов :-)
Возьмите упорядоченный по возрастанию (по неубыванию) массив из 1000 элементов и поменяйте в нем первый и последний элемент (или два любых элемента), какой получится результат?

Добавлено через 7 минут
И для сопоставимости результатов, в своем коде я использовал сортировку по убыванию и подсчет суммы первых k элементов, у Вас сортировка по возрастанию и сумма последних k элементов, это нужно учесть при прогонке пограничных условий по сортированным данным (или почти отсортированным).
0
Платежеспособный зверь
8750 / 4175 / 1606
Регистрация: 28.10.2009
Сообщений: 11,317
17.10.2018, 13:12 10
Написано много, разных программ куча, ни одной оптимальной.
Господа! Это классическая школьная задача на поиск оптимального решения.
Она решается ЗА 1 ПРОХОД!!!
Вот как-то так:
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
INPUT n
RANDOMIZE TIMER
DIM a(n)
FOR i = 1 TO n
a(i) = INT(RND * 1000)
PRINT a(i);
NEXT
PRINT
max1 = -1E+38
max2 = -1E+38
max3 = -1E+38
FOR i = 1 TO n
IF a(i) >= max1 THEN
max3 = max2:
max2 = max1:
max1 = a(i)
ELSEIF a(i) >= max2 THEN
max3 = max2:
max2 = a(i)
ELSEIF a(i) >= max3 THEN max3 = a(i)
END IF
NEXT
PRINT max1+max2+ max3
0
6136 / 903 / 305
Регистрация: 25.02.2011
Сообщений: 1,288
Записей в блоге: 1
17.10.2018, 14:55 11
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Написано много, разных программ куча, ни одной оптимальной.
Спорный вопрос, что является оптимальным решением?
Количество кода и скорость его написания и ловля возможных багов, быстрота работы программы, масштабируемость кода для решения подобной задачи но с другими исходными данными?

По приведенному Вами "оптимальному" решению
1. Количество кода я не буду рассматривать так как для данной микроскопической задачи его не должно быть много, можно уложится в 2-3 десятка строк
2. Быстрота работы
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Она решается ЗА 1 ПРОХОД!!!
в данном случае 1 проход весьма условный, т.к. в этом проходе Вы делаете по 3 сравнения, что сопоставимо с двумя вложенными циклами n*3 и фактически реализована сортировка вставками, но не через дополнительный массив, а через доп. переменные. При этом количество сравнений и обменов переменных аналогична.
3. Масштабируемость: Сколько нужно внести изменений в код, если нужна сумма не наибольших 3х, а наибольших 5ти или 100 или 200?
и что если все исходные данные будут меньше заданных Вами значения -1E+38?
0
Платежеспособный зверь
8750 / 4175 / 1606
Регистрация: 28.10.2009
Сообщений: 11,317
17.10.2018, 16:40 12
Не надо ничего выдумывать и пришивать к программе того, чего нет. Вы как-то забываете, что в ваших многопроходных программах тоже куча сравнений, но их вы почему-то не учитываете. Я сказал только то, что сказал: однопроходный алгоритм в отличие от ваших многопроходных. Вы можете сколько угодно выдумывать соответствие сравнений с вложенными циклами, но при оценке программы, скажем, в ЕГЭ, ни одна из ваших программ не будет признана оптимальной. Да и подумайте логически, если всё так просто, зачем огород городить? Просто отсортировали массив и взяли первые три элемента. Но задача эта входит в число заданий ПОВЫШЕННОЙ СЛОЖНОСТИ. Ничего Вам это не говорит? если мои слова для вас не убедительный аргумент, предложите Ваши рассуждения профессору Полякову, одному из лучших специалистов в стране, и потом скажете, куда он Вас с ними послал.

PS 1E+38 - стандартное задание минимального числа в задачах на QBASIC. Если вас не устраивает, можете взять 1.79769E+308
Но поскольку мы задаём случайные целые числа в интервале 0..1000, достаточно было написать max1=0 и т.д
0
6136 / 903 / 305
Регистрация: 25.02.2011
Сообщений: 1,288
Записей в блоге: 1
17.10.2018, 19:14 13
Цитата Сообщение от кот Бегемот Посмотреть сообщение
но при оценке программы, скажем, в ЕГЭ, ни одна из ваших программ не будет признана оптимальной
Различные критерии оптимальности на свой взгляд я привел выше.
Где речь шла про ЕГЭ? Если Ваше решение считается более оптимальным то не удивляюсь почему мы имеем такое программное обеспечение, которое описано в этой статье.

Цитата Сообщение от кот Бегемот Посмотреть сообщение
что в ваших многопроходных программах тоже куча сравнений, но их вы почему-то не учитываете.
Я в своем коде в #7 как раз и посчитал количество сравнений и количество обменов, Вы разве этого не увидели?
Вопрос какой метод сортировки используется, в Вашем случае это сортировка вставками.

Цитата Сообщение от кот Бегемот Посмотреть сообщение
Просто отсортировали массив и взяли первые три элемента.
В решениях предложено сортировать не весь массив, а только первые k (в данном случае 3) элемента
Кроме того, в решении из #7 test1 массив не сортируется, а делится на две части, в котором первые k элементов имеют наибольшее значение, при этом они не упорядочены, тем самым обеспечивается наименьшее кол-во сравнений и обменов при больших значений k (в частности при k > 0.1*n)

Цитата Сообщение от кот Бегемот Посмотреть сообщение
PS 1E+38 - стандартное задание минимального числа в задачах на QBASIC
Для типа Single значение может быть в диапазоне от -3,402823E+38 до +3,402823E+38, почему Вы взяли не самое минимальное значение? Если мы заранее не знаем диапазон изменения исходных данных, то можем получить ошибку при работе программы, лучше даже не допускать возможности подобной ошибки

Добавлено через 1 час 29 минут
как пример, применение сортировки вставками с использованием массива, для любого значения n и k (k,n>=1, k<=n)
тип переменных Long, можно использовать любое значение от -2147483648 до 2147483647

количество сравнений будет меньше чем в сортировке выбором, количество обменов может быть больше чем в сортировке выбором но меньше, чем в сортировке пузырьком
на "оптимальность" кода не претендую.
QBasic/QuickBASIC
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
CONST n = 1000, k = 100
DIM a(1 TO n) AS LONG, b(1 TO k)
DIM i AS LONG, j AS LONG, s AS LONG, m AS LONG, x AS LONG
RANDOMIZE 123
FOR i = 1 TO n
    a(i) = INT(RND * 1000 + 1)
NEXT i
'test4
b(1) = a(1)
FOR i = 2 TO n
    x = a(i)
    IF i > k THEN
        IF b(k) < x THEN m = k: GOSUB Insertion
    ELSE
        m = i: GOSUB Insertion
    END IF
NEXT i
FOR i = 1 TO k
    s = s + b(i)
NEXT i
PRINT "Sum ="; s
END
Insertion:
FOR j = m TO 2 STEP -1
    IF b(j - 1) >= x THEN EXIT FOR
    b(j) = b(j - 1)
NEXT j
b(j) = x
RETURN
1
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5754 / 3458 / 2449
Регистрация: 22.11.2013
Сообщений: 9,714
Записей в блоге: 1
17.10.2018, 23:30 14
кот Бегемот,
увы и ах, алгоритмически это полный эквивалент #2 с модификацией из #8.
И как было выше показано, сильно неоптимальный по скорости, в среднем случае O(n2) против O(n log(n)).
0
Платежеспособный зверь
8750 / 4175 / 1606
Регистрация: 28.10.2009
Сообщений: 11,317
18.10.2018, 02:25 15
Всё дело в неправильной формулировке задачи. Знаете, bormant, если бы вам сказали, что эту задачу надо решить за один проход (а именно так она и формулировалась в задачнике), вы бы написали бы точно такую же программу как у меня.
Удачи!
0
6136 / 903 / 305
Регистрация: 25.02.2011
Сообщений: 1,288
Записей в блоге: 1
18.10.2018, 07:42 16
немного изменил свой код сортировки вставками
QBasic/QuickBASIC
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
CONST n = 1000, k = 100
DIM a(1 TO n) AS LONG, b(1 TO k) AS LONG, i AS LONG, j AS LONG, s AS LONG
RANDOMIZE 123
FOR i = 1 TO n
    a(i) = INT(RND * 1000 + 1)
NEXT i
FOR i = 1 TO k
    FOR j = i TO 2 STEP -1
        IF b(j - 1) >= a(i) THEN EXIT FOR
        b(j) = b(j - 1)
    NEXT j
    b(j) = a(i)
NEXT i
FOR i = k + 1 TO n
    IF b(k) < a(i) THEN
        FOR j = k TO 2 STEP -1
            IF b(j - 1) >= a(i) THEN EXIT FOR
            b(j) = b(j - 1)
        NEXT j
        b(j) = a(i)
    END IF
NEXT i
FOR i = 1 TO k
    s = s + b(i)
NEXT i
PRINT "Sum ="; s
фактически получил аналог варианта предложенного bormant
только вместо обменов переменных используется присваивание (на мой взгляд должно работать немного быстрее на большом количестве данных)
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5754 / 3458 / 2449
Регистрация: 22.11.2013
Сообщений: 9,714
Записей в блоге: 1
19.10.2018, 23:04 17
Цитата Сообщение от кот Бегемот Посмотреть сообщение
если бы вам сказали, что эту задачу надо решить за один проход
В первом варианте из #2 и есть только один проход, разве не заметно? (Независимо, без или с модификацией из #8).
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.10.2018, 23:04

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

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

Найти количество максимальных среди трех чисел
Помогите пожалуйста!!! Задача: Найти количество максимальных среди трех чисел.

Найти разницу сумм четных и нечетных чисел в случайном массиве
Скоро экзамен, помогите пожалуйста решить задачки! Найти разницу сумм четных и нечетных чисел в...

В случайном массиве целых чисел с количеством элементов N найти наиболее часто встречающееся число
В случайном массиве целых чисел с количеством элементов N найти наиболее часто встречающееся число....


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.