На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение
постоянный участник


Сообщение: 24
ссылка на сообщение  Отправлено: 05.03.12 14:48. Заголовок: [C4] Эффективность алгоритма


В задачах С4 требуется написать ЭФФЕКТИВНУЮ программу. По каким критериям определяется эта эффективность? Например, в задаче необходимо для получения результата выбрать числовую информацию из строки. Есть два варианта: 1) прочитать всю строку и, используя стандартные операции, функции и процедуры, выделить нужные данные и перевести в нужный формат; 2) считывая по одному символу, "добраться" до числа и прочитать его.
Если взять объем используемой памяти, то первый вариант требует хранения данного строкового типа и числового, а второй - символьного и числового. Похоже, второй - эффективнее.
Если взять удобство пользования программой (а это немаловажная функция), то в первом случае набираем строку, нажимаем Enter и всю работу поручаем программе, а во втором набираем после КАЖДОГО символа Enter. Значит, здесь первый способ эффективнее. Что в приоритете?

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 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)
  • и т.д.

    На самом деле, часто требования эффективности по расходу памяти и по быстродействию противоречат друг другу. Это значит, что использование дополнительной памяти позволяет увеличить быстродействие и наоборот.

    Решение считается неэффективным, если можно увеличить быстродействие, не расходуя дополнительную память, или уменьшить объем расходуемой памяти, не снижая быстродействия.

  • ___________________________________________________
    Имей мужество пользоваться собственным умом. (И. Кант)
    Спасибо: 1 
    ПрофильЦитата Ответить
    постоянный участник




    Сообщение: 8
    ссылка на сообщение  Отправлено: 06.03.12 11:24. Заголовок: tavabar пишет: Если..


    tavabar пишет:

     цитата:
    Если взять удобство пользования программой (а это немаловажная функция), то в первом случае набираем строку, нажимаем Enter и всю работу поручаем программе, а во втором набираем после КАЖДОГО символа Enter. Значит, здесь первый способ эффективнее. Что в приоритете?


    Тут Вы не правы, нажатие ENTER записывает всю строку во входной поток, а дальше считываем либо целиком строку, либо циклом посимвольно. После каждого символа ENTER жать не надо

    Спасибо: 1 
    ПрофильЦитата Ответить
    постоянный участник


    Сообщение: 25
    ссылка на сообщение  Отправлено: 06.03.12 14:02. Заголовок: oval пишет: После к..


    oval пишет:

     цитата:
    После каждого символа ENTER жать не надо


    Да, проверила, Вы правы, спасибо.

    Спасибо: 0 
    ПрофильЦитата Ответить



    Сообщение: 2
    ссылка на сообщение  Отправлено: 16.03.12 11:13. Заголовок: К вопросу об эффективности алгоритма


    С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма.

    Спасибо: 0 
    ПрофильЦитата Ответить
    Администратор




    Сообщение: 177
    ссылка на сообщение  Отправлено: 16.03.12 13:22. Заголовок: Dmitry78 пишет: С++...


    Dmitry78 пишет:
     цитата:
    С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма.

    Судя о всему, использование STL разрешено. Постараюсь уточнить официальное мнение комиссии.

    ___________________________________________________
    Имей мужество пользоваться собственным умом. (И. Кант)
    Спасибо: 0 
    ПрофильЦитата Ответить
    постоянный участник




    Сообщение: 12
    ссылка на сообщение  Отправлено: 16.03.12 15:31. Заголовок: Если в задаче необхо..


    Если в задаче необходима сортировка, то сортируем спокойно, а если имеется алгоритм без сортировки, то снизят балл за неэффективность.
    Например: для нахождения максимума сортируем массив и берем первый(последний) элемент.
    Но это мое мнение
    Поляков пишет:

     цитата:
    официальное мнение комиссии.


    узнать хочется.

    Спасибо: 0 
    ПрофильЦитата Ответить
    Администратор




    Сообщение: 178
    ссылка на сообщение  Отправлено: 16.03.12 15:36. Заголовок: oval пишет: Если в з..


    oval пишет:
     цитата:
    Если в задаче необходима сортировка, то сортируем спокойно, а если имеется алгоритм без сортировки, то снизят балл за неэффективность.

    Согласен.

    ___________________________________________________
    Имей мужество пользоваться собственным умом. (И. Кант)
    Спасибо: 0 
    ПрофильЦитата Ответить
    Администратор




    Сообщение: 180
    ссылка на сообщение  Отправлено: 16.03.12 17:16. Заголовок: Dmitry78 пишет: С++...


    Dmitry78 пишет:
     цитата:
    С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма.

    Официальный ответ:
     цитата:
    Использование STL разрешено и не является основанием для снижения оценки. Желательно также, чтобы автор ознакомился с указаниями по оцениванию в демо-версии.




    ___________________________________________________
    Имей мужество пользоваться собственным умом. (И. Кант)
    Спасибо: 0 
    ПрофильЦитата Ответить



    Сообщение: 3
    ссылка на сообщение  Отправлено: 16.03.12 19:34. Заголовок: Спасибо за ответ.


    По поводу STL ясно. А по поводу сортировки, решение с сортировкой иногда является более "понятным", чем без нее. Хотя я в принципе понимаю, что проверяется возможность нахождения эффективного алгоритма решения задачи. С другой стороны встает вопрос о расширяемости алгоритма для решения более широкого круга задач. Найти 3 максимума (минимума) можно и без сортировки, а если нужно искать 10, 30 максимумов (минимумов)?

    Спасибо: 0 
    ПрофильЦитата Ответить
    Администратор




    Сообщение: 181
    ссылка на сообщение  Отправлено: 16.03.12 20:03. Заголовок: Dmitry78 пишет: Найт..


    Dmitry78 пишет:
     цитата:
    Найти 3 максимума (минимума) можно и без сортировки, а если нужно искать 10, 30 максимумов (минимумов)?

    Если вас интересует ЕГЭ, то таких задач там не будет. Если не ЕГЭ, то, по-видимому, сортировка проще и понятнее, а значит в большинстве случаев лучше.

    ___________________________________________________
    Имей мужество пользоваться собственным умом. (И. Кант)
    Спасибо: 0 
    ПрофильЦитата Ответить
    Ответ:
    1 2 3 4 5 6 7 8 9
    видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

    показывать это сообщение только модераторам
    не делать ссылки активными
    Имя, пароль:      зарегистрироваться    
    Тему читают:
    - участник сейчас на форуме
    - участник вне форума
    Все даты в формате GMT  3 час. Хитов сегодня: 196
    Права: смайлы да, картинки да, шрифты нет, голосования нет
    аватары да, автозамена ссылок вкл, премодерация откл, правка нет