Различия между версиями 2 и 3
Версия 2 от 2010-12-15 04:04:33
Размер: 2426
Редактор: FrBrGeorge
Комментарий:
Версия 3 от 2010-12-15 12:59:06
Размер: 3884
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 22: Строка 22:
  1. /!\ ещё?   1. Функция f(n) для целых неотрицательных п определена так: {{{
f(0)=0; f(1)=1; f(2n)=f(n); f(2n+1)=f(n)+f(n+1) }}}
  Для данного N найти и напечатать f(N). Обязательное условие: N столь велико, что недопустимо заводить массив из N чисел (равно как и массив, длина которого растет с ростом числа N).
  1. Найти последовательность из N нулей и единиц, в которой никакой отрезок не повторяется три раза подряд. Напечатать НЕТ, если такой последовательности не существует.
     Например, в искомой последовательности нигде не должны встречаться такие отрезки, как 000, или 101010, или 101101101.
  1. Задача коммивояжёра. Дан список пар вида `стоимость_предмета, объём_предмета`. Определить максимально дорогой набор предметов, суммарным объёмом не более N.
  1. {i} Попробовать порешать задачи в книжках, все трудности '''записать''' и задать на следующем занятии

Структура олимпиадной задачи, вырожденные примеры, файловый ввод-вывод

  • {o} — тема по Linux

  • <!> ­— необязательная тема

  • Класс file: read(), write(), readline(), [x]readlines() и close()

  • {o} Модуль sys: stdin, argv; использование argv

  • Роль «занимательной формы» олимпиадной задачи
  • Строгая спецификация в/в в олимпиадной задаче
  • Вырожденный в/в, проверка правильности

Домашнее задание

  • {i} — теоретическое задание

  • {*} — новая тема

  1. {i} Две книжки (есть тут:

    • Брудно А.Л., Каплан Л.И. Московские олимпиады по программированию. – М.: Наука, 1990. – 208 с.
    • Московские олимпиады по информатике / Под ред. Е.В. Андреевой, В.М. Гуровица и В.А. Матюхина. – М.: МЦНМО, 2006. – 256 с.
  2. Любопытная Варвара. Любопытная Варвара ходит по базару и повсюду суёт свой нос. Она заметила, что под прилавками продавцы прячут воздушные шары различной формы и расцветки, приготовленные для праздника весеннего равноденствия. Когда Варвара обнаруживает очередной шар, тот улетает высоко в небо, скрываясь из виду. Варвара знает, что больше половины шаров — одинаковые, закупленные на средства местного олигарха. Помоги Варваре узнать, какие шары закупил олигарх. Варвара может запомнить тип и количество нескольких виденных шаров, но не всех сразу.

  3. Функция f(n) для целых неотрицательных п определена так:

    f(0)=0; f(1)=1; f(2n)=f(n); f(2n+1)=f(n)+f(n+1) 
    Для данного N найти и напечатать f(N). Обязательное условие: N столь велико, что недопустимо заводить массив из N чисел (равно как и массив, длина которого растет с ростом числа N).
  4. Найти последовательность из N нулей и единиц, в которой никакой отрезок не повторяется три раза подряд. Напечатать НЕТ, если такой последовательности не существует.
    • Например, в искомой последовательности нигде не должны встречаться такие отрезки, как 000, или 101010, или 101101101.
  5. Задача коммивояжёра. Дан список пар вида стоимость_предмета, объём_предмета. Определить максимально дорогой набор предметов, суммарным объёмом не более N.

  6. {i} Попробовать порешать задачи в книжках, все трудности записать и задать на следующем занятии


CategoryClass CategoryVmsh

LecturesVMSH/2010-12-15 (последним исправлял пользователь PavelSutyrin 2010-12-22 19:25:46)