Схема на раздела

◄21 март - 26 март
►4 април - 10 април

  • КН, групи 5 и 6 - BFS, DFS

    Задачи, които решихме:

    1) 2013 Упражнение 5 - Графи:

    Ябълки - Задачата се решава с BFS в мрежа, като този път входните данни са малко по-особени. Координатите на първата ябълка ги четете стандартно, а за координатите на втората, можете да ползвате следния начин:

    if( scanf("%d %d", &x, &y) == 2 )

            apples.push_back(make_pair(x-1, y-1));, 

    където apples е от тип vector < pair<int, int> > apples; и служи да си запишем в него координатите на ябълките. Кодът на тази задача ще бъде качен в муудъл. Обърнете внимание на начина, по който достъпваме съседните клетки на текущата клетка с използването на масива delta[][].

    Школа - Задачата се решава с DFS, като целта е да преброим свързаните компоненти в неориентиран граф. Пускаме DFS от всеки необходен връх, обхождаме графа, като маркираме всеки връх през който минем. Ако след обхождането, все още има необходени върхове, пускаме DFS от някой от тях. Колкото пъти пуснем DFS, това ни е отговорът на задачата.

    Задачи за упражнение:

    1) 2013 Упражнение 5 - Графи:

    Лабиринт 

    2) 2012 - Извънредно контролно:

    Рицари

    3) 2015 (летен) Контролно 2:

    Още една редица

    • Apples Файл
    • BFS Файл
    • DFS Файл

    • КН 1-2

      Взехме двоично търсене.

      Видяхме, че за да търсим, не необходимо да разполагаме с всички стойности от колекцията, в която търсим. Конкретно правихме задачата, в която е дадена монотонно растяща функция, чийсто стойности са от - безк до +безк, и се търси коренай. Това разбира се стана с двоично търсене по аргумента. 

      Гледахме и задачата:

      Elliot 

      Напомням, че задачата Sysadmin от тук , която разглеждахме преди време, също се решава с двоично търсене. Като там търсим двоично отговора. 

    • Eliot 1 Файл

      Решение, в което представяме масива суми като растяща редица (както обсъдихме на упражнението ако някой елемент е по-малък от предишния, то винаги ще избираме поне предишния).

    • Eliot 2 Файл

      Второто решение, за което говорихме. Сортираме заявките и след това обхождаме линейно (въднъж) масива със суми.

◄21 март - 26 март
►4 април - 10 април