dungnv » Giải Thuật
DQ.1.2 GIẢI THUẬT ĐỆ QUY
7:42 PM |
Bài 6: Viết chương trình
có sử dụng hàm đệ quy để xuất biểu diễn nhị phân của 1 số nguyên.
#include <stdio.h>
#include <conio.h>
int nhiphan(int n)
{ int d;
if(n==1)
{printf("%d",n); return 0;}
d=n%2; n=nhiphan(n/2);
printf("%d",d); return 0;
}
void main ()
{ int n;
printf("nhap n=
");scanf("%d",&n);
printf("\n bieu dien nhi phan cua %d
:",n);
nhiphan(n);
getch();
}
Bài
7: Viết chương trình có sử dụng hàm đệ quy để xuất ngược 1 dãy kí tự.
#include <stdio.h>
#include <conio.h>
#include <string.h>
char xuatnguoc(char
s[],int n)
{ if(n==0) return 0;
putchar(s[n-1]);
xuatnguoc(s,n-1);
return 0;
}
main ()
{ char s[50];
int n;
printf("nhap xau= ");
fflush(stdin); gets(s);
n=strlen(s);
if(n==0) return 0;
printf("\n xuat nguoc cua day ky tu %s
la: ",s);
xuatnguoc(s,n);
getch();
return 0;
}
Bài 8: Viết chương trình
nhập 1 mảng số nguyên, nhập 1 giá trị x từ bàn phím, tìm vị trí có x cuối cùng
trong mảng, sử dụng kĩ thuật đệ quy.
#include <stdio.h>
#include <conio.h>
void nhap(int a[],int n)
{ int i;
for(i=0;i<n;i++)
{ printf("a[%d]= ",i);
scanf("%d",&a[i]);}
}
void xem(int a[],int n)
{ int i;
printf("\n xem mang vua nhap:");
for(i=0;i<n;i++)
printf("%5d",a[i]);
}
int timx( int a[], int n,
int x)
{ if(a[n]==x)
{printf("\n\n vi tri xuat hien cuoi
cung cua %d trong mang la : %d",x,n+1);
return 0;
}
if(n==0)
{ printf("\n\n gia tri %d khong xuat
hien trong mang",x);
return 0;
}
return timx(a,n-1,x);
}
void main()
{ int a[50],n,x;
printf(" nhap so luong phan tu cua mang
n = ");
scanf("%d",&n);
if(n<=0) printf("so luong phan tu
ban nhap ko hop le!");
else
{ printf(" nhap x = ");
scanf("%d",&x);
nhap(a,n);
xem(a,n);
timx(a,n-1,x);
}
getch();
}
Bài 9: Viết chương trình
nhập 1 ma trận vuông các số nguyên, nhập 1 giá trị x. Tìm vị trí <dòng –
cột> có x. Sử dụng kĩ thuật đệ quy.
#include <stdio.h>
#include <conio.h>
void nhap( int a[][50],int
n)
{ int i,j,tg;
if (n<=0) printf(" so hang so cot
ban nhap khong hop le!");
else
{ for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ printf("a[%d][%d] = ",i,j);
scanf("%d",&tg);
a[i][j]=tg;
}
printf("\n\n");
}
}
void xem( int a[][50],int
n)
{ int i,j;
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
printf("%5d",a[i][j]);
printf("\n");
}
}
void timx( int a[][50],
int i, int n, int x)
{ if(a[i][n]==x)
{ printf("\n vi tri xuat hien : Hang
%d - Cot %d",i+1,n+1);
return ;
}
if (n<0) return ;
timx(a,i,n-1,x);
}
void main()
{ int a[50][50],n,x,i=0;
printf("nhap so hang so cot n= ");
scanf("%d",&n);
nhap(a,n);
xem(a,n);
printf("\n nhap x = ");
scanf("%d",&x);
for(i=0;i<n;i++) timx(a,i,n-1,x);
getch();
}
DQ.1.1 GIẢI THUẬT ĐỆ QUY
7:40 PM |
Bài 1: Viết chương trình
xuất n trị đầu tiên của 1 cấp số cộng có số hạng đầu là a (nhập từ bàn phím),
công sai r (nhập từ bàn phím). Sử dụng kỹ thuật đệ quy để xây dựng hàm tính trị
thứ i của 1 cấp số cộng.
#include<conio.h>
#include<stdio.h>
int csc(int n,int a,int r)
{ if (n==1) return a;
return(r+csc(n-1,a,r));
}
void main()
{ int n, a, r, i;
printf("nhap
so hang dau a= "); scanf("%d",&a);
printf("nhap
cong sai r= "); scanf("%d",&r);
printf("nhap
so luong cac phan tu can xuat n= ");
scanf("%d",&n);
if
(n<=0) printf("so luong cac phan tu can xuat ban nhap ko hop
le!");
for(i=1;i<=n;i++)
printf("\n
tri thu %2d cua csc= %5d",i,csc(i,a,r));
getch();
}
Bài 2: Cho mảng gồm n phần
tử. Viết chương trình có sử dụng hàm đệ quy tính tổng các phần tử của mảng.
#include<conio.h>
#include<stdio.h>
int tong(int a[],int n)
{ if(n==1) return a[0];
return (a[n-1]+tong(a,n-1));
}
void main()
{ int a[50], n, i;
printf("\n nhap so luong phan tu cua
mang n= ");
scanf("%d",&n);
if (n<=0) printf("so luong phan tu
ban nhap ko hop le!");
else
{ for(i=0;i<n;i++)
{ printf("a[%d]= ",i);
scanf("%d",&a[i]);
}
printf("\n tong=
%5d",tong(a,n));
}
getch();
}
Bài 3: Cho mảng gồm n phần
tử. Viết chương trình có sử dụng hàm đệ quy cho biết giá trị lớn nhất, giá trị
nhỏ nhất của mảng.
#include<conio.h>
#include<stdio.h>
int max(int a[],int n)
{ if(n==1) return a[0];
if (a[n-1]>max(a,n-1)) return a[n-1];
return max(a,n-1);
}
int min(int a[],int n)
{ if(n==1) return a[0];
if (a[n-1]<min(a,n-1)) return a[n-1];
return min(a,n-1);
}
void main()
{ int a[50],n,i;
printf("\n nhap so luong phan tu cua
mang n= ");
scanf("%d",&n);
if(n<=0) printf("so luong phan tu
ban nhap ko hop le!");
else
{ for(i=0;i<n;i++)
{ printf("a[%d]= ",i);
scanf("%d",&a[i]);
}
printf("\n max=
%5d",max(a,n));
printf("\n min=
%5d",min(a,n));
}
getch();
}
Bài 4: Cho ma trận có m
hàng, n cột. Viết chương trình có sử dụng hàm đệ quy cho biết giá trị lớn nhất,
giá trị nhỏ nhất của ma trận.
#include <stdio.h>
#include <conio.h>
void nhap( int a[][50],int
m, int n)
{ int i,j,tg;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{ printf("a[%d][%d]= ",i,j);
scanf("%d",&tg);
a[i][j]=tg;
}
}
void xem( int a[][50],int
m,int n)
{ int i,j;
printf("\n xem mang vua nhap:\n");
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
printf("%5d",a[i][j]);
printf("\n");
}
}
int min1( int a[][50], int
m,int n)
{ if(n==0) return a[m][n];
if (a[m][n]<min1(a,m,n-1)) return
a[m][n];
return min1(a,m,n-1);
}
int min( int a[][50], int
m, int n)
{ if(m==0) return
min1(a,m,n);
if (
min1(a,m,n)<min(a,m-1,n)) return min1(a,m,n);
return min(a,m-1,n);
}
int max1(int a[][50],int
m,int n)
{ if (n==0)return a[m][n];
if (a[m][n]>max1(a,m,n-1)) return
a[m][n];
return max1 (a,m,n-1);
}
int max(int a[][50],int
m,int n)
{ if(m==0) return
max1(a,m,n);
If (max1(a,m,n)>max(a,m-1,n)) return
max1(a,m,n);
return max(a,m-1,n);
}
void main()
{ int a[50][50],m,n;
printf("Nhap so cot cua ma tran n =
"); scanf("%d",&n);
printf("Nhap so hang cua ma tran m =
"); scanf("%d",&m);
if ((n<=0)||(m<=0)) printf("so
hang so cot ban nhap ko hop le!");
else
{ nhap(a,m,n);
xem(a,m,n);
printf("\n min = %d",min(a,m-1,n-1));
printf("\n max = %d",max(a,m-1,n-1));
}
getch();
}
Bài
5: Viết chương trình có sử dụng hàm đệ quy tính xn.
#include<conio.h>
#include<stdio.h>
float luythua(int x,int n)
{ if(x==0) return 0;
if(n==0) return 1;
if(n<0) return (1/(luythua(x,-n-1)*x));
return luythua(x,n-1)*x;
}
void main()
{ int x,n;
printf("nhap x va n: ");
scanf("%d%d",&x,&n);
printf("%d^%d=%5.2f",x,n,luythua(x,n));
getch();
