2
Giải thuật tìm 3 số sao cho tích của 3 số đó là lớn nhất trong C?
0
Member44940 đã đăng:

Cho một dãy gồm n số nguyên, viết giải thuật tìm ba số của dãy sao cho tích của ba số đó là lớn nhất, cho biết độ phức tạp của giải thuật đã thực hiện.

Mọi người giúp mình với nha =).

Bạn sử dụng ngôn ngữ lập trình nào?

minhkiet 02.01.2019

Mình dùng C.

Member4494 02.01.2019
thêm bình luận...
1
viétkâz50 đã đăng:

Mình nghĩ rằng trong 1 dãy số, tích của 3 số nào đó lớn nhất chỉ khi 3 số đó là 3 số lớn nhất trong dãy (bao gồm số lớn nhất, số lớn thứ nhì và số lớn thứ ba), vậy bài toán tìm 3 số sao cho tích của 3 số đó là lớn nhất có thể quy về tìm 3 số lớn nhất trong dãy số đã cho.

#include <stdio.h>
#include <limits.h>
#include <conio.h>

int timSoLonNhat(int *&A, int n) {
    int soLonNhat = INT_MIN;
    int index;

    for (int i = 0; i < n; i++) {
        if (A[i] > soLonNhat) {
            soLonNhat = A[i];
            index = i;
        }
    }

    A[index] = INT_MIN;

    return soLonNhat;
}

void tim3SoLonNhat(int *&A, int n) {
    int ith = 1;
    while (ith <= 3) {
        printf("%5d", timSoLonNhat(A, n));
        ith++;
    };
}

int main() {
    int *A;
    int n = 7; // Dãy mặc định 7 số
    A = new int[n]; // Cấp phát bộ nhớ

    // Một số ví dụ, bạn có thể thay bằng cách nhập vào các số tùy ý
    A[0] = 50;
    A[1] = 48;
    A[2] = 57;
    A[3] = 14;
    A[4] = 86;
    A[5] = 37;
    A[6] = 78;

    printf("3 so co tich lon nhat la: \n");
    tim3SoLonNhat(A, n);
    printf("\n");

    delete[]A;
}

Độ phức tạp thuật toán trong giải thuật của mình là O(n), bởi vì ở hàm timSoLonNhat mình chạy vòng lặp for với điều kiện dừng là n, còn ở hàm tim3SoLonNhat có độ phức tạp không đáng kể, chỉ là 3 vòng lặp để trả về 3 số lớn nhất mà thôi.

đã bổ sung 2.2 năm trước bởi
Avatar: viétkâz viétkâz50

trong mảng có số âm là toang :))

Cộng đồng 09.12.2020

tại sao lại toang nhỉ, bạn ở trên chỉ cần tìm ra ba số lớn nhất rồi mới nhân 3 số đó lại thì trong bước tìm 3 số lớn nhất đâu có cần care nó là số âm hay dương đâu?

Cộng đồng 11.12.2020

Nhưng mà trường hợp 2 số âm nhân với nhau vẫn ra số dương và lớn hơn 2 số dương nhân với nhau thì sao?

Cộng đồng 31.01.2021

thế chỉ cần sắp xếp tăng dần rồi ta so sánh phần tử bé nhất và gần bé nhất nhân với nhau và với phần tử lớn nhất và gần lớn nhất nhân với nhau nếu tích 2 cái nhỏ nhất > 2 cái lớn nhất thì sẽ chọn 2 cái bé nhất ấy và cái lớn nhất ngược lại thì chọn 3 cái lớn nhất, chỉ vài dòng if không có vấn đề j về độ phức tạp

MinhRoro 19.02.2021
thêm bình luận...
1
minhkiet150 đã đăng:

Mình có cùng ý tưởng như bạn @viétkâz nhưng về cách thực hiện sẽ khác đôi chút, thay vì ở mỗi vòng lặp thực hiện rà soát lại dãy số một lần để tìm 3 số lớn nhất, mình sẽ sắp xếp mảng các dãy số theo thứ tự giảm dần trước, sau đó lấy 3 số hạng đầu tiên trong mảng, như thế độ phức tạp thuật toán sẽ giảm chỉ còn O (n log(n))

Tùy thuộc vào thuật toán bạn chọn để sắp xếp mảng các dãy số mà độ phức tạp thuật toán sẽ khác nhau, ở đây mình chọn thuật toán sắp xếp đơn giản nhất là Selection Sort.

#include <stdio.h>
#include <conio.h>

void Swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void SelectionSort(int *A, int n) {
    for (int i = 0; i < n; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] > A[maxIndex])
                maxIndex = j;
        }

        if (maxIndex != i)
            Swap(A[maxIndex], A[i]);
    }
}

int main() {
    int *A;
    int n;

    printf("Nhap vao so luong phan tu cua day = ");
    scanf("%d", &n);

    A = new int[n];

    for (int i = 0; i < n; i++) {
        printf("Nhap vao so thu %d = ", i + 1);
        scanf("%d", &A[i]);
    }

    SelectionSort(A, n);

    printf("Ba so co tich lon nhat la: %d - %d - %d \n", A[0], A[1], A[2]);
    printf("\n");

    delete[]A;
}

Thuật toán Selection Sort có độ phức tạp O ($\text{n}^2$), nhưng nếu bạn chọn các thuật toán sắp xếp cải tiến hơn như Quick Sort, Merge Sort, ... độ phức tạp sẽ giảm còn O (n log(n)).

đã bổ sung 2.2 năm trước bởi
Avatar: minhkiet minhkiet150

Cảm ơn 2 bạn đã giải đáp giúp mình.

Member4494 03.01.2019

của bạn có phần đúng nhưng mình nghĩ nếu gặp phần tử âm thì nên sắp xếp tăng dần rồi ta so sánh phần tử bé nhất và gần bé nhất nhân với nhau và với phần tử lớn nhất và gần lớn nhất nhân với nhau nếu tích 2 cái nhỏ nhất > 2 cái lớn nhất thì sẽ chọn 2 cái bé nhất ấy và cái lớn nhất ngược lại thì chọn 3 cái lớn nhất giống bạn.

MinhRoro 19.02.2021
thêm bình luận...

Câu trả lời của bạn

Chào mừng bạn đến với cộng đồng chia sẻ tri thức BanhoiTuidap.com, bạn có thể chia sẻ bất kỳ sự hiểu biết, nghiên cứu hoặc kinh nghiệm của mình về câu hỏi này với một số lưu ý:
  • Lịch sự, tế nhị.
  • Hạn chế ghi tắt, câu trả lời của bạn chỉ nên tập trung vào câu hỏi ở trên.
Câu trả lời của bạn sẽ được đăng ở chế độ cộng đồng, cho nên bạn sẽ không thể chỉnh sửa sau khi đăng, có thể đăng ký thành viên trên BanhoiTuidap.com khi bạn muốn theo dõi câu hỏi này hoặc chủ đề liên quan.
Bạn đang thắc mắc? Ghi câu hỏi của bạn và đăng ở chế độ cộng đồng (?)