Cách tính lũy thừa nhanh

     

Trong bài này chúng ta sẽ bên nhau đi tìm gọi về thuật toán tính lũy thừa cấp tốc trong C/C++. Thông thường so với các vấn đề tính lũy thừa họ thường sử dụng hàm pow sẽ giải pháp xử lý nhưng đối với các câu hỏi lớn sẽ mất không ít thời gian hơn nhằm xử lý.

Bạn đang xem: Cách tính lũy thừa nhanh

*


*

Bài viết này sẽ giới thiệu các phương pháp để giải một câu hỏi tính lũy quá một cách đơn giản dễ dàng và kết quả nhất.

Đề bài: Cho nhì số nguyên a và b. Tính lũy thừa bậc b của a (a^b).


1. Sử dụng hàm pow

Đây là cách dễ dàng và đơn giản nhất nhằm tính lũy thừa bậc b của a. Trong tủ sách cmath của C/C++ họ có hàm pow, cho phép tính lũy thừa.

Bài viết này được đăng tại


#include #include using namespace std;int main() { long long a, b, result; a = 5; b = 10000; result = pow(a, b); cout
Đây là cách đơn giản và sớm nhất có thể để giải quyết và xử lý bài toán.

Xem thêm: Bài Soạn Cấp Độ Khái Quát Của Nghĩa Từ Ngữ, Soạn Bài Cấp Độ Khái Quát Của Nghĩa Từ Ngữ

2. Sử dụng vòng lặp

Trong trường hòa hợp b = n là số nguyên dương, lũy thừa bậc n của a là tích của n quá số bằng nhau.

Ngoài việc áp dụng hàm pow trong thư viện tất cả sẵn làm việc C/C++, họ còn có 1 cách khá là quen thuộc với những người dân mới làm quen với lập trình đó là sử dụng vòng for. Ý tưởng thực thi thuật toán này là lặp từ là một tới b, với từng vòng lặp triển khai nhân cùng với a.

Triển khai việc với ngôn ngữ C/C++ như sau:


#include using namespace std;long long power(long long a, long long b) { long long result = 1; for(int i = 1; i
Thuật toán này công dụng với input là các số nhỏ. Mang sử những giá trị nguồn vào vượt thừa 10^8 thì chương trình chạy sẽ tốn không hề ít thời gian và cỗ nhớ, nên họ sẽ bao gồm cách buổi tối ưu hơn. Độ tinh vi của thuật toán này lên tới mức O(n).

3. Thực hiện công thức truy vấn hồi

Đây là cách tối ưu nhất khi tiến hành tính lũy thừa cơ mà không đề nghị dùng tới hàm pow. Giả sử muốn tính x^n theo cách thông thường sẽ đề nghị dùng cho tới n bước, tuy vậy khi sử dụng công thức truy tìm hồi thì sẻ giảm được 1 nửa. Ở đây bọn chúng tá sẽ thực hiện công thức sau để thực thi bài toán.

Xem thêm: Please Wait - 11 Cách Kết Hợp Cùng Áo Màu Hồng Đẹp Mà Không Sến

Áp dụng bí quyết và thực hiện thuật toán chúng ta sẽ có cách viết theo cách đệ quy như sau:


int sqr(int x) return x*x;int pow(int a, int b) if (b == 0) return 1; else if (b % 2 == 0) return sqr(pow(a, b/2)); else return a * (sqr(pow(a, b/2)));
Kết quả tương tự như như các cách bên trên nhưng độ phức tạp bé dại hơn tương đối nhiều chỉ O(log2(b)).

Trên đó là phần giới thiệu tương tự như triển khai của các thuật toán tính lũy thừa trong C/C++. Đây cũng là đông đảo thuật toán tuyệt được sử dụng cũng như rât hữu ích trong quy trình giải các bài toán tra cứu kiếm. Khôn cùng mong nội dung bài viết sẽ hữu ích cho bạn !



Tìm những số chẵn lẻ bởi Queue và Stack

Để có tác dụng được bài này chúng ta cần có kiến thức và kỹ năng về cấu trúc Queue…



thiết đặt hàng hóng Queue bởi mảng một chiều

bọn họ sẽ thuộc nhau mày mò về cách cài đặt hàng hóng Queue bằng…



setup hàng ngóng Queue bởi danh sách link

họ sẽ cùng nhau khám phá về cách khởi tạo kết cấu dữ liệu…



Hàng hóng Queue là gì? cấu trúc dữ liệu và những cách thiết lập Queue

Trong giải đáp này mình sẽ giới thiệu các bạn một cấu tạo lưu trữ…


bài bác tập kiểm tra số nguyên tố bằng Stack

họ sẽ cùng mọi người trong nhà tạo một cấu tạo Stack với danh sách liên kết…


bài bác tập biến đổi cơ số bởi Stack

Trong lý giải này bản thân sẽ thực hiện giải một bài xích toán biến hóa cơ…


thiết lập Stack bởi mảng một chiều

bọn họ sẽ lần lượt tiến hành tạo các hàm cơ phiên bản cho Stack như:…


thiết đặt Stack bằng danh sách links

bọn họ sẽ thực hiện lần lượt các thao tác trong Stack thực hiện danh…


chống xếp Stack là gì? cấu trúc và cơ chế vận động ra sao?

Trong gợi ý này mình sẽ giới thiệu chúng ta một kết cấu lưu trữ…


Cây đỏ black là gì? cấu tạo của Red-Black Tree

Trong trả lời này mình vẫn giới thiệu các bạn một cấu tạo dữ liệu…


Xóa Node khỏi cây nhị phân tra cứu kiếm

bọn họ sẽ cùng nhau thực hiện xóa Node có một con, Node có 2…


search Node MAX cùng MIN trong cây nhị phân tìm kiếm

bọn họ sẽ thực hiện một vài giải pháp tìm ra cực hiếm MAX với MIN…


Xuất Node bé và lá vào cây nhị phân tìm kiếm

Trong lí giải này mình sẽ giới thiệu các bạn cách xuất các Node con…


kiếm tìm kiếm Node trên cây nhị phân search kiếm

Trong lí giải này mình vẫn giới thiệu các bạn cách tìm kiếm kiếm một Node…


Thêm Node vào cây nhị phân tìm kiếm

Trong khuyên bảo này mình vẫn giới thiệu các bạn về kết cấu dữ liệu…


kết cấu cây nhị phân là gì? chuyển động ra sao?

Trong bài này mình đã giới thiệu các bạn một vào các cấu tạo dữ…


Gộp hai danh sách links đôi

họ sẽ thuộc nhau khám phá về phương pháp nối hai list liên kết…