Tìm dãy *2 /3 để đạt được N từ số ban đầu?

[dangle2006]

Xin chào các bác, em có một bài như thế này:
Cho 2 phép toán *2 (nhân với 2) và /3 (chia nguyên cho 3). Người ta chứng minh được rằng: cho trước một số tự nhiên n, xuất phát từ 1, sau một số hữu hạn thực hiện các phép *2 và /3 ta sẽ thu được kết quả là n. Viết ct cho nhập vào một số tự nhiên n (n<5.000) từ bàn phím, từ đó hãy thể hiện dãy các phép toán *2 và /3 để xuất phát từ 1, ta thu được n.
Ví dụ: nhập n=6, xuất ra 6=1*2*2*2*2*2/3/3*2 (các phép toán lần lượt được thực hiện từ trái sang phải)
Bác nào tìm giải thuật giúp em với. Cảm ơn nhiều!

[Kevin Hoang]

Ò, lần đầu gặp bài này thật. Nghe cũng rất hay, nhưng mà Dreaminess chưa nghĩ ra cách nào? Không lẽ đem thử tất cả các trường hợp thì công việc khổng lồ quá nhỉ?

Có ai biết thông tin gì về bài này không?

[huynguyen]

6=1*2*2*2*2*2/3/3*2

Thú vị đấy, từ ví dụ này ta suy ra rằng thực chất của bài toán chính là tìm m và n sao cho: x = 2^m/(3^n) với x là số cho trước. Bài toán này khó sử dụng được vòng lặp nêu như theo kiểu ví dụ của bạn. Tôi đã coding được bài này nhưng khi dùng vòng for thì chỉ ra kết quả là 2^9 / 3^4 chứ ko ra được kiểu của bạn. Thực sự bài toán này tôi ko hiểu ý định của người ra đề muốn cái gì vì thực tế là qua cái ví dụ ko thấy được logic của bài toán. Còn nếu ý định là tìm x như tôi đã nói thì đây là code:

#include <iostream>
#define r 14
using namespace std;
int main(){
    int x,m = 1,n = 1,s = 0,s1 = 1;
    do{
       cout <<"x = "; cin >>x;
    }
    while ((x < 1)||(x > 5000));
    while ((x != s)&&(m < r)){
          n = 1;
          s1 = s1 * 2;
          s = s1;
          while ((x != s)&&(n < r)){
                s = s1;
                for (int i = 0;i < n;++i) s = s / 3;
                if (x != s) ++n;
          }
          if (x != s) ++m;
    }
    cout <<"x = 1";
    for (int i = 0;i < m;++i) cout <<"x2";
    for (int i = 0;i < n;++i) cout <<"/3";
    cout <<endl; system("pause");
    return 0;
}

[Xcross87]

@huynguyen : hay nhi ... cần giải thuật chứ đâu cần code

Số kết quả phép tính là một số xấp xỉ n hay còn gọi là : lim(A) = n ( với m , n có giới hạn lần lượt là M , N ) .
Đây là bài toán ngược bài toán tìm lim : tìm M, N để limA = n .
Hữu hạn ở đây phải cụ thể là đến mức nào tức là phải chính xác đến một số e nào đó chẳng hạn : e = 10^(-10).... Chứ nếu khồng có tìm đến chục Lunar Tet cũng không ra vì : 6 = 1 * 2 * 2 ..... /3 / 3 -> Phép toán này cũng chỉ xấp xỉ và có thể tính ra : tích của các số 2 với nhau nếu lớn hơn n thì chia 3 nếu vẫn lớn hơn thì chia tiếp , nếu nhỏ hơn n thì lại nhân 2 rồi chia 3 -> có lẽ vô hạn

pete có đôi chút ý kiến ... có gì sai mong nhận được edit

[huynguyen]

cần giải thuật chứ đâu cần code

Trong code có giải thuật, trong giải thuật có code
Lười nói giải thuật nên post luôn cái code cho nó lẹ.

tích của các số 2 với nhau nếu lớn hơn n thì chia 3 nếu vẫn lớn hơn thì chia tiếp , nếu nhỏ hơn n thì lại nhân 2 rồi chia 3

Ý tưởng hay (cứ cho là nó hữa hạn đi đã) nhưng giải thích sao về trường hợp

6=1*2*2*2*2*2/3/3*2

Rõ ràng chỉ cần 2*2*2 là đã > 6 rồi, cần gì nhân đến 5 lần rồi mới chia nhỉ?
Rõ ràng bài toán này ko đưa ra được 1 trường hợp logic và phụ hợp tính chất giải thuật (sau 1 bước hữu hạn thì dừng)

[Tarzan]

Thuật giải trâu bò, không cần đầu óc đây, hôm qua post rồi mà bị dis mạng.

Coi mỗi số như 1 đỉnh của đồ thị. Đây là đồ thị có hướng với các đỉnh được nối với nhau bởi phép *2 và /3. Sau đó bài toán trở thành tìm đường đi giữa các đỉnh của đồ thị.

[Kevin Hoang]

Thuật giải trâu bò, không cần đầu óc đây, hôm qua post rồi mà bị dis mạng.

Coi mỗi số như 1 đỉnh của đồ thị. Đây là đồ thị có hướng với các đỉnh được nối với nhau bởi phép *2 và /3. Sau đó bài toán trở thành tìm đường đi giữa các đỉnh của đồ thị.

Hôm nay bác post tiếp đi, Dreaminess vẫn chưa thể lĩnh hội được ý này. hì hì