HC VIN CÔNG NGH BU CHÍNH VIN THÔNG
BÀI GING
K THUT LP TRÌNH

Biên son : Ths. NGUYN DUY PHNG
Gii thiu môn hc

GII THIU MÔN HC
I. GII THIU CHUNG
S phát trin công ngh thông tin trong nhng nm va qua đã làm thay đi b mt
kinh t xã hi toàn cu, trong đó công ngh phn mm tr thành mt ngành công nghip
quan trng đy tim nng. Vi s hi t ca công ngh vin thông và công ngh thông rin,
t trng v giá tr phn mm chim rt cao trong các h thng vin thông cng nh các thit
b đu cu
i. Chính vì lý do đó, vic nghiên cu, tìm hiu, tin ti phát trin cng nh làm
ch các h thng phn mm ca các k s đin t vin thông là rt cn thit.
Tài liu ging dy “K thut lp trình” cho h đào to t xa đc xây dng da trên
giáo trình “K thut lp trình” đã đc ging dy ti hc vi
n trong nhng nm qua vi
mc đích cung cp cho sinh viên nhng kin thc c bn nht, có tính h thng liên quan
ti lp trình.
Thông qua cun tài liu này, chúng tôi mun gii thiu vi các bn đc v k nng

vin Công ngh Bu chính Vin thông, 2002.
- Bài ging đin t môn hc: “K thut lp trình” ca Hc vin Công ngh Bu
chính Vin thông.
3. t ra mc tiêu, thi hn cho bn thân
t ra các mc tiêu tm thi và thi hn cho bn thân và c gng thc hin chúng
Xây d
ng mc tiêu trong chng trình nghiên cu.
4 Nghiên cu và nm nhng kin thc ct lõi
Sinh viên nên đc qua sách hng dn hc tp trc khi nghiên cu bài ging môn
hc và các tài liu tham kho khác.
5. Tham gia đy đ các bui hng dn hc tp
Thông qua các bui hng dn hc tp, ging viên s giúp sinh viên nm đc ni
dung tng th ca môn hc và gii đáp thc mc, đng th
i sinh viên cng có th trao đi,
tho lun vi nhng sinh viên khác v ni dung bài hc.
6. Ch đng liên h vi bn hc và ging viên
Cách đn gin nht là tham d các din dàn hc tp trên mng Internet, qua đó có th
trao đi trc tip các vn đ vng mc vi ging viên hoc các bn hc khác đang online.
7. T ghi chép li nhng ý chính
Vic ghi chép li nhng ý chính là mt ho
t đng tái hin kin thc, kinh nghim
cho thy nó giúp ích rt nhiu cho vic hình thành thói quen t hc và t duy nghiên cu.
8. Hc đi đôi vi hành
Hc lý thuyt đn đâu thc hành làm bài tp và thc hành ngay đn đó đ hiu và nm
chc lý thuyt. Sinh viên cn cài đt trên máy tính các thut toán trong bài hc bng các ngôn
ng lp trình đ t đó có th hiu và nm chc hn t
 tng và ni dung ca thut toán.

Hà Ni, ngày 20 tháng 02 nm 2006
Ths. Nguyn Duy Phng

d
i dng mt Version mi, ging nh: MS-DOS 4.0 ch tn ti trong thi gian vài tháng
ri thay đi thành MS-DOS 5.0, MS-DOS 5.5, MS-DOS 6.0 . . . ây không phi là mt sn
phm mi nh ta tng mà trong nó còn tn ti nhng li không th b qua đc, vì ngay
MS-DOS 6.0 cng ch là s khc phc hn ch ca MS-DOS 3.3 ban đu.
Trong thi k đu ca tin hc, các lp trình viên xây dng chng trình bng các
ngôn ng lp trình bc th
p, quá trình np và theo dõi hot đng ca chng trình mt cách
trc tip trong ch đ trc tuyn (on-line). Vic tìm và sa li (debbugging) nh ngày nay
là không th thc hin đc. Do vy, trc nhng nm 1960, ngi ta coi vic lp trình
Chng 1: i cng v k thut lp trình cu trúc

4
ging nh nhng hot đng ngh thut nhum màu sc cá nhân hn là khoa hc. Mt s
ngi nm đc mt vài ngôn ng lp trình, cùng mt s mo vt tn dng cu hình vt lý
c th ca h thng máy tính, to nên mt s sn phm l ca phn mm đc coi là mt
chuyên gia nm bt đc nhng bí 
n ca ngh thut lp trình.
Các h thng máy tính trong giai đon này có cu hình yu, b nh nh, tc đ các
thit b vào ra thp làm chm quá trình np và thc hin chng trình. Chng trình đc
xây dng bng k thut lp trình tuyn tính mà ni bt nht là ngôn ng lp trình Assembler
và Fortran. Vi phng pháp lp trình tuyn tính, lp trình viên ch đc phép th hin
chng trình ca mình trên hai c
u trúc lnh, đó là cu trúc lnh tun t (sequential) và
nhy không điu kin (goto). H thng th vin vào ra nghèo nàn làm cho vic lp trình tr
nên khó khn, chi phí cho các sn phm phn mm quá ln, đ tin cy ca các sn phm
phn mm không cao dn ti hàng lot các d án tin hc b tht bi, đc bit là các h thng
tin hc có tm c ln. Nm 1973, Hoare khng
đnh, nguyên nhân tht bi mà ngi M
gp phi khi phóng v tinh nhân to v phía sao V n (Sao Kim) là do li ca chng trình


5
làm ch s phc tp ca các hot đng lp trình. Nm 1969, Hoare đã phát biu các tiên đ
phc v cho vic chng minh tính đúng đn ca chng trình, phát hin tính bt bin ca
vòng lp bng cách coi chng trình va là bn mã hoá thut toán đng thi là bn chng
minh tính đúng đn ca chng trình. Sau đó Dahl, Hoare, Dijiksta đã phát trin thành ngôn
ng lp trình cu trúc.
 trin khai các nguyên lý lp trình c
u trúc, L. Wirth đã thit k và cài đt ngôn
ng ALGOL W là mt bin th ca ALGOL 60. Sau này, L. Wirth tip tc hoàn thin đ
tr thành ngôn ng lp trình Pascal. ây là ngôn ng lp trình gin d, sáng sa v cú pháp,
d minh ha nhng vn đ phc tp ca lp trình hin đi và đc coi là mt chun mc
trong ging dy lp trình.
Nm 1978, Brian Barninghan cùng Denit Ritche thit k ngôn ng lp trình C vi t
i
thiu các cu trúc lnh và hàm khá phù hp vi t duy và tâm lý ca ca ngi lp trình.
ng thi, hai tác gi đã phát hành phiên bn h điu hành UNIX vit ch yu bng ngôn
ng C, khng đnh thêm uy th ca C trong lp trình h thng.
1.2. CU TRÚC LNH, LNH CÓ CU TRÚC, CU TRÚC D LIU
1.2.1. Cu trúc lnh (cu trúc điu khin)
Mi chng trình máy tính v bn cht là mt bn mã hoá thut toán. Thut toán
đc coi là dãy hu hn các thao tác s cp trên tp đi tng vào (Input) nhm thu đc
kt qu ra (output). Các thao tác trong mt ngôn ng lp trình c th đc điu khin bi
các lnh hay các cu trúc điu khin, còn các đi tng chu thao tác thì đc mô t và biu
di
n thông qua các cu trúc d liu.
Trong các ngôn ng lp trình cu trúc, nhng cu trúc lnh sau đc s dng đ xây
dng chng trình. D nhiên, chúng ta s không bàn ti cu trúc nhy không điu kin goto
mc dù ngôn ng lp trình cu trúc nào cng trang b cu trúc lnh goto.



Hình 1.2. Các cu trúc lp
A, B : ký hiu cho các câu lnh đn hoc lnh hp thành. Mi lnh đn l đc gi là
mt lnh đn, lnh hp thành là lnh hay cu trúc lnh đc ghép li vi nhau theo qui đnh
ca ngôn ng, trong Pascal là tp lnh hay cu trúc lnh đc bao trong thân ca begin . . .
end; trong C là tp các lnh hay cu trúc lnh đc bao trong hai ký hiu { ... }.
E, E1, E2, E3 là các biu thc s hc hoc logic. Mt s ngôn ng lp trình coi giá tr

ca biu thc logic hoc đúng (TRUE) hoc sai (FALSE), mt s ngôn ng lp trình khác
nh C coi giá tr ca biu thc logic là đúng nu nó có giá tr khác 0, ngc li biu thc
logic có giá tr sai.
Cn lu ý rng, mt chng trình đc th hin bng các cu trúc điu khin lnh :
tun t, tuyn chn if..else, switch . . case .. default, lp vi đi
u kin trc while , lp vi
điu kin sau do . . while, vòng lp for bao gi cng chuyn đc v mt chng trình, ch

E
E1
E2
E3
A
Chng 1: i cng v k thut lp trình cu trúc

7
1.2.2. Lnh có cu trúc
Lnh có cu trúc là lnh cho phép cha các cu trúc điu khin trong nó. Khi tìm hiu
mt cu trúc điu khin cn xác đnh rõ v trí đc phép đt mt cu trúc điu khin trong
nó, cng nh nó là mt phn ca cu trúc điu khin nào. iu này tng nh rt tm
thng nhng có ý ngha ht sc quan trng trong khi xây d
ng và kim tra li có th xy
ra trong chng trình. Nguyên tc vit chng trình theo cu trúc: Cu trúc con phi đc
vit lt trong cu trúc cha, đim vào và đim ra ca mi cu trúc phi nm trên cùng mt
hàng dc. Ví d sau s minh ha cho nguyên tc vit chng trình:
if (E)
while (E1)
A;
else
do
B;
while(E2);
Trong ví d trên, while (E1) A; là cu trúc con nm trong thân ca cu trúc cha là if
(E) ; còn do B while(E2); là cu trúc con trong thân ca else. Do vy, câu lnh while(E1);
do . . . while(E2) có cùng cp vi nhau nên nó phi nm trên cùng mt ct, tng t nh
vy vi A, B và if vi else.
1.2.3. Cu trúc d liu
Các ngôn ng lp trình cu trúc nói chung đu ging nhau v cu trúc lnh và cu

void main(void) {
printf(“\n Kích c kiu kí t:%d”, sizeof(char));
printf(“\n Kích c kiu kí t không du:%d”, sizeof(unsigned char));
printf(“\n Kích c kiu s nguyên không du:%d”, sizeof(unsigned int));
printf(“\n Kích c kiu s nguyên có du:%d”, sizeof(signed int));
printf(“\n Kích c kiu s nguyên dài không du:%d”, sizeof(unsigned long ));
printf(“\n Kích c kiu s nguyên dài có du:%d”, sizeof(signed long ));
printf(“\n Kích c kiu s thc có đ chính xác đn:%d”, sizeof(float ));
printf(“\n Kích c kiu s thc có đ chính xác kép:%d”, sizeof(double ));
getch();
}
Kích c ca các kiu d liu do ngi dùng đnh ngha là tng kích c ca mi kiu
thành viên trong nó. Chúng ta cng vn dùng toán t sizeof(tên kiu) đ xác đnh đ ln tính
theo byte ca các kiu d liu này.
Mt đim đc bit chú ý trong khi lp trình trên các cu trúc d liu là cu trúc d liu
nào thì phi kèm theo phép toán đó, vì mt bin đc gi là thuc kiu d liu nào
đó nu
nh nó nhn mt giá tr t min xác đnh ca kiu và các phép toán trên kiu d liu đó.
1.3. NGUYÊN LÝ TI THIU
Hãy bt đu t mt tp nguyên tc và ti thiu các phng tin là các cu trúc lnh, kiu
d liu cùng các phép toán trên nó và thc hin vit chng trình. Sau khi nm chc nhng
công c vòng đu mi đt vn đ m rng sang h thng th vin tin ích ca ngôn ng.
Khi làm quen vi mt ngôn ng lp trình nào đó, không nht thit phi l thuc quá
nhiu vào h
 thng th vin hàm ca ngôn ng, mà điu quan trng hn là trc mt bài
toán c th, chúng ta s dng ngôn ng đ gii quyt nó th nào, và phng án tt nht là
lp trình bng chính h thng th vin hàm ca riêng mình. Do vy, đi vi các ngôn ng
lp trình, chúng ta ch cn nm vng mt s các công c ti thiu nh sau:
1.3.1. Tp các phép toán
Tp các phép toán s

int a =3, b =5;
if ( (a !=0) && (b!=0) ) // nu a khác 0 và b khác 0
if ((a!=0) || (b!=0)) // nu a khác 0 hoc b khác 0
if ( !a ) // ph đnh a khác 0
if (a==b) // nu a đúng bng b
Các toán t thao tác bít (không s dng cho float và double)
& : Phép hi các bít.
| : Phép tuyn các bít.
^ : Phép tuyn các bít có loi tr.
<< : Phép dch trái (dch sang trái n bít giá tr 0)
>> : Phép dch ph
i (dch sang phi n bít có giá tr 0)
~ : Phép ly phn bù.
Chng 1: i cng v k thut lp trình cu trúc

10
Ví d 1.2: Vit chng trình kim tra các toán t thao tác bít.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <io.h>
void main(void){
unsigned int a=3, b=5, c; clrscr();
c = a & b; printf(“\n c = a & b=%d”,c);
c = a | b; printf(“\n c = a | b=%d”,c);
c = a ^ b; printf(“\n c = a ^ b=%d”,c);
c = ~a; printf(“\n c = ~a =%d”,c);
c = a << b; printf(“\n c = a << b=%d”,c);
c = a >>b; printf(“\n c = a >> b=%d”,c);
getch();

& L -> R
^ L -> R
| L -> R
&& L -> R
|| L -> R
?: R -> L
=, +=, -=, *=, /=, %=, &=, ^=, |=, <<=, >>= R -> L
1.3.2. Tp các lnh vào ra c bn
Nhp d liu t bàn phím: scanf(“format_string, . . .”, &parameter . . .);
Nhp d liu t tp: fscanf( file_pointer,”format_string, . . .”, &parameter, . . .);
Nhn mt ký t t bàn phím: getch(); getchar();
Nhn mt ký t t file: fgetc(file_pointer, character_name);
Nhp mt string t bàn phím: gets(string_name);
Nhn mt string t file text : fgets(string_name, number_character, file_pointer);
Xut d liu ra màn hình: printf(“format_string . . .”, parameter . . .);
Xut d liu ra file : fprintf(file_pointer, “format_string . . .”, parameter. . .);
Xut mt ký t ra màn hình: putch(character_name);
Xut mt ký t ra file: fputc(file_pointer, character_name);
Xut mt string ra màn hình: puts(const_string_name);
Xut mt string ra file: fputs(file_pointer, const_string_name);
1.3.3. Thao tác trên các ki
u d liu có cu trúc
Tp thao tác trên string:
char *strchr(const char *s, int c) : tìm ký t c đu tiên xut hin trong xâu s;
char *stpcpy(char *dest, const char *src) : copy xâu scr vào dest;
Chng 1: i cng v k thut lp trình cu trúc

12
int strcmp(const char *s1, const char *s2) : so sánh hai xâu s1 và s2 theo th t t
đin, nu s1 < s2 thì hàm tr li giá tr nh hn 0. Nu s1>s2 hàm tr li giá tr

Phép truy nhp ti thành phn cu trúc:
Chng 1: i cng v k thut lp trình cu trúc

13
struct_parameter_name.parameter_name.
Phép gán hai cu trúc cùng kiu:
struct_parameter_name1 = struct_parameter_name2;
Phép tham tr ti thành phn ca con tr cu trúc:
pointer_struct_parameter_name -> struct_parameter_name.
Tp thao tác trên file:
Khai báo con tr file: FILE * file_pointer;
Thao tác m file theo mode: FILE *fopen(const char *filename,const char *mode);
Thao tác đóng file: int fclose(FILE *stream);
Thao tác đc tng dòng trong file: char *fgets(char *s, int n, FILE *stream);
Thao tác đc tng khi trong file:
size_t fread(void *ptr, size_t size,size_t n, FILE *stream);
Thao tác ghi tng dòng vào file: int fputs(const char *s, FILE *stream);
Thao tác ghi tng khi vào file:
size_t fwrite(const void *ptr, size_t size, size_t n, FILE *stream);
Thao tác kim tra s tn ti ca file: int access(const char *filename, int amode);
Thao tác đi tên file: int rename(const char *oldname,const char *newname);
Thao tác loi b file: int unlink(const char *filename);
1.4. NGUYÊN LÝ A PHNG
̇ Các bin đa phng trong hàm, th tc hoc chu trình cho dù có trùng tên
vi bin toàn cc thì khi x lý bin đó trong hàm hoc th tc vn không làm
thay đi giá tr ca bin toàn cc.
̇ Tên ca các bin trong đi ca hàm hoc th tc đu là hình thc.
̇ Mi bin hình thc truyn theo tr cho hàm hoc th tc đu là các bin đa
phng.
̇ Các bin khai báo bên trong các ch

Kt qu sau khi thc hin th tc a = 1 b =8
Trong ví d trên a, b là hai bin toàn cc, hai bin a, b trong th tc Swap là hai bin
cc b. Các thao tác trong th tc Swap gán cho a giá tr 3 và b giá tr 5 sau đó thc hin
đi giá tr ca a =5 và b =3 là công vic x lý ni b ca th tc mà không làm thay đi giá
tr ca bin toàn c
c ca a, b sau thi thc hin xong th tc Swap. Do vy, kt qu sau khi
thc hin Swap a = 1, b =8; iu đó chng t trong th tc Swap cha bao gi s dng ti
hai bin toàn cc a và b. Tuy nhiên, trong ví d sau, th tc Swap li làm thay đi giá tr ca
bin toàn cc a và b vì nó thao tác trc tip trên bin toàn cc.
Ví d 1.5. i giá tr ca hai bin a và b
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <io.h>
int a, b; // khai báo a, b là hai bin toàn cc.
void Swap(void) {
int temp; // khai báo a, b là hai bin đa phng
a= 3; b=5; // gán giá tr cho a và b
temp=a; a=b; b=temp;// đi giá tr ca a và b
printf(“\n Kt qu thc hin trong th tc a=%5d b=%5d:,a,b);
}
void main(void) {
Chng 1: i cng v k thut lp trình cu trúc

15
a=1; b=8; // khi đu giá tr cho bin toàn cc a, b.
Swap();
printf(“\n Kt qu sau khi thc hin th tc a =%5d b=%5d”,a,b);
getch();
}

nguyên mc dù thng hai s nguyên là mt s th
c, tích hai s nguyên hoc tng hai s
nguyên có th là mt s long int. Do vy, mun nhn đc kt qu đúng, chúng ta cn phi
chuyn đi các bin thuc cùng mt kiu trc khi thc hin phép toán. Ngc li, ta không
Chng 1: i cng v k thut lp trình cu trúc

16
th ly modul ca hai s thc hoc thc hin các thao tác dch chuyn bít trên nó, vì nhng
thao tác đó không nm trong đnh ngha ca kiu.
iu tng t cng xy ra vi các string. Trong Pascal, phép toán so sánh hai string
hoc gán trc tip hai Record cùng kiu vi nhau là đc phép, ví d : Str1>Str2, Str1 :=
Str2; Nhng trong C thì các phép toán trên li không đc đnh ngha, nu mun thc hin
nó, chúng ta ch có cách đnh ngha li hoc thc hi
n nó thông qua các li gi hàm.
1.6. NGUYÊN LÝ AN TOÀN
̇ Li nng nht nm  mc cao nht (mc ý đ thit k) và  mc thp nht th
tc phi chu ti ln nht.
̇ Mi li, dù là nh nht cng phi đc phát hin  mt bc nào đó ca
chng trình. Quá trình kim tra và phát hin li phi đc thc hin trc
khi li đó hoành hành.
Các loi li thng xy ra trong khi vit chng trình có th đc tng kt li nh
sau:
Li đc thông báo bi t khoá error (li cú pháp): loi li này thng xy ra
trong khi son tho chng trình, chúng ta có th vit sai các t khoá ví d thay vì vit là int
chúng ta son tho sai thành Int (li ch in thng thành in hoa), hoc vit sai cú pháp các
biu thc nh thiu các du ngoc đn, ngoc kép hoc du chm ph
y khi kt thúc mt
lnh, hoc cha khai báo nguyên mu cho hàm .
Li đc thông báo bi t khoá Warning (li cnh báo): li này thng xy ra khi
ta khai báo bin trong chng trình nhng li không s dng ti chúng, hoc li trong các

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef float dathuc[MAX];
void In(dathuc A, int n, char c){
int i;
printf("\n Da thuc %c:", c);
for(i=0;i<n; i++)
printf("%6.2f", A[i]);
}
void Init( dathuc A, int *n, dathuc B, int *m){
int i;float temp;
printf("\n Nhap n="); scanf("%d", n);*n=*n+1;
printf("\n Nhap m="); scanf("%d",m); *m=*m+1;
printf("\n Nhap he so da thuc A:");
for(i=0; i<*n;i++){
printf("\n A[%d]=", i); scanf("%f", &temp);
A[i]=temp;
}
printf("\n Nhap he so da thuc B:");
for(i=0; i<*m;i++){
printf("\n B[%d]=",i); scanf("%f", &temp);
B[i] = temp;
}
In(A,*n,'A'); In(B,*m,'B');
}
void Tong(dathuc A, int n, dathuc B, int m, dathuc C){
int i, k;
if (n>= m ){

khc phc bng cách đnh ngha BAC đ ln thì trong trng hp x lý các đa thc có bc n
nh s gây nên hin tng lãng phí b nh, và trong nhiu trng hp không đ b nh đ
đnh ngha đa thc. Gii pháp khc phc các li loi này là chúng ta s dng con tr thay
cho các hng, k thut này s đc th
o lun k trong Chng 2.
1.7. PHNG PHÁP TOP-DOWN
̇ Quá trình phân tích bài toán đc thc hin t trên xung di. T vn đ
chung nht đn vn đ c th nht. T mc tru tng mang tính cht tng
quan ti mc đn gin nht là đn v chng trình.
Mt trong nhng nguyên lý quan trng ca lp trình cu trúc là phng pháp phân
tích t trên xung (Top - Down) vi quan đim “thy cây không bng thy rng”, phi
đng cao hn đ quan sát tng th khu rng ch không th đng trong rng quan sát chính
nó.
Quá trình phân rã bài toán đc thc hin theo tng mc khác nhau. Mc thp nht
đc gi là mc tng quan (level 0), mc tng quan cho phép ta nhìn tng th h thng
thông qua các chc nng ca nó, nói cách khác mc 0 s tr li thay cho câu hi “H thng
có th thc hin đc nhng gì ?”. Mc tip theo là mc các chc nng chính.
 mc này,
nhng chc nng c th đc mô t. Mt h thng có th đc phân tích thành nhiu mc
khác nhau, mc thp đc phép s dng các dch v ca mc cao. Quá trình phân tích tip
Chng 1: i cng v k thut lp trình cu trúc

19
tc phân rã h thng theo tng chc nng ph cho ti khi nào nhn đc mc các đn th (
UNIT, Function, Procedure), khi đó chúng ta tin hành cài đt h thng.
Chúng ta s làm rõ hn tng mc ca quá trình Top-Down thông qua bài toán sau:
Bài toán: Cho hai s nguyên có biu din nh phân là a=(a
1
, a
2

F1- Chuyn đi a, b thành các s nh phân;
F2- Tính tng hai s nguyên: a + b;
F3- Tính hiu hai s nguyên: a - b;
F4 Tính tích hai s nguyên: a *b;
F5- Thng hai s nguyên : a/b;
F6- Phn d hai s nguyên: a % b;
F7- c s chung ln nht ca hai s nguyên.
Mc 1. Mc các chc nng chính: mi chc nng cn mô t đy đ thông tin vào
(Input), thông tin ra (Output), khuôn d
ng (Format) và các hành đng (Actions).
Chc nng F1: Chuyn đi a, b thành các s  h nh phân
Input : a : integer;
Output : a=(a
1
, a
2
, . . ., a
n
)
b
; (*khai trin c s b bt k*)
Format : Binary(a);
Actions
{ Q = n; k=0;
While ( Q≠ 0 ) {
a
k
= q mod b;
q = q div b;
k = k +1;

20
c = a + b;
Format: Addition(a, b);
Actions {
c = 0;
for (j = 0; j< n; j++){

d = (a
j
+ b
j
+ c) div 2;
s
j
= a
j
+ b
j
+ c - 2d;
c = d;
}
s
n
= c;
< Khai trin nh phân ca tng là (s
n
s
n-1
. . .s
1

Chc nng F4: Tích hai s nguyên a, b.
Input:
a=(a
1
, a
2
, . . ., a
n
),
b = (b
1
, b
2
, .., b
n
);
Output:
c = a * b;
Format: Multual(a, b);
Actions {
For (j =0; j< n; j++){
If ( b
j
=1)
c
j
= a<<j;
Else
c
j

1
, b
2
, .., b
n
);
Output:
c = a div b;
Format: Division(a, b);
Actions {
c = 0;
while ( a>= b ) {
c = c +1;
a = Subtraction(a, b);
}
return(c);
}
Chc nng F6: Modul hai s nguyên a, b.
Input:
a=(a
1
, a
2
, . . ., a
n
),
b = (b
1
, b
2

Actions {
Chng 1: i cng v k thut lp trình cu trúc

22
while ( a≠ b ) {
if (a > b)
a = Subtraction(a, b)
else
b = Subtraction(b,a);
}
return(a);
}
 ý rng, sau khi phân rã bài toán  mc 1, chúng ta ch cn xây dng hai phép toán
cng và phép tính nhân các s nh phân ca a, b. Vì hiu hai s a và b chính là tng s ca
(a,-b). Tng t nh vy, tích hai s a và b đc biu din bng tng ca mt s ln phép
nhân mt bít nh phân ca vi a. Phép chia và ly phn d hai s a và b chính là phép tr
nhiu ln s a. Phép tìm USCLN cng tng t nh vy.
i v
i các h thng ln, quá trình còn đc mô t tip tc cho ti khi nhn đc
mc đn v chng trình. Trong ví d đn gin này, mc đn v chng trình xut hin
ngay ti mc 1 nên chúng ta không cn phân rã tip na mà dng li đ cài đt h thng.
1.8. PHNG PHÁP BOTTOM-UP
̇ i t cái riêng ti cái chung, t các đi tng thành phn  mc cao ti các
đi tng thành phn  mc thp, t mc đn v chng trình ti mc tng
th, t nhng đn v đã bit lp đt thành nhng đn v mi.
Nu nh phng pháp Top-Down là phng pháp phân rã vn đ mt cách có h
thng t trên xung,
đc ng dng ch yu cho quá trình phân tích và thit h thng, thì
phng pháp Bottom- Up thng đc s dng cho quá trình cài đt h thng. Trong ví d
trên, chúng ta s không th xây dng đc chng trình mt cách hoàn chnh nu nh ta

return(0);
}
int Addition(int a, int b){
int du, d, s, j, c=0;
du=0;
for ( j=0; j<=15; j++){
d =( bit(a,j) + bit(b, j) +du)/2;
s = bit(a,j)+bit(b,j)+ du - 2*d;
c = c | (s <<j);
du = d;
}
return(c);
}
int Multial(int a, int b) {
int c,j, p=0;
for(j=0; j<=15; j++){
c = bit(b, j);
if (c==1) {
c = a<<j;
p= Addition(p, c);
}
else c=0;
}
return(p);
}
int Subtraction(int a, int b){
int c;
b=-b;
c=Addition(a,b);return(c);
Chng 1: i cng v k thut lp trình cu trúc

printf("\n 3- Tong hai so a,b");
printf("\n 4- Hieu hai so a,b");
printf("\n 5- Tich hai so a,b");
printf("\n 6- Thuong hai so a,b");
printf("\n 7- Phan du hai so a,b");
printf("\n 8- USCLN hai so a,b");
printf("\n 0- Tro ve");
key=getch();
switch(key){
case '1': Init(&a, &b); control=1; break;
case '2':
if (control){
Binary(a); Binary(b);

Trích đoạn ngd ng hàng đ i Danh sách liên kt kép nh ngha và khái n im nh ngha cây nh phân theo danh sách liê nk t: Duy t theo tht sau (Postorder Travesal)

---