Търсене и итерация

Search and Iteration

Какво е итерация? Задача за търсене. Инициализация на променливите.

Автор: Александър Георгиев

Преди да започнем да измисляме и имплементираме по-сложни алгоритми, трябва да сме сигурни, че можем да се справим с най-oсновните неща в програмирането: работа с променливи, масиви, цикли и условни оператори. Както казахме, голяма част от сложните алгоритми разчитат на по-прости такива, така че няма смисъл да продължаваме нататък без да можем това. Нещо повече, тъй като ще ни се налага да ги ползваме много, е хубаво да се чувстваме сигурни в тях.

Итерация

Най-основната техника, която изобщо съществува в програмирането, е итерацията. Нейната идея е ако имаме набор от неща (променливи, структури и т.н.) да минем през всяко от тях и да извършим някакво действие. Самото действие, което извършваме върху тях, може да е много различно, в зависимост какъв проблем решаваме - да проверим дали този елемент е равен на нещо, да променим неговата стойност, да го премахнем от множеството и т.н. В най-честия случай това се прави чрез цикъл (for(), while()), но понякога също така ще ползваме функции, които ни помагат за итерацията на по-сложни обекти (например рекурсия или клас-итератор). В тази тема, обаче, няма да се занимаваме с по-сложните - за рекурсия има цяла лекция, а за класове-итератори сме споменали накратко в темата за STL, като по-подробно ще ги учите чак в университета.

Търсене

Може би най-простата задача, която бихме срещнали в състезание по информатика, е следната:

Дадени са ни 1 ≤ N ≤ 1000 цели числа {A₀, A₁, …, A_N-1}. Проверете дали числото X се съдържа в тях.

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

Прочитаме числата (ако не са ни дадени в някаква структура, както е в TopCoder)
Сравняваме X с всяко от тях
Ако по някое време намерим съвпадение, връщаме положителен резултат
Ако не намерим съвпадение след като сме итерирали всички числа от A[], връщаме отрицателен резултат

?	По-късно ще видим защо е хубаво масивът, в който пазим числата, да е с 1024 вместо с точно 1000 (колкото е ограничението) елемента. Освен това ще видим, че такива блуждаещи константи по средата на кода не са хубава идея. Но затова - по-късно.

Какво ни трябва? Първо - да можем да четем числа и да изпишем резултата (отново, с изключение на TopCoder). Повече информация за това можете да намерите в тази тема. Второ - масив, в който да пазим числата. Трето - условен оператор, с който да проверяваме дали две числа са равни. Примерна имплементация би била (като тук вече сме прочели числата в масива A):

bool
 findX(int
 N,
 int
 A[1024
],
 int X) {
    for
 (int
 i =
 0
;
 i <
 N;
 i+
+) {
        if
 (A[i] =
= X)
            return
 true
;
    }
    return
 false
;
}

Да усложним малко задачата...

Дадени са ни 1 ≤ N ≤ 1000 цели числа {A₀, A₁, …, A_N-1}. Проверете колко пъти се среща числото X в тях.

Почти същото, като в миналата задача, но този път ще ни трябва допълнителна променлива, в която да пазим търсения резултат.

int
 countX(int
 N,
 int
 A[1024
],
 int X) {
    int
 ans =
 0
;
    for
 (int
 i =
 0
;
 i <
 N;
 i+
+) {
        if
 (A[i] =
= X)
            ans+
+
;
    }
    return
 ans;
}

И още малко...

Дадени са ни 1 ≤ N ≤ 1000 цели числа {A₀, A₁, …, A_N-1}. Намерете колко пъти се среща най-често срещаното от тях.

Тук вече е малко по-различно. Първо забележете, че макар и да имаме по-малко входни данни (нямаме X), задачата е по-сложна. Броят параметри изобщо не е показателен за сложността на дадена задача!

За решението ѝ отново ще ни трябва променлива, в която да пазим най-добрия намерен резултат. Тъй като не знаем кое е най-често срещаното число обаче, ще трябва да направим допълнителна стъпка. Едно лесно и интуитивно (до някъде) решение е да преброим колко пъти се среща всяко от дадените числа, като върнем най-голямата от намерените бройки. За целта ще ползваме вложен цикъл - тоест ще ползваме два пъти итерация - външна, която определя кое число броим в момента, и вътрешна, която брои колко пъти се среща дадено число X в масив. Примерна имплементация би била:

int
 findMaxCount(int
 N,
 int
 A[1024]) {
    int
 ans =
 0
;
    for
 (int
 i =
 0
;
 i <
 N;
 i+
+) {
        int
 cur =
 0
;
        // Броим колко пъти се среща в масива числото A[i]
        for
 (int
 c =
 0
;
 c <
 N;
 c+
+) {
            if
 (A[c] =
= A[i])
                cur+
+
;
        }
        // Ако тази бройка е по-голяма от най-голямата,
        // намерена до сега, я запазваме като нов отговор
        ans =
 max(ans,
 cur);
    }
    return
 ans;
}

Забележете, че вътрешната итерация (вътрешният цикъл) е много сходна с тази от предходната задача. Това е пример за алгоритъм в алгоритъма. Почти всички задачи, които ще решаваме в бъдеще, са от този тип - те са изградени от по-прости функции и/или алгоритми. Всъщност много често е по-удобно да разделим различните алгоритми в различни функции, което прави кода ни по-прегледен. В случая дадените алгоритми са просто по един for-цикъл, с което трудно може да се покажат предимствата на създаване на повече на брой, но по-малки функции. По-нататък, обаче, ще се сблъскаме с много задачи, в които това спестява много код.

Повечето от вас трябва вече да са учили и функции. Това е може би една от съвсем първите теми в синтаксиса на програмен език, така че ако случайно нямате идея за какво говоря, то погледнете малко синтаксис на C/C++ преди да продължите.

Сега да имплементираме същата задача, само че с отделяне на подзадачата като отделна функция.

int
 countX(int
 N,
 int
 A[1024
],
 int X) {
    int
 ans =
 0
;
    for
 (int
 i =
 0
;
 i <
 N;
 i+
+) {
        if
 (A[i] =
= X)
            ans+
+
;
    }
    return
 ans;
}

int
 findMaxCount(int
 N,
 int
 A[1024]) {
    int
 ans =
 0
;
    for
 (int
 i =
 0
;
 i <
 N;
 i+
+)
        ans =
 max(ans,
 countX(N,
 A,
 A[i]));
    return
 ans;
}

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

… и още малко...

Дадени са ни 1 ≤ N ≤ 1000 цели числа {A₀, A₁, …, A_N-1}. Намерете сумата на K-те най-големи от тях (K ≤ N).

Първото нещо, което трябва да забележим, е че тук отново имаме три аргумента - масива с числата, броя числа в него и допълнителен аргумент, който указва колко на брой числа трябва да сумираме. Тази задача е по-сложна най-вече защото трябва да измислим начин, по който да знаем кое число вече сме "ползвали" (тоест вече участва в сумата) и кое не.

Разбира се, отново имаме променлива, в която пазим отговора. В началото тя е инициализирана с 0, тъй като сумата на нула числа е нула. Също така отново ще имаме два цикъла (единият вътрешен (или вложен) в другия). Този път, обаче, циклите ще са до различни числа - единият ще е до K, докато другият - до N. Цикълът, който е до K, ще брои колко от K-те най-големи числа вече сме включили в сумата (очевидно, в началото те ще са 0, и ще приключим, когато те станат K). Вътрешният цикъл ще търси кое е най-голямото число, което все още не сме ползвали в сумата. След като го намерим, ще го добавим в сумата и ще го отбележим като използвано (или посетено).

Как обаче знаем дали дадено число вече е използвано или не? Ще ползваме още един масив с N елемента - масива bool vis[], който ще ни казва именно това. Ако vis[i] == false, то i-тият елемент все още не е използван,. Ако пък vis[i] == true, то въпросният елемент вече е използван. Така във вътрешния цикъл ще търсим най-големия елемент от тези, чиито vis е false.

Ето една възможна имплементация:

int
 sumOfKLargest(int
 N,
 int
 A[1024
],
 int K) {
    // Този тип заделяне на масив (със "static" преди типа)
    // е аналогичен на това да го заделим извън тялото на функцията.
    static
 bool
 vis[1024
];
    
    // Инициализираме елементите му
    for
 (int
 i =
 0
;
 i <
 N;
 i+
+)
        vis[i] =
 false
;
    
    int
 ans =
 0
;
    for
 (int
 i =
 0
;
 i <
 K;
 i+
+) {
        // Намираме индекса на най-голямото все още неизползвано число
        int
 idx =
 -
1
;
        for
 (int
 c =
 0
;
 c <
 N;
 c+
+) {
            if
 (!
vis[c] &
&
 (idx =
=
 -
1
 |
|
 A[idx] < A[c]))
                idx =
 c;
        }
        // Прибавяме стойността на числото към отговора
        ans +
=
 A[idx];
        // Отбелязваме числото като "посетено"
        vis[idx] =
 true
;
    }
    return
 ans;
}

Инициализация

Забележете, че е много важно да инициализираме променливите, които ползваме. Макар и не винаги това да е нужно, то много рядко ви пречи да го правите. Хубава практика е да инициализирате масивите, дори това вече да е станало автоматично по някаква причина. Така няма да изпаднете в ситуацията, в която премествате част от кода и автоматичното инициализиране вече не е изпълнено, или пък се налага да викате дадена функция повече от веднъж, и макар, че при първото викане всичко е било инициализирано, то при следващите не е.

?	На Иванчо са му дали три ябълки. Той е изял две. Колко ябълки има Иванчо? Мислите си че само една? Ама никъде не е казано, колко ябълки е имал Иванчо преди да му дадат трите. Извод - нулирайте си променливите!

Нещо повече, някои компилатори (/me гледа лошо Visual Studio) имат свойството да не се държат много по стандарт - например да инициализират автоматично с нула non-static променливи, или да разрешават заделянето на масив с нефиксирана (преди стартиране на програмата) големина. Това може да ви изиграе много, много лоша шега, като ви даде нула или близо до нула точки на иначе вярна задача (тъй като компилаторът на тестващата система обикновено е GCC, където това не е така).

Задачи

Ето няколко задачи, върху които можете да се упражнявате. Първо решете Grading, която е само итерация и работа с променливи. Следващата стъпка е Bazinga, в която ще трябва да ползвате или масив, или няколко променливи. Следва да тренирате вече вложена итерация, както и по-сложни масиви в задачата

Arrays

Training problems, informatika.bg

Author: Alexander Georgiev
Tags: Trivial, Iteration
Statement | Archive | Online Judge

Arrays. Няколко други задачи:

Shoes Easy

Dean's Cup 2009

Author: Alexander Georgiev
Tags: Easy, Search, Iteration, Sorting
Statement | Archive | Online Judge

ShoesEasy, DigitHoles, EllysTSP.
Две малко по-сложни задачи: Collatz, поради не много ясния размер на масива, който трябва да заделите, и Sudo Ku, поради малко по-дългата си имплементация.

За още задачи вижте секцията Implementation от подготовката на тренировъчната система към този сайт - action.informatika.bg.

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 12018 пъти.