GIẢI THUẬT ĐỆ QUY - Cấu trúc dữ liêu-giải thuật.(2)

I : GIẢI THUẬT ĐỆ QUY CƠ BẢN ( phần 2)

Bài 5: Viết chương trình có sử dụng hàm đệ quy tính xⁿ.

#include<conio.h>

#include<stdio.h>

float luythua(intx,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;

}

int 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();

}

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(intn)

{

      int d;

      if(n==1)  {printf("%d",n); return 0;}

      d=n%2; n=nhiphan(n/2);

      printf("%d",d); return 0;

}

int 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 để đảo ngược 1 dãy kí tự nhập từ bàn phím.

#include <stdio.h>

#include <conio.h>

#include <string.h>

void daonguoc(chars[],int n,inti)

{

      if(i==(n/2)) return;

      char tg=s[i];

      s[i]=s[n-i-1];

      s[n-i-1]=tg;

      daonguoc(s,n,i+1);

}

int main()

{

      char s[500];

      intn;

      printf("nhap xau = ");

      gets(s);

      n=strlen(s);

      printf("\n  Day ky tu vua nhap: %s",s);

      if(n==0) return 0;

      daonguoc(s,n,0);

      printf("\n  Day ky tu sau khi dao nguoc la: %s",s);

      getch();

}

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(inta[],int n)

{

      int i;

      for(i=0;i<n;i++)

      {

            printf("a[%d]= ",i);

            scanf("%d",&a[i]);

      }

}

void xem(inta[],int n)

{

      int i;

      printf("\n xem mang vua nhap:");

      for(i=0;i<n;i++)

      printf("%5d",a[i]);

}

int timx( inta[], int n, intx)

{

      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;

      }

      returntimx(a,n-1,x);

}

int 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();

}