Автор | Сообщение |
|
| постоянный участник
|
Сообщение: 24
|
|
Отправлено: 05.03.12 14:48. Заголовок: [C4] Эффективность алгоритма
В задачах С4 требуется написать ЭФФЕКТИВНУЮ программу. По каким критериям определяется эта эффективность? Например, в задаче необходимо для получения результата выбрать числовую информацию из строки. Есть два варианта: 1) прочитать всю строку и, используя стандартные операции, функции и процедуры, выделить нужные данные и перевести в нужный формат; 2) считывая по одному символу, "добраться" до числа и прочитать его. Если взять объем используемой памяти, то первый вариант требует хранения данного строкового типа и числового, а второй - символьного и числового. Похоже, второй - эффективнее. Если взять удобство пользования программой (а это немаловажная функция), то в первом случае набираем строку, нажимаем Enter и всю работу поручаем программе, а во втором набираем после КАЖДОГО символа Enter. Значит, здесь первый способ эффективнее. Что в приоритете?
|
|
|
Ответов - 10
[только новые]
|
|
|
| Администратор
|
Сообщение: 144
|
|
Отправлено: 05.03.12 18:03. Заголовок: tavabar пишет: В зад..
tavabar пишет: цитата: | В задачах С4 требуется написать ЭФФЕКТИВНУЮ программу. По каким критериям определяется эта эффективность? |
|
Эффективность оценивается по количеству операций и расходуемой памяти, как они зависят от размера исходных данных N (например, количества введенных чисел). Подробнее (на школьном уровне) можно почитать, например, здесь. Эффективность по памяти означает, например, что не нужно заводить массив там, где можно обойтись без массива решение с массивом, длина которого не зависит от исходных данных, лучше, чем решение, в котором все исходные данные сначала помещаются в массив решение с массивом [1..N] лучше, чем решение с массивом [1..M*N] (M > 1) решение с массивом [1..N] лучше, чем решение с матрицей [1..N,1..M] (M > 1) и т.д. Эффективность по быстродействию означает, например, что лучше получить какой-то результат без использования цикла (по формуле), чем с помощью цикла лучше решить задачу за один проход по массиву, чем за N проходов (N > 1) лучше решить задачу с помощью одного цикла (от 1 до N), чем с помощью вложенного цикла (1..N, 1..M, где M > 1) и т.д. На самом деле, часто требования эффективности по расходу памяти и по быстродействию противоречат друг другу. Это значит, что использование дополнительной памяти позволяет увеличить быстродействие и наоборот. Решение считается неэффективным, если можно увеличить быстродействие, не расходуя дополнительную память, или уменьшить объем расходуемой памяти, не снижая быстродействия.
|
|
|
|
| постоянный участник
|
Сообщение: 8
|
|
Отправлено: 06.03.12 11:24. Заголовок: tavabar пишет: Если..
tavabar пишет: цитата: | Если взять удобство пользования программой (а это немаловажная функция), то в первом случае набираем строку, нажимаем Enter и всю работу поручаем программе, а во втором набираем после КАЖДОГО символа Enter. Значит, здесь первый способ эффективнее. Что в приоритете? |
| Тут Вы не правы, нажатие ENTER записывает всю строку во входной поток, а дальше считываем либо целиком строку, либо циклом посимвольно. После каждого символа ENTER жать не надо
|
|
|
|
| постоянный участник
|
Сообщение: 25
|
|
Отправлено: 06.03.12 14:02. Заголовок: oval пишет: После к..
oval пишет: цитата: | После каждого символа ENTER жать не надо |
| Да, проверила, Вы правы, спасибо.
|
|
|
|
Отправлено: 16.03.12 11:13. Заголовок: К вопросу об эффективности алгоритма
С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма.
|
|
|
|
| Администратор
|
Сообщение: 177
|
|
Отправлено: 16.03.12 13:22. Заголовок: Dmitry78 пишет: С++...
Dmitry78 пишет: цитата: | С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма. |
|
Судя о всему, использование STL разрешено. Постараюсь уточнить официальное мнение комиссии.
|
|
|
|
| постоянный участник
|
Сообщение: 12
|
|
Отправлено: 16.03.12 15:31. Заголовок: Если в задаче необхо..
Если в задаче необходима сортировка, то сортируем спокойно, а если имеется алгоритм без сортировки, то снизят балл за неэффективность. Например: для нахождения максимума сортируем массив и берем первый(последний) элемент. Но это мое мнение Поляков пишет: цитата: | официальное мнение комиссии. |
| узнать хочется.
|
|
|
|
| Администратор
|
Сообщение: 178
|
|
Отправлено: 16.03.12 15:36. Заголовок: oval пишет: Если в з..
oval пишет: цитата: | Если в задаче необходима сортировка, то сортируем спокойно, а если имеется алгоритм без сортировки, то снизят балл за неэффективность. |
|
Согласен.
|
|
|
|
| Администратор
|
Сообщение: 180
|
|
Отправлено: 16.03.12 17:16. Заголовок: Dmitry78 пишет: С++...
Dmitry78 пишет: цитата: | С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма. |
|
Официальный ответ: цитата: | Использование STL разрешено и не является основанием для снижения оценки. Желательно также, чтобы автор ознакомился с указаниями по оцениванию в демо-версии. |
|
|
|
|
|
Отправлено: 16.03.12 19:34. Заголовок: Спасибо за ответ.
По поводу STL ясно. А по поводу сортировки, решение с сортировкой иногда является более "понятным", чем без нее. Хотя я в принципе понимаю, что проверяется возможность нахождения эффективного алгоритма решения задачи. С другой стороны встает вопрос о расширяемости алгоритма для решения более широкого круга задач. Найти 3 максимума (минимума) можно и без сортировки, а если нужно искать 10, 30 максимумов (минимумов)?
|
|
|
|
| Администратор
|
Сообщение: 181
|
|
Отправлено: 16.03.12 20:03. Заголовок: Dmitry78 пишет: Найт..
Dmitry78 пишет: цитата: | Найти 3 максимума (минимума) можно и без сортировки, а если нужно искать 10, 30 максимумов (минимумов)? |
|
Если вас интересует ЕГЭ, то таких задач там не будет. Если не ЕГЭ, то, по-видимому, сортировка проще и понятнее, а значит в большинстве случаев лучше.
|
|
|
|