Још неке могућности генератора колекција¶

Завршавање колекције пре краја метода¶

Метод може да заврши са генерисањем колекције и пре него што стигне до своје последње наредбе. Када желимо да на такав начин прекинемо извршавање метода, користимо наредбу yield break, као што је показано у примеру који следи.

Написати метод који за две дате колекције целих бројева враћа колекцију свих елемената прве, а затим ако је потребно и друге дате колекције, све до првог парног броја, не укључујући тај број. Написати и програм који илуструје рад метода.

Довољно је да при наиласку на паран број у било којој од две колекције извршимо поменуту наредбу yield break. Ако се у двема датим колекцијама не појави ниједан паран број, у резултујућој колекцији ће се наћи сви елементи обе дате колекције, а у том случају са генерисањем елемената се престаје када се изврши последња наредба генераторског метода.

Програм исписује

Elementi do prvog parnog su  -1 -3 5. Njihov zbir je 1.

Приметимо да би обична наредба break у првој foreach петљи метода изазвала наставак извршавања метода од следеће наредбе, а то је друга петља, што није понашање које желимо у овом примеру. Обична наредба return написана у методу DoParnog би била синтаксна грешка. Према томе, једини начин да прекинемо извршавање метода без могућности повратка и продужавања колекције је наредба yield break. Њеним извршавањем завршавамо генерисање колекције и јављамо делу програма који конзумира колекцију да је стигао до њеног краја.

Употреба набрајача при генерисању колекција¶

У овом примеру је потребно да кроз колекцију итерирамо на начин који нам даје више контроле него наредба foreach. Као што знамо, у ту сврху можемо да користимо набрајач (енумератор).

Написати метод који за две дате монотоно неопадајуће колекције целих бројева враћа неопадајућу колекцију која се састоји од свих елемената те две колекције. Написати и програм који илуструје рад метода.

Ово је у суштини познати проблем спајања два сортирана низа (merge алгоритам, који је део алгоритма merge sort), само се уместо низова користе колекције. Користићемо два набрајача, за сваку колекцију по један. На тај начин можемо да напредујемо кроз обе колекције упоредо. Тачније, након поређења текућих елемената у две колекције, враћамо мањи од та два елемента и напредујемо у колекцији из које је тај елемент. Када стигнемо до краја једне од датих колекција, треба још да вратимо све елементе преостале колекције, један по један.

Напомињемо да се приликом креирања набрајача над резултатом неког метода f() који генерише колекцију, тј. приликом извршавања метода f().GetEnumerator(), сам метод f() још увек не извршава, нити започиње са извршавањем. Креирање набрајача је само нека врста иницијализације, односно припреме за итерирање кроз колекцију коју генерише метод f().

Рекурзивни методи који генеришу колекције¶

Метод који генерише колекцију може у свој резултат да укомпонује резултате других метода који враћају колекције. На пример, ако метод f треба да врати све целе бројеве које враћају методи f1, f2 и f3 редом, он може да буде написан овако:

static IEnumerable<int> f1() { ... }
static IEnumerable<int> f2() { ... }
static IEnumerable<int> f3() { ... }

static IEnumerable<int> f()
{
    foreach (int x in f1())
        yield return x;
    foreach (int x in f2())
        yield return x;
    foreach (int x in f2())
        yield return x;
}

Метод који генерише колекцију може да овај начин да користи и сам себе, тј. да буде рекурзиван.

Написати метод који за дате \(k\) и \(m\) враћа све \(k\)-цифрене бројеве са цифрама од 1 до \(m\) у растућем поретку. Написати и програм који илуструје рад метода.

Дефинисаћемо рекурзиван метод Kombinacije са три параметра. Први параметар је већ формирани почетак (префикс) броја, који ће рекурзивно да буде допуњен на све могуће начине. Други параметар је број цифара које је још потребно дописати на формирани префикс. У иницијалном позиву из метода Main овај параметар има вредност k, а у каснијим позивима се смањује. Трећи параметар је највећа дозвољена цифра m.

Метод Kombinacije је позван из метода Main тако да генерише троцифрене бројеве са цифрама од 1 до 5 у растућем поретку. Зато програм исписује:

123 124 125 134 135 145 234 235 245 345

Приметимо да ни у овом програму не долази до гомилања елемената колекције, сваки од њих се само ланчано прослеђује из позива највеће дубине преко позива мање дубине све до наредбе исписивања у методу Main.

Примена у графичким апликацијама¶

У последњем примеру овог прилога илустроваћемо графичко решење познатог проблема ханојских кула. Подсетимо се најпре поставке задатка.

Дата су три једнака усправна штапа. На први од њих наређано је \(n\) дискова различите величине. Дискови су наређани редом по величини, тако да је највећи диск доле, а најмањи горе. Потребно је да се свих \(n\) дискова премести са првог штапа на трећи, користећи други штап као помоћни. При томе треба поштовати следећа правила:

• дозвољено је једино да се узме горњи (највиши) диск са неког штапа и да се стави на врх гомиле на неком другом штапу

• дискови могу да се премештају искључиво један по један

• није дозвољено ставити већи диск преко мањег

Означимо штапове редом словима A, B, C. Низ корака који представљају решење добија се следећим једноставним рекурзивним поступком:

using System;
class Program
{
    static void Hanoj(int n, string poc, string pom, string kraj)
    {
        if (n > 0)
        {
            Hanoj(n - 1, poc, kraj, pom);
            Console.WriteLine($"Kotur {n} sa {poc} na {kraj}");
            Hanoj(n - 1, pom, poc, kraj);
        }
    }

    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Hanoj(n, "A", "B", "C");
    }
}

Размотримо како би могао да се испрограмира графички приказ овог решења.

Дизајн, компоненте

Од компоненти корисничког интерфејса, можемо да искористимо поље типа NumericUpDown за задавање броја дискова и дугме (Button) за покретање решења. Приказивање намеравамо да успоримо, тако да после приказа сваког корака програм застане да би корисник могао да испрати решење. Зато ћемо апликацији да додамо и тајмер (Timer), са идејом да се на сваки откуцај (tick) тајмера изврши и прикаже по један корак решења.

Репрезентација податка

Да бисмо могли да приказујемо стање после сваког корака, треба да памтимо који дискови се налазе на ком штапу. Из описа проблема јасно је да се сваки штап понаша као стек, јер се дискови узимају само са врха и додају само на врх. Према томе, за представљање тренутног распореда дискова можемо да користимо листу stap, која се састоји од три стека. Уместо слова A, B, C, која означавају штапове, можемо да користимо бројеве 0, 1, 2 као индексе тих штапова у листи stap.

Решавање

Сваки корак је одређен паром индекса i, j, где овај пар означава да се узима диск са штапа i и ставља на штап j. Сам корак, односно премештање једног диска, у програму може да се изведе овако:

int disk = stap[i].Pop();
stap[j].Push(disk);

Желимо да на догађај тајмера извршимо један корак решења. Зато нам је погодно да дато рекурзивно решење напишемо у облику метода који генерише колекцију потеза, односно парова бројева. Нови облик метода који решава задатак може да изгледа овако:

static IEnumerable<Tuple<int, int>> HanojskeKule(
    int n, int poc, int pom, int kraj)
{
    if (n > 0)
    {
        foreach (var x in HanojskeKule(n - 1, poc, kraj, pom))
            yield return x;

        yield return new Tuple<int, int>(poc, kraj);

        foreach (var x in HanojskeKule(n - 1, pom, poc, kraj))
            yield return x;
    }
}

Преостали посао обухвата иницијализацију, писање метода за цртање тренутног стања, као и неколико краћих метода који реагују на остале догађаје (учитавање форме, клик на дугме за покретање решења, догађај тајмера). Тај део посла нећемо детаљно описивати, већ вам препуштамо да га самостално проучите читајући дати кôд и коментаре. У наставку је комплетан садржај фајла Form1.cs.