Vežbe iz Programiranja 1


 BITOVSKI OPERATORI (BITWISE operatori)

ZADACI ZA VEZBU
Zadatak 1: NCP koji ucitava sa standardnog ulaza dva cela broja i stampa njihov zbir u

ULAZ IZLAZ
11 20 OKTALNO: 37
HEKSADEKADNO:
1F
1f
11 7 OKTALNO: 22
HEKSADEKADNO:
12
12

Zadatak 2: NCP koji ucitava dva broja u oktalnom sistemu i stampa njihov zbir u oktalnom i u dekadnom sistemu.
Zadatak 3: NCP koji ucitava dva cela broja u dekadnom sistemu i stampa njihov zbir u binarnom sistemu.
Zadatak 4: NCP koji ucitava pozitivan ceo broj i ispisuje na standardni izlaz da li je broj paran. Nije dovoljeno koristiti aritmeticke operatore iz skupa {+,-,*,/,%}.

Ako imate problem sa implementacijom resenja za zadatke 3 ili 4, pazljivo proucite primere koji slede.

& bitovsko AND       1&1=1 0&1=0 0&0=0
Neka je b ili 0 ili 1.
Onda b & 0 =0, b&1=b
AKO ZELITE DA NEKE BITOVE POSTAVITE NA NULA, MORATE URADITI OPERACIJU AND SA 0

Primer: 255 & 15= ?
255 -> 1111 1111
15 -> 0000 1111
255&15-> 0000 1111 -> oktalno 17 -> heksadekadno 0F
-> dekadno 15

 

Primer: Dato je unsigned x; Koliko je x & 01?

B4, B3, ..., B0 su bitovi na pozicijama 4,3,...0
x binarno Bn Bn-1 ....B4 B3 B2 B1 B0
X&01= Bn Bn-1 ....B4 B3 B2 B1 B0
     & 0 0 ....    0 0   0 0   1
===================================
      0 0 ....     0 0   0 0   B0
ZAKLJUCAK x & 01 vraca kao rezultat nulti bit broja x
Da li Vam ovaj zakljucak pomaze da resite zadatak 4 sa gore navedenog spiska zadataka za vezbu?

 

| BITOVSKO OR       1 | 1 = 1, 1 | 0 =1, 0 | 0 = 0
Ako je b ili 0 ili 1, onda b | 0= b, b | 1 = 1
AKO ZELITE DA POSTAVITE NEKI BIT NA 1, RADITI OPERACIJU OR SA 1com

Primer: 255 | 15 = ?

255 -> 1111 1111
| 15 -> 0000 1111
======================
255 <- 1111 1111
oktalno 377
heksadekadno FF

Primer: Dato je unsigned x; Sta je rezultat rada x= x | 01

x Bn Bn-1 ... B3 B2 B1 B0
| 0  1    ... 0  0 0   1
==============================
  Bn Bn-1 ... B3 B2 B1 1

ODGOVOR> rezultat je broj X kome je 0-ti bit postavljen na 1

 

POSTAVITI 5. bit (B4) na 1, a ostale sacuvati

x Bn Bn-1 .... B6 B5 B4 B3 B2 B1 B0
| 0   0 .....  0  0  1  0  0  0  0      (dekadno gledano, ova maska je broj 16)
======================================
  Bn Bn-1 .... B6 B5 1 B3 B2 B1 B0

X | 16 postavlja 5. bit u X na 1, a ostle bitove ne menja

ZAKLJUCAK x | pow(2, n-1) postavlja n-ti bit u x na 1

KAKO POSTAVITI 4. bit u broju x na 0, a ostale ne menjati?
X & 8 postavlja bit B3 na 0, a ostale bitove ne menja

 

 

KAKO POSTAVITI NAJNIZA 3 BITA U BROJU X na nule, a ostale bitove ne dirati?

X Bn Bn-1 ... B3 B2 B1 B0
& 1  1 ...    1  0  0  0
=====================================
  Bn Bn-1 ... B3 0  0  0

KOJI JE TO BROJ KOME SU POSLEDNJE 3 bita 0?

AKO JE REGISTAR 8-bitni to je broj 1111 1000 = 255 - 7 = (256 - 1) -7
AKO JE REGISTAR 16-bitni to je broj 1111 1111 1111 1000 = (2 na 16) -1 - 7
ZAKLJUCAK
X & ( ( 2 na (sizeof(x)*8)) -1 -7) postavlja tri posednja. bita na 0

KAKO POSTAVITI NAJNIZA 3 BITA U X na 1ce?
X | 7

***************************************************************

^ caret BITOVSKO XOR, XOR JE ekskluzivna disjunkcija
JE not EQUIVAVLENT

1 ^ 0 = 1, 1 ^ 1 =0, 0 ^ 0 = 0
AKO je b ili 0 ili 1, onda b ^ 1 = !b , b ^ 0 = b

255 ^ 15 = ?
255 -> 1111 1111
15 -> 0000 1111
^ ==============
1111 0000 256 -1 - 15 = 240

Primer: Dato je unsigned x; Sta je rezultat naredbe x = x ^ 01;

x -> Bn Bn-1 .... B2 B1 B0
01 -> 0 0   ....  0  0  1
^ ===========================
     Bn Bn-1 .... B2 B1 !B0
ODGOVOR> Rezultat je broj X kome je 0-ti bit invertovan, a ostali bitovi su nepromenjeni

 

~ BITOVSKO NOT invertuje bitove
Ako je u 8-bitnom registru smesten dekadni broj 7, onda ~7= INVERTOVANO(0000 0111) = 1111 1000 tj. dekadno 248

CEMU JE JEDNAKO ~1?
CEMU JE JEDNAKO ~0?
AKO JE SIZEOF (int) = 1, tj. ako se int registruje u 1 bajtu,
tj. u 8 bitova, onda se:
1 registruje kao 0000 0001
0 registruje kao 0000 0000

TE JE ~1 = INVERTOVANO(0000 0001) = 1111 1110 tj. 254
~1 = (2 na sizeof(int)*8) -2

TE JE ~0 = INVERTOVANO (0000 0000) = 1111 1111
~0 daje citav registar napunjen bitovima koji su 1

>> SHIFT RIGHT, POMERANJE NADESNO,
EFEKAT DELJENJA STEPENOM DVOJKE

NA PRIMER 32 >> 3 je isto sto i 32 / 23,
ali 32 >> 3 se brze izvrsava

<< SHIFT LEFT, POMERANJE NALEVO
NAPRIMER 3 << 5 je isto sto i 3 * 25,
ali se 3 << 5 brze izvrsava

Primer 59. (Demonstracija bitskih operatora) Sta je rezultat rada sledeceg programa?


#include <stdio.h>
main()
{ printf("%o %o\n",255,15);
printf( "255 & 15 = %d\n", 255 & 15 );
printf( "255 | 15 = %d\n", 255 | 15 );
printf( "255 ^ 15 = %d\n", 255 ^ 15 );
printf( "2 << 2 = %d\n", 2 << 2 );
printf( "16 >> 2 = %d\n", 16 >> 2 );
}
Izlaz iz programa je:
377 17
255 & 15 = 15
255 | 15 = 255
255 ^ 15 = 240
2 << 2 = 8
16 >> 2 = 4

60. Napisati funkciju print bits koja stampa bitove u zapisu datog neoznacenog celog broja x i program koji ilustruje rad sa tom funkcijom. Uocimo da funkcijom print bits se zapravo stampa binarna predstava broja x.


#include <stdio.h>

/*
Funkcija print_bits stampa bitove datog celog broja x.
Vrednost bita na poziciji i je 0 ako i samo ako se dobija 0
pri konjunkciji broja x sa
maskom 000..010....000 (ovu masku cine sve nule, osim 1ce na poziciji i)

Funkcija krece od pozicije najvece tezine kreirajuci masku pomeranjem jedinice u levo
za (broj_bitova(x) - 1) mesto, i zatim pomerajuci ovu masku za jedno mesto u levo u svakoj
sledecoj iteraciji sve dok maska ne postane 0.
*/

void print_bits(unsigned x){

   unsigned wl = sizeof(unsigned)*8; /* wl je broj bitova za registrovanje unsigned promenljive */
    unsigned mask; /* maska bitova */


    for (mask = 1<<wl-1; mask; mask >>= 1) putchar(x&mask ? '1' : '0');

    putchar('\n');
}

main()
{
    print_bits(127);
    print_bits(128);
    print_bits(0x00FF00FF);
    print_bits(0xFFFFFFFF);
}


Izlaz iz programa:
00000000000000000000000001111111
00000000000000000000000010000000
00000000111111110000000011111111
11111111111111111111111111111111

Da li Vam f-ja print_bits pomaze da resite zadatak 3 sa gore navedenog spiska zadataka za vezbu?

ZADACI ZA VEZBU


Zadatak 1: NCP koji ucitava sa standardnog ulaza neoznacen ceo broj i ispisuje samo tri najniza(poslednja, krajnja desno) bita tog broja.
IDEJA RESENJA:
x binarno Bn Bn-1 ....B4 B3 B2 B1 B0
X& 7= Bn Bn-1 ....B4 B3 B2 B1 B0
     & 0 0 ....    0 0   1 1   1
===================================
      0 0 ....     0 0   B2 B1   B0

ZAKLJUCAK x & 7 vraca kao rezultat tri bita broja x sa njanizih pozicija B2, B1, B0
Da li Vam ovaj zakljucak pomaze da resite zadatak?
Ako ne, pogledajte resenje, a inace pokusajte sami da resite zadatak.

Zadatak 2: NCP koji ucitava sa standardnog ulaza neoznacen ceo broj i ispisuje taj broj sa postavljenim petim bitom na 1cu. (Pogledajte jedan od gore navedenih primera).

Zadatak 3: NCP koji ucitava sa standardnog ulaza neoznacen ceo broj i ispisuje taj broj sa postavljenim petim bitom na 0lu. (Pogledajte jedan od gore navedenih primera).

 

61. NCP koji proverava da li se na k-tom bitu broja koji se ucitava sa standardnog ulaza nalazi 1. Pozicija k se ucitava sa standardnog ulaza. Voditi racuna numeracija bitova je takva da bit najmanje tezine (krajnji desno) je nulti bit, a ne prvi bit.

#include <stdio.h>
main(){
int n,k;
printf("Unesite broj i poziciju tog broja koju zelite da proverite:\n");
scanf("%d %d",&n,&k);

if ((n&(1 << k))!=0) printf("Bit je 1\n");
else printf("Bit je 0\n");

return 0;
}

62. NCP koji postavlja na k-to mesto 1

#include <stdio.h>
void print_bits(unsigned x);
main(){

int n,k;

printf("Unesite broj i poziciju tog broja koju zelite da proverite:\n");
scanf("%d %d",&n,&k);

printf("Binarno\v uneseni broj je\n");
print_bits(n);

printf("Novi broj je %d\n",(n |(1<<k)));
printf("Binarno, novi broj je\n");
print_bits((n |(1<<k)));

return 0;
}


void print_bits(unsigned x){

   unsigned wl = sizeof(unsigned)*8; /* wl je broj bitova za registrovanje unsigned promenljive */
    unsigned mask; /* maska bitova */


    for (mask = 1<<wl-1; mask; mask >>= 1) putchar(x&mask ? '1' : '0');

    putchar('\n');
}

Izrazom a>>b vrsi se pomeranje sadrzaja operanda a predstavljenog u binarnom obliku za b mesta u desno. Popunjavanje upraznjenih mesta na levoj strani zavisi od tipa podataka i vrste racunara. Ako se pomeranje primenjuje nad operandom tipa unsigned popunjavanje je nulama.
Ako se radi o oznacenom operandu popunjavanje je jedinicama kada je u krajnjem levom bitu jedinica, a nulama kada je u krajnjem levom bitu nula.

63. Napisati funkciju koja broji bitove postavljene na 1 u neoznacenom celom broju.


int bitcount(unsigned x)
{
int b;

for(b=0; x!=0; x>>=1)
if (x & 01) b++;

return b;
}

64. NCP koji izracunava sumu bitova datog neoznacenog broja.


#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}

/* MANJE EFIKASNA VERZIJA
int sum_of_bits(unsigned x){

int wl = sizeof(unsigned)*8;
int br = 0;
unsigned mask;

for (mask = 1<<wl-1; mask; mask>>=1)
if (x&mask) br++;

return br;
}

*/

 

/* Efikasnija verzija */
int sum_of_bits(unsigned x)
{
int br;

for (br = 0; x; x>>=1)
if (x&1) br++;


return br;
}

main()
{
printf("Binarni zapis broja 127 je\n"); print_bits(127);
printf("Suma bitova broja 127 je %d\n",sum_of_bits(127));

printf("Binarni zapis broja 128 je\n");print_bits(128);
printf("Suma bitova broja 128 je %d\n",sum_of_bits(128));

printf("Binarni zapis broja 0x00FF00FF je\n"); print_bits(0x00FF00FF);
printf("Suma bitova broja 0x00FF00FF je %d\n",sum_of_bits(0x00FF00FF));

printf("Binarni zapis broja 0xFFFFFFFF je\n");print_bits(0xFFFFFFFF);
printf("Suma bitova broja 0xFFFFFFFF je %d\n",sum_of_bits(0xFFFFFFFF));
}

65. Napisati funkcije get bits, set bits, invert bits za (redom) izdvajanje, postavljanje i invertovanje pojedinacnih bitova


#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}


/* Funkcija vraca n bitova broja x koji pocinju na poziciji p */
unsigned get_bits(unsigned x, int p, int n)
{
/* Gradimo masku koja ima poslednjih n jedinica
0000000...00011111
tako sto sve jedinice ~0 pomerimo u levo za n mesta
1111111...1100000
a zatim komplementiramo
*/
unsigned last_n_1 = ~(~0 << n);

/* x pomerimo u desno za odgovarajuci broj mesta, a zatim
konjunkcijom sa konstruisanom maskom obrisemo pocetne cifre */
return (x >> p+1-n) & last_n_1;

}

 


/* Funkcija vraca modifikovano x tako sto mu je izmenjeno n bitova
pocevsi od pozicije p i na ta mesta je upisano poslednjih n bitova broja y */
unsigned set_bits(unsigned x, int p, int n, unsigned y)
{
/* Maska 000000...000111111 - poslednjih n jedinica */
unsigned last_n_1 = ~(~0 << n);
/* Maska 1111100..000111111 - n nula pocevsi od pozicije p */
unsigned middle_n_0 = ~(last_n_1 << p+1-n);

/* Brisemo n bitova pocevsi od pozicije p */
x = x & middle_n_0;

/* Izdvajamo poslednjih n bitova broja y i pomeramo ih na poziciju p */
y = (y & last_n_1) << p+1-n;

/* Upisujemo bitove broja y u broj x i vracamo rezultat */
return x | y;
}

/* Invertuje n bitova broja x pocevsi od pozicije p */
unsigned invert_bits(unsigned x, int p, int n)
{
/* Maska 000000111...1100000 - n jedinica pocevsi od pozicije p */
unsigned middle_n_1 = ~(~0 << n) << p+1-n;

/* Invertujemo koristeci ekskluzivnu disjunkciju */
return x ^ middle_n_1;
}

main()
{
unsigned x = 0x0AA0AFA0;
print_bits(x);
print_bits(get_bits(x, 15, 8));
print_bits(set_bits(x, 15, 8, 0xFF));
print_bits(invert_bits(x, 15, 8));
}

Izlaz iz programa:
00001010101000001010111110100000
00000000000000000000000010101111
00001010101000001111111110100000
00001010101000000101000010100000

66. napisati funkcije right rotate bits, mirror bits za rotiranje i simetrija bitova.

#include <stdio.h>
/* Pomocna funkcija - stampa bitove neoznacenog broja */
void print_bits(unsigned x)
{
int wl = sizeof(unsigned)*8;
unsigned mask;
for (mask = 1<<wl-1; mask; mask >>= 1)
putchar(x&mask ? '1' : '0');
putchar('\n');
}

/* Funkcija vrsi rotaciju neoznacenog broja x za n pozicija u desno */
unsigned right_rotate(unsigned x, int n)
{
int i;
int wl = sizeof(unsigned)*8;

/* Postupak se ponavlja n puta */
for (i = 0; i < n; i++)
{
/* Poslednji bit broja x */
unsigned last_bit = x & 1;

/* x pomeramo za jedno mesto u desno */
x >>= 1;

/* Zapamceni poslednji bit stavljamo na pocetak broja x*/
x |= last_bit<<wl-1;
}

return x;
}

/* Funkcija obrce binarni zapis neoznacenog broja x tako sto bitove cita unatrag */
unsigned mirror(unsigned x)
{
int i;
int wl = sizeof(unsigned)*8;

/* Rezultat inicijalizujemo na poslednji bit broja x */
unsigned y = x & 1;

/* Postupak se ponavlja wl-1 puta */
for (i = 1; i<wl; i++)
{
/* x se pomera u desno za jedno mesto */
x >>= 1;
/* rezultat se pomera u levo za jedno mesto */
y <<= 1;
/* Poslednji bit broja x upisujemo na poslednje mesto rezultata */
y |= x & 1;
}

return y;
}

main()
{
unsigned x = 0xFAF0FAF0;
print_bits(x);
print_bits(mirror(x));
print_bits(right_rotate(x, 2));
}

Izlaz iz programa:
11111010111100001111101011110000
00001111010111110000111101011111
00111110101111000011111010111100

Zadaci za vezbu:
Zadatak 1. Napisati program koji prihvata sa standardnog ulaza dva niza iste dimenzije i ispisuje na standardni izlaz da li dva niza imaju barem jedan zajednicki element.
Zadatak 2. Napisati operator dodeljivanja koji ce broju x tipa unsigned sacuvati n krajnjih desnih bitova, a ostale postaviti na nulu.
x=x&~(~0 << n); ili x&=~(~0 << n);


Zadatak 3. Napisati operator dodeljivanja koji ce u x ocistiti n bitova (postaviti nule) pocev od pozicije p.
x&=~(~(~0<<n)<<(p-1))


Zadatak 4. Napisati operator dodeljivanja kojim se invertuje x (prevodi jedan u nulu i nula u jedan) pocev od pozicije p na duzini n.
x^=(~(~0<<n)<<(p-1));

67. (naredba break)
Napisati C program koji proverava korektnu uparenost zagrada ( i ) u tekstu koji dolazi sa standardnog ulaza. Npr. zagrade su korektno uparene u izrazu 5 * (8+3), a nisu u izrazu 3 + )2) ili izrazu ( (3+6) * 8





#include <stdio.h> 

main() 
{ 
    int c;    /*tekuci karakter sa ulaza*/
    int br_otv = 0; /*brojac zagrada*/
    while((c=getchar()) != EOF) 
    { 
         if(c=='(')   br_otv++; 
         if (c== ')') 
             { br_otv--; 
              if (br_otv<0) { printf("Visak zatvorenih zagrada\n"); break; } 
             } 
    } 
     if (br_otv == 0) printf("Zagrade su u redu\n"); 
     else      if (br_otv >0) printf("Visak otvorenih zagrada\n"); 
} 



68. (naredba continue) NCP koji prihvata sa standardnog ulaza pozitivan ceo broj n (n <=50), proverava korektnost unete vrednosti, a zatim prihvata po jedan element n-dimenzionalnog niza celih brojeva. Formirati drugi niz koji sadrži samo nenegativne elemente unetog niza, a potom članove drugog niza ispisati na standardni izlaz. /*prepis pozitivnih clanova niza u drugi niz i stampanje drugog niza */

#include <stdio.h>
main()
{
int n; /* dimenzija niza */
int indeks; /* brojac */
int a[50];/*niz celih brojeva iz kog se izdvajaju nenegativni brojevi */
  int j; /*broj nenegativnih clanova*/
  int rezultat[50];/* niz nenegativnih clanova*/
 

/*unos dimenzije niza : 1..50 */
do
{printf("Unesite broj elemenata niza\n");
scanf("%d", &n);
} while (n <1 || n > 50);
 

/* unos clanova niza celih brojeva */
for( indeks=0; indeks<n; indeks++) scanf("%d", &a[indeks]);
 

/* prepis nenegativnih elemenata u niz rezultat */
for( indeks=0, j=0; indeks<n; indeks++)
{

/* ignorisanje clanova niza a koji ne mogu biti clanovi niza rezulat */
if(a[indeks]<0)    continue;
/* dopuni niz rezultat */rezultat[j++]=a[indeks];
}
 

/* ispis niza rezultat */
  printf("\nNovi niz je: ");
  for( indeks=0; indeks<j; indeks++) printf("%d\t", rezultat[indeks]);

printf("\n");
return 0;
}



Biblioteka matematičkih funkcija

69. (zaglavlje math.h) NCP koji unosi realan broj sa standardnog ulaza i ispisuje na standardni izlaz: taj broj, najmanji ceo broj ne manji ( >=) od tog broja, najveći ceo broj ne veći ( <=) od tog broja, kvadratni koren tog broja (ako broj je nenegativan), kub tog broja, kosinus tog broja.

Pri upotrebi kompajlera gcc, mora se upotrebiti opcija -l za naziv biblioteke s kojom se linkuje program, a za matematicku biblioteku libm(#include <math.h>) oznaka je m, tj. kompilacija zad69.c bi mogla biti:
gcc zad69.c -lm -o racunaj


#include <stdio.h>
#include <math.h>
/*NAPOMENA: Funkcije ceil(x), floor(x), sqrt(x), sin(x) su iz zaglavlja math.h
Argumenti su tipa double, rezultati su tipa double*/

 main()
{  double x;
   printf("Unesite broj: ");
   scanf( "%lf", &x);
   printf("\n\nUneli ste: %lf", x);
   printf("\nCeil Vaseg broja: %lf", ceil(x));
   printf("\nFloor Vaseg broja %lf", floor(x));
   if( x >= 0 )  printf("\nKvadratni koren: %lf", sqrt(x) );
    else printf("\nNegativni broj" );
   printf("\nKub Vaseg broja %lf", pow(x,3));
  printf("\nCosinus: %lf\n", cos(x));
 return(0);
}

Testirajte program za x =4.9998887, x=4.11199, x=0.001, x=-0.001, x=0.25, x=0, x=-1, x=1

70. (zaglavlje math.h, funkcija fabs) Napisati C program koji prihvata sa standardnog ulaza koeficijente kvadratne jednacine, a na standrdni izlaz ispisuje njene korene.


/* Program za nalazenje korena kvadratne jednacine */

#include <stdio.h>  
#include <math.h> 

main () {
  double a, b, c,              /* Koeficijenti jednacine                      */
         d,                    /* Diskriminanta jednacine                     */
         x1, x2,               /* Realni koreni                               */
         z1r, z1i, z2r, z2i,   /* Kompleksni koreni                           */
         x;                    /* Resenje linearne jednacine                  */
  int    por;                  /* Poruka o vrsti resenja                      */

  printf ("Koeficijenti kvadratne jednacine: ");
  scanf ("%lf%lf%lf", &a, &b, &c);
  if (! a)
    if (! b)               por = 1;
    else     { x = -c / b; por = 2; }
  else {
    d = b * b - 4 * a * c;
    if (d < 0) {
      z1r = -b / (2 * a); z1i =  sqrt (-d) / (2 * a);
      z2r = z1r;          z2i = - z1i;                por = 3;
    } else {
      x1 = (-b + sqrt (d)) / (2 * a);
      x2 = (-b - sqrt (d)) / (2 * a);                 por = 4;
    }
  }

  switch (por) {
    case 1: printf ("Ulazni podaci nemaju smisla!\a\n");
            break;
    case 2: printf ("Koren linearne jednacine je %g\n", x);
            break;
    case 3: printf ("Kompleksni koreni su %g%ci%g i %g%ci%g\n",
                    z1r, ((z1i >= 0) ? '+' : '-'),  fabs (z1i),
                    z2r, ((z2i >= 0) ? '+' : '-'), fabs (z2i));
            break;
    case 4: if (x1 != x2)
              printf ("Realni koreni su %g i %g\n", x1, x2);
            else
              printf ("Jednacina ima dvostruki koren %g\n",x1);
            break;
  }
}




TESTIRAJTE ZADATAK UPOTREBOM NEKOG IDE-a za Windows OS: DEV C/C++, MSVC++, BC++, TURBO C, QUICK C

ZADACI ZA VEZBU

Zadatak 1. NCP koji koji će prebrojati koliko puta se pojavila svaka cifra dekadnog brojnog sistema u ulaznoj datoteci i rezultat ispisati u izlaznu datoteku. Program treba da radi sa preusmeravanjem standardnog ulaza i izlaza.

ulaz (stdin, getchar())

izlaz (stdout, putchar())

123 75
abcd efg\13
[enter]
^D


Broj pojave cifre 0 je 0.
Broj pojave cifre 1 je 2.
Broj pojave cifre 2 je 1.
Broj pojave cifre 3 je 2.
Broj pojave cifre 4 je 0.
Broj pojave cifre 5 je 1.
Broj pojave cifre 6 je 0.
Broj pojave cifre 7 je 1.
Broj pojave cifre 8 je 0.
Broj pojave cifre 9 je 0.



Zadatak 2. NCP koji će tekst ulazne datoteke prepisati u izlaznu datoteku tako da se višestruke uzastopne pojave znaka * zamene jednom zvezdicom. (sažimanje). Program treba da radi sa preusmeravanjem standardnog ulaza i izlaza.

ulaz (stdin, getchar())

izlaz (stdout, putchar())

1*3[tab]**
a***d efg*+*
[enter]
^D

1*3[tab]*
a*d efg*+*

EOF



Zadatak 3. NCP koji će tekst ulazne datoteke prepisati u izlaznu datoteku tako da se prepiše svaki drugi karakter ulazne datoteke počev od drugog pročitanog karaktera. Program treba da radi sa preusmeravanjem standardnog ulaza i izlaza.

ulaz (stdin, getchar())

izlaz (stdout, putchar())

1234abcd *+-
^D

24bd*-
EOF



Zadatak 4. NCP koji učitava sa standardnog ulaza broj k i ispisuje vrednost Fk, gde elementi niza Fi se zadaju na sledeći način
F0=1
F1=3
Fn=2 Fn-1 + 3 Fn-2, za n >= 2.
Ne koristiti nizove pri implementaciji.



Konverzije (malog slova u veliko, iz dekadnog sistema u druge brojcane sisteme,...)


Automatska konverzija - primeri
Ako je jedan od operanada razlizlicit vrsi se konverzija, uvek u smeru manjeg ka ve´cem tipu
Naredba dodele:
int i=5;
float f=2.3;
f=i; /* f ce imati vrednost 5.0*/
obrnuto:
int i=5;
float f=2.3;
i=f; /* i ce imati vrednost 2*/
VII.2. Eksplicitna konverzija
(tip)<izraz>
float x;
x=2.3+4.2; /* x ce imati vrednost 6.5 */
x=(int)2.3+(int)4.2; /* x ce imati vrednost 6 */
x=(int)2.3*4.5; /* x ce imati vrednost 9.0 jer zbog prioriteta
operatora konverzije prvo ce biti izvrsena
konverzija broja 2.3 u 2 pa tek onda izvrseno
mnozenje. */
x=(int)(2.3*4.5) /* x ce imati vrednost 10.0 */

71. Kako izbeci celobrojno deljenje
int a,b;
float c;
a = 5;
b = 2;
c = a/b; /* Celobrojno deljenje, c=2*/
c = (1.0*a)/b; /* Implicitna konverzija: 1.0*a je realan
broj pa priliko deljenja sa b dobija se
realan rezultat c=2.5*/
c = (0.0+a)/b; /* Implicitna konverzija: (0.0+a) je realan
broj pa priliko deljenja sa b dobija se
realan rezultat c=2.5*/
c = (float)a/(float)b; /* Eksplicitna konverzija*/

72. Konverzija medju konstantama - primer znakovnih konstanti

UVODNA TEORIJSKA PODLOGA: Koji su tipovi konstanti?
Celobrojna konstanta 1234 je tipa int.
Da bi konstanta bila long navodi se iza nje slovo L ili l, npr 123456789L.
Ako zelimo da nam je konstanta unsigned onda na kraju pisemo U ili u.
Moze i 1234567ul.
Konstante realnih brojeva sadrze decimalnu tacku(123.4) ili eksponent(1e-2) ili i jedno i
drugo. Njihov tip je double osim ako nemaj sufiks f ili F kada je u pitanju float.
L ili l oznacavaju long double.
Oktalna konstanta pocinje sa 0, a heksadecimalna sa 0x. Npr broj 31 ili 037 - oktalno ili
0x1f - heksadecimalno. I one mogu da imaju U i L na kraju. Znakovna konstanta je celobrojna vrednost napisana izmedjuu jednostrukih navodnika. Vrednost
date konstante je numericka vrednost datog znaka u racunarskom setu znakova. Npr mozemo
da pisemo ’0’ umesto 48.
!!!Razlikovati znakovne konstante i niske koje se navode izmedju dvostrukih navodnika!
Posebni znaci su znak za kraj reda, tab i slicno.
Znakovna konstanta '\0' predstavlja znak cija je vrednost nula, treba ga razlikovati od ’0’ koja
je znak cija je vrednost 48.
Konstantna niska: ”Ja sam niska”
ili
”” /*prazna niska*/
Navodnici nisu deo niske vec se koriste da bi je ogranicili. Ako ih zelimo unutar niske, oni se
navode sa \".
Konstantna niska je polje znakova. Da bi se znalo gde je kraj niske, fizicko memorisanje liste
zahteva da postoji jedan znak vise koji oznacava kraj, to je '\0'. Da bi se odredila duzina niske
mora se proci kroz celu nisku.
!!!Vazno:
Koja je razlika izmedju ”x” i ’x’?

#include <stdio.h>
main()
{
int vrednost;
vrednost='A';
printf("Veliko slovo\n karakter=%3c\nvrednost=%3d\n",vrednost,vrednost);
vrednost='a';
printf("Malo\n karakter=%3c\nvrednost=%3d\n",vrednost,vrednost);
}
Izlaz (u slucaju ASCII):
Veliko slovo
karakter= A
vrednost= 65
Malo
karakter= a
vrednost= 97

73. Napisati funkcija koja konvertuje velika slova u mala slova i program koji ilustruje rad te funkcije.
#include<stdio.h>
/* Konvertuje karakter iz velikog u malo slovo */
char lower(char c)
{
if (c >= 'A' && c <= 'Z')
return c - 'A' + 'a' ;
else
return c;
}
main()
{
char c;
printf("Unesi neko veliko slovo:\n");
scanf("%c", &c);
printf("Odgovarajuce malo slovo je %c\n", lower(c));
}
Izlaz:
Unesi neko veliko slovo:
J
Odgovarajuce malo slovo je j


Implementirati prethodni zadatak upotrebom funkcije tolower iz zaglavlja <ctype.h> #include<stdio.h>
#include<ctype.h>

main()
{
char c;
printf("Unesi neko veliko slovo:\n");
c=getchar();
printf("Odgovarajuce malo slovo je %c\n", tolower(c));
}


74. Napisati funkciju koja vrsi konvertovanje niske cifara u ceo broj i program koji ilustruje rad te funkcije.(funkcija atoi, str. 41 K&R)

NISKA "000723" predstavlja broj 723 čija vrednost se formira (po Hornerovoj shemi???) u formi ('7'-'0')*100 + ('2'-'0')*10 + ('3'-'0') = 7*100 + 2*10 + 3*1 = 10 * ( 10 * (7) + 2) + 3


#include<stdio.h>
/* atoi: konvertuje s u ceo broj */
int atoi(char s[])
{
int i, n;
n = 0;
for (i = 0; (s[i] >= '0') && (s[i] <= '9'); ++i)
n = 10 * n + (s[i] - '0');
return n;
}
main()
{
int n;
n = atoi("234");
printf("\nN je : %d\n",n);
}
Izlaz:
N je : 234



Konverzije među brojčanim osnovama


75. Napisati funkciju btoi koja vrsi konverzija iz datog brojnog sistema u dekadni i program koji ilustruje rad te funkcije.
#include <stdio.h>
#include <ctype.h>
/* Pomocna funkcija koja izracunava vrednost koju predstavlja karakter u datoj osnovi
Funkcija vraca -1 ukoliko cifra nije validna.
Npr.
cifra 'B' u osnovi 16 ima vrednost 11
cifra '8' nije validna u osnovi 6
*/
int digit_value(char c, int base)
{
/* Proveravamo dekadne cifre */
if (isdigit(c) && c < '0'+base)
return c-'0';
/* Proveravamo slovne cifre za mala slova */
if ('a'<=c && c < 'a'+base-10)
return c-'a'+10;
/* Proveravamo slovne cifre za velika slova */
if ('A'<=c && c < 'A'+base-10)
return c-'A'+10;
return -1;
}
/* Funkcija izracunava vrednost celog broja koji je zapisan u datom
nizu karaktera u datoj osnovi. Za izracunavanje se koristi Hornerova shema.
*/
int btoi(char s[], int base)
{
int sum = 0;
/* Obradjuju se karakteri sve dok su cifre */
int i, vr;
for (i = 0; (vr = digit_value(s[i], base)) != -1; i++) sum = base*sum + vr;
return sum;
}
main()
{
char bin[] = "11110000";
char hex[] = "FF";
printf("Dekadna vrednost binarnog broja %s je %d\n", bin, btoi(bin, 2));
printf("Dekadna vrednost heksadekadnog broja %s je %d\n", hex, btoi(hex, 16));
}
Izlaz:
Dekadna vrednost binarnog broja 11110000 je 240
Dekadna vrednost heksadekadnog broja FF je 255

76. NCP koji vrsi konverziju iz dekadnog brojnog sistema u datu osnovu
#include<stdio.h>
#define OSNOVA 16
main()
{
int x; /* Broj cija se konverzija vrsi */
int ostaci[32]; /* Niz ostataka pri deljenju sa osnovom */
int i = 0;
/* Unosi se dekadni broj */
scanf("%d",&x);
/* Algoritam konverzije */
while(x>0)
{
/* novi ostatak se dodaje u pomocni niz */
ostaci[i++] = x%OSNOVA;
x/=OSNOVA;
}
/* Niz se ispisuje unatrag */
for (i--; i>=0; i--)
if (ostaci[i]<=10) /* Slucaj kada je cifra dekadna */
printf("%d",ostaci[i]);
else /* Slucaj kada cifra prevazilazi dekadni opseg */
printf("%c",'A'+ostaci[i]-10);
printf("\n");
}


77. NCP koji učitava nisku koja predstavlja ili heksadekadnu konstantu (npr. 0x1a ili 0XFF, pocinje sa 0x ili 0X) ili heksadekadni broj koji je strogo manji od maksimalne vrednosti INT_MAX. Potom konvertuje nisku u numerički dekadni ekvivalent i ispisuje broj za 1 veći.

PRIMER
ULAZ DEKADNI EKVIVALENT ++IZLAZ
0XA 10 11
0x7ffe 32766 32767




#include <stdio.h>
#include <ctype.h>
#define MAXLINE 1000
int getline( char s[], int Limit);
unsigned htoi( char s[] );
int hexvalue( int znak );

main()
{
int duz; /* duzina ucitane linije */
unsigned Number; /* numericki ekvivalent niske kojom je predstavljena heksadekadna vrednost sa ulaza */
  char linija[MAXLINE]; /* linija sa ulaza */

  printf("Unesite broj \n");
   duz=getline(linija,MAXLINE);
    Number=htoi(linija);
  printf( "Inkrementirani broj je:\n%u\n", ++Number );
return 0;
}

/* hvalue: vrednost hexadecimalne cifre  */
int hexvalue( int znak )
{
  if(isdigit(znak))   return(znak-'0');
   if    (znak>='A' && znak<='F')      return(znak-'A'+10);
   if     (znak>='a' && znak<='f')       return(znak-'a'+10);
return 0;
}
/* htoi: hexadecimal ascii -> integer */
unsigned htoi( char s[] )
{
   int Pos;
 unsigned  Num;
   if((s[0]=='0' && s[1]=='x')     || (s[0]=='0' && s[1]=='X') )        Pos=2;
  else   Pos=0;
for(Num=0; isdigit(s[Pos])
    || (s[Pos]>='A' && s[Pos]<='F')
   || (s[Pos]>='a' && s[Pos]<='f'); ++Pos)
  Num=16*Num+hexvalue(s[Pos]);
return Num;
}
/* getline: ucitava liniju i vraca njenu duzinu */
int getline( char Linija[], int Limit)
{
 int  znak, indeks;
 for( indeks=0; indeks<Limit -1&& (znak=getchar())!=EOF && znak!='\n'; ++indeks)
  Linija[indeks]=znak;
 if( znak=='\n' )
 {Linija[indeks]=znak;
                 ++indeks;
 }
 Linija[indeks]='\0';
 return indeks;
}


(Enumeracija - sluzbena rec enum)


78. NCP koji tekst sa standardnog ulaza prepisuje na standardni izlaz pretvarajući početna slova rečenice u velika. Pretpostaviti da se u tekstu znaci .?! pojavljuju samo kao znaci završetka rečenica. Dakle, u tekstu nema rednih brojeva koji bi se završavali tačkom,... Tekst se završava markerom kraja datoteke.

Enumeracija i enumerisane konstante

enum boolean {NO, YES};
enum meseci {JAN = 1, FEB, MAR, APR, MAJ,JUN, JUL, AVG, SEP, OKT, NOV, DEC}
enum boje {CRVENA, ZELENA=5, PLAVA, LJUBICASTA=10, ZUTA, CRNA}

koriscenje: int x=0; boje b;
x=CRVENA+3; /*x ce biti jednako tri*/
b=ZELENA;
x=b+CRNA; /* 5 + 12=17*/
b=0; /*Greska, ovako ne moze!!!*/


/* Velika slova na pocetku recenice */
#include <stdio.h>
#include <ctype.h>

main()
{
enum {F,T};   /*false,true;0,1*/
int znak,prvi=T; /* znak sa ulaza, indikator pojavepocetka recenice */
 

/* ucitavanje ulaza do markera kraja (EOF) i pretvaranje pocetnih slova recenice u velika i pretvaranje velikih slova iz sredine recenice u mala slova. */
while ( (znak=getchar() ) != EOF)
{
  if (isupper(znak) )
   { if ( !prvi)            /* if (prvi==0)  */
       znak=tolower(znak);    /*u sredini recenice veliko slovo->malo slovo */
     else prvi=F;           /*napusta se pocetak recenice */
   }
  else  if (islower(znak) )
    { if(prvi)                /*recenica pocinje */
       { znak=toupper(znak);  /*  velikim slovom */
         prvi=F;              /*napusta se pocetak recenice */
       }
     }
  else  /*nije slovo */
   if (znak =='.' || znak=='!' || znak =='?')
      prvi=T;     /*novi pocetak */
  putchar(znak); /*slanje rezultata obrade naizlaz */
}
ZADACI ZA VEZBU
Zadatak 1. Napisati program koji broji pojavljivanja samoglasnika i suglasnika u tekstu koji se unosi sa standardnog ulaza (koristiti naredbu switch).
Zadatak 2. Napisati program koji broji pojavljivanja za svako od slova engleske abecede u tekstu koji se unosi sa standardnog ulaza i stampa rezultat na standardni izlaz.
Zadatak 3. Napisati funkciju koja konvertuje malo u veliko slovo.
Napisati program koji prepisuje ulaz na izlaz pri cemu se sva mala slova konvertuju u velika.

 

 

 

 

 

 

 

 

 

 

 

 


Jelena Grmuša

Programiranje 1


e-mail: Jelena Grmuša



Poslednja izmena: januar 2006.
URL: http://www.matf.bg.ac.yu/~jelenagr/P1/