Viết chương trình đệ quy tính tổng n số nguyên đầu tiên
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (69.09 KB, 6 trang )
1. Viết chương trình đệ quy tính tổng n số nguyên đầu tiên
long int Tong(long int n){
if (n==0){
return 0;
} else return (Tong (n-1)+n);
}
Int main(){ cout<<Tong(10); getch(); }
2. Viết chương trình đệ quy tính ước số chung lớn nhất của hai số nguyên dương a và
b.
int USCLN(int a, int b){
if (b==0){
return a;
} else return USCLN(b, a%b);
}
3. Viết chương trình tìm số lớn nhất trong dãy số x
1
,...,x
n
.
Int A[]= {-5, -4,-2,400,311,711,8,12,30,34,45};
1. Tìm tuần tự
int max = A[0];
int n = sizeof(A)/sizeof(int);
for (int i=1;i<n;i++){
if (max<A[i]) max = A[i];
}
2. Tìm đệ quy
int A[]={-5, -4,-2,400,311,711,8,12,30,34,45};
int Tg;
int Max(int m){
if (m ==0){
return A[0];
} else{
Tg = Max(m-1);
if (A[m]>Tg) return A[m];
else return Tg;
}
}
int n = sizeof(A)/sizeof(int);
cout << Max(n-1);
4. Cho mảng A có n số nguyên đã được sắp xếp không giảm. Xây dựng thủ tục đệ quy tìm
phần tử x trong dãy theo thuật toán tìm kiếm nhị phân.
int A[]={-5, -4,-2,0,3,7,8,12,30,34,45};
int k;
int BS(int x, int i, int j){
if (i<=j){
k = (int)((i+j)/2);
if (A[k]==x) return k;
else
if (A[k]>x) return BS(x,i,k-1);
else return BS(x,k+1,j);
} else return -1;
}
int main(){
int n = sizeof(A)/sizeof(int);
int x = -4;
cout << BS(x,0,n-1);
}
5. Cho đa thức P
n
(x) = a
n
x
n
+ a
n-1
x
n-1
+...+a
1
x+a
0
. Xây dựng thuật toán tính P
n
(x
0
) dựa trên biểu diễn
P
n
(x) = (((...((a
n
x+ a
n-1
)x+a
n-2
)x+....)x+a
2
)x+a
1
)x+a
0
6. Viết chương trình tìm số lớn nhất, số nhỏ nhất trong danh sách liên kết S có cấu
trúc
typedef struct node{
int k;
struct node* next;
} list;
list *s;
7. Viết thủ tục đệ quy tìm số lớn nhất, số nhỏ nhất trong danh sách liên kết S có cấu
trúc
typedef struct node{
int k;
struct node* next;
} list;
list *s;
// Ky phap Ba Lan
//Tinh gia tri bieu thuc, bieu thuc cho o dang hau to
// DevC++
//----------------------------------------------------
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<malloc.h>
#include<string.h>
#include<ctype.h>
#define maxlen 255
#define n 15
using namespace std;
typedef char chars[maxlen];
chars M[n] = {"24","4","+","2","/","2","*","6","1","2","+","/","12","*","-"};
typedef struct node{
int data;
struct node* next;
} stack;
stack *s;
void Print(stack* &Qptr){
if (Qptr != NULL){
cout<<Qptr->data;
cout<<Qptr->next;
}
else cout<<endl;
}
void push(int x, stack * &sptr){
stack *m;
m = (stack*)malloc(sizeof(stack));
m->data = x;
m->next = sptr;
sptr = m;
}
void pop(stack * &qptr, int &x){
x = qptr->data;
qptr = qptr->next;
}
int calc(int a, int b, char x){
int y;
switch(x){
case '+': y = a+b;break;
case '-': y = a-b;break;
case '*': y = a*b;break;
case '/': y = a/b;break;
}
return y;
}
int main(){
int i,j, kq, a, b;
chars x;
for(i=0;i<n;i++){
strcpy(x,M[i]);
if (x[0]>='0'&& x[0]<='9'){
a = 0;
for(j=0;j<strlen(x);j++)
a = a*10 + (char(x[j])-48);
push(a,s);
}
