Trang 1/3 123 cuối
kết quả từ 1 tới 12 trên 25

Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Unhappy Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Mặc dù dùng ngôn ngữ lập trình khác nhau, nhưng ý tưởng thuật toán là giống nhau; bạn có thể tham khảo post #2 của mình trong link sau:
    HTML Code:
    http://vforum.vn/diendan/showthread.php?94983-Mot-so-bai-tap-pascal-giai-thuat-sap-xep-mong-su-chi-giao
    Riêng n <= 30000 thì nhiều quá. Cái solution space đã phải tới n^2 rồi, cho nên thuật toán tệ nhất cũng phải là O(n^2).
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Hong hỉu bạn ơi

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Sắp đi ngủ rồi, để mình tóm gọn lại chút: đề bài là chúng ta cần tìm 4 số: a[i], a[j], a[k], a[p] sao cho a[p] là trung bình cộng của 3 số kia với i, j, k đôi một khác nhau.
    - Tư tưởng là với mỗi số a[p] trong mảng, mình cần tìm 3 số còn lại ở trong mảng sao cho a[i] + a[j] + a[k] = 3 a[p].
    - Tương tự, với mỗi số a[k] và a[p] trong mảng, mình cần tìm 2 số còn lại ở trong mảng sao cho a[i] + a[j] = 3 a[p] - a[k].
    Tới đây rõ ràng bạn sẽ thấy cần 2 vòng lặp trong ngoài cho mỗi a[p] và a[k].
    - Tiếp theo, làm sao xác định mảng có 2 phần tử a[i] và a[j] có tổng bằng 3 a[p] - a[k]? Để làm đc cái này thì mình sẽ tạo 1 mảng để lưu tổng của từng cặp số một trước. Đây là mảng 3 dòng, n * n / 2 cột, gọi là mảng S.
    - Với mỗi a[i] và a[j], i < j, tổng của nó sẽ lưu vào dòng thứ 0, i lưu ở dòng 1, j lưu ở dòng 2.
    - Sau đó sort mảng S này lại.

    Bây giờ bạn tạo mảng S ra rồi sort lại trước đã, sau đó tính tiếp.

    PS: Bạn gắng dùng quick sort nhé, ko dùng insertion sort. Thời gian chạy của thuật toán này phụ thuộc vào sort đấy.

  5. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    hic .. mình vẫn duyệt k đc 2 vòng lặp .. nhờ bạn duyệt code giúp mh them6 chút nưa nha cho mh chút code

  6. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Code tính mảng S đây bạn:
    Mã:
    int t = 0;
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j) {
            sum[0][t] = a[i] + a[j];
            sum[1][t] = i;
            sum[2][t++] = j;
        }
    Tiếp theo bạn cần sort lại theo giá trị ở dòng 0 nhé. Mảng S này có t phần tử.

  7. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Mã:
    #include <iostream.h>
    #include <stdio.h>
    void sapxep(int a[][20], int d, int c) ;
    int timkiem(int a[][], int n, int x);
    void swap (int a, int b);
    int main()
    {
     int a[100][100],n;
     cout<<"nhap n: "; cin>>n;
     for (int i=0; i<=n; i++)
     {
      cout<<"Nhap A["<<i<<"]=";
      cin>>a[1][i];
      
     }
     int t = 0;
     int sum[3][3];
     for (int i = 0; i < n - 1; ++i)
     for (int j = i + 1; j < n; ++j) 
     {
      sum[0][t] = a[1][i] + a[1][j];
      sum[1][t] = i;
      sum[2][t++] = j;
     }
     int count=0;
     for(int i=1; i<=n;i++)
     {
      int s=3*a[1][i];
      for(int j=1; j<=n;j++)
      {
       int k=timkiem(sum[][],n,s-a[1][j]);
       if(k) {count++; cout<<a[1][i]; break;}
       
       
      }
     }
     return 0;
    }
    int timkiem(int a[][], int n, int x)
    {
     int i=0;
     while(i<n && a[1][i]!=x)
     {
      i++;
      
     }
     if(i==n) return -1;
     return i;
    } 
    void sapxep(int a[][20], int d, int c) 
    { 
        for (int i=0; i<d*c;i++) 
            for (int j=0; j<d*c;j++) 
                if (a[i/c][i%c] < a[j/c][j%c]) 
                { 
                    int tmp = a[i/c][i%c] ; 
                    a[i/c][i%c] = a[j/c][j%c] ; 
                    a[j/c][j%c] = tmp ; 
                } 
    }
    nho xem giup mh code voi, mh lam theo nhu vay nhung ko chay

  8. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    - Mình nghĩ mảng 'a' đâu cần 2 chiều.
    - Mảng 'sum', như mình đã nói, gồm n(n - 1) / 2 dòng, và 3 cột.
    - Tìm kiếm là phải binary search mới phát huy đc ưu điểm của sort.
    Đoạn code của nó đại khái như thế này. Input là 1 mảng 'a'.

    [ fixed code ]
    Mã:
    int averageOf3Sum(std::vector<int> a) {
        std::vector<std::vector<int>> sum;
        for (int i = 0; i < a.size() - 1; ++i)
            for (int j = i + 1; j < a.size(); ++j)
                sum.push_back(std::vector<int>({ a[i] + a[j], i, j }));
    
        std::sort(sum.begin(), sum.end(),
            [&](const std::vector<int> &x, const std::vector<int> &y) {
                return x[0] < y[0];
        });
    
        int count = 0;
        for (int p = 0; p < a.size(); ++p) {
            for (int i = 0; i < a.size() - 2; ++i) {
                int target = 3 * a[p] - a[i], left = 0, right = (int)sum.size() - 1, pos = -1;
                while (left <= right) {
                    int mid = left + ((right - left) >> 1);
                    if (target < sum[mid][0])
                        right = mid - 1;
                    else if (target > sum[mid][0])
                        left = mid + 1;
                    else {
                        if (mid == 0 || (mid > 0 && sum[mid - 1][0] < target)) {
                            pos = mid;
                            break;
                        }
                        right = mid - 1;
                    }
                }
                if (pos >= 0) {
                    if (sum[pos][1] > i)
                        ++count;
                    for (int u = pos + 1; u < sum.size() && sum[u][0] == target; ++u)
                        if (sum[u][1] > i)
                            ++count;
                }
            }
        }
        return count;
    }

  9. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Mã:
      qS(sum, 0, t - 1);
    Quicksort mảng sum là mảng 2 chiều đúng không bạn, mh thấy code không có hàm Quicksort.

  10. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Trích Nguyên văn bởi Organvn Xem bài viết
    Mã:
      qS(sum, 0, t - 1);
    Quicksort mảng sum là mảng 2 chiều đúng không bạn, mh thấy code không có hàm Quicksort.
    Đúng rồi, quick sort theo giá trị của dòng 0, nhưng khi đổi chỗ phải đổi luôn dòng 1 và 2. Hàm đó mình để lại. Bạn có thể tham khảo thread trước của bạn mình viết quick sort đấy. :-)

  11. #11
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    bạn cho mình xin link thread đó đc không, minh chưa học Qicksort mảng 2 chiều

  12. #12
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) ......

    Mã:
    1. oid HoanVi(int &a, int &b)
    2. {
    3. int temp = a;
    4. a = b;
    5. b = temp;
    6. }
    7. void QuickSort(int a[][MAX],int l, int r,int m)//Dùng l = 0, r = m*n - 1;
    8. {
    9. if(l>=r)return;
    10. int i = l,j =r;
    11. int x = a[((i+j)/2)/m][((i+j)/2)%m];
    12. do
    13. {
    14. while(a[i/m][i%m] < x ) i++;
    15. while(a[j/m][j%m] > x ) j--;
    16. if(i<=j)
    17. {
    18. HoanVi(a[i/m][i%m],a[j/m][j%m]);
    19. i++,j--;
    20. }
    21. }while(i<j);
    22. QuickSort(a,l,j,m);
    23. QuickSort(a,i,r,m);
    24. }
    Quicksort mang 2 chieu co 4 tham , nhung code qS(sum, 0, t - 1); truyền có 3 tham số . vậy để như thế nào cho đúng hả bạn..

Trang 1/3 123 cuối