CNTT4A2 COMMUNITY

Thảo luận học tập


You are not connected. Please login or register

Chuyển đến trang : Previous  1, 2

Go downThông điệp [Trang 2 trong tổng số 2 trang]

7/3/2011, 9:44 pm
Ice.Tea
Ice.Tea

First topic message reminder :

phương pháp Quickshort:


Code:
#include<iostream.h>
#include<iomanip.h>
#include<conio.h>
float a[100];
int n;
void QuickSort(float a[],int l,int r)
{
 int i,j;
 int x;
 i=l;
 j=r;
 x=a[(l+r)/2];
 do
  {
   while (a[i]<x)i++;
   while(a[j]>x)j--;
   if(j<=j)
    {
     if(i<j)
      {
       int temp=a[i];
       a[i]=a[j];
       a[j]=temp;
      }
   i++;
   j--;
     }
   }
   while(i<j);
   if(l<j)QuickSort(a,l,j);
   if(i<r)QuickSort(a,i,r);
}
void input(float a[],int n)
{
 int i;
 for (i = 1; i <= n; i++)
  {
   cout<<"a["<<i<<"]= ";
   cin>>a[i];
  }
}
void output(float a[],int n)
{
  int i;
  for (i = 1; i <= n; i++)
      cout<<a[i]<<"  ";
}
void main()
{
cout<<"Nhap n : ";cin>>n;
          if(n>0)
          {
          cout<<"Day ban dau: ";
          input(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP QuickSort:"<<endl;
          cout<<endl;
          QuickSort(a,1,n);
          output(a,n);
          }
getch();
 }
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea

21/8/2011, 11:49 pm
vungoc
vungoc

Cảm ơn Ice.Tea đã check kết quả.
Nhưng bạn đã mắc phải một lỗi sai lầm rất lớn của lập trình đó là khâu: Kiểm thử.
Như mình đã nói là mình không chạy chương trình nhưng mình khẳng định là bạn đã sai về giải thuật.
Để chứng minh bạn thử kiếm tra theo bộ số sau nhé:
Với giá trị lớn nhât của dãy số (MAX), bạn kiểm tra dãy: 1,5,3,15,4 -> Max của bạn sẽ là 4 - Sai
Với giá trị nhỏ nhất của dãy số (MIN), bạn kiểm tra dãy số 7,2,10,5,7,4 -> MIN của bạn sẽ là 4 - Sai.
Có đúng không Ice.Tea???
Có gì không phải mong bạn bỏ qua nhé!
Chúc vui vẻ.

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà vungoc
21/8/2011, 11:52 pm
kienhl
kienhl

nhìn qua có vẻ như ko sai, nhưng khi ta test nhiều trường hợp ra kết quả khác nhau, yêu cầu xem lại. sử dụng giải thuật tối ưu nhất :956785:
http://tin4a2uneti.tk

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà kienhl
22/8/2011, 12:08 am
vungoc
vungoc

Trong tin học thì không có khái niệm ...có vẻ đâu. Tôi khẳng định là giải thuật này sai.
Goodluck!

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà vungoc
22/8/2011, 2:39 pm
whatsltd4us
whatsltd4us

Vấn đề là ở chỗ này.

Code:
for (i=1;i<n;i++)
  {
  if (a[i]>a[0])
      max=a[i];
  if (a[i]<a[0])
      min=a[i];
  }


Sửa thế này :

Code:
for (i=1;i<n;i++)
  {
  if (a[i]>max)
      max=a[i];
  if (a[i]<min)
      min=a[i];
  }

Cảm ơn vungoc rất nhiều !

http://vdvinh-nd.blogspot.com

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà whatsltd4us
22/8/2011, 5:50 pm
Ice.Tea
Ice.Tea

vungoc đã viết:Cảm ơn Ice.Tea đã check kết quả.
Nhưng bạn đã mắc phải một lỗi sai lầm rất lớn của lập trình đó là khâu: Kiểm thử.
Như mình đã nói là mình không chạy chương trình nhưng mình khẳng định là bạn đã sai về giải thuật.
Để chứng minh bạn thử kiếm tra theo bộ số sau nhé:
Với giá trị lớn nhât của dãy số (MAX), bạn kiểm tra dãy: 1,5,3,15,4 -> Max của bạn sẽ là 4 - Sai
Với giá trị nhỏ nhất của dãy số (MIN), bạn kiểm tra dãy số 7,2,10,5,7,4 -> MIN của bạn sẽ là 4 - Sai.
Có đúng không Ice.Tea???
Có gì không phải mong bạn bỏ qua nhé!
Chúc vui vẻ.

Đã test lại ! Tiếp thu ý kiến của Vungoc ! Thanks! Tại mình cũng mới học lập trình nên cũng hơi kém nên mong nhận đc sự giúp đỡ của mọi người ! :D
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea
22/8/2011, 5:51 pm
Ice.Tea
Ice.Tea

whatsltd4us đã viết:Vấn đề là ở chỗ này.

Code:
for (i=1;i<n;i++)
  {
  if (a[i]>a[0])
      max=a[i];
  if (a[i]<a[0])
      min=a[i];
  }


Sửa thế này :

Code:
for (i=1;i<n;i++)
  {
  if (a[i]>max)
      max=a[i];
  if (a[i]<min)
      min=a[i];
  }

Cảm ơn vungoc rất nhiều !


OK ! Thanks Anh !
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea
24/8/2011, 9:05 pm
doc2v
doc2v

Những giải thuật trong sắp xếp các bạn chưa học nên theo mình khi Post Code lên mạng Ice.Tea nên giải thích ý tưởng giải thuật (trình bày tương đối rõ trong quyển Cấu trúc dữ liệu và giải thuật của Đỗ Xuân Lôi) để các bạn đọc còn hiểu được chứ.
Không hiểu ý tưởng thì các bạn hiểu làm sao được code?
Đẫ đưa lên thì nên cố thêm chút nữa em nhé!
Thân!

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà doc2v
24/8/2011, 10:03 pm
kienhl
kienhl

chuẩn không cần chỉnh, cám ơn thầy góp ý!
http://tin4a2uneti.tk

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà kienhl
25/8/2011, 6:32 am
Ice.Tea
Ice.Tea

doc2v đã viết:Những giải thuật trong sắp xếp các bạn chưa học nên theo mình khi Post Code lên mạng Ice.Tea nên giải thích ý tưởng giải thuật (trình bày tương đối rõ trong quyển Cấu trúc dữ liệu và giải thuật của Đỗ Xuân Lôi) để các bạn đọc còn hiểu được chứ.
Không hiểu ý tưởng thì các bạn hiểu làm sao được code?
Đẫ đưa lên thì nên cố thêm chút nữa em nhé!
Thân!

Vâng ! Em cảm ơn !
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea
25/8/2011, 7:10 am
Ice.Tea
Ice.Tea

Em xin trình bày như sau :


Ý tưởng của giải thuật xếp chọn( Selection sort)


Với mảng gồm n phần tử (Ai,Ai+1,…,An-1). Trước hết ta xét với n phần tử đầu tiên và chọn ra phần tử nhỏ nhất trong n phần tử đó và đưa phần tử này về vị trí đúng của nó là vị trí đầu tiên của dãy hiện hành. Sau đó chúng ta không quan tâm đến phần tử đó nữa, xem dãy hiện hành bây giờ chỉ còn n-1 phần tử của dãy ban đầu, và bắt đầu với vị trí thứ 2, tiếp tục lặp lại quá trình trên cho dãy hiện hành. Cứ như vậy đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng của giải thuật là thực hiện n-1 lượt đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy :

Tiến hành :
Mô tả thuật giải:

B1: Với i=0;
B2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1].
B3: Hoán vị đổi chỗ vị trí a[min] với a[i].
B4: Nếu i<n-1 thì tăng i = i+1;
Lặp lại bước 2
Ngược lại : Dừng // n-1 đã đc sắp xếp đúng vị trí


Các ban tham khảo code :

Code:
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void SelectionSort(float a[], int n)
{
int min; //chi so phan tu nho nhat cua day hien hanh
    for (int i = 0; i < n-1; i++)
    {
        min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j; // xác nhân. vi tri phan tu nho nhât
                if (a[min]<a[i])
                {
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
        }
    }
}
void input(float a[],int n)
{
int i;
for (i = 0; i <n; i++)
  {
cout<<"a["<<i<<"]= ";
cin>>a[i];
  }
}
void output(float a[],int n)
{
  int i;
  for (i = 0; i <n; i++)
cout<<a[i]<<"  ";
}
void main()
{
cout<<"Nhap n : ";cin>>n;
if(n>0)
{
cout<<"Day ban dau: ";
input(a,n);
cout<<endl;
cout<<"\nSap xep theo PP Selection Sort:"<<endl;
cout<<endl;
SelectionSort(a,n);
output(a,n);
}
}



http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea
25/8/2011, 8:02 am
Ice.Tea
Ice.Tea

Ý tưởng của giải thuật xếp chèn( Insertion sort)

Giả sử mảng gồm n phần tử (A0,A1,A2,…,An-1) trong đó i phần tử đầu tiên A0,A1,…,Ai-1 đã có thứ tự. Ý tưởng chính của phương pháp chèn trực tiếp là tìm cách chèn phần tử Ai vào vị trí thích hợp của đoạn đã đc sắp xếp để có dãy mới A0,A1,…,Ai có thứ tự !

Vị trí chèn có thể là :
+ Trước A0
+ Sau Ai-1
+ Giữa 2 phần tử Ak-1 và Ak thỏa Ak-1<=Ai<=Ak ( 1<=k<=i-1)
Cho dãy ban đầu A0,A1,A2,…,An-1 ta có thể xem như đã có đoạn gồm 1 phần tử A0 đã đc sắp.
Sau đó, thêm A1 vào đoạn A0 --> ta có đoạn A0,A1 đc sắp.
Tiếp tục, ta thêm vào đoạn A0,A1 phần tử A2 --> ta có đoạn A0,A1,A2 đc sắp
………
Tiếp tục như vậy cho đến khi thêm xong An-1 vào đoan A0,A1,…,An-2 --> ta có đoạn A0,A1,…,An-1 đc sắp .

Tiến hành :
Mô tả thuật giải:

B1: Với i=1; // đoạn có 1 phần tử A[0] đã đc sắp
B2: x=A[i]// Tìm vị trí (vt) thích hợp trong đoạn A[0] đến A[i-1] để chèn x vào
// đồng thời gán x=A[i] giúp lưu giá trị A[i] tránh bị ghi đè khi dời chỗ các phần tử
B3: Dời các phần tử A[vt] đến A[i-1] sang phải 1 vị trí để dành chỗ cho A[i]
B4: A[vt]=x; // có đoạn A[0],A[1],…,A[i] đã đc sắp
B5: Tăng i=i+1;
Nếu i<n-1--> lặp lại B2.
Ngược lại -->dừng

Các bạn tham khảo code :

Code:
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void InsertionSort(float a[],int n)
{
float x;
for(int i=1;i<n;i++)
  {
   x=a[i];// luu giá tri a[i] tránh bi ghi dè khi doi cho các ptu
int vt=i-1;//tiên' vê ` trai' tìm vi tri chen x
while ((a[vt]>x)&&(vt>=0))
    {
  a[vt+1]=a[vt];
  vt--;
    }
a[vt+1]=x;// chèn x vào dãy
  }
}
void input(float a[],int n)
{
int i;
for (i = 0; i <n; i++)
  {
cout<<"a["<<i<<"]= ";
cin>>a[i];
  }
}
void output(float a[],int n)
{
  int i;
  for (i = 0; i <n; i++)
cout<<a[i]<<"  ";
}
void main()
{
cout<<"Nhap n : ";cin>>n;
if(n>0)
{
cout<<"Day ban dau: ";
input(a,n);
cout<<endl;
cout<<"\nSap xep theo PP insertion sort:"<<endl;
cout<<endl;
InsertionSort(a,n);
output(a,n);
}
getch();
}
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea
25/8/2011, 8:30 am
Ice.Tea
Ice.Tea

Ý tưởng của giải thuật sắp xếp nổi bọt ( Bubble sort)

Ý tưởng chính của thuật giải là xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành.
Sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ I sẽ có vị trí đầu dãy là i . Lặp lại xử lý cho đến khi không còn cặp phần tử nào để xét .

Mô tả thuật giải :

Tiến hành :
B1: i=0; // lần xử lý đầu tiên
B2: j= n-1; // duyệt từ cuối dãy về vị trí i
Trong khi (j<i) thì thực hiện:
Nếu a[j]<a[j-1] // a[j], a[j-1] xét cặp phần tử kế cận
j=j-1;
Hoán vị đổi chỗ vị trí a[j] với a[j-1]
B3: i=i+1; // lần xử lý kế tiếp
Nếu i= n-1: Hết dãy …dừng
Ngược lại : lặp lại B2

Các ban tham khảo Code :

Code:
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void BubbleSort(float a[],int n)
{
 int temp;
 for(int i=0;i<n-1;i++)
 for(int j=n-1;j>i;j--)
 if(a[j]<a[j-1])
  {
   temp=a[j];
   a[j]=a[j-1];
   a[j-1]=temp;
  }
}
void input(float a[],int n)
{
 int i;
 for (i = 0; i <n; i++)
  {
   cout<<"a["<<i<<"]= ";
   cin>>a[i];
  }
}
void output(float a[],int n)
{
  int i;
  for (i = 0; i <n; i++)
      cout<<a[i]<<"  ";
}
void main()
{
cout<<"Nhap n : ";
cin>>n;
cout<<"Day ban dau: ";
          input(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP Bubble sort:"<<endl;
          cout<<endl;
          BubbleSort(a,n);
          output(a,n);

getch();
 }
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea
25/8/2011, 8:45 am
Ice.Tea
Ice.Tea

Phương pháp QUICKSORT

Ý tưởng của giải thuật này là chọn một phần tử đóng vai trò là khoá chốt (còn gọi là điểm mốc), các phần tử nhỏ hơn khoá chốt sẽ phải chuyển lên đứng trước khoá chốt. Các phần tử lớn hơn khoá chốt thì phải chuyển xuống đứng sau khoá chốt. Các bước cụ thể như sau:
• Chọn một phần tử (bất kì) làm khoá chốt.
• Đi từ đầu mảng đến cuối mảng, tìm phần tử đầu tiên lớn hơn khoá chốt, đánh dấu nó là phần tử thứ i.
• Đi từ cuối mảng lên đầu mảng, tìm phần tử đầu tiên nhỏ hơn khoá chốt, đánh dấu nó là phần tử thứ j.
• Nếu i<j, đổi chỗ phần tử thứ i và thứ j.
• Sau đó, đi tiếp theo hai chiều, và đổi chỗ, nếu có, cho đến khi i=j.
• Đổi chỗ phần tử thứ i (cũng là j vào thời điểm này) với phần tử chốt. Khi đó, phần tử chốt là đúng vị trí của nó trong mảng sắp xếp.
• Lặp lại giải thuật trên với hai đoạn của mảng: đoạn trước chốt và đoạn sau chốt.
• Quá trình sẽ dừng khi mỗi đoạn chỉ còn hai phần tử.


Code :
Code:
#include<iostream.h>
#include<conio.h>
float a[100];
int n;
void QuickSort(float a[],int l,int r)
{
 int i,j;
 int x;
 i=l;
 j=r;
 x=a[(l+r)/2];
 do
  {
  while (a[i]<x)i++;
  while(a[j]>x)j--;
 
    if(i<j)
      {
      int temp=a[i];
      a[i]=a[j];
      a[j]=temp;
      }
  i++;
  j--;
   
  }
  while(i<j);
  if(l<j)QuickSort(a,l,j);
  if(i<r)QuickSort(a,i,r);
}
void input(float a[],int n)
{
 int i;
 for (i = 1; i <= n; i++)
  {
  cout<<"a["<<i<<"]= ";
  cin>>a[i];
  }
}
void output(float a[],int n)
{
  int i;
  for (i = 1; i <= n; i++)
      cout<<a[i]<<"  ";
}
void main()
{
cout<<"Nhap n : ";cin>>n;
          if(n>0)
          {
          cout<<"Day ban dau: ";
          input(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP QuickSort:"<<endl;
          cout<<endl;
          QuickSort(a,1,n);
          output(a,n);
          }
getch();
 }
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea
25/8/2011, 8:49 am
Ice.Tea
Ice.Tea

Thầy và các bạn tham khảo nếu chỗ nào chưa hợp lý thì Comment để cùng nhau sửa và tìm phương án tốt hơn nhé ! Thanks !
http://manhtuan-leo.blogspot.com/

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Ice.Tea

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Sponsored content

Về Đầu TrangThông điệp [Trang 2 trong tổng số 2 trang]

Chuyển đến trang : Previous  1, 2

« Xem bài trước | Xem bài kế tiếp »

Bài viết mới cùng chuyên mục

    Bài viết liên quan với Code tham khảo BT Tin

      Quyền hạn của bạn:

      Bạn không có quyền trả lời bài viết