помогите написать алгоритм

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
alinna
Сообщения: 3
Зарегистрирован: 04 мар 2015, 13:58

помогите написать алгоритм

Сообщение alinna » 04 мар 2015, 14:05

С последовательности 1,...,n на вступ получаем масив n-1 елементов в любом порядке. Один элемент отсутствует. Нужен алгоритм, который определит этот елемент(число).

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: помогите написать алгоритм

Сообщение somewhere » 04 мар 2015, 16:27

Если требования ко времени выполнения не критичны, то достаточно:
1) Отсортировать оба массива
2) Сравнить поэлементно (n-1) элементов
2.1) первый несовпавший элемент в более длинном массиве и есть искомый элемент
2.2) если совпали все элементы, то искомый элемент - последний элемент длинного массива
It's a long way to the top if you wanna rock'n'roll

alinna
Сообщения: 3
Зарегистрирован: 04 мар 2015, 13:58

Re: помогите написать алгоритм

Сообщение alinna » 04 мар 2015, 17:16

да, спасибо. но сложность алгоритма должна быть линейная. то есть, если я правильно понимаю, может быть только один цикл. а сортировка массивов осложнит его. ( первый уже отсортирован 1,2,3....n)

alinna
Сообщения: 3
Зарегистрирован: 04 мар 2015, 13:58

Re: помогите написать алгоритм

Сообщение alinna » 04 мар 2015, 17:32

уже нашла решение, спасибо :)

Ответить