| Цитата(Mayk @ 30.10.2005, 09:58) |
| Если A[n+1] - A[n] != 1, то пропущено число A[n]+1. По-моему так |
Mayk, только это паскаль, а не С++...
Поэтому оператор "не равно" пишется не "!=", а вот так "<>"Т.е.
| Код |
|
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Object Pascal: кроссплатформенные технологии > Логика решения задачи |
| Автор: champion 30.10.2005, 08:29 |
| Дана задача: "Есть массив из N последовательно кол-ва чисел, определите пропущенное число" Не понимаю логику задачи, объясните плз., буду очень признателен |
| Автор: Mayk 30.10.2005, 08:58 |
| Если A[n+1] - A[n] != 1, то пропущено число A[n]+1. По-моему так |
| Автор: Zero 30.10.2005, 21:52 | ||||
Mayk, только это паскаль, а не С++... Поэтому оператор "не равно" пишется не "!=", а вот так "<>"Т.е.
|
| Автор: Mayk 30.10.2005, 22:09 |
Спасибо. Я просто запамятовал как пишется оператор не равно  |
| Автор: Snowy 31.10.2005, 15:36 |
| Просто Пропущенное число = n*(n+1)/2 - Сумма_всех_чисел Это для диапазона от 1 до n |
| Автор: Mayk 31.10.2005, 20:05 |
| Хмм. Еще имхо можно попоробовать бинарным поиском пройтись, сравнивая A[medium-1]-A[left] с medium-1-left и A[right]-A[medium] с right-medium |
| Автор: Snowy 1.11.2005, 08:28 | ||
Этот способ все же проще. Мы знаем сумму всех чисел от 1 до n. Просто считаем сумму чисел в нашем массиве и вычитаем ее. Разница и будет пропущенным числом. Это самый быстрый и самый простой способ. |
| Автор: Mayk 1.11.2005, 08:38 | ||
Ты уверен, что просчитать сумму всех чисел (всегда N операций) будет быстрее, чем найти такое n, что A[n]+1 < a[n], (n операций в худшем слчае)  ИМХО так не бывает. К тому же при больших N при суммировании и перемножении произойдет ошибка переполнения. Добавлено @ 08:39 (а бинарный поиск,который кажется здесь возможным, так вообще за логарифмическое время выполняется, что есть быть хорошо...) |
| Автор: Snowy 3.11.2005, 11:24 | ||||||
Конечно. Однопроходный цикл от 1 до N-1.
Это при условии, что все числа идут по порядку. А если нет?
Ну это маловероятно. Перемножать ничего не нужно. Главное, чтобы сумма всех чисел не вышла за границы LongInt. А это весьма маловероятно. Это ж какое n должно быть, чтобы 32-битное число переполнить... |
| Автор: Mayk 3.11.2005, 11:56 | ||||
А это разве не по условию?
|
| Автор: Snowy 3.11.2005, 12:51 | ||
Нет Это всего лишь говорит о том, что мы имеем последовательность из N чисел.Остальное предполагается. Ничего не сказано ни о диапазоне, ни о порядке. Имеем всего 2 факта - набор чисел и одно из них пропущено. То есть мы сами должны догадаться, что за числа, подразумевать, что они не дублируются, что пропущено только одно, а не несколько... Условие кривое. |