SPOJ.COM - Thuật toán bài BOKAM143SOU - Checking cubes

Posted on September 25th, 2016

Đề 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

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 mình triển khai theo thuật toán quay lui có điều kiện - Backtracking.

Lời giải

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 mình 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 mình 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 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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!