Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Sắp xếp và so sánh thời gian các giải thuật !!!

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    2

    Angry Sắp xếp và so sánh thời gian các giải thuật !!!

    Xây dựng chuơng trình với các chương trình con sau:
    1. Nhập n số thực (từ bàn fím, hoặc nhập ngẫu nhiên, hoặc nhập từ file)
    2. Sắp xếp n số thực ( theo phương pháp đổi chỗ, Quick Sort, Heap Sort) và tính thời gian thực hiện (theo % giây)
    3. So sánh thời gian thực hiện của từng giải thuật. (cái này e thấy khó nhất)

    Câu 3 chưa ai làm được. hehe

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    Câu hỏi này có ai đó đã post rồi. Phiền bạn search trước khi hỏi.
    Keep moving forward!

    ... Retired ...

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    2

    Bài của em viết đó, mong các bác tham khảo và giúp đỡ, còn phần tính thời gian em vẫn chưa làm được.


    Code:
    #include <conio.h>
    #include <stdio.h>
    #include <iostream.h>
    #include <stdlib.h>
    #include <mem.h>
    
    #define MAX 3267
    #define size sizeof(int)
    
      void GioiThieu();
      void chonlua_kieunhap();
      void chonlua_pp();
      void banphim();
      void ngaunhien();
      void creatfile();
      void filetep();
      void dcho(int&,int&);
      void sx_doicho(int);
      void phanhoach(int,int,int&);
      void sx_quick(int,int);
      void Adjust(int,int);
      void time_1();
      void time_2();
      void time();
      void hienthi(int);
      void doicho();
      void quick();
      void heapsort();
      void menu_kieunhap(char);
      void menu_pp(char);
    
      int i,j,n,a[MAX],*index;
      char chon1,chon2,t;
      float time1,time2;
      char ten[15];
      FILE *f;
    
      void main()
           {
    	  GioiThieu();
    	  do{
    	     chonlua_kieunhap();
    	     menu_kieunhap(chon1);
    	     chonlua_pp();
    	     menu_pp(chon2);
    	     cout<<"Thoat chuong trinh ko (Y/N) ? : ";
    	     cin>>chon1;
    	  }while((chon1 == 'n') ||(chon1 == 'N'));
           }
    
      void GioiThieu()
           {
    	 clrscr();
    	 cout<<"***********************************************************************"<<endl;
    	                                    
    	 cout<<"***********************************************************************"<<endl;
           }
      void chonlua_kieunhap()
           {
    	 cout<<"     Hay chon lua cach de nhap : "<<endl;
    	 cout<<"        1.Nhap tu ban phim\n";
    	 cout<<"        2.Nhap ngau nhien\n";
    	 cout<<"        3.Nhap tu file \n";
    	 cout<<"        4.Thoat\n";
    	 cout<<"     Lua chon cua ban :";
    	 cin>>chon1;
           }
      void chonlua_pp()
           {
    	 clrscr();
    	 cout<<"Bai toan sap xep bang cac phuong phap :\n";
    	 cout<<"1.Kieu doi cho\n";
    	 cout<<"2.Kieu quick sort\n";
    	 cout<<"3.Kieu heap sort\n";
    	 cout<<"Thoat cho nhe no \n";
    	 cout<<"Lua chon cua ban : ";
    	 cin>>chon2;
           }
      void banphim()
           {
    	 cout<<"Nhap vao tong so phan tu : ";cin>>n;
    	   for (i=0;i<n;i++)
    	       {
    		 cout<<"\nNhap vao phan tu thu "<<i<<" : ";
    		 cin>>a[i];
    	       }
           }
      void ngaunhien()
           {
    	 randomize();
    	 cout<<"Nhap vao tong so phan tu muon tao : ";cin>>n;
    	 for (i=0;i<n;i++)
    	     a[i] = random(n) + 1;
           }
      void creatfile()
           {
    	 cout<<"Nhap vao ten file can tao : ";cin>>ten;
    	 f = fopen(ten,"wb");
    	   for (i=0;i<n;i++)
    	       {
    		 cout<<"\nNhap vao phan tu thu "<<i<<" : ";
    		 cin>>a[i];
    	       }
    	 fwrite(&a,size,n,f);
    	 fclose(f);
           }
      void filetep()
           {
    	 creatfile();
    	 cout<<"\nCho biet ten file lay du lieu : ";cin>>ten;
    	 f = fopen(ten,"rb");
    	 fread(&a,size,n,f);
    	 fclose(f);
           }
      void dcho(int &w,int &z)
           {
    	 int tg = w;
    	 w = z;
    	 z = tg;
           }
      void sx_doicho(int m)
           {
    	 for (i=0;i<m-1;i++)
    	   for (j=i+1;j<m;j++)
    	     if ( a[i] > a[j] )
    		dcho(a[i],a[j]);
           }
      void phanhoach(int low,int up,int& pivot)
           {
    	int pivotval=a[low];
    	int i=low;
    	int j=up;
    	while(i<j)
    	  {
    	    while(a[i]<=pivotval && i<up) i++;
    	    while(a[j]>pivotval)  j--;
    	    if(i<j) dcho(a[i],a[j]);
    	  };
    	dcho(a[low],a[j]);pivot=j;
           }
      void sx_quick(int i,int j)
           {
    	 int k;
    	 if ( i<j )
    	    {
    	      phanhoach(i,j,k);
    	      sx_quick(i,k-1);
    	      sx_quick(k+1,j);
    	    }
           }
      void Adjust(int first,int last)
           {
    	  int r = first;
    	  while ( r <= (last / 2))
    	    if ( last == 2*r)
    	       {
    		 if (a[r] <a[last]) dcho(a[r],a[last]);
    		 r = last;
    	       }
    	    else if ( ( a[r] <a[2*r] ) && (a[2*r] >= a[2*r+1]))
    	       {
    		 dcho(a[r],a[2*r]);
    		 r = 2*r;
    	       }
    	    else if ( (a[r] < a[2*r+1]) && (a[2*r+1] > a[2*r]))
    	       {
    		 dcho(a[r],a[2*r+1]);
    		 r = 2*r+1;
    	       }
    	    else r = last;
    
    
           }
      void time_1()
           {
    
           }
      void time_2()
           {
           }
      void time()
           {
           }
      void hienthi(int m)
           {
    	 cout<<"\nKet qua sort : ";
    	   for (i=0;i<m;i++)
    	     cout<<a[i]<<"   ";
    	 cout<<endl;
           }
      void doicho()
           {
    	 GioiThieu();
    	 cout<<"Chuong trinh sort bang phuong phap doi cho"<<endl;
    	 sx_doicho(n);
    	 hienthi(n);
    	 time();
           }
      void quick()
           {
    	 GioiThieu();
    	 cout<<"Chuong trinh sort bang phuong phap Quick"<<endl;
    	 sx_quick(0,n-1);
    	 hienthi(n);
    	 time();
           }
      void heapsort()
           {
    	 int i;
    	 GioiThieu();
    	 cout<<"Chuong trinh sort bang phuong phap heap"<<endl;
    	   for(i=n/2;i>=0;i--)
    	     Adjust(i,n);
    	   for (i=n;i>0;i--)
    	       {
    		 dcho(a[1],a[i]);
    		 Adjust(1,j-1);
    	       }
    	 hienthi(n);
    	 time();
           }
      void menu_kieunhap(char chon)
           {
    	  switch (chon)
    	      {
    		case '1' : banphim();break;
    		case '2' : ngaunhien();break;
    		case '3' : filetep();break;
    		case '4' : exit(0);
    	      }
           }
      void menu_pp(char chon)
           {
    	  switch (chon)
    	      {
    		case '1' : doicho();break;
    		case '2' : quick();break;
    		case '3' : heapsort();break;
    		case '4' : exit(0);
    	      }
           }
    Chú ý phải bỏ code vào thẻ CODE ký tự {#} trên thanh công cụ. Nếu không sửa bài viết sẽ bị xóa.
    posted by iamvtn
    Đã được chỉnh sửa lần cuối bởi iamvtn : 27-11-2007 lúc 09:34 PM.

  4. #4
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Tính thời gian thì cậu nên lấy xung lock đổi ra sẽ chính xác hơn

  5. #5
    Ngày gia nhập
    04 2007
    Bài viết
    27

    cho em hỏi bài này đã có ai giải rồi à . thế code ở đâu vậy . em search hoài mà không thấy .

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

    Mặc định Sắp xếp và so sánh thời gian các giải thuật !!!

    Trích dẫn Nguyên bản được gửi bởi


    [CODE
    #include <conio.h>
    #include <stdio.h>
    #include <iostream.h>
    #include <stdlib.h>
    #include <mem.h>
    Này bạn, mình copy về Máy chạy thử sao nó báo thiếu include trên vậy bạn.

    mình có file này không biết có giúp gì được cho bạn không nữa,vì mình cũng là lính mới trong lập trình C thui. Mới tham khảo buổi sáng của thầy giáo xong. hihhihi
    Code:
    #include <stdio.h>
    #include <sys/timeb.h>
    #include <time.h>
    void main( void )
    {
       struct _timeb timebuffer;
       _ftime( &timebuffer );
       
    	
    
    	char *timeline = ctime( & ( timebuffer.time ) );
        printf( "The time is %.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20] );
    
    
    
    	for (long i=0;i<100000;i++)
    		for (long j=0;j<10000;j++);
    			
    				
    
       struct _timeb timebuffer1;
       _ftime( &timebuffer1 );
    
    	char *timeline1 = ctime( & ( timebuffer1.time ) );
        printf( "The time is %.19s.%hu %s", timeline1, timebuffer1.millitm, &timeline1[20] );
    
    
    	long milisecond = timebuffer1.millitm - timebuffer.millitm;
    	long second = timebuffer1.time - timebuffer.time;
    
    	printf("\n So giay %ld  va %ld phan tram giay",second, milisecond);
    
    }

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

    Mình chạy trên BC3.1 và bỏ cái include đó thì chạy đc nhưng code của thuật toán Heap Sort bị sai rùi bạn. Nó xắp xếp không có đúng, bạn coi và test lại thử coi nhé.

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

  1. BackTracking Giải thuật tìm đường đi sao cho thời gian ngắn nhất?
    Gửi bởi y5k72pk trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 16-06-2011, 06:31 AM
  2. So sánh thời gian thực hiện giải thuật của 2 phương pháp (T(n))
    Gửi bởi TapLamIT trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 05-01-2011, 08:39 PM
  3. Thời gian thực hiện thuật toán
    Gửi bởi duyphuc8x trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 05-05-2009, 04:17 PM
  4. Tính thời gian thực hiện thuật toán?
    Gửi bởi thangtcnb trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 25-12-2008, 10:37 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