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]

on 7/3/2011, 9:44 pm

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();
 }

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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

on 21/8/2011, 11:49 pm

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
on 21/8/2011, 11:52 pm

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:

__________________________________
I have a dream! It'stechnology hardware & software.
And......Prime Minister of a country in technology! [You must be registered and logged in to see this image.] [You must be registered and logged in to see this image.]
http://tin4a2uneti.tk

Thích

Báo xấu [0]

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

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
on 22/8/2011, 2:39 pm

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 !


__________________________________
Only You ...
[You must be registered and logged in to see this link.]
[You must be registered and logged in to see this image.]


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
on 22/8/2011, 5:50 pm

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

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
on 22/8/2011, 5:51 pm

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 !

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
on 24/8/2011, 9:05 pm

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
on 24/8/2011, 10:03 pm

chuẩn không cần chỉnh, cám ơn thầy góp ý!

__________________________________
I have a dream! It'stechnology hardware & software.
And......Prime Minister of a country in technology! [You must be registered and logged in to see this image.] [You must be registered and logged in to see this image.]
http://tin4a2uneti.tk

Thích

Báo xấu [0]

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

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 !

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
on 25/8/2011, 7:10 am

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);
}
}




__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
on 25/8/2011, 8:02 am

Ý 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();
}

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
on 25/8/2011, 8:30 am

Ý 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();
 }

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
on 25/8/2011, 8:45 am

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();
 }

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
on 25/8/2011, 8:49 am

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 !

__________________________________
No Signal ...

[You must be registered and logged in to see this link.]
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
Today at 1:33 am

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