Trang 1 trên tổng số 9 123... Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 87 kết quả

Đề tài: Tím số nguyên nhỏ thứ k trong dãy.

  1. #1
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Red face Tím số nguyên nhỏ thứ k trong dãy.

    Cho một dãy số nguyên A có n phần tử. Hãy tìm số nguyên nhỏ thứ k trong dãy.

  2. #2
    Ngày gia nhập
    12 2009
    Bài viết
    190

    Mình cũng thử xem sao. Cách truyền thống sắp xếp sau đó tìm từ đầu dãy. Sử dạng thêm 1 mảng phụ để tìm các vị trí đạt giá trị đó.
    C++ Code:
    1. #include <iostream>
    2. #include <conio.h>
    3. #include <iomanip>
    4. using namespace std;
    5.  
    6. void sort( int a[], int n )
    7. {
    8.     int i, j;
    9.     int tmp;
    10.    
    11.     for( i = 0; i < n - 1; i++ )
    12.         for( j = i + 1; j < n; j++ )
    13.             if( a[i] > a[j] )
    14.             {
    15.                 tmp = a[i];
    16.                 a[i] = a[j];
    17.                 a[j] = tmp;
    18.             }
    19. }
    20.  
    21. int minK( int a[], int n, int k, bool& flag )
    22. {
    23.     int i = 0, count = 1;
    24.     int tmp = a[0];
    25.    
    26.     do
    27.     {
    28.         i++;
    29.         if( a[i] > tmp )
    30.         {
    31.             count++;
    32.             tmp = a[i];
    33.         }
    34.     }while( count < k && i < n );
    35.    
    36.     if( i == n )
    37.     {
    38.         cout << "Khong co so lon thu " << k;
    39.         flag = false;
    40.         return 0;
    41.     }
    42.     else
    43.     {
    44.         cout << "So lon thu " << k << " la : " << tmp << endl;
    45.         return tmp;
    46.     }
    47. }
    48.  
    49. int main()
    50. {
    51.     int a[] = { 10,9,8,3,6,5,4,3,2,5 };
    52.     int *b;
    53.     int n = 10;     // So phan tu mang nhap vao
    54.     int k = 4;      //
    55.     bool flag = true;
    56.    
    57.     // Sao chep ra mang moi
    58.     b = new int[ sizeof(a) / sizeof( int ) ];
    59.     for( int i = 0; i < n; i++ )
    60.         b[i] = a[i];
    61.    
    62.     // Sap xep mang moi
    63.     sort( b, n );
    64.  
    65.     // Tim min thu K
    66.     int result = minK( b, n, k, flag );
    67.    
    68.     // Neu ton tai so nho thu k thi xuat ra cac vi tri do
    69.     if( flag )
    70.     {
    71.         cout << "Vi tri : ";
    72.         for( int i = 0; i < n; i++ )
    73.             if( a[i] == result )
    74.                 cout << setw(3) << i + 1;
    75.     }
    76.    
    77.     delete [] b;
    78.     _getch();
    79.     return 0;
    80. }
    Đã được chỉnh sửa lần cuối bởi pannaruto : 20-04-2010 lúc 02:42 AM.

  3. #3
    Ngày gia nhập
    05 2008
    Bài viết
    224

    sắp xếp nó từ nhỏ đến lớn rồi lấy ngay ở vị trí thứ K thôi bạn , nếu dãy có số trùng , thì xét thêm . nghĩ thế, chưa làm
    Em có thấy nắng vàng kỷ niệm
    Hạ ngồi ru thanh thản những môi cười
    Thuở ngồi ngóng tay choàng tay nỗi nhớ
    Vin tay vào tháng năm chơi vơi...

  4. #4
    Ngày gia nhập
    12 2009
    Nơi ở
    Tp. Hồ Chí Minh
    Bài viết
    64

    Uh còn mình nghĩ cũng không cần phải sắp xếp! Các bạn có thể tham khảo bài này:
    C Code:
    1. #include "stdio.h"
    2. #include "conio.h"
    3.  
    4. #define m 10
    5. int timmaxk(int a[],int n,int maximum,int min);
    6. void main()
    7. {   int a[m],n,i,k,max,min;
    8.     long maximum;
    9.     printf("\nNhap n: N= "); scanf("%d",&n);
    10.     for(i=0;i<n;i++)    {   printf("\nNhap phan tu thu %d ",i+1);
    11.                             scanf("%d",&a[i]);
    12.                             if(i==0) {maximum=a[i];min=a[i];}
    13.                             else    {if(a[i]>maximum) maximum=a[i];
    14.                                      if(a[i]<min) min=a[i];
    15.                                     }
    16.                         }
    17.    
    18.     printf("\nBan muon tim max thu k(1<=k<=%d). K=? ",n);
    19.     do
    20.     {   scanf("%d",&k);
    21.         if(k>n || k<=0) printf("\nNhap lai!");
    22.     } while(k>n|| k<=0);
    23.  
    24.     maximum++;  //Dung thu thuat maximum+1>maximum de tim max thu 1
    25.     for(i=1;i<=k;i++)   {  
    26.                             max=timmaxk(a,n,maximum,min);  
    27.                             maximum=max;
    28.                             if(maximum==min && i<k) break;
    29.                         }
    30.     if(i>k) printf("\nMax thu %d la %d ",k,max);
    31.     else printf("\nKhong ton tai max thu %d trong day da cho!!!!",k);
    32.     getch();
    33. }
    34. //timmaxk function
    35. int timmaxk(int a[],int n,int maximum, int min)
    36. {   int max=min;
    37.     for(int i=0;i<n;i++)
    38.         if(a[i]>max && a[i]<maximum) max=a[i];
    39.     return max;
    40. }
    Hãy quyết định và đấu tranh
    Để hạnh phúc và hi vọng!
    --------Thiên Điệp --> http://khmt.lifeme.net

  5. #5
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi cafelanh Xem bài viết
    sắp xếp nó từ nhỏ đến lớn rồi lấy ngay ở vị trí thứ K thôi bạn , nếu dãy có số trùng , thì xét thêm . nghĩ thế, chưa làm
    Bài này nếu giải vậy thì chưa phải tối ưu, bạn ạ. Mà chỉ là giải được.
    Cái này tớ gợi ý là dùng giải thuật của Selection Sort, xong chỉ chạy đến vị trí thứ k trong dãy mà thôi. Như vậy mới tối ưu được (Đó là theo quan điểm riêng của tớ, vì tớ chỉ biết được đến đó, ai đó có ý kiến hay hơn xin đóng góp)

    Hi quên thiếu 1 điều kiện là n>=k.

    Tư tưởng như sau
    C++ Code:
    1. //Tìm min thứ K trong n phần tử , tính chỉ số từ 0 nhé
    2. int MinK(int A[],int n,int k)
    3. {
    4.   for (int i=0;i<k;i++)
    5.   {
    6.     int min=A[i];
    7.     int pos=i; //Vị trí số nhỏ nhất trong dãy từ i+1 trở đi
    8.  
    9.     //Bắt đầu tìm số nhỏ nhất để đưa vào vị trí i trong dãy
    10.     for (int j=i+1;j<n;j++)
    11.       if (A[j]<=min)
    12.        {
    13.         min=A[j];
    14.         pos=j;
    15.        }
    16.     //Nếu i==k-1 thì ta đã có kết quả là min
    17.      if (i==k-1) return min;
    18.      else
    19.        //Ngược lại thì đưa đổi chỗ A[i] với A[pos],trong đó A[pos]==min
    20.      {
    21.        int tmp=A[i];
    22.        A[i]=A[pos];
    23.        A[pos]=tmp;
    24.      }
    25.   }
    26. }

    Với tư tưởng trên ta không cần xắp xếp toàn bộ dãy, vì bản thân tư tưởng của Selection Sort là tại vị trí i luôn tìm đúng phần tử có trong để đặt vào đó
    Vậy thôi xin hết.

  6. #6
    Ngày gia nhập
    04 2010
    Bài viết
    30

    Mặc định Tím số nguyên nhỏ thứ k trong dãy.

    nếu sắp xếp dãy thì làm theo cách nào cũng sẽ thay đổi thông tin của dãy ban đầu . (sau khi tìm kiếm các bạn thử cho in lại dãy xem )
    Mình đóng góp bài code này nhé ! tuy hơi dài nhưng thông tin không bị sai so với mảng vào!
    mong các bạn đóng góp cho code đơn giản gọn nhẹ hơn giúp mình với nhé !
    thân !!!

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #define vocung 10000;
    4.  
    5. int n,b[100];
    6. /*
    7.       intput a[] : 3 9 13 7 16 8
    8.     tao mang b[i]: 1 3 5 2 6 4 (muc dich : xep thu tu cua mang a )
    9.             co nghia la :
    10.             a[1] la so nho nhat
    11.             a[4] la so nho thu 2
    12.             a[2] la so nho thu 3
    13. ....
    14. */
    15. void khoitao()
    16. {
    17.      for(int i=1;i<=n;i++)
    18.      b[i]=0;
    19. }
    20.  
    21. void min(int a[],int count)// tim min thu count trong day a
    22. {
    23.      int min=vocung;
    24.      int vt;
    25.      for(int i=1;i<=n;i++)
    26.      if(a[i] < min && b[i]==0)
    27.      {
    28.              min = a[i];
    29.              vt=i;
    30.            
    31.      }
    32.       b[vt]=count;//mang b se ghi lai so thu tu nho tang dan tuong ung voi mang a[]
    33.      
    34. }
    35.  
    36. void thuattoan(int a[],int k)
    37. {
    38.      for(int count=1;count<=k;count++)
    39.      {
    40.              min(a,count);
    41.      }
    42. }
    43. void inkq(int a[],int k)
    44. {
    45.      int vt=1;
    46.      for(int i=1;i<=n;i++)
    47.      if(b[i]==k) vt=i;
    48.      printf("\n %d ",a[vt]);
    49. }
    50.  
    51. int main()
    52. {
    53.     int a[100],k;
    54.     printf("nhap n ");
    55.     scanf("%d",&n);
    56.     for(int i=1;i<=n;i++)
    57.     scanf("%d",&a[i]);
    58.     khoitao();
    59.     printf("nhap k ");
    60.     scanf("%d",&k);
    61.     if(k > n)
    62.          printf("\nkhong tim thay dau nhe !^_^");
    63.     else
    64.         {
    65.                          thuattoan(a,k);
    66.                          inkq(a,k);
    67.         }
    68.     getch();
    69.     return 0;
    70. }

  7. #7
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi butbi_pro Xem bài viết
    nếu sắp xếp dãy thì làm theo cách nào cũng sẽ thay đổi thông tin của dãy ban đầu . (sau khi tìm kiếm các bạn thử cho in lại dãy xem )
    Mình đóng góp bài code này nhé ! tuy hơi dài nhưng thông tin không bị sai so với mảng vào!
    mong các bạn đóng góp cho code đơn giản gọn nhẹ hơn giúp mình với nhé !
    thân !!!

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #define vocung 10000;
    4.  
    5. int n,b[100];
    6. /*
    7.       intput a[] : 3 9 13 7 16 8
    8.     tao mang b[i]: 1 3 5 2 6 4 (muc dich : xep thu tu cua mang a )
    9.             co nghia la :
    10.             a[1] la so nho nhat
    11.             a[4] la so nho thu 2
    12.             a[2] la so nho thu 3
    13. ....
    14. */
    15. void khoitao()
    16. {
    17.      for(int i=1;i<=n;i++)
    18.      b[i]=0;
    19. }
    20.  
    21. void min(int a[],int count)// tim min thu count trong day a
    22. {
    23.      int min=vocung;
    24.      int vt;
    25.      for(int i=1;i<=n;i++)
    26.      if(a[i] < min && b[i]==0)
    27.      {
    28.              min = a[i];
    29.              vt=i;
    30.            
    31.      }
    32.       b[vt]=count;//mang b se ghi lai so thu tu nho tang dan tuong ung voi mang a[]
    33.      
    34. }
    35.  
    36. void thuattoan(int a[],int k)
    37. {
    38.      for(int count=1;count<=k;count++)
    39.      {
    40.              min(a,count);
    41.      }
    42. }
    43. void inkq(int a[],int k)
    44. {
    45.      int vt=1;
    46.      for(int i=1;i<=n;i++)
    47.      if(b[i]==k) vt=i;
    48.      printf("\n %d ",a[vt]);
    49. }
    50.  
    51. int main()
    52. {
    53.     int a[100],k;
    54.     printf("nhap n ");
    55.     scanf("%d",&n);
    56.     for(int i=1;i<=n;i++)
    57.     scanf("%d",&a[i]);
    58.     khoitao();
    59.     printf("nhap k ");
    60.     scanf("%d",&k);
    61.     if(k > n)
    62.          printf("\nkhong tim thay dau nhe !^_^");
    63.     else
    64.         {
    65.                          thuattoan(a,k);
    66.                          inkq(a,k);
    67.         }
    68.     getch();
    69.     return 0;
    70. }
    Tuyệt vời. Thuật toán chạy rất nhanh tuy nhiên vẫn chưa tối ưu.
    Chương trình sau sẽ chứng minh điều đó. Tớ đo số lần thực hiện của các vòng for
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #define vocung 10000;
    4. int dem=0;
    5.  
    6. int n,b[100];
    7. /*
    8.       intput a[] : 3 9 13 7 16 8
    9.     tao mang b[i]: 1 3 5 2 6 4 (muc dich : xep thu tu cua mang a )
    10.             co nghia la :
    11.             a[1] la so nho nhat
    12.             a[4] la so nho thu 2
    13.             a[2] la so nho thu 3
    14. ....
    15. */
    16. void khoitao()
    17. {
    18.      for(int i=1;i<=n;i++)
    19.      b[i]=0;
    20. }
    21.  
    22. void min(int a[],int count)// tim min thu count trong day a
    23. {
    24.      int min=vocung;
    25.      int vt;
    26.      for(int i=1;i<=n;i++)
    27.      {
    28.       if(a[i] < min && b[i]==0)
    29.       {
    30.              min = a[i];
    31.              vt=i;
    32.            
    33.       }
    34.      
    35.       dem++; //Thêm biến dem vao đây để tính sô lần vòng for thực hiện
    36.      }
    37.  
    38.      b[vt]=count;//mang b se ghi lai so thu tu nho tang dan tuong ung voi mang a[]
    39.  
    40. }
    41.  
    42. void thuattoan(int a[],int k)
    43. {
    44.      for(int count=1;count<=k;count++)
    45.      {
    46.              min(a,count);
    47.      }
    48. }
    49.  
    50. void inkq(int a[],int k)
    51. {
    52.      int vt=1;
    53.      for(int i=1;i<=n;i++)
    54.      if(b[i]==k) vt=i;
    55.      printf("\nMin1=%d\n",a[vt]);
    56. }
    57.  
    58. //Tìm min thứ K trong n phần tử , tính chỉ số từ 0 nhé
    59. //Cái này là thuật toán của tớ
    60. int MinK(int A[],int n,int k)
    61. {
    62.  //Tớ đặt lại biến đếm tại đây
    63.   dem=0;
    64.   for (int i=1;i<=k;i++)
    65.   {
    66.     int min=A[i];
    67.     int pos=i; //Vị trí số nhỏ nhất trong dãy từ i+1 trở đi
    68.  
    69.     //Bắt đầu tìm số nhỏ nhất để đưa vào vị trí i trong dãy
    70.     for (int j=i+1;j<=n;j++)
    71.     {
    72.       if (A[j]<=min)
    73.        {
    74.         min=A[j];
    75.         pos=j;
    76.        }
    77.       dem++; //Và đếm được tăng lên mỗi lần trong vòng for lặp
    78.     }
    79.     //Nếu i==k-1 thì ta đã có kết quả là min
    80.      if (i==k) return min;
    81.      else
    82.        //Ngược lại thì đưa đổi chỗ A[i] với A[pos],trong đó A[pos]==min
    83.      {
    84.        int tmp=A[i];
    85.        A[i]=A[pos];
    86.        A[pos]=tmp;
    87.      }
    88.   }
    89. }
    90.  
    91. int main()
    92. {
    93.     int a[100],k;
    94.     printf("nhap n ");
    95.     scanf("%d",&n);
    96.     for(int i=1;i<=n;i++)
    97.     scanf("%d",&a[i]);
    98.     khoitao();
    99.     printf("nhap k = ");
    100.     scanf("%d",&k);
    101.     if(k > n)
    102.          printf("\nkhong tim thay dau nhe !^_^");
    103.     else
    104.         {
    105.                          thuattoan(a,k);
    106.                        
    107.                          //Đây là kết quả thuật toán của bạn
    108.                          inkq(a,k);
    109.                          printf("\ndem1 =%d\n",dem);
    110.         }
    111.    
    112.     dem=0;
    113.     //Còn đây là kết quả chạy thuật toán của tớ các bạn hãy so sánh nhé.
    114.     //Hãy nhập thử 1 dãy bất kỳ để xem số lần thực hiện vòng for của 2 thuật toán
    115.     if(k > n)
    116.          printf("\nkhong tim thay dau nhe !^_^");
    117.     else
    118.     {
    119.      printf("Min2 = %d\n",a[MinK(a,n-1,k)]);
    120.      printf("\ndem2 = %d",dem);
    121.     }
    122.     getch();
    123.     return 0;
    124. }
    Đã được chỉnh sửa lần cuối bởi Tadius : 20-04-2010 lúc 07:47 PM.

  8. #8
    Ngày gia nhập
    04 2010
    Bài viết
    30

    hihi!
    minh chưa xét đến độ phức tạp thuật toán
    điều mình muốn nhắc đến là việc bảo toàn dữ liệu sau khi đã giải quyết bài toán thôi .
    nếu làm như bạn mảng a[] sẽ bị thay đổi vị trí các phần tử,và nếu muốn in ra vị trí của phần tử nhỏ thứ k thì làm thế nào ? rắc rối hơn đấy nhé !
    Đón chờ 1 giải thuật Đệ Quy cho bài toán này ...?????
    thân !!!

  9. #9
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi butbi_pro Xem bài viết
    hihi!
    minh chưa xét đến độ phức tạp thuật toán
    điều mình muốn nhắc đến là việc bảo toàn dữ liệu sau khi đã giải quyết bài toán thôi .
    nếu làm như bạn mảng a[] sẽ bị thay đổi vị trí các phần tử,và nếu muốn in ra vị trí của phần tử nhỏ thứ k thì làm thế nào ? rắc rối hơn đấy nhé !
    Đón chờ 1 giải thuật Đệ Quy cho bài toán này ...?????
    thân !!!
    Nếu áp dụng phương pháp của cậu vào thì ta vẫn bảo toàn được dữ liệu bài toán xong lúc đó mảng B ban đầu sẽ lưu chỉ số các phần tử bình thường trong mảng a B[i]=i. Sau đó tiến hành thuật toán của tớ trên B. và trả về chỉ số B[k] là cái chỉ số của phần tử nhỏ thứ k trong dãy.

    Còn về giải thuật đệ quy tớ đang xem xét.
    Cảm ơn đã học đã giúp tớ học thêm được một phương pháp hay.

  10. #10
    Ngày gia nhập
    03 2010
    Nơi ở
    My Home
    Bài viết
    772

    Giải thuật của tớ như sau: Vừa quicksort vừa tim luôn phần từ đó.
    C Code:
    1. void swap(int* a, int* b)
    2. {
    3.     int temp = *a;
    4.     *a = *b;
    5.     *b = temp;
    6. }
    7. int find_by_quicksort(int* a, int lo, int hi, int k)
    8. {
    9.     if(lo <= hi)
    10.         return a[lo];
    11.     int pivot = a[hi];
    12.     int j = hi;
    13.     int i = lo - 1;
    14.     while(i < j)
    15.     {
    16.         while(a[--j] > pivot && j >= lo);
    17.         while(a[++i] < pivot && i <= hi);
    18.         if(i < j)
    19.             swap(a + i, a + j);
    20.     }
    21.     swap(a + i, a + hi);
    22.     // sau khi quicksort ở thời điểm này a[i] đứng đúng vị trí
    23.     // nếu k = i thì ta return ngay a[i]
    24.     if(k == i)
    25.         return a[i];
    26.     //nếu k năm giữa bên trái thì tìm ở dãy bên trái
    27.     else if(k < i)
    28.         return find_by_quicksort(a, lo, i - 1, k);
    29.     //nếu k nằm ở phía bên phải thì tìm ở phía bên phải
    30.     return find_by_quicksort(a, i + 1, hi, k);
    31. }

    ý tưởng là thế, code chay không test
    Đã được chỉnh sửa lần cuối bởi namdq2k : 21-04-2010 lúc 02:00 AM.

Các đề tài tương tự

  1. Tối ưu Code nhập số nguyên dương rồi đảo ngược số nguyên dương vừa nhập trong C
    Gửi bởi tyrant trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 12
    Bài viết cuối: 21-06-2018, 06:19 PM
  2. Kiểm tra xem trong mảng các số nguyên có tồn tại số nguyên lẻ hayko?
    Gửi bởi caphetim trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 8
    Bài viết cuối: 06-05-2013, 03:56 PM
  3. Database cách nhập nhiều nguyên liệu cho một món ăn trong một form quản lý nguyên liệu món ăn
    Gửi bởi mamachue92 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 31-10-2012, 09:55 AM
  4. Bài tập C++ chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo và cộng 2 số nguyên được
    Gửi bởi nghiapro512 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 23-01-2011, 02:14 PM
  5. tìm số nguyên tố có trong mảng 2 chiều, tính tổng các số nguyên tố đó??
    Gửi bởi lesliuton01 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 08-06-2010, 10:21 AM

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