Задаци: Позициони запис броја

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

Број и збир цифара броја

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

Серију цифара у декадном запису броја (здесна налево) можемо одредити операцијом целобројног дељења са 10, као што смо то већ видели. Последња декадна цифра броја одређује се као остатак при дељењу са 10, а уклања се када се израчуна целобројни количник са 10. Подсетимо се, један начин да одредимо последње три цифре броја био јe следећи итеративни поступак.

c0 = n mod 10; n = n div 10;
c1 = n mod 10; n = n div 10;
c2 = n mod 10; n = n div 10;

При том, ако је почетни број био троцифрен, тада ће вредност променљиве n након извршавања овог фрагмента кода бити 0.

За разлику од ранијих задатака у којима је број цифара био фиксиран (и обично мали), у овом задатку није унапред познат број цифара броја. Зато је цифре броја потребно одређивати у петљи. У сваком кораку текућу цифру одређујемо као \(n\mod 10\), а затим је уклањамо тако што вредност променљиве \(n\) замењујемо вредношћу \(n \div 10\). Петља се завршава када се уклоне све цифре и када вредност променљиве \(n\) постане нула. Да би се и у случају када је број \(n\) једнак 0 ова цифра обрадила мора се организовати петља са постусловом do-while. У неким случајевима, на пример, код бројања цифара, то утиче на исправност алгоритма, док у неким другим, на пример, код сабирања свих цифара, то није неопходно (наиме обрада цифре подразумева њено додавање на збир, а сасвим је свеједно да ли ће се збир увећати за цифру нула или ће остати непромењен - ефекат је исти). Тако се добија следећи алгоритам.

do {
    // ...
    c = n % 10;
    n /= 10;
    // ...
} while (n != 0);

Када знамо како се одређује серија цифара, онда је лако одредити њене статистике - број и збир. Број цифара се израчунава бројањем елемената серије, на стандардни начин. Бројач се пре петље иницијализује на нулу и увећава се за један у телу петље, приликом одређивања сваке наредне цифре. Збир се израчунава сабирањем елемената серије, опет на веома стандардан начин. У почетку се променљива која треба да садржи збир иницијализује на нулу (неутрални елемент за сабирање), а затим се у сваком кораку петље увећава за вредност тренутно одређене цифре броја (она је одређена вредношћу \(n\mod 10\)).

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, i = 0, s = 0;
    scanf("%d", &n);
    do {
        i++;
        int c = n % 10;
        s += c;
        n /= 10;
    } while (n > 0);
    printf("%d %d", i , s);
    return 0;
}

Да ли запис броја садржи цифру

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

Провера да ли број садржи цифру заснива се на алгоритму издвајања цифара броја сдесна налево и на алгоритму претраге којим се проверава да ли у серији постоји тражени елемент тј. елемент са траженим својством.

Као што смо видели, постоје разни начини да се алгоритам претраге имплементира. Једна променљива би на почетку имала вредност 0, па би се у тренутку проналаска тражене цифре постављала на 1 (ефикасности ради, у том тренутку би се петља могла прекинути, било наредбом break било ојачавањем услова петље у којем би се тражило да претрага траје само док је вредност те променљиве 0).

Рецимо и да уобичајени алгоритам издвајања цифара броја сдесна постепено мења његову вредност. Зато, ако је потребно након претраге имати оригиналну вредност броја на располагању (а у овом задатку јесте, да би се могла исписати одговарајућа порука), онда је потребно направити његову копију пре претраге.

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, c, s = 0;
    scanf("%d%d", &n, &c);
    int m = n;
    do {
        if (m % 10 == c)
        {
            s = 1;
            break;
        }
        m /= 10;
    } while (m > 0);
    printf("broj %d", n);
    printf(s ? " " : " ne ");
    printf("sadrzi cifru %d", c);
    return 0;
}

Различите цифре

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

Постоје различити начини да се провери да ли су све цифре броја различите.

Један је да се за сваку цифру броја провери да ли се јавља у префиксу броја испред себе (делу броја испред те цифре). На пример, за број \(132345\) проверавамо да ли се цифра \(5\) јавља у броју \(13234\), пошто се не јавља, проверавамо да ли се цифра \(4\) јавља у броју \(1323\), пошто се не јавља, проверавамо да ли се цифра \(3\) јавља у броју \(132\) и пошто се јавља, можемо да закључимо да полазни број нема све различите цифре. Дакле, у петљи у којој се одређују цифре броја сдесна налево, за сваку цифру одређену као n % 10 проверавамо да ли је садржана у запису броја n / 10 добијеног њеним уклањањем. У основни лежи алгоритам претраге (испитујемо да ли постоји цифра која задовољава услов да се појављује) - први пут када се у петљи наиђе на цифру која је садржана у префиксу испред ње прекида се са претрагом.

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, d = 1;
    scanf("%d", &n);
    while (n >= 10)
    {
        int c = n % 10;
        n /= 10;
        int m = n;
        do {
            if (m % 10 == c)
            {
                d = 0;
                break;
            }
            m /= 10;
        } while (m > 0 && d);
    }
    printf(d ? "DA" : "NE");
    return 0;
}

Армстронгов број

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

Проверу да ли је број Армстронгов можемо разложити на неколико подзадатака.

Прво, на основу дефиниције Армстронговог броја изложилац на који ће се степеновати све цифре директно зависи од броја цифара броја (на пример, за троцифрене бројеве рачуна се збир кубова цифара, а за петоцифрене бројеве збир петих степена цифара). Зато је потребно да пребројимо цифре учитаног броја.

Друго, потребно је да умемо да рачунамо степене цифара. Један начин да то урадимо је да искористимо библиотечку функцију за степеновање (pow), међутим, пошто она ради са реалним бројевима написаћемо сами петљу за специјалан случај степеновања када су основа и изложилац природни бројеви. Ако рачунамо \(x^n\), потребно је да израчунамо производ у којем се \(n\) пута јавља чинилац \(x\). Зато је потребно да производ иницијализујемо на \(1\), а затим да га у петљи чије се тело извршава \(n\) пута помножимо са \(x\) у којем се такође израчунава производ.

Када умемо да рачунамо степен, потребно је да израчунамо збир степена цифара броја. Серију цифара броја одређујемо на уобичајени начин, здесна на лево, коришћењем целобројног дељења са 10. За сваку издвојену цифру израчунавамо степен и добијени резултат додајемо на текући збир, који пре петље иницијализујемо на нулу. Дакле, у сваком кораку пресликавамо текућу цифру степеном функцијом и сабирамо серију добијених слика, тј. примењујемо алгоритам сабирања пресликане серије.

На крају веома једноставно можемо проверити да ли је број Армстронгов тако што га упоредимо са добијеним збиром степена.

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

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n;
    scanf("%d", &n);
    int n0 = n, b = 0;
    while (n > 0)
    {
        b++;
        n /= 10;
    }
    n = n0;
    long long s = 0;
    while (n != 0)
    {
        int c = n % 10;
        n /= 10;
        int p = 1;
        for (int i = 1; i <= b; i++)
            p *= c;
        s += p;
    }
    printf(s == n0 ? "DA" : "NE");
    return 0;
}

Трансформација броја у производ цифара

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

Да би се израчунао производа цифара датог броја, потребно је одредити серију цифара броја и пронаћи производ елемената те серије. У петљи, прoизвод, чија је вредност на почетку 1, множићем, редом, цифрама броја, почев од цифре јединица. Цифру јединица броја одређујемо као остатак при дељењу броја са 10. Дељењем броја са 10 уклањамо цифру јединица па у следећем извршавању тела петље, приступамо следећој цифри. Понављамо поступак док полазни број не постане 0.

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

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n;
    scanf("%d", &n);
    int i = 0;
    while (n >= 10)
    {
        int m = n;
        int p = 1;
        do {
            p *= m % 10;
            m /= 10;
        } while (m != 0);
        n = p;
        printf("%d\n", n);
        i++;
    }
    printf("%d", i);
    return 0;
}

Најмањи број са највећим збиром парних цифара

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

У овом задатку се комбинују разне технике приказане у ранијим задацима. Прво, потребно је уносити серију бројева, све док се не учита број -1. Међу учитаним бројевима анализирамо само оне који садрже бар једну парну цифру, тј. вршимо филтрирање серије на основу услова да садржи бар једну парну цифру. Испитивање да ли број садржи бар једну парну цифру засновано је на комбинацији алгоритма одређивања цифара броја и алгоритму претраге. Међу бројевима који садрже парне цифре одређујемо максимум (врши се одређивање максимума тј. минимума филтриране серије). Максимум се одређује у односу на релацију лексикографског поретка. Прво се пореди збир парних цифара. Цифре броја издвајамо и сабирамо оне које су парне, што је алгоритам одређивања статистике филтриране серије.

Имајући речено у виду, можемо описати основну варијанту алгоритма.

Имплементираћемо петљу која одређује да ли декадни запис датог броја садржи неку парну цифру. У петљи одређујемо и уклањамо цифру по цифру сдесна коришћењем целобројног дељења са 10. Иницијализоваћемо помоћну променљиву p на нулу. Ако је цифра парна (тј. ако јој је остатак при дељењу са 2 једнак нули), тада променљиву p постављамо на 1. Ако се током извршавања петље не пронађе парна цифра променљива p остаје 0.

Имплементираћемо и петље које одређују збир цифара декадног записа датог броја (збир који ћемо иницијализовати на нулу ћемо увећавати за једну по једну цифру броја).

У бесконачној петљи можемо учитавати број по број и након сваког учитаног броја проверавати да ли је учитана вредност -1. Ако јесте, прекидаћемо петљу. За сваки учитани број провераваћемо да ли садржи неку парну цифру и број ћемо даље обрађивати само ако садржи парну цифру. Одржаваћемо променљиву max која чува вредност до сада најбољег учитаног елемента (најмањег до сада учитаног броја који садржи бар једну парну цифру и има збир парних цифара већи или једнак збировима парних цифара свих до сада учитаних бројева). Одржаваћемо и променљиву pmax која ће указивати на то да ли је до сада учитан неки број који садржи парну цифру, тј. да ли је променљива max постављена (друга могућност је да максимум иницијализујемо на неку специјалну, негативну вредност). За сваки учитани број за који је утврђено да садржи парну цифру, провераваћемо да ли је бољи од свих раније учитаних тј. да ли вредност променљиве max треба ажурирати и поставити на тај број. Постоји неколико случајева када је то потребно урадити:

  • први случај је када је ово први од свих до сада учитаних бројева који садржи парну цифру (што лако испитујемо на основу вредности променљиве pmax), и у том случају нема потребе за поређењима са вредношћу променљиве max (она у том тренутку ни нема постављену вредност),

  • други случај је када је збир парних цифара тренутног броја мањи од вредности збира парних цифара броја max,

  • трећи случај је када су та два збира једнака, али је тренутни број мањи од броја max.

У првом случају треба ажурирати и вредност променљиве pmax и поставити је на вредност 1 (а не смета да се то уради и у осталим случајевима, увек када се ажурира вредност max).

На крају, по завршетку бесконачне петље у којој се учитавају сви бројеви, на основу уведене променљиве знамо да ли је био учитан бар један број чији декадни запис садржи парну цифру и ако јесте, исписујемо вредност променљиве max, а ако није, исписујемо вредност -1.

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int max, pmax = 0;
    while (1)
    {
        int n;
        scanf("%d", &n);
        if (n == -1)
            break;
        int p = 0;
        int m = n;
        do {
            if (m % 2 == 0)
                p = 1;
            m /= 10;
        } while (m != 0 && !p);
        if (p)
        {
            int zn = 0;
            m = n;
            do {
                if (m % 2 == 0)
                    zn += m % 10;
                m /= 10;
            } while (m != 0);
            int zmax = 0;
            m = max;
            do {
                if (m % 2 == 0)
                    zmax += m % 10;
                m /= 10;
            } while (m != 0);
            if (!pmax || zn > zmax || (zn == zmax && n < max))
            {
                max = n;
                pmax = 1;
            }
        }
    }
    if (pmax)
        printf("%d", max);
    else
        printf("-1");
    return 0;
}

Овако дефинисан алгоритам исправно ради, али га је могуће оптимизовати у неколико аспеката. Један од проблема је то што се приликом сваког упоређивања изнова рачуна и збир цифара броја max и збир цифара тренутно учитаног броја. Зато има смисла уз променљиву max чувати и променљиву која садржи збир њених парних цифара. Приликом обраде сваког новог броја који садржи бар једну парну цифру, треба израчунати њен збир парних цифара, проверити да ли је испуњен неки од наведених услова за ажурирање вредности max и ако јесте, уз ажурирање вредности max на вредност текућег броја, променљивој која чува збир парних цифара броја max треба доделити раније израчунату вредност збира парних цифара текућег броја.

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

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int max, zmax = -1;
    while (1)
    {
        int n;
        scanf("%d", &n);
        if (n == -1)
            break;
        int p = 0;
        int m = n;
        do {
            if (m % 2 == 0)
                p = 1;
            m /= 10;
        } while (m != 0 && !p);
        if (p)
        {
            int zn = 0;
            m = n;
            do {
                if (m % 2 == 0)
                    zn += m % 10;
                m /= 10;
            } while (m != 0);
            if (zn > zmax || (zn == zmax && n < max))
            {
                max = n;
                zmax = zn;
            }
        }
    }
    if (zmax != -1)
        printf("%d", max);
    else
        printf("-1");
    return 0;
}

Број формиран од датих цифра с лева на десно

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

Читамо цифру по цифру са стандардног улаза, све док не дођемо до краја и формирамо број додајући му прочитану цифру на десну страну (као цифру најмање тежине). Формирање броја на основу цифара с лева надесно разматрали смо и раније. Подсетимо се, алгоритам се назива Хорнерова шема и на основу тог алгоритма број се гради тако што се у сваком кораку претходна вредност броја помножи са 10 и добијени производ се увећа за вредност наредне цифре (тако се цифра допише на десни крај претходног броја). Анализирајмо пример у којем учитавамо редом цифре 3, 2, 7 и 5 и треба да добијемо број 3275. На основу дефиниције позиционог записа тај број је једнак вредности израза \(3\cdot 10^3+2\cdot 10^2+7\cdot 10+5\). Међутим, претходни израз можемо израчунати на следећи начин \(((3\cdot 10+2)\cdot 10+7)\cdot 10+5\), што доводи до Хорнеровог поступка.

Пошто број цифара није унапред познат, цифре ћемо учитавати у петљи којом учитавамо бројеве до краја стандардног улаза. Број који формирамо памтићемо у променљивој n коју иницијализујемо на нулу. Када прочитамо цифру, додајемо је као цифру јединица на до сада формирани број. Додавање цифре јединица на број n, постижемо тако што помножимо броја n са 10 и додамо му учитану цифру. Ако унесемо \(k\) цифара, на описан начин цифру коју смо прву прочитали множићемо са 10 тачно \(k-1\) пут, другу прочитану цифру множимо са 10 тачно \(k-2\) пута, и тако редом. Последњу прочитану цифру не множићемо са 10 (то је цифра јединица).

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n = 0, c;
    while (scanf("%d", &c) != EOF)
        n = n * 10 + c;
    printf("%d", n);
    return 0;
}

Број формиран од датих цифара здесна на лево

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

Читамо цифру по цифру са стандардног улаза, све док не дођемо до краја и формирамо број додавајући му прочитану цифру на леву страну (као цифру највеће тежине). Формирање броја на основу цифара здесна налево разматрали смо и раније. Цифре се учитавају здесна на лево па су њихове позиције редом цифра јединица, цифра десетица, стотина и тако даље. На пример ако учитамо цифре редом 3, 2, 7 и 5, треба да добијемо број 5723. Тај број можемо формирати као \(3+2\cdot 10+7\cdot 10^2+5\cdot 10^3\). Тежину текуће цифре можемо одредити уз помоћ променљиве у којој памтимо одговарајући степен броја 10.

Пошто број цифара није унапред познат, цифре ћемо учитавати у петљи којом учитавамо бројеве до краја стандардног улаза. Број који формирамо памтићемо у променљивоj n коју иницијализујемо на нулу, а тежину цифре, тј. степен броја 10 у променљивој s коју иницијализујемо на 1. Цифру додајемо броју n с лева тако што број n увећамо за производ те цифре и одговарајућег степена броја 10 (променљиве s). У сваком кораку вредност променљиве s коригујемо множећи је са 10 (тако ће, с обзиром да је иницијализована на вредност 1, она редом узимати вредности 1, 10, 100, 1000 …).

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n = 0, c, s = 1;
    while (scanf("%d", &c) != EOF)
    {
        n = n + c * s;
        s *= 10;
    }
    printf("%d", n);
    return 0;
}

Замени цифре 0 са 5

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

У решењу овог задатка комбинујемо алгоритам одређивања серије цифара броја здесна налево, заснован на целобројном дељењу са 10 и алгоритам формирања броја од серије његових цифара здесна налево. Издвајаћемо цифру по цифру полазног броја и додаваћемо их на почетак новог броја, при чему ћемо проверавати да ли је тренутна цифра једнака цифри коју треба заменити. Ако јесте, на почетак броја додаће се цифра којом се мења цифра коју треба заменити, а ако није, додаће се тренутна цифра.

Имплементираћемо петљу која мења цифру 0 цифром 5. Променљиву која ће садржати модификовани број ћемо пре петље иницијализовати на нулу. Увешћемо и променљиву која одређује тежину наредне цифре и иницијализоваћемо је на 1 (тежина цифре јединица). У петљи ћемо издвајати последњу цифру текуће вредности броја n (одређивањем остатка при дељењу са \(10\)), уклањати је из броја (одређивањем целобројног количника броја n са 10) и проверавати да ли је цифра јединица једнака 0. Ако јесте, нови број ћемо увећавати за производ цифре 5 и текуће тежине, а у супротном за производ текуће цифре и текуће тежине. Након тога ћемо тежину увећати \(10\) пута тј. постављаћемо је на тежину наредне цифре. Тело петље се понавља док се из датог броја n не издвоје све цифре, тј. док вредност n не постане \(0\).

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, m = 0, t = 1;
    scanf("%d", &n);
    do {
        int c = n % 10;
        m += (c == 0 ? 5 : c) * t;
        n /= 10;
        t *= 10;
    } while (n > 0);
    printf("%d", m);
    return 0;
}

Децимале броја 1/n

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

Због јако великог броја децимала (\(k\) може бити и 1000) не можемо користити рад са реалним бројевима (тип double подржава највише 15-16 децимала).

Децимале одређујемо стандардним поступком дељења бројева. Размотримо, на пример, како се одређују прве три децимале броја \(\frac{1}{7}\).

1 : 7 = 0.142
10
 7
--
 30
 28
 --
  20
  14
  --
   6

Кренули смо од броја 1, помножили смо га са 10 (спустили наредну нулу), одредили смо количник са 7 и тако смо добили прву децималу 1. Након тога смо од броја 10 одузели производ броја 1 и броја 7 и тако добили број 3. Приметимо да је број 3 заправо остатак при дељењу броја 10 бројем 7. Након тога, помножили смо број 3 бројем 10, одредили смо количник са 7 и тако добили наредну децималу 4. Након тога, смо од броја 30 одузели количник броја 4 и броја 7 и тако добили број 2, што је заправо остатак при дељењу броја 30 бројем 7. Помножили смо 2 бројем 10, одредили количник са 7 и добили наредну децималу 2. Уједно смо припремили и наредни корак тако што смо од броја 20 одузели производ бројева 2 и 7 и тако добили број 6, што је заправо, остатак при дељењу бројева 20 и 7.

Приметимо да се у сваком кораку понавља исти поступак. Претходни број множимо са 10, а наредну децималу и наредни број одређујемо као целобројни количник и остатак добијеног производа бројем \(n\). Овај корак треба поновити тачно \(k\) пута.

broj = 1;
ponovi k puta:
    decimala = (10 * broj) div n;
    broj = (10 * broj) mod n;

Покажимо и формално да се на овај начин исправно добијају децимале броја. Претпоставимо да је \(0\leq x<n\), и да је

\[\frac{x}{n}=0,a_1a_2\ldots a_k\ldots\]

Тада је

\[10\cdot\frac{x}{n}=a_1,a_2\ldots a_k\ldots\]

Пошто је \(0,a_2\ldots a_k\ldots<1\), а \(0\leq a_1<10\), важи да је

\[a_1=\left\lfloor{\frac{10\cdot x}{n}}\right\rfloor=(10\cdot x)\div n\]

На основу дефиниције целобројног количника и остатка важи да је \(10\cdot x=((10\cdot x)\div n)\cdot n+(10\cdot x)\mod n\). Зато је

\[\frac{(10\cdot x)\mod n}{n}=\frac{10\cdot x}{n}-((10\cdot x)\div n)=(a_1,a_2\ldots a_k\ldots)-a_1=0,a_2\ldots a_k\ldots\]

Дакле, прва децимала броја \(\frac{x}{n}\) се може одредити као \((10\cdot x)\div n\) док се остале децимале могу одредити тако што се исти поступак примени на број \(\frac{x'}{n}\), где је \(x'=(10\cdot x)\mod n\).

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int k, n, m = 1;
    scanf("%d%d", &k, &n);
    printf("0,");
    for (int i = 0; i < k; i++)
    {
        printf("%d", (10 * m) / n);
        m = (10 * m) % n;
    }
    return 0;
}

K децимала у бинарном запису

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

Пошто тражени број децимала може бити велики, не можемо користити системску репрезентацију реалних бројева (која јесте бинарна), тј. резултат не можемо добити ишчитавањем битова мантисе. Наиме, мантиса у запису података типа double има око 50 битова, а у задатку се тражи и до 1000 битова.

Да бисмо објаснили бинарни запис реалних бројева, подсетимо се прво дефиниције позиционог записа броја. Као што је то раније показано запис \((x_nx_{n-1}\ldots x_1)_b\) има вредност \(x_n\cdot b^n+x_{n-1}\cdot b^{n-1}+\ldots+x_1\cdot b+x_0\). На пример, декадни запис \(123\) означава \(1\cdot 10^2+2\cdot 10+3\), док бинарни запис \((1001)_2\) означава \(1\cdot 2^3+0\cdot 2^2+0\cdot 2+1=9\).

Слично, децимални запис \(0,123\) представља број \(1\cdot\frac{1}{10}+2\cdot\frac{1}{100}+3\cdot\frac{1}{1000}\). Заиста, децимални запис \((0,x_1x_2\ldots x_k\ldots)_b\) има вредност

\[x_1\cdot b^{-1}+x_2\cdot b^{-2}+\ldots+x_kb^{-k}+\ldots=x_1\cdot\frac{1}{b}+x_2\cdot\frac{1}{b^2}+\ldots+x_k\cdot\frac{1}{b^k}+\ldots\]

Зато запис броја \(x\) (\(0\leq x<1\)) у бинарном систему \(0,x_1x_2x_3\ldots x_k\ldots\) значи да је \(x=\frac{x_1}{2}+\frac{x_2}{2^2}+\frac{x_3}{2^3}+\ldots+\frac{x_k}{2^k}+\ldots\) На пример, запис \(0,101\) означава \(1\cdot\frac{1}{2}+0\cdot\frac{1}{4}+1\cdot\frac{1}{8}=0,5+0,125=0,625\). Множењем са 2 добијамо \(x\cdot 2=x_1+\frac{x_2}{2}+\frac{x_3}{2^2}+\ldots+\frac{x_k}{2^{k-1}}+\ldots\). Пошто је \(\frac{x_2}{2}+\frac{x_3}{2^2}+\ldots+\frac{x_k}{2^{k-1}}+\ldots<1\), закључујемо да је \(x_1\) цео део производа \(x\cdot 2\), тј. \(x_1=\left\lfloor{x\cdot 2}\right\rfloor\), и да разломљени (децимални) део броја \(x\cdot 2\) има вредност \(\frac{x_2}{2}+\frac{x_3}{2^2}+\ldots+\frac{x_k}{2^{k-1}}\), тј. да је његов бинарни запис \(0,x_2\ldots x_k\). Постоји неколико начина да се децимални број раздвоји на свој цео и разломљени део (на пример, цео део можемо израчунати функцијом floor или конверзијом у цео број, а можемо употребити и функцију modf).

Настављајући исти поступак за разломљени део броја \(x\cdot 2\) добијамо и остале цифре бинарног записа.

Дакле, решење формулишемо тако што у петљи која се извршава \(k\) пута понављамо следеће:

  • израчунавамо производ броја \(x\) и броја 2,

  • приказујемо цео деo добијеног производа (то је наредна цифра у бинарном запису),

  • постављамо број \(x\) на вредност разломљеног дела нађеног производа, припремајући се тако за наредну итерацију.

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    double x;
    int k;
    scanf("%lf%d", &x, &k);
    printf("0.");
    for (int i = 0; i < k; i++)
    {
        x = x * 2;
        printf("%d", (int)x);
        x = x - (int)x;
    }
    return 0;
}

Бројеви који не садрже цифру 5

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

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

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, m = 0;
    while (scanf("%d", &n) != EOF)
    {
        int p = 0;
        do {
            if (n % 10 == 5)
                p = 1;
            n /= 10;
        } while (n > 0 && !p);
        if (p == 0)
            m++;
    }
    printf("%d", m);
    return 0;
}

Комбинација два броја минимумом и максимумом одговарајућих цифара

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

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

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

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int x, y, nmin = 0, nmax = 0, s = 1;
    scanf("%d%d", &x, &y);
    while (x != 0 || y != 0)
    {
        int a = x % 10;
        x /= 10;
        int b = y % 10;
        y /= 10;
        nmin += (a < b ? a : b) * s;
        nmax += (a > b ? a : b) * s;
        s *= 10;
    }
    printf("%d\n%d", nmin, nmax);
    return 0;
}