SPOJ.COM – Thuật toán bài BOKAM143SOU – Checking cubes
25/09/2016 4 minutes read
Share:
Đề bài:
Cho một số nguyên N. Tìm ra số lượng cách để biểu diễn số N thành tổng của tối đa 5 số lập phương.
Đầu vào:
1 dòng chứa số N, với 1 <= N <= 12500.
Đầu ra:
In ra kết quả về số lượng cách.
Ví dụ:
Đầu vào:
64
Đầu ra:
2
Giải thích:
- Cách 1: 64 = 27 + 27 + 8 + 1 + 1 + Cách 2: 64 = 64 + 0 + 0 + 0 + 0
Các bạn có thể tham khảo đề bài tiếng anh và submit code tại: http://www.spoj.com/problems/BOKAM143SOU/
Phân tích:
- Trước tiên ta sẽ tìm tất cả những số lập phương không lớn hơn N + Sau đó kiểm tra tất cả các trường hợp có thể + Có nhiều cách triển khai, tuy nhiên ở đây tôi triển khai theo thuật toán quay lui có điều kiện - Backtracking
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include<iostream> | |
| using namespace std; | |
| int N; // Số đầu vào | |
| int Answer; // Số lượng cách | |
| int A[51]; // Mảng lưu các số lập phương <= N | |
| int Leng; // Lưu số lượng các số lập phương <= N | |
| /* | |
| * num : số phần tử đã chọn, khi num = 5 thì sẽ được một cách | |
| * sum : là tổng của các số đã chọn | |
| * oldpos : lưu vị trí của số đã chọn lúc trước | |
| * số chọn sau phải có vị trí lớn hơn hoặc bằng vị trí số chọn trước | |
| * => các cách sẽ không bị lặp lại | |
| */ | |
| void Check(int num, int sum, int oldpos) | |
| { | |
| // Khi chọn đủ 5 số mà tổng các số đã chọn == N thì được 1 cách mới | |
| if(num == 5) | |
| { | |
| if(sum == N) Answer++; | |
| return; | |
| } | |
| // Duyệt mảng các số lập phương <= N để thử các số | |
| for(int i = 0; i < Leng; i++) | |
| if(i >= oldpos) | |
| Check(num + 1, sum + A[i], i); | |
| } | |
| int main() | |
| { | |
| // Comment dòng này trước khi submit | |
| freopen("input.txt","r",stdin); | |
| cin >> N; | |
| Leng = 0; | |
| Answer = 0; | |
| // Tìm ra tất cả các số lập phương <= N và lưu vào 1 mảng | |
| while(true) | |
| { | |
| int temp = (Leng * Leng * Leng); | |
| if(temp > N) break; | |
| A[Leng++] = temp; | |
| } | |
| // Bắt đầu backtrack để thử tất cả các trường hợp xảy ra | |
| Check(0, 0, -1); | |
| cout << Answer << endl; | |
| return 0; | |
| } |
Code by Phạm Văn Lâm
Share: