Osnovi programiranja - vežbe

Filip Marić

9. januar 2003.

1 Zadaci sa praktikuma

Zadatak 1.1 Izračunati sumu cifara broja koji se unosi sa tastature.

Rešenje: Kako odrediti poslednju cifru u dekadnom zapisu broja n? Zapišimo :

n = (a_{m}a_{m−1} … a_{0})_{10}

tj.

n = a_{m}10^{m} + a_{m−1}10^{m−1} + … + a_{1}10 + a_{0}

gde su a_{0} … a_{m} dekadne cifre. Vidimo da su svi clanovi ove sume deljivi sa 10, osim a_{0}. To znači da je a_{0} ostatak pri deljenju broja n sa 10. Posmatrajmo broj [\frac{n}{10}]. On se može zapisati kao (a_{m}a_{m−1} … a_{1})_{10}. Znači, cifre našeg broja n možemo da odredimo tako što odredimo njegovu poslednju cifru, a zatim problem svedemo na odredjivanje cifara broja [\frac{n}{10}].

Npr. Broj n=1234. Njegova poslednja cifra je (1234 mod 10) tj. 4. Da bi smo mu odredili sve ostale cifre, potrebno je odrediti cifre broja [\frac{1234}{10}] = 123. Njegova poslednja cifra je 3. Dalje odredimo cifre broja [\frac{123}{10}] = 12. Njegova poslednja cifra je 2. Preostaje da se odrede cifre broja 1. Njegova poslednja i jedina cifra je 1.

Na osnovu ovog razmatranja možemo da pristupimo i pisanju koda:

#include <stdio.h>
int main()
{    /* Broj ciju sumu cifara izracunavamo */
    int n;
    /* Promenjiva koja cuva trenutnu vrednost sume */
    int suma=0;
    /* Unos broja sa tastature */
    printf("Unesite ceo broj : ");
    scanf("%d",&n);

    /* Ako je broj 0, zavrsavamo */
    while(n!=0)
    {   suma+=n%10;  /* Poslednja cifra broja n se dodaje na sumu */
        n/=10;       /* Svodimo problem na broj [n/10] */

    }
    /* Ispisimo sumu cifara */
    printf("Suma cifara je %d\n",suma);
    return 0;
}

Zadatak 1.2 Sa tastature se unosi ceo broj n. Ispisati sve cifre koje sačinjavaju binarni zapis ovog broja, počevši od cifre najmanje težine.

Rešenje:Iako formulacija ovog zadatka na prvi pogled izgleda prilično različita od formulacije prethodnog zadatka, u suštini se radi o veoma sličnim problemima. Naime, zapišimo broj n u obliku:

n = (a_{m} … a_{0})_{2}

tj.

n = a_{m}2^{m} + a_{m−1}2^{m−1} + … + a_{1}2 + a_{0}

Sada primećujemo, slično kao i malo pre, da je cifra a_{0} jednaka n mod 2. Problem sada možemo da svedemo na odredjivanje binarnog zapisa broja (a_{m} … a_{1}), koji je ustvari jednak [\frac{n}{2}]. Dakle kod izgleda ovako:

#include <stdio.h>
int main()
{    /* Broj cije binarne cifre racunamo */
    int n;
    /* Unos broja sa tastature */
    printf("Unesite ceo broj : ");
    scanf("%d",&n);

    printf("Binarne cifre broja %d,
            pocevsi od cifre najmanje tezine su:\n",n);
    /* Ako je broj 0, zavrsavamo */
    while(n!=0)
    {   /* Ispisujemo binarnu cifru broja n najmanje tezine */
        printf("%d\n",n%2);
        /* Svodimo problem na broj [n/2] */
        n/=2;
    }
    return 0;
}

Zadatak 1.3 Sa tastature se unosi broj n, a zatim n binarnih cifara. Ispisati dekadnu vrednost broja koji se zapisuje pomoću unetih binarnih cifara i to počevši od cifre najveće težine. Npr. Ako je uneto n=4, i zatim cifre : 1 1 0 1, program treba da ispiše 13.

Rešenje: Neka su redom sa tastature unošene cifre : c_{1}, c_{2}, …, c_{n}. Broj koji treba da izračunamo je dakle:

a = c_{1}2^{n−1} + c_{2}2^{n−2} + … + c_{n−1}2 + c_{n}

Ovo možemo da zapišemo na malo drugačiji način :

a = (… ((((0) ∗ 2 + c_{1}) ∗ 2 + c_{2}) ∗ 2 + c_{3}) …) ∗ 2 + c_{0}

Počnimo od vrednosti najugnježdjenije zagrade tj. 0. Vrednost sledeće zagrade se može izračunati kao (0) ∗ 2 + c_{1}. Vrednost zagrade koja je sledeća po dubini može da se dobije tako što se vrednost ove zagrade pomnoži sa 2 i na to se doda c_{2}. Ova pravilnost se i na dalje prenosi. Naime vrednost svake sledeće zagrade je jednaka proizvodu vrednosti prethodne zagrade i broja 2, na koji je dodata sledeća binarna cifra c_{i}. Ova pravilnost nam pomaže da lako napišemo program:

#include <stdio.h>
int main()
{
/* Broj binarnih cifara naseg broja */
int n;
/* Promenjiva koja cuva vrednost tekuce zagrade u izrazu
    (...((((0)*2+c_1)*2+c_2)*2+c_3)...)*2+c_0) */
int a=0;
/* Brojacka promenjiva u petlji */
int i;
/* Unos broja cifara sa tastature */
printf("Unesite broj cifara binarnog broja: ");
scanf("%d",&n);

/* Unosimo cifru po cifru broja
   i ujedno racunamo vrednost sledece zagrade */
for (i=1; i<=n; i++)  /* unosimo n cifara */
{  int c;  /* Tekuca cifra */
   printf("Unesite binarnu cifru : ");
   scanf("%d",&c);
   a=a*2+c; /* Vrednost nove zagrade */
}
/* Dekadna vrednost broja je vrednost spoljasnje zagrade,
   koja se trenutno nalazi u promenjivoj a */
printf("Dekadna vrednost broja je : %d \n",a);

return 0;
}

Zadatak 1.4 Sa tastature se unosi prirodan broj n. Ispisati na ekran sve delioce broja n.

Rešenje: Ideja algoritma je da proverimo redom za sve brojeve koji su potencialno delioci broja n, da li su i stvarno delioci broja n. Broj 1 je delilac svakog prirodnog broja, tako da nema potrebe za njega vrsiti bilo kakvu proveru, nego je dovoljno konstatovati da je 1 delilac broja n. Uočimo na ovom mestu još i činjenicu da je najveći delilac broja n (osim samog n), svakako manji ili jednak [\frac{n}{2}]. Zaista, predstavimo broj n u obliku:

n = a · b

Ako je a > [\frac{n}{2}], tada je b < 2, što je naravno nemoguće. Znači da se svi potencialni delioci broja n (osim 1 i n), nalaze izmedju 2 i n/2 (gde je ovo covska oznaka za celobrojno deljenje, pošto je n celobrojnog tipa). Sada možemo da napišemo program:

#include <stdio.h>
#define GRESKA 1
#define OK 0
int main()
{   int n; /* Broj cije delioce trazimo */
int i; /* Pomocna brojacka promenjiva,
          koja ce da prolazi kroz sve potencijalne
          delioce broja n */
/* Unesimo broj sa tastature */
printf("Unesite prirodni broj : ");
scanf("%d",&n);
/* Proverimo da li je stvarno unet prirodan broj
   Ako nije, ispisujemo odgovarajucu poruku i
   program zavrsava rad sa kodom greske */
if (n<=0)
{   printf("Uneti broj %d nije prirodan!\n",n);
    return GRESKA;
}
/* Ako je n=1, postoji samo jedan delilac */
if (n==1)
{   printf("1 je jedini delilac\n");
    return OK; /* Uspesno zavrsavamo funkciju */
}
/* 1 je delioc svakog prirodnog broja! Ispisimo to */
printf("Delioci broja %d su : 1\t",n);
/* Ispitajmo svaki potencijalni delioc broja n,
   da li stvarno deli broj n */
for (i=2; i<=n/2; i++)
{   /* Ako je ostatak pri deljenju n sa i 0

       i je stvarno delilac */
    if (n%i==0)
       printf("%d\t",i);
}
/* n je delioc broja n. Ispisimo i to */
printf("%d\n",n);
return OK;
}

Drugo rešenje: Ako nije potrebno ispisati delioce poredjane po velicini, ovo rešenje se može još malo poboljšati. Ilustrujmo to na primeru izračunavanja sume svih delioca broja. Rešenje se zasniva na činjenici da ako je a delilac broja n, onda je i \frac{n}{a}, takodje delilac broja n. Prilikom implementacije, brojeve koji su veći od \sqrt{n} nema smisla ispitivati. Zaista ako napišemo:

n = a · b

gde je a > \sqrt{n}, važi da je b < \sqrt{n}, tako da je delilac a, već ispitan prilikom ispitivanja broja b, kao \frac{n}{b}.

#include <stdio.h>
#include <math.h>
#define GRESKA 1
#define OK 0
int main()
{   /* Broj cije delioce trazimo */
int n;
/* Pomocna brojacka promenjiva */
int i;
/* Suma delioca broja n */
int suma;
/* Unesimo broj sa tastature */
printf("Unesite prirodni broj : ");
scanf("%d",&n);
/* Proverimo da li je stvarno unet prirodan broj
   Ako nije, ispisujemo odgovarajucu poruku i
   program zavrsava rad sa kodom greske */
if (n<=0)
{   printf("Uneti broj %d nije prirodan!\n",n);
    return GRESKA;
}
/* 1 i n su svakako delioci broja n, osim pa sumu
   inicijalizujemo na n+1. Problem nastaje ako je
   n=1, jer onda sumu treba postaviti inicijalno na 1 */
if (n==1)
    suma=1;

else
    suma=n+1;

/* Ispitajmo za svaki broj i izmedju 2 i koren iz n
   da li deli broj n. Ako deli, ispisimo da je on
   delilac, kao i da je broj n/i delilac broja n */
for (i=2; i*i<n; i++)
{   /* Ako je ostatak pri deljenju n sa i 0
       i je stvarno delilac, kao i n/i */
    if (n%i==0)
    {    suma+=i;
         suma+=n/i;
    }
}
/* Ako je koren iz n ceo broj, onda je i on delilac broja n.
   Ovaj slucaj posebno ispitujemo, kako ga ne bismo
   dva puta dodavali na sumu. Promenjiva i trenutno sadrzi
   najmanji ceo broj za koji vazi da je i*i>=n */
if (i*i==n)
   suma+=i;

/* Ispisimo sumu delioca */
printf("Suma delioca broja %d je %d\n",n,suma);
return OK;
}

Zadatak 1.5 Sa tastature se unosi prirodan broj n. Odrediti da li je n prost broj.

Rešenje: Broj je prost ako je deljiv samo sa 1 i sa samim sobom. Iskoristimo tehniku pokazanu u drugom rešenju zadatka 1.4. Dovoljno je dakle da proverimo da li broj n ima delioce izmedju 2 i [\sqrt{n}]. Rešenje zasnivamo na osobini c-jezika, da postoji naredba za bezuslovni prekid rada funkcije i ”vraćanje” vrednosti, tj. naredba return.

#include <stdio.h>
#define GRESKA 1
#define OK 0
int main()
{   int n; /* Broj za koga ispitujemo da li je prost */
int i; /* Pomocna brojacka promenjiva,
          koja ce da prolazi kroz sve potencijalne
          delioce broja n */
/* Unesimo broj sa tastature */
printf("Unesite prirodni broj : ");

scanf("%d",&n);
/* Proverimo da li je stvarno unet prirodan broj
   Ako nije, ispisujemo odgovarajucu poruku i
   program zavrsava rad sa kodom greske */
if (n<=0)
{   printf("Uneti broj %d nije prirodan!\n",n);
    return GRESKA;
}
/* Prolazimo kroz sve potencijalne delioce broja n.
   Primetimo da je dovoljno proveriti samo delioce koji
   su manji do jednaki korenu iz n. Napomenimo da se
   mogao izbeci poziv funkcije sqrt iz zaglavlja <math.h>,
   tako sto bismo uslov zamenili sa i*i<=n. */
for (i=2; i<=sqrt(n); i++)
   if (n%i==0) /* Broj i je delilac broja n */
   {  printf("Broj %d je slozen broj!\n",n);
      /* Veoma vazno mesto! Ako smo nasli
         bar jedan delilac, program moze da zavrsi sa radom
         sa kodom OK, jer nije doslo ni do kakve greske.
         Nema svrhe ispitivati dalje delioce. */
      return OK;
   }
/* Ako smo stigli do ovog mesta, nismo naisli ni na jednog
   delioca (jer bi u suprotnom izasli iz programa), tako
   da mozemo da konstatujemo da je broj prost */
printf("Broj %d je prost\n",n);
return OK;
}

Zadatak 1.6 Sa tastature se unosi dimenzija vektorskog prostora ℝ^{n},gde je dimenzija n ≤ 10, a zatim dva vektora x i y koja mu pripadaju. Na ekran ispisati vektore x+y, x−y kao i vrednost njihovog skalarnog proizvoda < x, y >.

Rešenje: Pošto je dimenzija prostora najviše 10, vektore možemo da pamtimo u dva niza dužine 10, pri čemu ćemo u računu da koristimo samo prvih n elemenata ta dva niza.

#define MAXN 10
#define GRESKA 1
#define OK 0
#include <stdio.h>
int main()
{   /* prostor za dva vektora duzine najvise MAXN */
float x[MAXN], y[MAXN];
/* vrednost skalarnog proizvoda */
float skalpr;
/* dimenzija prostora */
int n;

/* pomocna brojacka promenjiva */
int i;
/* unosimo dimenziju prostora */
printf("Unesite dimenziju prostora (1<=n<=10) : ");
scanf("%d",&n);
if (n<1 || n>MAXN)
{   printf("Prostor nije odgovarajuce dimenzije!\n");
    return GRESKA;
}
/* unosimo vektore x i y */
printf("Unesite koordinate prvog vektora : \n");
for (i=0; i<n; i++)
{   printf("x[%d]=",i+1);
    scanf("%f",&x[i]);
}
printf("Unesite koordinate drugog vektora : \n");
for (i=0; i<n; i++)
{   printf("y[%d]=",i+1);
    scanf("%f",&y[i]);
}
/* posto se zbir i razlika samo jednom ispisuju i
   ne koriste se u programu, ne smestamo ih u memoriju */
printf("Zbir vektora x i y je :\n");
/* Pre prve koordinate stampamo otvorenu zagradu, dok pre
   svih ostalih koordinata stampamo zarez */
printf("(%f",x[0]+y[0]);
for (i=1; i<n; i++)
    printf(",%f",x[i]+y[i]);
printf(")\n");
printf("Razlika vektora x i y je :\n");
printf("(%f",x[0]-y[0]);
for (i=1; i<n; i++)
    printf(",%f",x[i]-y[i]);
printf(")\n");
/* Skalarni proizvod racunamo tako sto na njegovu
   tekucu vrednost dodajemo vrednost x[i]*y[i] za
   svako i redom od 0 do n-1 */
skalpr=0;
for (i=0; i<n; i++)
    skalpr+=x[i]*y[i];
printf("Skalarni proizvod ova dva vektora je : %f\n",skalpr);
return OK;

}

Zadatak 1.7 Sa tastature se unosi neki tekst. Napraviti malu statistiku u kojoj se prikazuje koliko puta je pritisnuto svako od malih slova engleske azbuke, zatim koliko puta je pritisnuto svako od velikih slova engleske azbuke, koliko puta je bila pritisnuta koja cifra i na kraju koliko je bilo karaktera koji ne spadaju ni u jednu od ove tri kategorije.

Rešenje: Program bi trebalo da sadrži tri niza brojača za svaku od pomenutih kategorija : brojač pojavljivanja svakog malog slova, brojač pojavljivanja svakog velikog slova i brojač pojavljivanja svake cifre. Sa standardnog ulaza učitavamo karakter po karakter i proveravamo da li je malo, veliko slovo ili cifra. Ako je nešto od ovoga, pronalazimo odgovarajući brojač u nizu i uvećavamo ga. Rešenje je zasnovano na činjenici da su karakteri iz svake od ovih kategorija poredjani jedan za drugim u ASCII tabeli, tako da je jako lako odrediti indeks odgovarajućeg brojača u nizovima brojača, tako što ćemo od ascii vrednosti tekućeg karaktera oduzeti ascii kod početnog karaktera ogovarajuće kategorije (’a’, ’A’ ili ’0’). Primetimo još da možemo na ekran da ispišemo proizvoljan karakter korišćenjem :

        printf("%c",acsiikod);

gde je asciikod ASCII kod karaktera koji ispisujemo.

#include <stdio.h>
int main()
{   int c; /* tekuci karakter sa ulaza */
    int i; /* pomocna brojacka promenjiva */
    /* brojaci za svako malo slovo, veliko slovo, cifru,
       kao i brojac za sve ostale karaktere */
    int mslova[26], vslova[26], cifre[10], ostali;
    /* postavimo vrednost svih brojaca na 0 */
    for (i=0; i<26; i++)
    {   mslova[i]=0;
        vslova[i]=0;
    }
    for (i=0; i<10; i++)
        cifre[i]=0;
    ostali=0;
    printf("Unesite neki tekst (kraj sa ctrl+z) : \n");
    /* Sve dok procitani karakter ne bude oznaka za kraj datoteke
       proveravamo o kom se karakteru radi i povecavamo odgovarajuci
       brojac. */
    while ((c=getchar())!=EOF)
    {   /* Da li je c malo slovo? */
        if ('a'<=c && c<='z')
            /* Uvecavamo brojac za to malo slovo,

           koji se nalazi u nizu brojaca mslova, na poziciji c-'a'. */
        mslova[c-'a']++;
    /* Ako nije bilo malo slovo, proveravamo da li je mozda veliko */
    else if ('A'<=c && c<='Z')
            /* Uvecavamo brojac za to veliko slovo,
               koji se nalazi u nizu brojaca vslova,
               na poziciji c-'A'. */
            vslova[c-'A']++;
        /* Ako nije veliko slovo proveravamo da li je mozda cifra */
        else if ('0'<=c && c<='9')
                /* Uvecavamo brojac pojavljivanja te cifre,
                koji se nalazi u nizu brojaca cifre, na
                poziciji c-'0'. */
                cifre[c-'0']++;
             else /* Radi se o nekom od ostalih karaktera, pa
                     povecavamo brojac za ostale karaktere */
                ostali++;
}
/* Na kraju ispisujemo vrednost svih brojaca */
printf("\n\n Broj pojavljivanja slova : \n");
printf("Mala slova : \n");
for (i=0; i<26; i++)
    printf("%c : %d\t",'a'+i,mslova[i]);
printf("\nVelika slova : \n");
for (i=0; i<26; i++)
    printf("%c : %d\t",'A'+i,vslova[i]);
printf("\nCifre \n");
for (i=0; i<10; i++)
    printf("%c : %d\t",'0'+i,cifre[i]);
printf ("\nOstali : %d\n",ostali);
return 0;
}

Zadatak 1.8 (Hornerova šema) Sa tastature se unosi stepen polinoma (n ≤ 10), a zatim niz njegovih koeficijenata počevši od koeficijenta uz najniži stepen. Zatim se unosi racionalan broj x. Izračunati vrednost polinoma u tački x.

Rešenje: Neka su koeficijenti polinoma redom : c_{0}, c_{2}, …, c_{n}. Broj koji treba da izračunamo je dakle:

P (x) = c_{n}x^{n} + c_{n−1}x^{n−1} + … + c_{1}x + c_{0}

Ovo možemo da zapišemo na malo drugačiji način :

a = (… ((((0) ∗ x + c_{n}) ∗ x + c_{n−1}) ∗ x + c_{n−2}) …) ∗ x + c_{0}

Počnimo od vrednosti najugnježdjenije zagrade tj. 0. Vrednost sledeće zagrade se može izračunati kao (0) ∗ x + c_{n}. Vrednost zagrade koja je sledeća po dubini može da se dobije tako što se vrednost ove zagrade pomnoži sa x i na to se doda c_{n−1}. Ova pravilnost se i na dalje prenosi. Naime vrednost svake sledeće zagrade je jednaka proizvodu vrednosti prethodne zagrade i broja x, na koji je dodata sledeći koeficijent polinoma c_{i}. Ova pravilnost nam pomaže da lako napišemo program ^{1}

#define MAXSTEPEN 10
#define GRESKA 1
#define OK 0
#include <stdio.h>
int main()
{   /* Stepen polinoma */
int n;
/* Niz koeficijenata polinoma */
float koeficijenti[MAXSTEPEN+1];
/* Tacka u kojoj se racuna vrednost polinoma */
float x;
/* Promenjiva koja cuva vrednost tekuce zagrade u izrazu
    (...((((0)*x+c_n)*x+c_{n-1})*x+c_{n-2})...)*x+c_0) */
float p=0;
/* Brojacka promenjiva u petlji */
int i;
/* Unos polinoma sa tastature */
printf("Unesite stepen polinoma : ");
scanf("%d",&n);
if (n<1 || n>MAXSTEPEN)
{   printf("Stepen polinoma nije odgovarajuci!\n");
    return GRESKA;
}
for (i=0; i<=n; i++)
{   printf("Koeficijent uz x^%d je : ",i);
    scanf("%f",&koeficijenti[i]);
}
/* Unos tacke u kojoj racunamo vrednost polinoma */
printf("Unesite tacku x : ");
scanf("%f",&x);
/* Izracunavamo vrednosti "zagrada" od unutra ka spolja */
for (i=n; i>=0; i--)
   p=p*x+koeficijenti[i]; /* Vrednost nove zagrade */
/* Vrednost polinoma je vrednost spoljasnje zagrade,
   koja se trenutno nalazi u promenjivoj p */
printf("P(%f)=%f\n",x,p);

1primetimo da se program mogao napisati i bez smeštanja niza koeficijenata polinoma u memoriju, da je unos koeficijenata počeo od koeficijenta uz najniži stepen

    return 0;
}

Zadatak 1.9 a) Napraviti funkciju koja izračunava vrednost faktorijela zadatog broja.

b)Sa tastature se unosi broj n. Ispisati vrednosti faktorijela svih brojeva od 1 do n.

Pošto je faktorijel funkcija koja veoma brzo raste, već za male vrednosti broja n, n! je prilično veliki broj. Zbog toga je rezultat funkcije tipa long, a argument funkcije je dovoljno da bude tipa int (za koji se podrazumeva da je kratki integer). Pošto radimo samo sa pozitivnim brojevima, koristimo samo unsigned tipove. Važno je primetiti da je već broj 13! toliko veliki da ne može da se zapiše ni u unsigned long tip podataka, tako da naša funkcija ne može da radi ispravno već za n > 12.

n! = 1 · 2 · . . . · n

Pri čemu važi da je 0! = 1! = 1.

Znači da vrednost faktorijela možemo izračunati množeci sve brojeve od 2 do n za n ≥ 2. To se standardno postiže uvodjenjem promenjive proizvod, čija se vrednost na početku postavi na 1, da bi se kasnije množila sa svim činiocima traženog proizvoda. Pošto je 0! = 1! = 1, vrednost promenjive proizvod će da sadrži odgovarajuću vrednost faktorijela i u slučajevima n = 1 i n = 0.^{2}

        unsigned long faktorijel(unsigned int n)
        {   unsigned long proizvod=1;
            for (unsigned int i=2; i<=n; i++)
                proizvod*=i;
            return proizvod;
        }

b)Rešenje koje prvo pada na pamet je da iskoristimo već napravljenu funkciju:

        #include <stdio.h>
        unsigned long faktorijel(unsigned int n)
        {   unsigned long proizvod=1;
            for (unsigned int i=2; i<=n; i++)
                proizvod*=i;
            return proizvod;
        }
        main()
        {   unsigned int n;
            scanf("%u",&n);
            for (int i=0; i<=n; i++)
                printf("%u!=%lu\n",i,faktorijel(i));
        }

2Obratite pažnju da se definicija funkcije faktorijel piše nezavisno od funkcije main(), tj.

celokupni tekst funkcije je napisan van funkcije main()

Medjutim, to rešenje je jako neefikasno. Prilikom računanja svake nove vrednosti faktorijela unutar funkcije, implicitno se izračunavanju vrednosti faktorijela i svih brojeva do tog, a te vrednosti smo već računali (i to najčešće mnogo puta) prilikom prethodnih poziva funkcije. Zato je rešenje koje mnogo bolje radi:

#include<stdio.h>
main()
{   unsigned long proizvod=1;
    unsigned int n,i;
    printf("Unesite broj n (0<=n<=12) : ");
    scanf("%u",&n);
    printf("0!=1\n");
    for (i=1; i<=n && i<13; i++)
    {   proizvod*=i;
        printf("%u!=%lu\n",i,proizvod);
    }
    if (n>12)
       printf("Vrednosti vece od 12! ne mogu
               da budu zapisane pomocu long-a\n");
}

Zadatak 1.10 Sa tastature se unosi ceo broj n. Proveriti da li je taj broj palindrom, tj. da li mu se vrednost promeni ako se njegove cifre pročitaju u obrnutom redosledu. Neki palindromi su npr. 1, 123321, 1234321 …

Zadatak će biti rešen korišćenjem prevodjenja datog broja u niz znakova, a zatim provere da li je taj niz znakova palindrom. Ograničimo se na pozitivne ”male” brojeve, tj. koristimo tip unsigned int. Najveći broj koji može da se zapiše u unsigned int je \underbrace{111..111}_{16}, tj. 2^{16} − 1 = 65535. Za njegov zapis je

dovoljno 5 karaktera, ali pošto svaki string u C-u, mora da se završi karakterom 0, u našem programu je potrebno odvojiti mesto za čuvanje niza od 6 karaktera. Za uputstvo kako odrediti cifre od kojih se sastoji broj pogledati zadatak (1.1). Postavlja se pitanje, kako kada imamo brojnu vrednost neke cifre broja, dobiti ASCII kod karaktera koji predstavlja tu cifru. Ako imamo na umu da ’0’ predstavlja ASCII kod karaktera 0 i da su cifre poredjane jedna iza druge u ASCII tabeli, jasno je da na ’0’ treba samo dodati vrednost te cifre.

Poželjno je taj deo zadatka izdvojiti kao posebnu funkciju. Argumenti te funkcije su broj čiji niz cifara odredjujemo i niz karaktera u koji ćemo da smestimo dobijene cifre. Funkcija pretpostavlja, da je u memoriji već odvojeno mesto za taj niz karaktera, u trenutku poziva.

#include<stdio.h>
int uint_to_char(unsigned int a, char cifre[])
{   int c=0;    /*tekuca pozicija cifre*/
    while(a!=0)
    {   /* c se ovde uvecava, ali se broj pamti na poziciji
           koja odgovara staroj vrednosti c zbog c++, a ne ++c */

       cifre[c++]='0'+a%10;
       a=a/10;
}
/* Na kraj niza cifara postavimo karakter 0, koji je oznaka
   za kraj stringa */
cifre[c]='\0';
/* funkcija vraca poziciju poslednje cifre u nizu */
return c-1;
}

main()
{   /* Niz od 6 karaktera koji ce da sadrzi cifre naseg broja */
char cifre[6];
/* Broj n */
unsigned int n;
/* Indeks poslednje cifre u nizu */
unsigned int poslednja;
/* Pomocna promenjiva za proveru da li je broj palindrom */
unsigned int indeks;
/* Unosimo sa tastature broj n */
printf("Unesi broj n : ");
scanf("%u",&n);
/* Nadjimo niz karaktera koji odgovara broju n */
poslednja=uint_to_char(n,cifre);
/* Poredimo sada prvi i poslednji, drugi i pretposlednji
   karakter sve dok ne naidjemo na neslaganje, ili dok
   nam se levi i desni kraj ne mimoidju */
/* prvi karakter ima indeks 0, a poslednja */
indeks=0;
while ( cifre[indeks]==cifre[poslednja-indeks] &&
        indeks<poslednja-indeks)
      indeks++;
/* Ako su se levi i desni kraj mimoisli, broj je palindrom */
if (indeks>=poslednja-indeks)
      printf("Broj %u je palindrom\n",n);
 else
      printf("Broj %u nije palindrom\n",n);
}

Zadatak 1.11 Napraviti funkciju

            int atoi(char []);

čiji je rezultat brojna vrednost označenog broja, koji je zapisan u prosledjenom nizu karaktera.

#include <stdio.h>
/* Makro koji proverava da li je c cifra */
#define isdigit(c) ('0'<=c && c<='9')
int atoi(char broj[])
{   /* brojevna vrednost broja */
int vrednost=0;
/* indeks tekuce pozicije u nizu karaktera */
int indeks=0;
/* znak broja (1 za pozitivne, -1 za negativne) */
int znak=1;
/* Preskocimo razmake na pocetku broja */
while(broj[indeks]==' ')
   indeks++;
/* Da li je prvi znak mozda '-'? */
if (broj[indeks]=='-')
{   znak=-1;
    indeks++;
}
else /* Preskocimo + ako naidjemo na njega*/
    if (broj[indeks]=='+')
        indeks++;
/* Sve dok se pojavljuju cifre */
while(isdigit(broj[indeks]))
     vrednost=vrednost*10+broj[indeks++]-'0';
return vrednost*znak;
}
main()
{   char broj[]="  -32321";
printf("Vrednost broja je %d\n",atoi(broj));
}

2 Zadaci za pripremu prvog kolokvijuma

Zadatak 2.1 Fibonačijevi brojevi se definišu na sledeći način:

f_{0} = 0

f_{1} = 0

f_{n} = f_{n−1} + f_{n−2}, n ≥ 2

Tj. niz brojeva f_{n} počinje sa : 0,1,1,2,3,5,8,13,21,… Napisati program koji za uneto n, ispisuje f_{n}.

Zadatak 2.2 Sa tastature se unosi pozitivan ceo broj x manji od 2^{32}, kao i dva broja i i j, koji su izmedju 0 i 10. Napisati program koji menja i-tu i j-tu cifru broja x.

Zadatak 2.3 Iz analize je poznato da je :

e^{x} = ∑_{n=0}^{∞} \frac{x^{n}}{n!}

sin(x) = ∑_{n=1}^{∞}(−1)^{n−1} \frac{x^{2n−1}}{(2n − 1)!}

cos(x) = ∑_{n=0}^{∞}(−1)^{n} \frac{x^{2n}}{(2n)!}

Sa tastature se unosi racionalan broj x i prirodan broj n. Izračunati približno e^{x}, sin(x), cos(x), tako što ćete sračunati prvih n članova gornjih suma.

Zadatak 2.4 Sa tastature se unose brojevi s i t. Napisati program koji ispisuje cifre najmanjeg prirodnog broja koji ima osobinu da se završava cifrom s i da se poveća t puta ako mu se cifra s prebaci sa kraja na početak.

a) Redosled cifara nije bitan

b) Ispisati broj u ispravnom redosledu cifara

Zadatak 2.5 n-tocifreni broj je Armstrongov, ako je jednak sumi n-tih stepena svojih cifara. Napisati program koji za uneti broj ispituje da li je Armstrongov.

Zadatak 2.6 Napisati program koji ispisuje prvih n brojeva koji imaju osobinu da su deljivi sa 7, i da im je suma cifara paran broj.

Zadatak 2.7 Broj je Nivenov ako je deljiv sumom svojih cifara. Napisati program koji za uneto n ispisuje prvih n Nivenovih brojeva.

Zadatak 2.8 Neka je dat broj s_{0}. Broj s_{1} je suma kvadrata cifara broja s_{0}. Slično dalje definišemo da je s_{i+1} suma kvadrata cifara broja s_{i}. Broj s_{0} je Srećan, ako (∃k)s_{k} = 1. Napisati program koji za uneti broj n ispituje da li je srećan.

Zadatak 2.9 Za uneto n ≤ 10 ispisati niz koeficijenata u razvoju (a + b)^{n}, koristeći postupak poznat kao Paskalov trougao, tj. koristeći osobinu da je u ”trouglu”:

                                 1
                               1 2 1
                              1 3 3 1
                             1 4 6 4 1
                             .........

Svaki elemenat jednak zbiru dva koja su iznad njega levo i desno. Tj. koristeći osobinu binomnih koeficijenata da je:

\binom{n}{k} = \binom{n − 1}{k} + \binom{n − 1}{k − 1}

Modifikovati program tako da na ekran ispiše prvih n redova paskalovog trougla.

Zadatak 2.10 Za uneti broj n manji od milijardu ispitati da li su mu cifre poredjane u neopadajući niz.

Zadatak 2.11 Sa tastature se unose prirodni brojevi a i b. Napisati program, bez korišćenja operatora / i %, koji ispisuje celobrojni količnik i ostatak pri deljenju broja a brojem b.

Zadatak 2.12 Napisati funkciju :

      int mirror(unsigned long a, int n)

Koja obrće prvih n bitova najmanje težine broja a.

Zadatak 2.13 Napisati funkciju

                int hex_value(char c);

koja za karakter c odredjuje da li je heksadecimalna cifra i ako jeste vraća njenu vrednost, a ako nije vraća -1. Koristeći ovu funkciju, napisati program koji za uneti niz karaktera (ne duži od 8) ispisuje heksadekadnu vrednost broja predstavljenog tim nizom karaktera.

Zadatak 2.14 Napisati program koji sve višestruke razmake u tekstu koji se unosi sa tastature zamenjuje sa jednostrukim razmakom. Npr. za uneto

            Zdravo      Svete

program ispisuje

            Zdravo Svete

Zadatak 2.15 Napisati funkciju

                void to_lower(char[] string);

koja menja sve pojave velikih slova tog stringa u odgovarajuća mala slova. Zatim napisati program koji koristeći ovu funkciju konvertuje uneti tekst u odgovarajući tekst bez malih slova i ispisuje ga. Pretpostaviti da se tekst koji se unosi sa tastature sastoji od najviše 80 karaktera.

Zadatak 2.16 Jedan od najprostijih načina kodiranja reči je tzv. Cezarova šifra. Postupak se sastoji u cikličkom pomeranju slova po abecedi za odgovarajući razmak. Npr. za razmak 2 slovo A se kodira sa C, B sa D, dok se Y kodira sa A, a Z sa B. Napisati funkciju:

                void cezar(char[] string, int razmak);

koja kodira prosledjeni tekst Cezarovom šifrom. Napisati i program, koji koristeći ovu funkciju, prvo kodira uneti tekst (nema više od 80 karaktera), a zatim ga dekodira.

Zadatak 2.17 Napisati funkciju:

      void izbaci(char c, char s[])

Koja iz stringa s izbacuje sva pojavljivanja slova c.

Zadatak 2.18 a) Napraviti funkciju :

      int getline(char s[], int lim)

Koja u čita liniju teksta otkucanog na tastaturi i smešta je u niz karaktera s koji je dužine lim. Vrednost funkcije je dužina pročitane linije.

b) Sa tastature se unosi reč koja ima manje od 10 slova. Napraviti funkciju:

      int findstr(char str[], char substr[])

koja vraća poziciju prvog pojavljivanja reči subrstr u reči str. Ako str ne sadrži substr, funkcija vraća -1.

c) Sa tastature se unosi reč koja ima najviše 10 slova. Koristeći funkcije iz prvog dela zadatka napisati program koji na ekran ispisuje sve one linije teksta otkucanog na tastaturi koje sadrže tu reč.