Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 16 kết quả

Đề tài: tìm số lớn thứ 3

  1. #1
    Ngày gia nhập
    12 2011
    Nơi ở
    quảng ninh
    Bài viết
    0

    Unhappy tìm số lớn thứ 3

    bài tập :
    cho một danh sách có n phần tử =>xây dựng thuật toán tìm số lớn thứ 3 trong danh sách =>đưa ra số max1, max2, max3 .đánh giá thuật toán .

    chương trình chạy được nhưng chưa đúng nhờ các sư huynh xem giùm

    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<iomanip.h>
    #include<iostream.h>
    #define SPT 100
    void nhapmang(int a[],int n)
    {
    for(int i=0;i<n;i++)
    	{
    	cout<<"\nNhap vao phan tu thu "<<i+1<<" :";
    	cin>>a[i];
    	}
    }
    void xuatmang(int a[],int n)
    {
    	for(int i=0;i<n;i++)
    	cout<<a[i]<<setw(4);
    }
    void xoa(int a[],int &n,int x)
    {
    	for(int i=0;i<n;i++)
    	{
    		if(a[i]==x)
    		{
    			for(i;i<n;i++)
    			{
    				a[i]=a[i+1];
    			}
    			n--;
    		}
    	}
    }
    void loaibotrungnhau(int a[],int &n)
    {
    	for(int i=0;i<n-1;i++)
    	for(int j=i+1;j<n;j++)
    	if(a[i]==a[j])
    	{
    		for(j;j<n;j++)
    		a[j]=a[j+1];
    		i--;
    		j--;
    		n--;
    	}
    }
    void timmax(int a[],int &n)
    {
    	int vitri=0;
    	loaibotrungnhau(a,n);
    	for(int i=0;i<3;i++)
    	{
    		int max=a[0];
    		for(int j=0;j<n;j++)
    		{
    			if(max<a[j])
    			max=a[j];
    		}
    		xoa(a,n,max);
    		cout<<"\nGia tri max "<<i+1<<setw(4)<<max;
    	}
    }
    void main()
    {
    	int a[SPT],n;
    	cout<<"Nhap vao so phan tu cua mang: ";
    	cin>>n;
    	nhapmang(a,n);
    	xuatmang(a,n);
    	timmax(a,n);
    	getch();
    }
    __hochoivachiase__

  2. #2
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Chạy được chỗ nào? có thấy tìm số lớn thứ 3 đâu?

  3. #3
    Ngày gia nhập
    12 2011
    Nơi ở
    quảng ninh
    Bài viết
    0

    xin lỗi các a nhé .......đây mới là bài cần các ae xem giùm

    Code:
    #include <stdio.h>
    #include <conio.h>
    
    main()
    {
     int a[50];
     int n, i, m1,m2,m3;
     printf("Nhap so phan tu cua mang: ");
     scanf("%d",&n);
     for(i=0;i<n;i++)
     {
      printf("Nhap phan tu thu %d: ",i+1);
      scanf("%d",&a[i]);
     }
     m1=m2=m3=a[0];
     for(i=1;i<n;i++)
      if(m1<a[i]) m1=a[i];
     for(i=1;i<n;i++)
      if((m2<a[i]&&a[i]<m1)||m2==m1) m2=a[i];
     for(i=1;i<n;i++)
      if((m3<a[i]&&a[i]<m2)||m3==m2||m3==m1) m3=a[i];
     if(m3<m2)
     {
      printf("Max 3 la: %d",m3);
      printf("\nMax 1 = %d, max 2 = %d, max 3 = %d",m1,m2,m3);
     }
     else printf("Khong ton tai max 3");
     getch();
    }
    __hochoivachiase__

  4. #4
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Xem những dòng màu

    Trích dẫn Nguyên bản được gửi bởi congtubuonngu Xem bài viết
    Code:
    ...
     m1=m2=m3=a[0];
     for(i=1;i<n;i++)
      if(m1<a[i]) m1=a[i];
     for(i=1;i<n;i++)
      if((m2<a[i]&&a[i]<m1)||m2==m1) m2=a[i]; // giải thích tại sao phải ||m2==m1 ? 
     for(i=1;i<n;i++)
      if((m3<a[i]&&a[i]<m2)||m3==m2||m3==m1) m3=a[i]; // giải thích như trên ? 
     if(m3<m2)  // (m3 < m2 && m2 < m1) 
     {
      printf("Max 3 la: %d",m3);
      printf("\nMax 1 = %d, max 2 = %d, max 3 = %d",m1,m2,m3);
     }
     else printf("Khong ton tai max 3");
     getch();
    }

  5. #5
    Ngày gia nhập
    12 2011
    Bài viết
    1

    theo em thi mình nên sắp xếp tăng dần hoặc giảm dần rùi in ra phần tử max1 max2 max3

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mặc định tìm số lớn thứ 3

    Trích dẫn Nguyên bản được gửi bởi boyvui821 Xem bài viết
    theo em thi mình nên sắp xếp tăng dần hoặc giảm dần rùi in ra phần tử max1 max2 max3
    ^^ Cũng ổn nhưng ko nên "sắp xếp hết" mà chỉ nên sắp đúng 3 lần. Là 3 giá trị ở top 1 2 3 sẽ hiện ra trước mắt ^^ (các top có khả năng có cùng giá trị, nếu bài chỉ yêu cầu tìm 3 thằng lớn nhất mà ko yêu cầu phân biệt)

    Cách hay hơn thì là : Chạy 1 lượt rồi cầm 3 biến, bắt đầu đẩy vào. : top 1 top2 top3.
    Mới vào top1=top2=top3 = giá trị mốc nào đấy.
    Sau đó lần lượt: tìm dc Max của mảng thì bắt đầu đẩy các top lên như sau : top3=top2 ; top2=top1 ; top1=max;
    Lưu ý khi so sánh để tìm max thì tùy vào yêu cầu là 3 cái top có cần phải phân biệt ko, hay có thể "đồng hạng nhất , hạng nhì ... vân vân" mà đặt điều kiện thêm dấu = hay ko

    Như vậy khi out ra khỏi hàm thể nào cũng lòi ra 3 số lớn của mảng .
    Đã được chỉnh sửa lần cuối bởi clchicken : 28-12-2011 lúc 11:11 AM.
    Um Mani Padme Hum...!!

  7. #7
    Ngày gia nhập
    11 2010
    Nơi ở
    hell
    Bài viết
    165

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    ^^ Cũng ổn nhưng ko nên "sắp xếp hết" mà chỉ nên sắp đúng 3 lần. Là 3 giá trị ở top 1 2 3 sẽ hiện ra trước mắt ^^ (các top có khả năng có cùng giá trị, nếu bài chỉ yêu cầu tìm 3 thằng lớn nhất mà ko yêu cầu phân biệt)

    Cách hay hơn thì là : Chạy 1 lượt rồi cầm 3 biến, bắt đầu đẩy vào. : top 1 top2 top3.
    Mới vào top1=top2=top3 = giá trị mốc nào đấy.
    Sau đó lần lượt: tìm dc Max của mảng thì bắt đầu đẩy các top lên như sau : top3=top2 ; top2=top1 ; top1=max;
    Lưu ý khi so sánh để tìm max thì tùy vào yêu cầu là 3 cái top có cần phải phân biệt ko, hay có thể "đồng hạng nhất , hạng nhì ... vân vân" mà đặt điều kiện thêm dấu = hay ko

    Như vậy khi out ra khỏi hàm thể nào cũng lòi ra 3 số lớn của mảng .
    nếu pác đã chạy 3 cái top rùi chẳng lẻ nó ko so sánh top2 vs top1 rùi top3 vs 2 cái trc.hay pác cho nó out ra khỏi mảng thế
    HT117-5277

  8. #8
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Trích dẫn Nguyên bản được gửi bởi treatmaster Xem bài viết
    nếu pác đã chạy 3 cái top rùi chẳng lẻ nó ko so sánh top2 vs top1 rùi top3 vs 2 cái trc.hay pác cho nó out ra khỏi mảng thế
    top1 là số lớn nhất, top2 nhì top3 thứ 3 và luôn luôn là như thế trong quá trình chạy thuật toán nên ko cần phải so sánh chúng với nhau bạn ạ !

    Ầy mà nhờ bạn vào xoắn nên mới lòi ra 1 chỗ sơ suất
    Sr, đưa thuật toán tầm bậy quá
    Phải xem thêm bọn top2 top3 nữa chứ @@

    Vậy cần kiểm tra 3 phát chứ kiểm tra 1 phát là bị sót top2 top3 ^^.
    Duyệt mảng, với mỗi phần tử:
    so sánh với top1, nếu >top1 thì cuộn top1,top2,top3. (top3=top2;top2=top1;top1=a[i])
    nếu <top1 mà >top2 thì cuộn top2,top3
    ngược lại nếu >top3 thì cuộn cho top3

    Cảm ơn đã nhắc nhở
    __
    Làm cách này nếu muốn lấy các giá trị là khác nhau
    Còn bằng nhau cũng chơi (đồng hạng nhất, nhì) thì nên thực hiện 3 bước sắp xếp thì 3 thằng lớn nhất sẽ tự động chui lên cho mình xem
    Đã được chỉnh sửa lần cuối bởi clchicken : 28-12-2011 lúc 05:29 PM.
    Um Mani Padme Hum...!!

  9. #9
    Ngày gia nhập
    07 2011
    Bài viết
    38

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Làm cách này nếu muốn lấy các giá trị là khác nhau
    Còn bằng nhau cũng chơi (đồng hạng nhất, nhì) thì nên thực hiện 3 bước sắp xếp thì 3 thằng lớn nhất sẽ tự động chui lên cho mình xem
    Nếu là các giá trị khác nhau thì qsort cái từ cao đến thấp, xong printf thằng thứ 3 là xong, khỏi top 123 với chả lặp cho mệt :P
    Còn nếu mà đồng giải thì ta cũng có thể xài qsort, xong :
    C Code:
    1. int a = 1;
    2. for ( i = 1 ; i < so_luong_so_nhap_vao ; i ++ )
    3.       if ( mang_chua_so [i-1] > mang_chua_so [i] ) a++;
    4.       if ( a == 3 ) {
    5.                printf ( "---------- %... \n", mang_chua_so [i] );  
    6.                break ;
    7.       }

  10. #10
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Trích dẫn Nguyên bản được gửi bởi tuanc Xem bài viết
    Nếu là các giá trị khác nhau thì qsort cái từ cao đến thấp, xong printf thằng thứ 3 là xong, khỏi top 123 với chả lặp cho mệt :P
    Còn nếu mà đồng giải thì ta cũng có thể xài qsort, xong :
    C Code:
    1. int a = 1;
    2. for ( i = 1 ; i < so_luong_so_nhap_vao ; i ++ )
    3.       if ( mang_chua_so [i-1] > mang_chua_so [i] ) a++;
    4.       if ( a == 3 ) {
    5.                printf ( "---------- %... \n", mang_chua_so [i] );  
    6.                break ;
    7.       }
    Qsort hay gì sort cũng dc. Bài này mà có sort vào thì sẽ đơn giản.
    Nhưng bạn phải biết là Các giải thuật sort có thơm lắm cũng phải tiêu tốn 1 độ không đơn giản là nlogn .
    Trong khi bài này ko cần phải tiêu tốn nhiều đến thế. Phải ngồi nghĩ cách khác làm sao ko phí phạm chứ ? Lại còn phải xét thêm là có khả dụng với yêu cầu Bảo toàn trật tự phần tử ko ? Sort rồi thì coi như toi, mà muốn bảo toàn mà vẫn sort thì lại phải clone input ra 1 cái để mà làm ??
    Vì thế mới phải đẻ ra top1 top2 top3 là như thế đấy bạn ạ

    Nếu cứ thích sort cũng dc, nhưng sort phải mở mắt ra mà sort. Ko cần phải sort hết cả mảng, chỉ cần mở con mắt ra, sort cho đủ để đầy 3 thằng lớn nhất lên đầu mảng thôi.
    Thì cũng chỉ tiêu tốn n + n-1 + n-2 lần lặp = 3n-3 thì cũng chỉ là độ ko đơn giản O(n)
    _______
    Code là công việc 1 lần. Và chạy code là công việc xảy ra nhiều lần
    Bạn mất "mệt" 1 lần code để cái code nó chạy nhẹ nhàng mọi lần sau hay là "khỏe" 1 lần code để lần sau chạy code nó" mệt"
    ___
    Với những bài như này: Sort là điều đầu tiên mình nghĩ tới, nhưng sẽ là phương án cuối cùng (khi ko còn cách nào hay hơn) mình chọn để giải quyết
    Đã được chỉnh sửa lần cuối bởi clchicken : 29-12-2011 lúc 10:07 AM.
    Um Mani Padme Hum...!!

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