" />
  • Thứ Hai, 18/02/2008 09:03 (GMT+7)

    Bài toán min, max của 2 chuỗi

    Câu hỏi :
    Xin hướng dẫn code cho bài toán sau: "nhập 2 chuỗi bất kỳ, xuất giá trị lớn nhất, giá trị nhỏ nhất, giá trị trung bình của 2 chuỗi đó, sắp xếp tăng dần, giảm dần, tổng các giá trị trong 2 chuỗi đó.
     

    Trả lời :

     Thuật ngữ chuỗi được dùng để miêu tả 1 danh sách (dãy) gồm nhiều phần tử dữ liệu cùng loại (chuỗi các ký tự, chuỗi các số nguyên, chuỗi các số thực, chuỗi các record...). Bạn không nói rõ chuỗi của bạn chứa các phần tử gì, hơn nữa tìm giá trị lớn nhất, nhỏ nhất, giá trị trung bình, sắp xếp, tổng giá trị, tìm kiếm 1 phần tử... là các bài toán trên 1 chuỗi cụ thể chứ không phải trên 2 chuỗi. Trên 2 chuỗi, bài toán thường được thực hiện là merge (trộn) 2 chuỗi thành 1 chuỗi.
     Để giải quyết 1 bài toán nào đó, người ta đã tìm ra nhiều thuật giải khác nhau, mỗi thuật giải có những tính chất riêng và phù hợp trong tình huống cụ thể.

     Nếu cần giải quyết tất cả bài toán mà bạn yêu cầu trên 1 chuỗi các số nguyên (hay số thực), bạn cần thực hiện bài toán sắp xếp tăng dần trước. Sau khi có 1 chuỗi thứ tự tăng dần các phần tử, bạn đảo ngược các phần tử thì được chuỗi có thứ tự giảm dần. Phần tử đầu tiên trong chuỗi tăng dần là phần tử nhỏ nhất, phần tử cuối cùng trong chuỗi tăng dần là phần tử lớn nhất, lấy tổng các giá trị bằng cách duyệt từng phần tử trong chuỗi rồi tích lũy giá trị của nó vào 1 biến Sum, giá trị trung bình bằng kết quả phép chia giá trị Sum cho số phần tử trong chuỗi.

     Sau đây là ứng dụng C++ nhỏ demo việc nhập 1 chuỗi các số nguyên, thực hiện các bài toán mà bạn yêu cầu trên nó và hiển thị kết quả ra màn hình. Chương trình này chạy ở chế độ Text-mode (loại Project "Win32 Console Application" trong VC++):

     #include <stdio.h>
     #include <malloc.h>
     //định nghĩa biến dãy
     int* day;
     int N;
     //chương trình chính
     void main() {
     int i, j, minidx;
     int tmp;
     //chờ nhập số phần tử
     printf("Nhập số phần tử của dãy : ");
     scanf("%d",&N);
     //phân phối biến dãy theo yêu cầu
     day = (int*) malloc (N*sizeof(int));
     //chờ nhập từng phần tử của dãy
     for (i = 0; i <N; i++) {
     printf("Nhập phần tử day(%d) : ",i);
     scanf("%d",&day[i]);
     }
     //1. bài toán sắp xếp dãy tăng dần
     //sắp xếp các phần tử tăng dần
     for (i = 0; i < N-1; i++) {
     // tìm phần tử nhỏ nhất
     minidx = i;
     for (j = i+1; j< N; j++)
     if (day[minidx] > day[j]) minidx = j;
     // hoán vị 2 phần tử day[i] <--> day[min]
     tmp = day[i];
     day[i] = day[minidx];
     day[minidx] = tmp;
     }
     //in kết quả dãy tăng dần
     printf ("Dãy tăng dần là :");
     for (i=0; i < N ; i++)
     printf(" %d,",day[i]);
     printf ("\n");
     //2. bài toán sắp xếp dãy giảm dần
     //in kết quả dãy giảm dần
     printf ("Dãy giảm dần là :");
     for (i=N-1; i >=0 ; i--)
     printf(" %d,",day[i]);
     printf ("\n");
     //3. bài toán tìm phần tử nhỏ nhất
     //in giá trị phần tử nhỏ nhất
     printf ("Phần tử nhỏ nhất là : %d\n", day[0]);
     //4. bài toán tìm phần tử lớn nhất
     //in giá trị phần tử lớn nhất
     printf ("Phần tử lớn nhất là : %d\n", day[N-1]);
     //5. bài toán tính tổng giá trị các phần tử
     int sum = 0;
     for (i=0; i < N ; i++)
     sum += day[i];
     //in tổng giá trị
     printf ("Tổng giá trị là : %d\n", sum);
     //6. bài toán tính giá trị trung bình
     //in giá trị trung bình,
     //có thể không trùng với phần tử nào trong dãy
     //và có thể nhận giá trị thực
     printf ("Giá trị trung bình là : %f\n", (double)sum/N);
     }
     Dựa vào mã nguồn trên, bạn có thể hiệu chỉnh lại để xử lý chuỗi các số thực hay chuỗi các dữ liệu bất kỳ.

    Chuyên mục: Lập trình