Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Tối ưu chương trình về thời gian

  1. #1
    Ngày gia nhập
    09 2016
    Bài viết
    1,009

    Mặc định Tối ưu chương trình về thời gian

    01 - Mở đầu
    Có topic link gốc:
    http://diendan.congdongcviet.com/thr...ai-tap-cpp.cpp

    Tìm số - đếm các số là tích của 3 số nguyên tố trong khoảng [a, b] cụ thể [2, 10000000] (10^7)
    Với bài tham khảo sau:

    C++ Code:
    1. #include <iostream>
    2. #include <time.h>
    3.  
    4. using namespace std;
    5.  
    6. //So la tich 3 so nguyen to
    7. bool tinhtoan(int n){
    8.     int k = 0;
    9.    
    10.     while (n % 2 == 0){
    11.         if (++k > 3) return false;
    12.         n = n / 2;
    13.     }
    14.    
    15.     for (int i = 3; i <= sqrt(n); i += 2)
    16.         while (n%i == 0){
    17.             if (++k > 3) return false;
    18.             n = n / i;
    19.         }
    20.  
    21.     if (n > 2) ++k;
    22.     return k == 3;
    23. }
    24.  
    25. int main(void){
    26.     time_t start_t, end_t;
    27.     double diff_t;
    28.    
    29.     int k = 0, a, b;
    30.     //cout << "input a, b: "; cin >> a >> b;
    31.     a = 2; b = 10000000;
    32.    
    33.     time(&start_t);
    34.     for (int i = a; i <= b; i++){
    35.         if (tinhtoan(i)) k++;
    36.     }
    37.     cout << k << endl;
    38.  
    39.     time(&end_t);
    40.     diff_t = difftime(end_t, start_t);
    41.     cout << "Execution time = " << diff_t;
    42.    
    43.     return 0;
    44. }

    Không hạn chế sử dụng loại NNLT, hãy viết CT tính nhanh nhất có thể.
    Tôi viết thảo bằng c tầm 20 second


    I am responsible for what I say, I am not responsible for what you understand.

    Trong trại súc vật, có những con vật tự cho mình cái quyền bình đẳng hơn những con vật khác.
    Phọt đâu xa 2017
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    09 2016
    Bài viết
    1,009

    Với tiêu chí tối ưu về thời gian, tôi sẽ bỏ qua một số vấn đề khác như đúng sai, ...

    C++ Code:
    1. //Số là tích 3 số nguyên tố ?
    2. bool tinhtoan(int n){
    3.     int k = 0;
    4.    
    5.     while (n % 2 == 0){ // <== (1)
    6.         if (++k > 3) return false;
    7.         n = n / 2; // <== (2a)
    8.     }
    9.    
    10.     for (int i = 3; i <= sqrt(n); i += 2) // <== (3)
    11.         while (n % i == 0){
    12.             if (++k > 3) return false;
    13.             n = n / i; // <== (2b)
    14.         }
    15.  
    16.     if (n > 2) ++k;
    17.     return k == 3;
    18. }

    Do không có chú thích nên tôi sẽ suy diễn chủ quan:
    Spam Code:
    1. (1) là số chẵn, là số chia hết cho 2
    2. (2) tách lấy thừa số còn lại
    3. (3) tính lại cận trên

    Để tăng tốc độ, chúng ta nên biết (đã biết) về Assembly, các chỉ thị / tính toán cùng ngữ nghĩa có thời gian khác nhau
    Spam Code:
    1. (1)  số chẵn lẻ có thể biết chỉ cần xét bit nhỏ là đủ
    2. (2a) khi số chẵn cần chia 2, dùng shift
    3. (3b) tính lại cận trên chỉ thực hiện khi cần thiết

    C++ Code:
    1. //Số là tích 3 số nguyên tố ?
    2. bool tinhtoan(int n){
    3.     int k = 0;
    4.    
    5.     while ((n & 1) == 0){ // <== (1)
    6.         if (++k > 3) return false;
    7.         n >>= 1; // <== (2a)
    8.     }
    9.  
    10.     int m = sqrt(n) + 1; // <== (3a)
    11.     for (i = next; i < m; i += 2)
    12.         while (n % i == 0){
    13.             if (++k > 3) return false;
    14.             n /= i;
    15.             m = sqrt(n) + 1; // <== (3b)
    16.         }
    17.     //
    18.     if (n > 1)  ++k;
    19.     return k == 3;
    20. }

    Lúc khác bàn tiếp, ...

    I am responsible for what I say, I am not responsible for what you understand.

    Trong trại súc vật, có những con vật tự cho mình cái quyền bình đẳng hơn những con vật khác.
    Phọt đâu xa 2017

  3. #3
    Ngày gia nhập
    08 2017
    Bài viết
    3,527

    Viết bằng c, có thời gian khoảng 10 giây.

    http://diendan.congdongcviet.com/threads/t372056::tan-man-nnlt.cpp/page2/

  4. #4
    Ngày gia nhập
    08 2017
    Bài viết
    3,527

    Có ai quan tâm, ai làm nhanh hơn nữa không ?

  5. #5
    Ngày gia nhập
    08 2017
    Bài viết
    3,527

    Cần thay block khác ?

  6. #6
    Ngày gia nhập
    08 2017
    Bài viết
    3,527

    Mặc định Tối ưu chương trình về thời gian

    TTO - Hãng công nghệ IBM vừa trình làng mẫu máy tính nhỏ nhất thế giới, nhỏ hơn hạt muối nhưng lại được tích hợp công nghệ “thời thượng” blockchain.

    đừng để kích thước đánh lừa, bởi thiết bị này có năng lực xử lý thông tin mạnh mẽ tương đương với một con chip x86 của những năm 1990. Và để nhìn thấy nó, bạn sẽ phải dùng tới kính hiển vi.

    Theo IBM, chi phí sản xuất máy tính siêu tí hon này chưa tới 10 cent và nó gồm "vài trăm ngàn bóng bán dẫn". Theo đó nó có khả năng "theo dõi, phân tích, liên lạc và thậm chí xử lý trên dữ liệu".

    Với những người quan tâm tới bitcoin, họ càng có lý do hơn để tìm hiểu về mẫu máy tính nhỏ nhất thế giới của IBM vì thiết bị này tích hợp công nghệ blockchain, một công nghệ nền tảng của tiền điện tử.

    https://congnghe.tuoitre.vn/ibm-ra-mat-may-tinh-nho-hon-hat-muoi-20180320095307146.htm
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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