Задаци: Итерација кроз правилне серије бројева¶

Алгоритми и програми у програмском језику C: Итерација кроз правилне серије бројева.

Бројеви од a до b¶

Потребно је исписати све целе бројеве од a до b и да би се то могло урадити потребно је употребити петљу.

Најприроднији начин је да се употреби петља for. Користићемо петљу у којој ћемо бројачкој променљивој i додељивати редом вредности од најмање (то је вредност a) до највеће (то је вредност b) и у сваком пролазу кроз петљу исписивати њену вредност. У иницијализацији петље вредност променљиве i поставићемо на a, у услову ћемо проверавати да ли важи i <= b, док ћемо у кораку петље вредност променљиве i увећавати за један.

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    for (int i = a; i <= b; i++)
        printf("%d\n", i);
    return 0;
}

Свака петља for може се једноставно изразити и помоћу петље while. Иницијализацију i = a потребно је извршити непосредно пре петље while, услов петље је i <= b, док се корак i++, i += 1 или i = i + 1 додаје као последња наредба у телу петље.

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    int i = a;
    while (i <= b)
    {
        printf("%d\n", i);
        i++;
    }
    return 0;
}

Задатак је могуће решити и исписивањем тренутне вредности променљиве a у петљи while, при чему се при сваком проласку кроз петљу вредност променљиве a увећа за 1, све док a не достигне вредност већу од b. Мана таквог решења је да након исписа бројева, оригинални интервал $[a, b]$ није више доступан.

Бројање у игри жмурке¶

Прочитај текст задатка.

Бројачку променљиву потребно је иницијализовати на $5$ , итерацију вршити док је њена вредност мања или једнака од $x$ и у сваком кораку је увећавати за $5$ (помоћу i += 5 или i = i + 5). Наравно, ово је могуће реализовати било уз помоћу петље for било петље while.

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int x;
    scanf("%d", &x);
    for (int i = 5; i <= x; i += 5)
        printf("%d\n", i);
    return 0;
}

Још један могући приступ (додуше, мање ефикасан од претходног), је да се у петљи набрајају сви бројеви између $5$ и $x$ , да се за сваки проверава да ли је дељив са $5$ и исписује се само ако јесте дељив. Кажемо да међу свим бројевима од 5 до горње границе филтрирамо оне дељиве са 5.

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int x;
    scanf("%d", &x);
    for (int i = 5; i <= x; i++)
        if (i % 5 == 0)
            printf("%d\n", i);
    return 0;
}

Троцифрени парни бројеви¶

Прочитај текст задатка.

Потребно је исписати све троцифрене парне бројеве редом, почевши од најмањег троцифреног парног броја из целобројног интервала $[a, b]$ до највећег троцифреног парног броја из тог интервала. Троцифрени бројеви припадају целобројном интервалу $[100, 999]$ . Дакле, тражени бројеви припадају пресеку та два интервала тј. интервалу $[max (a, 100), min (b, 999)]$ . Пошто се траже само парни бројеви из интервала добијеног пресеком, набрајање треба почети од његове леве границе, ако је она парна, односно од њеног следбеника ако је она непарна, а завршити на десној граници ако је она парна тј. на њеном претходнику ако је она непарна. На тај начин добијамо интервал $[o d, d o]$ чије су границе парни бројеви и чије све парне бројеве треба исписати (провера да ли је број паран се своди на израчунавање остатака при дељењу са 2).

Само набрајање бројева можемо извршити било помоћу петље for, било помоћу петље while. У оба случаја бројачку променљиву ћемо иницијализовати на почетну вредност $o d$ , услов петље ће бити то да је вредност бројачке променљиве мања или једнака завршној вредности $d o$ , док ће корак петље бити увећање бројачке променљиве за 2. Нагласимо и да променљива не може да носи име do, јер је то резервисана реч у већини програмских језика.

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    int x = a > 100 ? a : 100;
    int y = b < 999 ? b : 999;
    if (x % 2 != 0)
        x++;
    if (y % 2 != 0)
        y--;
    for (int i = x; i <= y; i += 2)
        printf("%d\n", i);
    return 0;
}

Други начин (мање ефикасан од претходног) је заснован на филтрирању. Могуће је да се итерација (набрајање) врши редом по свим бројевима из целобројног интервала $[100, 999]$ , да се за сваки број проверава да ли припада интервалу $[a, b]$ (да ли је између $a$ и $b$ ) и да ли је паран, и да се број исписује само ако су оба услова испуњена.

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    for (int i = 100; i <= 999; i++)
        if (a <= i && i <= b && i % 2 == 0)
            printf("%d\n", i);
    return 0;
}

Одбројавање уназад¶

Прочитај текст задатка.

Потребно је исписати све бројеве од $a$ до 0. Задатак можемо решити помоћу петље for или помоћу петље while. Ако користимо петљу for, тада ћемо променљивој $i$ (бројачка променљива петље for), додељивати редом вредности од највеће (тј. од вредности $a$ ) до најмање (тј. до вредности $0$ ) и у сваком пролазу кроз петљу исписивати њену вредност. Умањивање бројачке променљиве за један се може постићи изразом i--, i -= 1 или i = i - 1.

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a;
    scanf("%d", &a);
    for (int i = a; i >= 0; i--)
        printf("%d\n", i);
    return 0;
}

Решење са петљом while се може имплементирати и без помоћне бројачке промељиве (тако што се умањује вредност a).

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a;
    scanf("%d", &a);
    while (a >= 0)
    {
        printf("%d\n", a);
        a--;
    }
    return 0;
}

Најаве емисије у правилним временским интервалима¶

Прочитај текст задатка.

Рад са временом се олакшава ако се преведе дато време у број минута протеклих од поноћи и обратно. Тако ћемо времена почетка и завршетка филма изразити у минутима. Времена приказивања најаве ћемо израчунати и исписати у оквиру петље у којој се користи променљива која представља време текуће најаве (опет у минутима). Полазећи од времена почетка филма у сваком кораку петље приказаћемо текуће време најаве и увећати га за интервал у минутима, док не престигне време завршетка филма. Наравно, ово је могуће имплементирати било петљом for, било петљом while.

Предложено решење задатка

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int hp, mp, hk, mk, v;
    scanf("%d%d%d%d%d", &hp, &mp, &hk, &mk, &v);
    int p = hp * 60 + mp;
    int k = hk * 60 + mk;
    for (int i = p; i <= k; i += v)
    {
        int hi, mi;
        hi = i / 60;
        mi = i % 60;
        printf("%d:%d\n", hi, mi);
    }
    return 0;
}

Подела интервала на једнаке делове¶

Прочитај текст задатка.

Потребно је прво одредити равномерно растојање $d x$ , између $n$ бројева интервала $[a, b]$ тако да је први број $a$ , а последњи $b$ . Таквих $n$ бројева деле интервал $[a, b]$ на $n - 1$ једнаких делова, па је растојање $d x$ између свака два броја $\frac{b - a}{n - 1}$ . Након тога је могуће применити исту технику и делује да га је могуће решити петљом облика for (double x = a; x <= b; x += dx).

Међутим, због непрецизности до којих може доћи при раду са реалним бројевима, могуће је да се вредност растојања $d x$ не може сасвим прецизно репрезентовати и да променљива dx = (b-a) / (n-1) заправо садржи вредност која је мало већа од стварне вредности растојања $d x$ . Зато је могуће да се деси да вредност променљиве x у последњој итерацији тек за мало премаши вредност променљиве b и да се због тога прескочи исписивање десног краја интервала тј. тачке $b$ , што је грешка.

Због тога је ипак пожељно итерацију контролисати бројачем помоћу којег се броје тачке које су исписане, тј. помоћу петље облика for (int i = 0; i < n; i++). Једна могућност је да се у реалној променљивој $x$ чува вредност текуће тачке, да се пре почетка петље она инцијализује на вредност $a$ , а да се у сваком кораку петље она исписује и затим увећава за вредност $d x$ .

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n;
    double a, b;
    scanf("%d", &n);
    scanf("%lf%lf", &a, &b);
    double dx = (b - a) / (n - 1);
    double x = a;
    for (int i = 0; i < n; i++)
    {
        printf("%.5lf\n", x);
        x += dx;
    }
    return 0;
}

Може се приметити да су тражени бројеви $a, a + d x, a + 2 \cdot d x, . . ., a + (n - 1) \cdot d x$ , па се они могу приказивати као бројеви $a + i \cdot d x$ за све целе бројеве $i$ од $0$ до $n - 1$ (кажемо да пресликавамо бројеве од $0$ до $n - 1$ функцијом $f (i) = a + i \cdot d x$ ).

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n;
    double a, b;
    scanf("%d", &n);
    scanf("%lf%lf", &a, &b);
    double dx = (b - a) / (n - 1);
    for (int i = 0; i < n; i++)
        printf("%.5lf\n", a + i * dx);
    return 0;
}

Геометријска серија¶

Прочитај текст задатка.

Потребно је исписати све природне бројеве из интервала $[a, b]$ , од којих је први број који се исписује једнак $a$ , а сваки следећи три пута већи од претходног.

Задатак ћемо решити тако што ћемо у променљивој коју ћемо мењати кроз петљу одржавати текућу вредност ове серије бројева. Променљиву ћемо иницијализовати на вредност $a$ , а затим у петљи проверавати да ли јој је вредност мања или једнака $b$ и ако јесте исписиваћемо је и множићемо јој вредност са три. На оваквом месту је прилично природно употребити петљу while.

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    int i = a;
    while (i <= b)
    {
        printf("%d\n", i);
        i *= 3;
    }
    return 0;
}

Приметимо да се јасно могу идентификовати четири основне целине петље: иницијализација (бројачка променљива се иницијализује на вредност $a$ ), услов (проверава се да ли је текућа вредност бројачке променљиве мања или једнака броју $b$ ), тело (исписује се вредност бројачке променљиве) и корак (вредност бројачке променљиве се поставља на стару вредност помножену бројем 3). Зато је најелегантнији начин имплементације употреба петље for.

Приметимо и да је серија бројева који се исписују геометријска серија бројева, док класична петља генерише аритметичку серију - разлика је заправо само у томе да ли се у кораку врши увећавање сабирањем или множењем са датом вредношћу (да ли се користи += или оператор *=).

Приметимо и да се сваки наредни елемент серије израчунава само на основу претходног (није потребно памтити све елементе од почетка). За овакве серије кажемо да су рекурентне (за ову серију важи да је $a_{0} = a$ , док је $a_{i + 1} = 3 \cdot a_{i}$ , за све природне бројеве $i \geq 0$ ).

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    for (int i = a; i <= b; i *= 3)
        printf("%d\n", i);
    return 0;
}