Thứ Năm, 11 Tháng Tám 2022
Trang chủLập trìnhCTDL & Thuật toánTính A^n bằng phương pháp chia để trị

Tính A^n bằng phương pháp chia để trị

XEM THÊM
Duyệt đồ thị, tìm kiếm đường đi dài nhất, đường đi ngắn nhất trong đồ thị
Kiểm tra đồ thị liên thông trong bài toán đồ thị lập trình
Sinh các chuỗi nhị phân có độ dài bằng n trong C/C++
Tìm dãy con có tổng trọng số lớn nhất trong lập trình C/C++
Tính A^n bằng phương pháp chia để trị
Quy hoạch động tìm xâu con chung độ dài lớn nhất

Đọc thêm: Tìm hiểu thuật toán chia để trị trong lập trình, ví dụ áp dụng

Tất nhiên để tính A mũ n trong lập trình C/C++ thì ta có thể tính luôn bằng hàm pow, hoặc không dùng hàm thì cũng có thể dùng cách đơn giản hơn là duyệt vòng lặp. Nhưng trong bài viết này chúng ta sẽ sử dụng chia để trị, mục đích là nhằm nắm chắc hơn phương pháp thuật toán này.

Ta viết code chia để trị cho bài toán tính a mũ n như sau:

#include <iostream>
using namespace std;
long long chiadetri(int a,int n)
{
//2 trường hợp suy biến
	if(n== 0 ) return 1;
	if(n==1) return a;

//Chia đôi n  và gọi đệ quy chia đệ trị
	int temp = chiadetri(a,n/2);

//n&1 tương đương với nếu n là số lẻ - dấu & là toán tử thao tác trên bit
	if(n&1) return temp*temp*a;//n lẻ trả vè kq là temp*temp*a
	return temp*temp; //ngược lại trả về temp * temp
}
int main()
{
	int a, n; cin>>a>>n;
	cout<<"a^n = "<<chiadetri(a,n); //Gọi hàm tính a^n bằng pp chia để trị
}

[Xem tất cả bài viết chủ đề C/C++ tại đây]

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x