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

Organvn · 12/9/16

Nhập vào số nguyên a1..an(n<30000, |ai|<=10000).Số ap(1<=p<=n) được gọi là một số trung bình cộng trong day số tồn tại 3 chỉ số i,j,k(1<=i,j,k<=n) đôi một khác nhau, sao cho ap=(ai+aj+ak)/3. Tìm số lượng giác trung bình cộng trong day.
giúp giúp với ..:jindo:

tengiday · 12/9/16

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:

https://vfo.vn/t/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).

Organvn · 13/9/16

Hong hỉu bạn ơi :xucdong2:

tengiday · 13/9/16

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, 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 + 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 + 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 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 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.

Organvn · 13/9/16

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:xuan-2015: cho mh chút code

tengiday · 13/9/16

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

Organvn · 13/9/16

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 :botay:

tengiday · 14/9/16

- 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;
}

Organvn · 14/9/16

Mã:

[COLOR=#ff0000]  qS(sum, 0, t - 1);[/COLOR]

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.

tengiday · 14/9/16

Organvn:
Mã:

[COLOR=#ff0000] qS(sum, 0, t - 1);[/COLOR]

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.

Organvn · 14/9/16

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

Organvn · 14/9/16

Mã:

[LIST=1]
[*][COLOR=#0903D8][B]oid[/B][/COLOR] HoanVi[COLOR=#000000]([/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] [COLOR=#000000]&[/COLOR]a[COLOR=#000000],[/COLOR] [COLOR=#0903D8][B]int[/B][/COLOR] [COLOR=#000000]&[/COLOR]b[COLOR=#000000])[/COLOR]

[*][COLOR=#000000]{[/COLOR]

[*]    [COLOR=#0903D8][B]int[/B][/COLOR] temp [COLOR=#000000]=[/COLOR] a[COLOR=#000000];[/COLOR]

[*]           a [COLOR=#000000]=[/COLOR] b[COLOR=#000000];[/COLOR]

[*]           b [COLOR=#000000]=[/COLOR] temp[COLOR=#000000];[/COLOR]

[*][COLOR=#000000]}[/COLOR]

[*][COLOR=#0903D8][B]void[/B][/COLOR] QuickSort[COLOR=#000000]([/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] a[COLOR=#000000][[/COLOR][COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]MAX[COLOR=#000000]][/COLOR][COLOR=#000000],[/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] l[COLOR=#000000],[/COLOR] [COLOR=#0903D8][B]int[/B][/COLOR] r[COLOR=#000000],[/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] m[COLOR=#000000])[/COLOR][COLOR=#008000][I]//Dùng l = 0, r = m*n - 1;[/I][/COLOR]

[*][COLOR=#000000]{[/COLOR]

[*]    [COLOR=#0903D8][B]if[/B][/COLOR][COLOR=#000000]([/COLOR]l[COLOR=#000000]>=[/COLOR]r[COLOR=#000000])[/COLOR][COLOR=#0903D8][B]return[/B][/COLOR][COLOR=#000000];[/COLOR]

[*]    [COLOR=#0903D8][B]int[/B][/COLOR] i [COLOR=#000000]=[/COLOR] l[COLOR=#000000],[/COLOR]j [COLOR=#000000]=[/COLOR]r[COLOR=#000000];[/COLOR]

[*]    [COLOR=#0903D8][B]int[/B][/COLOR] x [COLOR=#000000]=[/COLOR] a[COLOR=#000000][[/COLOR][COLOR=#000000]([/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]+[/COLOR]j[COLOR=#000000])[/COLOR][COLOR=#000000]/[/COLOR][COLOR=#FF0000]2[/COLOR][COLOR=#000000])[/COLOR][COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR][COLOR=#000000]([/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]+[/COLOR]j[COLOR=#000000])[/COLOR][COLOR=#000000]/[/COLOR][COLOR=#FF0000]2[/COLOR][COLOR=#000000])[/COLOR][COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000];[/COLOR]

[*]    [COLOR=#0903D8][B]do[/B][/COLOR]

[*]    [COLOR=#000000]{[/COLOR]

[*]        [COLOR=#0903D8][B]while[/B][/COLOR][COLOR=#000000]([/COLOR]a[COLOR=#000000][[/COLOR]i[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]i[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR] [COLOR=#000000]<[/COLOR] x [COLOR=#000000])[/COLOR] i[COLOR=#000000]++;[/COLOR]

[*]        [COLOR=#0903D8][B]while[/B][/COLOR][COLOR=#000000]([/COLOR]a[COLOR=#000000][[/COLOR]j[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]j[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR] [COLOR=#000000]>[/COLOR] x [COLOR=#000000])[/COLOR] j[COLOR=#000000]--;[/COLOR]

[*]        [COLOR=#0903D8][B]if[/B][/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]<=[/COLOR]j[COLOR=#000000])[/COLOR]

[*]        [COLOR=#000000]{[/COLOR]

[*]            HoanVi[COLOR=#000000]([/COLOR]a[COLOR=#000000][[/COLOR]i[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]i[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000],[/COLOR]a[COLOR=#000000][[/COLOR]j[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]j[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR]

[*]            i[COLOR=#000000]++,[/COLOR]j[COLOR=#000000]--;[/COLOR]

[*]        [COLOR=#000000]}[/COLOR]

[*]    [COLOR=#000000]}[/COLOR][COLOR=#0903D8][B]while[/B][/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]<[/COLOR]j[COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR]

[*]    QuickSort[COLOR=#000000]([/COLOR]a[COLOR=#000000],[/COLOR]l[COLOR=#000000],[/COLOR]j[COLOR=#000000],[/COLOR]m[COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR]

[*]    QuickSort[COLOR=#000000]([/COLOR]a[COLOR=#000000],[/COLOR]i[COLOR=#000000],[/COLOR]r[COLOR=#000000],[/COLOR]m[COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR]

[*][COLOR=#000000]}[/COLOR]
[/LIST]

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

tengiday · 14/9/16

Sort mảng 'sum' này tương tự như sort trong bài tìm vị trí k số lớn nhất trong mảng. Khi đó, lúc đổi chỗ, ngoài trừ mảng a thì mình phải đổi cả mảng 'pos'. Bây giờ tương tự, khi đổi chỗ thì đổi cả 3 dòng: sum[0], sum[0][j], sum[1], sum[1][j], sum[2], sum[2][j].

0 ... t - 1
sum[0]
sum[1]
sum[2]

Organvn:

Mã:

[LIST=1] [*][COLOR=#0903D8][B]oid[/B][/COLOR] HoanVi[COLOR=#000000]([/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] [COLOR=#000000]&[/COLOR]a[COLOR=#000000],[/COLOR] [COLOR=#0903D8][B]int[/B][/COLOR] [COLOR=#000000]&[/COLOR]b[COLOR=#000000])[/COLOR] [*][COLOR=#000000]{[/COLOR] [*] [COLOR=#0903D8][B]int[/B][/COLOR] temp [COLOR=#000000]=[/COLOR] a[COLOR=#000000];[/COLOR] [*] a [COLOR=#000000]=[/COLOR] b[COLOR=#000000];[/COLOR] [*] b [COLOR=#000000]=[/COLOR] temp[COLOR=#000000];[/COLOR] [*][COLOR=#000000]}[/COLOR] [*][COLOR=#0903D8][B]void[/B][/COLOR] QuickSort[COLOR=#000000]([/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] a[COLOR=#000000][[/COLOR][COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]MAX[COLOR=#000000]][/COLOR][COLOR=#000000],[/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] l[COLOR=#000000],[/COLOR] [COLOR=#0903D8][B]int[/B][/COLOR] r[COLOR=#000000],[/COLOR][COLOR=#0903D8][B]int[/B][/COLOR] m[COLOR=#000000])[/COLOR][COLOR=#008000][I]//Dùng l = 0, r = m*n - 1;[/I][/COLOR] [*][COLOR=#000000]{[/COLOR] [*] [COLOR=#0903D8][B]if[/B][/COLOR][COLOR=#000000]([/COLOR]l[COLOR=#000000]>=[/COLOR]r[COLOR=#000000])[/COLOR][COLOR=#0903D8][B]return[/B][/COLOR][COLOR=#000000];[/COLOR] [*] [COLOR=#0903D8][B]int[/B][/COLOR] i [COLOR=#000000]=[/COLOR] l[COLOR=#000000],[/COLOR]j [COLOR=#000000]=[/COLOR]r[COLOR=#000000];[/COLOR] [*] [COLOR=#0903D8][B]int[/B][/COLOR] x [COLOR=#000000]=[/COLOR] a[COLOR=#000000][[/COLOR][COLOR=#000000]([/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]+[/COLOR]j[COLOR=#000000])[/COLOR][COLOR=#000000]/[/COLOR][COLOR=#FF0000]2[/COLOR][COLOR=#000000])[/COLOR][COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR][COLOR=#000000]([/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]+[/COLOR]j[COLOR=#000000])[/COLOR][COLOR=#000000]/[/COLOR][COLOR=#FF0000]2[/COLOR][COLOR=#000000])[/COLOR][COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000];[/COLOR] [*] [COLOR=#0903D8][B]do[/B][/COLOR] [*] [COLOR=#000000]{[/COLOR] [*] [COLOR=#0903D8][B]while[/B][/COLOR][COLOR=#000000]([/COLOR]a[COLOR=#000000][[/COLOR]i[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]i[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR] [COLOR=#000000]<[/COLOR] x [COLOR=#000000])[/COLOR] i[COLOR=#000000]++;[/COLOR] [*] [COLOR=#0903D8][B]while[/B][/COLOR][COLOR=#000000]([/COLOR]a[COLOR=#000000][[/COLOR]j[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]j[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR] [COLOR=#000000]>[/COLOR] x [COLOR=#000000])[/COLOR] j[COLOR=#000000]--;[/COLOR] [*] [COLOR=#0903D8][B]if[/B][/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]<=[/COLOR]j[COLOR=#000000])[/COLOR] [*] [COLOR=#000000]{[/COLOR] [*] HoanVi[COLOR=#000000]([/COLOR]a[COLOR=#000000][[/COLOR]i[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]i[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000],[/COLOR]a[COLOR=#000000][[/COLOR]j[COLOR=#000000]/[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000][[/COLOR]j[COLOR=#000000]%[/COLOR]m[COLOR=#000000]][/COLOR][COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR] [*] i[COLOR=#000000]++,[/COLOR]j[COLOR=#000000]--;[/COLOR] [*] [COLOR=#000000]}[/COLOR] [*] [COLOR=#000000]}[/COLOR][COLOR=#0903D8][B]while[/B][/COLOR][COLOR=#000000]([/COLOR]i[COLOR=#000000]<[/COLOR]j[COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR] [*] QuickSort[COLOR=#000000]([/COLOR]a[COLOR=#000000],[/COLOR]l[COLOR=#000000],[/COLOR]j[COLOR=#000000],[/COLOR]m[COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR] [*] QuickSort[COLOR=#000000]([/COLOR]a[COLOR=#000000],[/COLOR]i[COLOR=#000000],[/COLOR]r[COLOR=#000000],[/COLOR]m[COLOR=#000000])[/COLOR][COLOR=#000000];[/COLOR] [*][COLOR=#000000]}[/COLOR] [/LIST]

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

Nhấn để mở rộng...

Organvn · 15/9/16

thua ban ah, doc nhung k hiu ma code đc nhu the nao:too_sad:

tengiday · 15/9/16

Code đoạn function qS đây:

Mã:

void qS(int ** & a, int left, int right) {
    if (left >= right) return;
    int pivot = a[0][rand() % (right - left + 1) + left];
    int i = left, j = right;
    do {
        while (a[0][i] < pivot) ++i;
        while (a[0][j] > pivot) --j;
        if (i <= j) {
            if (i < j) {
                std::swap(a[0][i], a[0][j]);
                std::swap(a[1][i], a[1][j]);
                std::swap(a[2][i], a[2][j]);
            }
            ++i;
            --j;
        }
    } while (i <= j);
    qS(a, left, j);
    qS(a, i, right);
}

Nó giống như đoạn quick sort mình viết cho bạn trước đây, chỉ đổi phần so sánh (vì mình đang sort giảm dần), và thêm đổi chỗ cho 2 dòng kia nữa. Bạn xem lại comment trc đây của mình: sort theo dòng 0, đổi chỗ luôn cả 3 dòng.

Organvn · 15/9/16

Mã:

#include <iostream.h>
#include <stdio.h>
void qS(int ** & a, int left, int right) {
    if (left >= right) return;
    int pivot = a[0][rand() % (right - left + 1) + left];
    int i = left, j = right;
    do {
        while (a[0][i] < pivot) ++i;
        while (a[0][j] > pivot) --j;
        if (i <= j) {
            if (i < j) {
                std::swap(a[0][i], a[0][j]);
                std::swap(a[1][i], a[1][j]);
                std::swap(a[2][i], a[2][j]);
            }
            ++i;
            --j;
        }
    } while (i <= j);
    qS(a, left, j);
    qS(a, i, right);
}
int main()
{
 int a[100],n;
 cout<<"nhap n: "; cin>>n;
 for (int i=0; i<n; i++)
 {
  cout<<"Nhap A["<<i<<"]=";
  cin>>a[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[i] + a[j];
  sum[1][t] = i;
  sum[2][t++] = j;
 }
 int ** sum = new int*[3];
    for (int i = 0; i < 3; ++i) sum[i] = new int[n * (n - 1) / 2];
  srand((unsigned)time(0));
    qS(sum, 0, t - 1);
 int count = 0;
    for (int i = 0; i < n; ++i) {
        int s = 3 * a[i];
        for (int j = 0; j < n; ++j) {
            bool found = false;
            int left = 0, right = t - 1, mid, target = s - a[j];
            while (left <= right) {
                mid = (left + right) / 2;
                if (sum[0][mid] == target) {
                    if (sum[1][mid] != j && sum[2][mid] != j) {
                        ++count;
                        found = true;
                        cout<<a[i];
                    }
                    break;
                }
                else if (sum[0][mid] < target) left = mid + 1;
                else right = mid - 1;
            }
            if (found) break;
        }
 return 0;
 }
}

[Error] error: invalid initialization of non-const reference of type 'int**&' from a temporary of type 'int (*)[3] // loi khong lam duoc ban oi !!

tengiday · 15/9/16

Organvn:

Mã:

#include <iostream.h>
#include <stdio.h>
void qS(int ** & a, int left, int right) {
    if (left >= right) return;
    int pivot = a[0][rand() % (right - left + 1) + left];
    int i = left, j = right;
    do {
        while (a[0][i] < pivot) ++i;
        while (a[0][j] > pivot) --j;
        if (i <= j) {
            if (i < j) {
                std::swap(a[0][i], a[0][j]);
                std::swap(a[1][i], a[1][j]);
                std::swap(a[2][i], a[2][j]);
            }
            ++i;
            --j;
        }
    } while (i <= j);
    qS(a, left, j);
    qS(a, i, right);
}
int main()
{
 int a[100],n;
 cout<<"nhap n: "; cin>>n;
 for (int i=0; i<n; i++)
 {
  cout<<"Nhap A["<<i<<"]=";
  cin>>a[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[i] + a[j];
  sum[1][t] = i;
  sum[2][t++] = j;
 }
 int ** sum = new int*[3];
    for (int i = 0; i < 3; ++i) sum[i] = new int[n * (n - 1) / 2];
  srand((unsigned)time(0));
    qS(sum, 0, t - 1);
 int count = 0;
    for (int i = 0; i < n; ++i) {
        int s = 3 * a[i];
        for (int j = 0; j < n; ++j) {
            bool found = false;
            int left = 0, right = t - 1, mid, target = s - a[j];
            while (left <= right) {
                mid = (left + right) / 2;
                if (sum[0][mid] == target) {
                    if (sum[1][mid] != j && sum[2][mid] != j) {
                        ++count;
                        found = true;
                        cout<<a[i];
                    }
                    break;
                }
                else if (sum[0][mid] < target) left = mid + 1;
                else right = mid - 1;
            }
            if (found) break;
        }
 return 0;
 }
}

[Error] error: invalid initialization of non-const reference of type 'int**&' from a temporary of type 'int (*)[3] // loi khong lam duoc ban oi !!

Bạn thử bỏ dấu & trong function qS xem. Vừa mới test thử, máy của mình vẫn chạy btg ko có lỗi.
PS: Bạn cần in 'count' ra mới đúng với đề bài.

Organvn · 15/9/16

vẫn bị bạn ah, bạn cho mh xin code của bạn xem :beat_brick:

Organvn · 15/9/16

Mã:

#include <iostream.h>
#include <stdio.h>
int averageOf3(int * a, int n) {
    int ** sum = new int*[3];
    for (int i = 0; i < 3; ++i) sum[i] = new int[n * (n - 1) / 2];
    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;
        }
}
void qS(int ** & a, int left, int right) 
 {
    if (left >= right) return;
    int pivot = a[0][rand() % (right - left + 1) + left];
    int i = left, j = right;
    do {
        while (a[0][i] < pivot) ++i;
        while (a[0][j] > pivot) --j;
        if (i <= j) {
            if (i < j) {
                std::swap(a[0][i], a[0][j]);
                std::swap(a[1][i], a[1][j]);
                std::swap(a[2][i], a[2][j]);
            }
            ++i;
            --j;
        }
    } while (i <= j);
    qS(a, left, j);
    qS(a, i, right);
}
int main()
{
 int a[100],n;
 cout<<"nhap n: "; cin>>n;
 for (int i=0; i<n; i++)
 {
  cout<<"Nhap A["<<i<<"]=";
  cin>>a[i];  
 }
    
    srand((unsigned)time(0));
    qS(sum, 0, t - 1);
    int count = 0;
    for (int i = 0; i < n; ++i) {
        int s = 3 * a[i];
        for (int j = 0; j < n; ++j) {
            bool found = false;
            int left = 0, right = t - 1, mid, target = s - a[j];
            while (left <= right) {
                mid = (left + right) / 2;
                if (sum[0][mid] == target) {
                    if (sum[1][mid] != j && sum[2][mid] != j) {
                        ++count;
                        found = true;
                        printf("%d ", a[i]);
                    }
                    break;
                }
                else if (sum[0][mid] < target) left = mid + 1;
                else right = mid - 1;
            }
            if (found) break;
        }
    }
    printf("\n");
    for (int i = 0; i < 3; ++i) delete[] sum[i];
    delete[] sum;
    return count;
}

khong tim duoc nguyen nhan loi.. hu1 hu1

tengiday · 15/9/16

Mình sửa trên dựa trên đoạn code của bạn. Bạn chưa khai báo 'sum', chưa tính 'sum' đâu thể gọi hàm đc. Hơn nữa phải cần stdlib và time.h để chạy.

Mã:

#include <iostream>
#include <stdlib.h>
#include <time.h>

void qS(int ** a, int left, int right)
{
    if (left >= right) return;
    int pivot = a[0][rand() % (right - left + 1) + left];
    int i = left, j = right;
    do {
        while (a[0][i] < pivot) ++i;
        while (a[0][j] > pivot) --j;
        if (i <= j) {
            if (i < j) {
                std::swap(a[0][i], a[0][j]);
                std::swap(a[1][i], a[1][j]);
                std::swap(a[2][i], a[2][j]);
            }
            ++i;
            --j;
        }
    } while (i <= j);
    qS(a, left, j);
    qS(a, i, right);
}

int averageOf3(int * a, int n)
{
    int ** sum = new int*[3];
    for (int i = 0; i < 3; ++i) sum[i] = new int[n * (n - 1) / 2];
    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;
        }

    srand((unsigned)time(0));
    qS(sum, 0, t - 1);

    int count = 0;
    for (int i = 0; i < n; ++i) {
        int s = 3 * a[i];
        for (int j = 0; j < n; ++j) {
            int left = 0, right = t - 1, mid, target = s - a[j];
            while (left <= right) {
                mid = (left + right) / 2;
                if (sum[0][mid] == target) {
                    if (sum[1][mid] != j && sum[2][mid] != j) {
                        ++count;
                        break;
                        printf("%d %d %d  %d\n", a[j], a[sum[1][mid]], a[sum[2][mid]], a[i]);
                    }
                }
                else if (sum[0][mid] < target) left = mid + 1;
                else right = mid - 1;
            }
        }
    }
    for (int i = 0; i < 3; ++i) delete[] sum[i];
    delete[] sum;
    return count;
}

int main()
{
    int a[100], n;
    std::cout << "nhap n: "; std::cin >> n;
    for (int i = 0; i < n; i++)
    {
        std::cout << "Nhap A[" << i << "]=";
        std::cin >> a[i];
    }
    std::cout << averageOf3(a, n) << std::endl;
    return 0;
}

PS: Lưu ý sẽ có cặp khác nhau nhưng cho cùng 1 kết quả average.

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

tengiday

Happy life

Organvn

tengiday

Happy life

Organvn

tengiday

Happy life

Organvn

tengiday

Happy life

Organvn

tengiday

Happy life

Organvn

Organvn

tengiday

Happy life

Organvn

tengiday

Happy life

Organvn

tengiday

Happy life

Organvn

Organvn

tengiday

Happy life

Bài viết mới nhất

Thống kê

Bài viết được quan tâm nhiều