|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.10.2009, 20:31 | #1 |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
Ошибка в алгоритме нахождения тройки чисел с максимальным произведением
Вот вроде простая задача:
Дан массив чисел, надо выделить 3 числа с наибольшим произведением (числа целые и любого знака). Например: 1 2 -100 -30 -90 50. Оно бы написало -90 -100 50. Вот что я сделал: Код:
|
22.10.2009, 20:49 | #2 |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
В общем я отключил здравый смысл и сделал так (но работает!):
Код:
|
22.10.2009, 20:57 | #3 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Странно, но у меня все работает, и ошибки я не вижу. Ответы совпадают с простенькими тестами к этой задаче.
З.Ы. Ваше решение далеко не самое оптимальное. Ее можно делать линейно (и за секунду будет ответ для 2-3 миллионов чисел), а вы решаете лобовым методом за куб (и за секунду можно решить для 100-200 чисел), разницу видите? З.З.Ы. И все таки Ваше решение неверное. Правда ошибка в другом и на многих тестах это не отобразится. Код:
|
22.10.2009, 21:26 | #4 | |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
Цитата:
А второе быстрее? |
|
22.10.2009, 21:45 | #5 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Пример: массив -1 -2 -3. В нем единственное произведение равно -1*(-2)*(-3), тоесть -6. При (i = j) or (i = k) or (j = k) Вы присваиваете темпу 0, это не меньше мула, поэтому происходит присваивание значений произведения и 1ого, 2ого, 3его чисел ответа. Как результат - бред. Конкретно в моем тесте произведение будет в памяти хранится, как 0, а на выходе будет -3 -3 -3.
Второе решение немного быстрее, квадрат вместо куба, если в первом случае за секунду решалось для 100-300 чисел, то сдесь текущая реализация прокатит, в зависимости от мощности системы, для 2-5 тысяч. Оптимальное решение работает для нескольких миллионов (давно не мерил скорость считывания в паскале, она сильно затормозит тот солюшн, при уже готовом массиве в памяти - гарантировано укладывается в секунду для 20 миллионов чисел). |
22.10.2009, 22:04 | #6 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
И все равно неверно, причем довольно сильно бросаются в глаза недоработки. Вот, придумал тест-завалитель:
6 -1 10 10 -1111 -1111 -1111 Тоесть 6 чисел, которые начинаются после числа 6 Выводит: Maximum trio is: -1111, -1111, -1111 |
22.10.2009, 22:30 | #7 |
Участник клуба Подтвердите свой е-майл
Регистрация: 19.11.2007
Сообщений: 1,022
|
Пробуйте. Только, что набросал.
Код:
Последний раз редактировалось profi; 23.10.2009 в 09:30. |
22.10.2009, 22:30 | #8 |
Участник клуба Подтвердите свой е-майл
Регистрация: 19.11.2007
Сообщений: 1,022
|
[удалил сам]
Последний раз редактировалось profi; 22.10.2009 в 22:32. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
TASM - нахождения максимального числа из трех положительных целых чисел и умножения максимального числа | iggor | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 4 | 24.05.2009 20:16 |
Разность между максимальным и минимальным значениями | StudeHt | Помощь студентам | 7 | 23.04.2009 22:26 |
Ошибка в алгоритме программы на бинарные фйлы | ROD | Общие вопросы C/C++ | 0 | 15.04.2009 22:15 |
правильно написать формулу нахождения минимального значения из диапазона чисел в строке | Legame | Microsoft Office Excel | 14 | 01.03.2009 22:29 |
Задача с произведением | Many man | Помощь студентам | 1 | 20.12.2008 20:47 |