Từ 1 tới 7 trên tổng số 7 kết quả

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

  1. #1
    Ngày gia nhập
    01 2007
    Nơi ở
    TpHCM
    Bài viết
    4

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

    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!

  2. #2
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Ò, 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?
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  3. #3
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Trích dẫn Nguyên bản được gửi bởi dangle2006
    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:
    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;
    }
    Đã được chỉnh sửa lần cuối bởi huynguyen : 15-01-2007 lúc 09:25 AM.

  4. #4
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    @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
    None!

  5. #5
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Trích dẫn Nguyên bản được gửi bởi pete_87
    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)
    Đã được chỉnh sửa lần cuối bởi huynguyen : 15-01-2007 lúc 09:45 AM.

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

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

    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ị.

  7. #7
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    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ì
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn