Можно ли элементы массива переставить так, чтобы получилась арифметическая прогрессия

@Badaboom · Регистрация: 06.04.2021

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

Задан числовой массив из N элементов. Напишите программу, которая проверяет, можно ли элементы этого массива переставить так, чтобы получилась арифметическая прогрессия.
Примеры
Ввод:
5
20 10 40 30 50
Вывод:
YES
10
Ввод:
5
60 10 40 50 30
Вывод:
NO
50
P.S. НАПИСАТЬ ЧЕРЕЗ СЛОВАРИ ИЛИ СТРОКИ, ЭТО ОЧЕНЬ ВАЖНО

@Badaboom · 06.04.2021, 19:23 **[ТС]**

Arsegg, что ж, учитывая, что я планирую быть менеджером в IT, а не девелопером, не так уж и критично, что с языками программирования у меня не очень (всё-таки прожект менеджер код не пишет, слава Богу)
Тем не менее, можно было бы просто обьяснить, а не угорать с того, что я не полностью улавливаю суть...

@Arsegg · 06.04.2021, 19:26

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

Тем не менее, можно было бы просто обьяснить, а не угорать с того, что я не полностью улавливаю суть...

Проще нужно к этому относится и не принимай близко к сердцу.

@Badaboom · 06.04.2021, 19:34 **[ТС]**

3C_273, так что? Можешь подправить код? Ибо в первом примере со скрина вывод какой-то неверный (выше сказал какой)

@Catstail · 06.04.2021, 19:42

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

НАПИСАТЬ ЧЕРЕЗ СЛОВАРИ ИЛИ СТРОКИ, ЭТО ОЧЕНЬ ВАЖНО

- не могу не отметить два момента:

1) очевидную глупость этой постановки. Ибо, если нужно использовать все элементы списка, то арифметическая прогрессия (как монотонная последовательность) может получиться только в двух случаях: при возрастающем или убывающем порядке. Этому соответствуют две перестановки элементов (из общего количества n!). Поэтому - сортировка и проверка разности соседних элементов (что и сделал уважаемый Arsegg)

2) Оборот "через словари или строки" - это насилие над русским языком.

@3C_273 · 06.04.2021, 20:06

Badaboom, Забыл отсортировать массив
Вот теперь вроде работает
Но я надеюсь ты понимаешь, что так делать нельзя и это полное извращение над языком.
И по идее ты скорее всего что-то перепутал с заданием

Python
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
n = int(input())
voc = {}
str = input()
j= 0
for item in str.split():
    voc.update({j:int(item)})
    j+=1
flag = True
for i in range(n):
    for j in range(1, n):
        if voc[j] < voc[j-1]:
            voc.update({j-1:voc[j], j:voc[j-1]}) 
d = voc[1] - voc[0]
for i in range(1,n):
    if voc[i] != voc[i-1]+d:
        flag = False 
if flag:
    print('Yes \n {}'.format(d))
else:
    min = voc[0]
    max = voc[0]
    for i in range(1, n):
        if voc[i] < min:
            min = voc[i]
        if voc[i] > max:
            max = voc[i]
    print('No\n{}'.format(max-min))

Добавлено через 3 минуты
Arsegg, Хахахаххахах, всякое может быть, но я надеюсь что преподы в вузах понимают как работает словарь, иначе у них проблемы с кадрами

@Badaboom · 06.04.2021, 20:10 **[ТС]**

3C_273, именно благодаря таким кадрам, как мои преподы, у ПТУшника Петьки шансов больше устроиться на работу девелопером, если он окончил всякие там курсы по Питону/ПОХэпэ/ДС/Жабе и тп, чем у Василия Пупкина-магистра из Урюпинского Физико-Техничнского Университета; и именно потому я хочу быть менеджером в ИТ, а не девелопером...

@3C_273 · 06.04.2021, 20:25

Badaboom, это хорошо)
код-то работает?

@Badaboom · 06.04.2021, 20:30 **[ТС]**

3C_273, к счастью, да))

@u235 · 06.04.2021, 20:44

Arsegg, можно и множества задействовать, если человеку хочется,

типа такого:

Python
1
len(set([y - x  for x, y in zip(a, a[1:])]))==1

@Arsegg · 06.04.2021, 20:49

u235, с множествами и словарями более менее понятно, но блин, как прикажете повторить данную задачу, задействуя только кортежи и стеки и/или строки? О_о
Я даже концептуально не могу понять условие задачи((

@eaa · 06.04.2021, 20:58

Не по теме:

Задачу можно решить без сортировки, сетов и прочего.

@Arsegg · 06.04.2021, 21:06

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

Задачу можно решить без сортировки, сетов и прочего.

Быстрее, чем O(N * log(N))?
/upd
eaa, вы совершенно правы: Check whether Arithmetic Progression can be formed from the given array.
/upd2
Дела...

Find out the smallest and second smallest elements
Find different between the two elements. d = second_smallest – smallest
Store all elements in a hashmap and return “NO” if duplicate element found (can be done together with step 1).
Now start from “second smallest element + d” and one by one check n-2 terms of Arithmetic Progression in hashmap. If any value of progression is missing, return false.
Return “YES” after end of the loop.

А ведь действительно нужно было через словари решать)) О_О

@eaa · 07.04.2021, 06:06

От ТС видимо этого добивались, только он объяснить ничего толком не смог, в итоге препод виноват

@Arsegg · 07.04.2021, 11:13

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

От ТС видимо этого добивались, только он объяснить ничего толком не смог, в итоге препод виноват

Но, согласись, решение далеко не тривиальное - сложно с ходу придумать такое, не сталкиваясь с аналогичными задачами. Хотя решение через Counting Sort - попросту читерское!)))

@Catstail · 07.04.2021, 12:27

Интересно чуть изменить задачу: дан список, построить из его элементов ар. прогрессию максимальной длины

@Arsegg · 07.04.2021, 12:32

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

Интересно чуть изменить задачу: дан список, построить из его элементов ар. прогрессию максимальной длины

Пахнет ДП. Но, возможно, есть и итеративная версия ее решения.

@Gdez · 07.04.2021, 12:51

Arsegg, через отсортированный список словарь -> {a[i]: a[k] - a[i] for k in range(i+1, n)} -> counter(dict.values()) ?
Сложность большая будет?

@Arsegg · 07.04.2021, 13:02

Gdez, почему-то, мне кажется, что это частное решение. Наивное решение, по идее, за O(N ^ 2) - перебираем все варианты для каждого diff. ДП позволит уменьшить временную сложность до O(N) (?) - нужно разбирать детально, т. к. рекурсивная формула подсчета на ум не пришла.
Возможно, я не понял твое решение((

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

Сложность большая будет?

По идее O(N), ведь всего два прохода по всем элементам.

Новые блоги и статьи Все статьи Все блоги /
Теория всего 12. ВГК anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .	Теория всего 10. Клод трусишка anaschu 21.07.2026 Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
Теория всего 9. Окончательная проработка метафоры "дерево = традиции" anaschu 21.07.2026 Скрытые параметры ядра ОДУ: Механика Глубинного Рока Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .	Теория всего 8. Clauude трусишка. Ответ джемени anaschu 21.07.2026 Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .	Теория всего 7. Дерево - это патриархат, грибы - это феминизм anaschu 21.07.2026 Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат» Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .	История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры. anaschu 21.07.2026 Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .

@Badaboom 0 / 0 / 0 Регистрация: 06.04.2021 Сообщений: 79

	Можно ли элементы массива переставить так, чтобы получилась арифметическая прогрессия 06.04.2021, 18:07. Показов 3897. Ответов 37 Метки нет (Все метки) Задан числовой массив из N элементов. Напишите программу, которая проверяет, можно ли элементы этого массива переставить так, чтобы получилась арифметическая прогрессия. Примеры Ввод: 5 20 10 40 30 50 Вывод: YES 10 Ввод: 5 60 10 40 50 30 Вывод: NO 50 P.S. НАПИСАТЬ ЧЕРЕЗ СЛОВАРИ ИЛИ СТРОКИ, ЭТО ОЧЕНЬ ВАЖНО Миниатюры 0

@Badaboom 0 / 0 / 0 Регистрация: 06.04.2021 Сообщений: 79
	06.04.2021, 19:23 [ТС]
	Arsegg, что ж, учитывая, что я планирую быть менеджером в IT, а не девелопером, не так уж и критично, что с языками программирования у меня не очень (всё-таки прожект менеджер код не пишет, слава Богу) Тем не менее, можно было бы просто обьяснить, а не угорать с того, что я не полностью улавливаю суть... 0

@Badaboom 0 / 0 / 0 Регистрация: 06.04.2021 Сообщений: 79
	06.04.2021, 19:34 [ТС]
	3C_273, так что? Можешь подправить код? Ибо в первом примере со скрина вывод какой-то неверный (выше сказал какой) 0

@Badaboom 0 / 0 / 0 Регистрация: 06.04.2021 Сообщений: 79
	06.04.2021, 20:10 [ТС]
	3C_273, именно благодаря таким кадрам, как мои преподы, у ПТУшника Петьки шансов больше устроиться на работу девелопером, если он окончил всякие там курсы по Питону/ПОХэпэ/ДС/Жабе и тп, чем у Василия Пупкина-магистра из Урюпинского Физико-Техничнского Университета; и именно потому я хочу быть менеджером в ИТ, а не девелопером... 0

@3C_273 42 / 29 / 14 Регистрация: 09.06.2018 Сообщений: 147
	06.04.2021, 20:25
	Badaboom, это хорошо) код-то работает? 0

@Badaboom 0 / 0 / 0 Регистрация: 06.04.2021 Сообщений: 79
	06.04.2021, 20:30 [ТС]
	3C_273, к счастью, да)) 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	06.04.2021, 20:49
	u235, с множествами и словарями более менее понятно, но блин, как прикажете повторить данную задачу, задействуя только кортежи и стеки и/или строки? О_о Я даже концептуально не могу понять условие задачи(( 0

@eaa
	06.04.2021, 20:58
	Не по теме: Задачу можно решить без сортировки, сетов и прочего. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.04.2021, 06:06
	От ТС видимо этого добивались, только он объяснить ничего толком не смог, в итоге препод виноват 1

@Catstail Супер-модератор 38210 / 21143 / 4313 Регистрация: 12.02.2012 Сообщений: 34,757 Записей в блоге: 14
	07.04.2021, 12:27
	Интересно чуть изменить задачу: дан список, построить из его элементов ар. прогрессию максимальной длины 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	07.04.2021, 12:51
	Arsegg, через отсортированный список словарь -> {a[i]: a[k] - a[i] for k in range(i+1, n)} -> counter(dict.values()) ? Сложность большая будет? 0

Можно ли элементы массива переставить так, чтобы получилась арифметическая прогрессия

Решение