Облако тэгов
Статистика
Зарегистрировано участников: 15246
Опубликовано работ: 5134
Базовые алгоритмы олимпиадного программирования.
Опубликовано 04.05.2010 18:18. Автор Кольцов Михаил Петрович
В данной консультационной линии будут рассматриваться различные подходы и алгоритмы решения традиционных олимпиадных задач. Так же будут предлагаться тренировочные задания по этим алгоритмам.
- Войдите или зарегистрируйтесь, чтобы получить возможность отправлять комментарии
Извините меня за возможно резкую реакцию на материал опубликованный здесь, но я не мог остаться равнодушным.
Я далёк от сферы образования, поэтому мне трудно судить о положении дел. Могу только догадываться.
Михаил Петрович, хочу сказать спасибо. Спасибо, что вы что то стараетесь делать, судя по активности на этом ресурсе и, возможно, где то ещё.
Но к сожалению, информация, которой вы делитесь не совсем верна, а часто даже совсем не верна.
Во первых, язык Си - это ни скриптовый язык. "Он[язык Си] является самым популярным языком для создания системного программного обеспечения." Примеры скриптовых языков: PHP, Perl, JavaScript и т.д.
Во вторых, я никогда не читал книгу С. Окулова и, возможно, она является хорошим учебным пособием по алгоритмам (я обязательно посмотрю). Но отрывок про динамические структуры данных содержит массу не совсем верной информации. Буквально с первого предложения.
Автор пишет: "Различные типы данных используют статическое распределение памяти, т. е. распределение памяти на стадии компиляции. Перераспределение памяти на стадии выполнения программы не допускается."
Типы данных не используют распределение памяти. Распределение памяти может быть статическим, автоматическим и динамическим. Да, если вы декларируете глобальную переменную, то память может быть выделена при компилировании, но если ваша переменная на уровне процедуры, то память для этой переменной не выделена пока не запущена эта процедура. А после завершения процедуры, автоматически выделенная память освобождается.
Далее: "Все ссылочные переменные имеют одинаковый размер, равный 4 байтам".
Извините, но это совершенно не верно. Всё зависит от разрядности процессора. Если вы запускаете программу на 16-ти разрядном процессоре, то размер ссылочной переменной будет 2 байта. Начиная с 80386 процессора, мы имели 32-ух разрядные процессоры, где ссылочная переменная имела размер 4 байта. Тогда как в наши дни практически все процессоры 64 разрядные. Но нужно учитывать тот факт, что современные операционные системы могут тоже быть либо 32-ух, либо 64-ёх разрядными. От чего и будет зависеть размер ссылочной переменной (хотя я опустил ещё несколько деталей).
Далее: "Переменной, на которую указывает указатель, не обязательно присваивать какое-либо имя"
Указатель указывает не на переменную, а на начало данных.
"Для хранения динамических переменных выделяется специальная область памяти"
Не для переменных, а для данных. Для самих же переменных память может быть выделена либо статически, если они декларированы к примеру глобально, либо автоматически, если на уровне процедур, либо так же в "куче", если переменная например является частью структуры и т.д.
Ещё раз извиняюсь за вторжение...
Спасибо за "вторжение" Виталий Владимирович. Постараюсь учесть замечания, но в отрывке была цитата книги.
Тем не менее, я упустил то, что выхватывал только часть текста и не указал, что до этого материала есть еще 3 части.
"Различные типы данных используют статическое распределение памяти, т. е. распределение памяти на стадии компиляции. Перераспределение памяти на стадии выполнения программы не допускается." - это мой промах, там было сказано "...различные типы данных, которые используют статическое распределение памяти, т. е. распределение памяти на стадии компиляции. Перераспределение памяти на стадии выполнения программы не допускается."
"Все ссылочные переменные имеют одинаковый размер, равный 4 байтам".
когда писалась данная книга, возможно не было еще 64-разрядных процессоров.
"Переменной, на которую указывает указатель, не обязательно присваивать какое-либо имя". Перед этим предложением записано то, что Вы подчеркнули, "Указатель указывает не на переменную, а на начало данных." Но поскольку адреса могут изменяться - эти адреса назвали переменной, я думаю допустимо.
Виталий Владимирович, у меня встречное предложение. Дело в том, что с олимпиадным движением немного "туговато", оно развито только там где расположены крупные ВУЗы заинтересованные в нем. А что если Вы опубликуете на сайте часть лекций связанных с вопросами которые рассматриваются на олимпиадах, тогда и таких ляпов будет меньше, да и мы "Америку открывать" не будем. Может это предложение Вас заинтересует? Все таки будет диалог, а это интересно.
С уважением Кольцов М.П.
Спасибо большое за ссылочки. Очень пригодились.
А Pascal изучают не только в ВУЗах но и школах Казахстана.
Ниже предлагается отрывок из книги С. Окулова "Программирование в алгоритмах". Сегодняшняя тема "Динамические структуры данных. Линейные списки".
/sites/default/files/users/user4213/Dinamicheskie_struktury_dannyh.zip
Сегодня возникает вопрос какому языку учить и по каким учебникам
Доброго времени суток Ирина Михайловна.
При нынешнем распределении учебных часов, остается только алгоритмический язык. А если серьезно, то хорошо было бы изучить скриптовый язык (например СИ), но я с ним не работал. В принципе все современные языки достаточно хороши и использование Pascal как учебного имеет преимущество только в том, что мы привыкли, ну и достаточно гибок, много приложений на Delphi. Какие учебники использовать - я детям говорю, читайте толстые книжки. Сам часто использовал Сухарева и Немюгина, пока не запомнил как это работает, а затем достаточно было справочника ШУ, очень удобен (может опять же сила привычки), сборник задач Златопольского (в нем много хороших задач решаемых математическими методами). Думаю пробовать СИ, но это год-два пока ознакомлюсь немного. А в принципе все языки одинаковы, зная один легко перестроиться на другой вопрос только времени. В ВУЗах пока изучают Pascal, по крайне мере у нас в Казахстане.
С уважением Кольцов М.П.
Какой язык программирования должен знать школьник? Как Вы считаете?
Спасибо!
В продолжении материала о длинной арифметике. Приводится продолжение отрывка из книги С. Окулова "Программирование в алгоритмах".
Сегодняшняя тема "Сложение и сравнение "длинных" чисел"
/sites/default/files/users/user4213/Slozhenie_i_sravnenie_dlinnyh_chisel.doc
Ниже предлагается отрывок из книги С. Окулова "Программирование в алгоритмах".
Сегодняшняя тема "Длинная арифметика. Ввод и вывод "длинных" чисел".
/sites/default/files/users/user4213/Dlinnaya_arifmetika._Vvod_i_vyvod_chisel.doc