 |
|
Модераторы: volvo877, Snowy, MetalFan |
 
|
|
Логика решения задачи 
| champion |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 272 Регистрация: 26.1.2005 Репутация: нет Всего: 2 |
Дана задача:
"Есть массив из N последовательно кол-ва чисел, определите пропущенное число" Не понимаю логику задачи, объясните плз., буду очень признателен --------------------  |
|||
|
||||
Загрузка ...
| Mayk |
|
|||
 ^аВаТаР^ сообщение>> Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: нет Всего: 134 |
Если A[n+1] - A[n] != 1, то пропущено число A[n]+1. По-моему так
-------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
| Zero |
|
||||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 2169 Регистрация: 23.10.2004 Где: Россия, г. Рязань Репутация: нет Всего: 24 |
Mayk, только это паскаль, а не С++...  Поэтому оператор "не равно" пишется не "!=", а вот так "<>"Т.е.
|
||||
|
|||||
| Mayk |
|
|||
|
^аВаТаР^ сообщение>> Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: нет Всего: 134 |
Спасибо.
Я просто запамятовал как пишется оператор не равно  -------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
| Snowy |
|
|||
 Эксперт Профиль Группа: Модератор Сообщений: 11363 Регистрация: 13.10.2004 Где: Питер Репутация: нет Всего: 484 |
Просто
Пропущенное число = n*(n+1)/2 - Сумма_всех_чисел Это для диапазона от 1 до n |
|||
|
||||
| Mayk |
|
|||
|
^аВаТаР^ сообщение>> Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: нет Всего: 134 |
Хмм. Еще имхо можно попоробовать бинарным поиском пройтись, сравнивая
A[medium-1]-A[left] с medium-1-left и A[right]-A[medium] с right-medium -------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
| Snowy |
|
|||
|
Эксперт Профиль Группа: Модератор Сообщений: 11363 Регистрация: 13.10.2004 Где: Питер Репутация: нет Всего: 484 |
Этот способ все же проще. Мы знаем сумму всех чисел от 1 до n. Просто считаем сумму чисел в нашем массиве и вычитаем ее. Разница и будет пропущенным числом. Это самый быстрый и самый простой способ. |
|||
|
||||
| Mayk |
|
|||
|
^аВаТаР^ сообщение>> Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: нет Всего: 134 |
Ты уверен, что просчитать сумму всех чисел (всегда N операций) будет быстрее, чем найти такое n, что A[n]+1 < a[n], (n операций в худшем слчае)  ИМХО так не бывает. К тому же при больших N при суммировании и перемножении произойдет ошибка переполнения. Добавлено @ 08:39 (а бинарный поиск,который кажется здесь возможным, так вообще за логарифмическое время выполняется, что есть быть хорошо...) Это сообщение отредактировал(а) Mayk - 1.11.2005, 08:43 -------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
| Snowy |
|
||||||
|
Эксперт Профиль Группа: Модератор Сообщений: 11363 Регистрация: 13.10.2004 Где: Питер Репутация: нет Всего: 484 |
Конечно. Однопроходный цикл от 1 до N-1.
Это при условии, что все числа идут по порядку. А если нет?
Ну это маловероятно. Перемножать ничего не нужно. Главное, чтобы сумма всех чисел не вышла за границы LongInt. А это весьма маловероятно. Это ж какое n должно быть, чтобы 32-битное число переполнить... |
||||||
|
|||||||
| Mayk |
|
||||
|
^аВаТаР^ сообщение>> Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: нет Всего: 134 |
А это разве не по условию?
-------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
||||
|
|||||
| Snowy |
|
|||
|
Эксперт Профиль Группа: Модератор Сообщений: 11363 Регистрация: 13.10.2004 Где: Питер Репутация: нет Всего: 484 |
Нет Это всего лишь говорит о том, что мы имеем последовательность из N чисел.Остальное предполагается. Ничего не сказано ни о диапазоне, ни о порядке. Имеем всего 2 факта - набор чисел и одно из них пропущено. То есть мы сами должны догадаться, что за числа, подразумевать, что они не дублируются, что пропущено только одно, а не несколько... Условие кривое. |
|||
|
||||
|
|
| Правила форума "Delphi" | |
|
|
Запрещается! 1. Обсуждать и делится взломанными компонентами или программным обеспечением 2. Публиковать ссылки на варез 3. Оффтопить
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, THandle, Rrader, volvo877. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Object Pascal: кроссплатформенные технологии | Следующая тема » |
[ Время генерации скрипта: 0.2530 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |