Prevođenje u C program

Prevedimo sada program iz paskalolikog jezika (za koji smo dokazali totalnu korektnost), u C program vodeći računa da pri tome ne narušimo invarijantu petlje i korektnost programa.

Prateći algoritam korak po korak, dobija se sledeći C kod programa:

#include<stdio.h>
#include<stdlib.h>

main()
{ 
 unsigned int x, y, z1, z2; 
 unsigned int q, r; 
 printf("Unesite brojeve x i y za koje zelite da izracunate celobrojno deljenje:\n"); 
 scanf("%d%d", &x, &y);
 if(y == 0)
 {
   printf("Greska pri unosu vrednosti y!\n");   
   exit(1);
 }
 q = 0;
 r = x; 
 z1 = y;
 z2 = 1;
 while (z1 < r ) 
 {
   z1 = 2 * z1;
   z2 = 2 * z2; 
 }
 if(z1 <= r )
 {
   r = r - z1;
   q = q + z2;
 }
 while (z2 != 1) 
 {
   z1 = z1 / 2;
   z2 = z2 / 2;
   if(z1 <= r )
   {
     r = r - z1;
     q = q + z2;
   }
 }
 printf("%d = %d * %d + %d\n", x, q, y, r); 
}

Iskoristimo sada činjenicu da je operacija šiftovanja (pomeranja) datog broja udesno za n mesta ekvivalentna celobrojnom deljenju sa n-tim stepenom dvojke, a operacija šiftovanja ulevo za n mesta ekvivalentna množenju tog broja sa n-tim stepenom dvojke, pri čemu su ove operacije efikasnije od pomenutih operacija množenja i deljenja sa stepenom dvojke.

Program možemo napisati koristeći samo operacije sabiranja, oduzimanja i šiftovanja ulevo i udesno na sledeći način:

#include<stdio.h>
#include<stdlib.h>

main()
{ 
 unsigned int x, y, z1, z2; 
 unsigned int q, r; 
 printf("Unesite brojeve x i y za koje zelite da izracunate celobrojno deljenje:\n"); 
 scanf("%d%d", &x, &y); 
 if(y == 0)
 {
   printf("Greska pri unosu vrednosti y!\n");   
   exit(1);
 }
 q = 0;
 r = x; 
 z1 = y;
 z2 = 1; 
 while (z1 < r ) 
 {
   z1 = z1 << 1;
   z2 = z2 << 1; 
 }
 if(z1 <= r )
 {
   r = r - z1;
   q = q + z2;
 }
 while (z2 != 1) 
 {
   z1 = z1 >> 1;
   z2 = z2 >> 1;
   if(z1 <= r )
   {
     r = r - z1;
     q = q + z2;
   }
 }
 printf("%d = %d * %d + %d\n", x, q, y, r); 
}

#include<stdio.h>
#include<stdlib.h>

main()
{ 
 unsigned int x, y, z1, z2; 
 unsigned int q, r; 
 printf("Unesite brojeve x i y za koje zelite da izracunate celobrojno deljenje:\n"); 
 scanf("%d%d", &x, &y);
 if(y == 0)
 {
   printf("Greska pri unosu vrednosti y!\n");   
   exit(1);
 }
 q = 0;
 r = x; 
 z1 = y;
 z2 = 1; 
 while (z1 < r ) 
 {
   z1 <<= 1;
   z2 <<= 1; 
 }
 if(z1 <= r )
 {
   r -= z1;
   q += z2;
 }
 while (z2 != 1) 
 {
   z1 >>= 1;
   z2 >>= 1;
   if(z1 <= r )
   {
     r -= z1;
     q += z2;
   }
 }
 printf("%d = %d * %d + %d\n", x, q, y, r); 
}

Naredna: Selection sort Gore: Hardverdsko celobrojno deljenje Prethodna: Dokaz zaustavljanja programa   Sadržaj