Thảo luận bài toán sắp xếp

Tiêu đề: Thảo luận bài toán sắp xếp 16/7/2009, 9:03 am

đây là bài sắp xếp giảm dần của tớ.

Code:: import java.util.Scanner;
public class sapxep
{
int n;
int so[]=new int[100];
Scanner scan = new Scanner(System.in);
//-------------------------------------------------------------------------------------------------------//
void nhap()
{
System.out.print("Co bao nhieu so?: ");
n= scan.nextInt();
for(int i=0;i<n;i++)
{
System.out.printf("So thu %d: ",i+1);
so[i]=scan.nextInt();
}
}

void sapxep()
{
for(int i=0;i<n-1;i++)
for(int k=i+1;k<n;k++)
{
if(so[i]<so[k])
{
int c;
c=so[i];
so[i]=so[k];
so[k]=c;
}
}
}

void xuat()
{
for(int i=0;i<n;i++)
System.out.printf("So thu %d la: %d \n",i+1,so[i]);
}
//-------------------------------------------------------------------------------------------------------//
public static void main(String[] args)
{
sapxep sx = new sapxep();
sx.nhap();
sx.sapxep();
sx.xuat();
}
}

Vấn đề ở chỗ nếu tớ xây dựng hàm đổi chỗ như sau:

Code:: void swap(int a, int b)
{
int c;
c=a;
a=b;
b=c;
}

Thì khi sử dụng vào trong hàm nó sẽ là:

Code:: void sapxep()
{
......
swap(so[i],so[k]);
}

nhưng nó toàn ko đổi.

Bạn nào biết ko giúp mình với?

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 12:06 am

Bài của bạn copy code thiếu à nha. :shock:

Được sửa bởi Lee87 ngày 17/7/2009, 12:41 am; sửa lần 2.

Baạn xem lại thuật toán sắp xếp đi kìa. cái biến int c phải để ra ngoài các vòng lặp và phải khởi tạo giá trị ban đầu.(int c = 0;)chỉ cần thằng đó chuyển ra ngoài là ok rùi, vì nêu như đặt bên trong vòng lặp thì nó sẽ luôn in ra cái c đó mà ko phải giá trị gán đâu nhé bạn.

Mình sửa nó như thế này:

Code:: import java.util.Scanner;
public class sapxep
{
int n;
int so[]=new int[100];
Scanner scan = new Scanner(System.in);
//-------------------------------------------------------------------------------------------------------//
void nhap()
{
System.out.print("Co bao nhieu so?: ");
n= scan.nextInt();
for(int i=0;i<n;i++)
{
System.out.printf("So thu %d: ",i+1);
so[i]=scan.nextInt();
}
}

void sapxep()
{
int c = 0;
for(int i=0;i<n-1;i++)
for(int k=i+1;k<n;k++)
{
if(so[i]<so[k])
{
c=so[i];
so[i]=so[k];
so[k]=c;
}
}
}

void xuat()
{
for(int i=0;i<n;i++)
System.out.printf("So thu %d la: %d \n",i+1,so[i]);
}
//-------------------------------------------------------------------------------------------------------//
public static void main(String[] args)
{
sapxep sx = new sapxep();
sx.nhap();
sx.sapxep();
sx.xuat();
}
}

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 12:37 am

Tớ sửa lại cái lỗi copi thiếu rồi. ct vẫn chạy ngon
Còn cái lỗi int c thì để trong cũng được vì c chỉ là biến tạm nhằm hoán vị a,b thôi.

Quan trọng là tớ muốn xây dựng 1 cái hàm đổi chỗ swap riêng ý.
Nhưng xây dựng xong sử dụng nó ko đổi chỗ.
Ở trong C++ thì chỗ này phải sử dụng tham chiếu, (hoặc con trỏ gì đó)
Trong java thì tớ chịu

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 12:54 am

dohoangdat90 đã viết:: Tớ sửa lại cái lỗi copi thiếu rồi. ct vẫn chạy ngon
Còn cái lỗi int c thì để trong cũng được vì c chỉ là biến tạm nhằm hoán vị a,b thôi.

Quan trọng là tớ muốn xây dựng 1 cái hàm đổi chỗ swap riêng ý.
Nhưng xây dựng xong sử dụng nó ko đổi chỗ.
Ở trong C++ thì chỗ này phải sử dụng tham chiếu, (hoặc con trỏ gì đó)
Trong java thì tớ chịu

Sory! tớ hiểu nhầm ý bạn.
vậy thì đơn giản quá rùi. hàm của bạn viết chạy đc mà.
bạn sai ở chỗ trong hàm sắp xếp ấy, khi bạn gọi thằng swap() đối với 2 biến mảng mà không có vòng lặp thì nó sẽ không ra cái j cả. mình test lại cho bạn luôn này.
Code của bạn đây:

Code:: import java.util.Scanner;
public class sapxep
{
int n;
int so[]=new int[100];
Scanner scan = new Scanner(System.in);
//-------------------------------------------------------------------------------------------------------//
void nhap()
{
System.out.print("Co bao nhieu so?: ");
n= scan.nextInt();
for(int i=0;i<n;i++)
{
System.out.printf("So thu %d: ",i+1);
so[i]=scan.nextInt();
}
}
// Ham bạn tạo ra đây

void swap(int a, int b)
{
int c;
c=a;
a=b;
b=c;
}

void sapxep()
{
for(int i=0;i<n-1;i++)
for(int k=i+1;k<n;k++)
{
if(so[i]<so[k])
{
swap(so[i],so[k]);
}
}
}

void xuat()
{
for(int i=0;i<n;i++)
System.out.printf("So thu %d la: %d \n",i+1,so[i]);
}
//-------------------------------------------------------------------------------------------------------//
public static void main(String[] args)
{
sapxep sx = new sapxep();
sx.nhap();
sx.sapxep();
sx.xuat();
}
}

Nó vẫn ok mà bạn.

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 9:21 am

her, bài bạn nó có sắp xếp đâu.

Co bao nhieu so?: 6
So thu 1: 3
So thu 2: 6
So thu 3: 4
So thu 4: 1
So thu 5: 7
So thu 6: 4
So thu 1 la: 3
So thu 2 la: 6
So thu 3 la: 4
So thu 4 la: 1
So thu 5 la: 7
So thu 6 la: 4

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 9:52 am

hic, nghỉ 2 buổi, đọc lại mệt quá Sad

tớ hiểu ý của bạn dat rồi, nhưng cũng test thử mà không đc.
Tớ nghĩ là có lẽ bạn sai ở cấu trúc gọi hàm thôi. thuật toán không sai ở đâu cả.
có lẽ swap(A[i],A[j]) không gọi đến hàm swap thì sao, tớ nghỉ 2 buổi vừa rồi lên cũng không biết có học phần gọi hàm chưa Sad

chỉ góp ý thế thôi Razz

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 10:03 am

Code:: void swap(int a, int b)
{
int c;
c=a;
a=b;
b=c;
}

Trong java bạn không thể làm như vậy với các kiểu biến int , float ...trừ phi đó là các đối tượng .

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 10:12 am

Vấn đề này hơi bị phức tạp.

Trích dẫn :

Một trong những điểm khó khăn (và gây tranh cãi) cho những lập trình
viên C++ khi lập trình Java là việc pass-by-value hay
pass-by-reference. Ví dụ:
Object a = new Object("Object A"); //kỳ quặc với C++: Object* a = new ...
Object b = a;
b.setNewName("Object B");

Theo cách hiểu của C++ devs thì rõ ràng Object b thay đổi tên
chẳng liên quan gì đến Object a cả. Thực tế theo Java thì khác, Object
a sẽ có name là “Object B” chẳng khác gì Object b cả.
Để Object b hoàn toàn “độc lập” với Object a thì:
Object b = a.clone();

Thế nhưng hàm swap() trong Java lại chẳng hoạt động theo cách pass-by-reference.
private void swap(Type arg1, Type arg2) {
Type temp = arg1;
arg1 = arg2;
arg2 = temp;
}

Vậy đấy!!! Java thực sự đã làm như thế nào? Ẩn sau những cái lằng nhằng gây tranh cãi như vậy là gì?

Trước hết cần hiểu rằng pass-by-value là cách truyền bằng cách copy giá
trị của tham số vào một “biến” được sử dụng trong nội hàm đó. Do đó khi
hàm trả về thì sẽ hủy đi các tham số copied, và các tham số truyền vào
thì không bị ảnh hưởng thay đổi gì. Trái ngược với nó là
pass-by-reference thì thực sự tạo ra một alias tới các tham số thực sự.
Khi trong hàm thay đổi các tham số đó thì nó cũng thay đổi trực tiếp
các tham số truyền vào. Việc không phải tạo một bản copy ở trong C++
nhiều khi tiết kiệm được CPU với object lớn, có quá trình copy/khởi tạo
phức tạp.
Tuy nhiên thì ở trong Java hàm swap không hoạt động vì nó hoạt động
theo cách thức pass-by-value. Sau khi hàm swap trả về thì arg1 và arg2
không đổi chỗ cho nhau. Nhưng kỳ lạ hơn nếu trong thân hàm swap gọi một
phương thức của Type làm thay đổi object, ví dụ như:
arg1.setValue("Change");

Theo cách nghĩ pass-by-value thì sau khi thoát khỏi hàm swap thì
arg1 chẳng bị thay đổi gì. Thực tế lại khác, arg1 đã gọi phương thức
setValue() do đó khi thoát khỏi hàm thì value của arg1 đã thay đổi.
Hãy nhớ lại rằng trong C cũng không có khái niệm reference (&). Thế
nhưng C lại có pointer (con trỏ) và nó làm cho C mạnh mẽ uyển chuyển
không cần có reference. Java có pointer không?
Nhiều người cho rằng: Object thì là pass-by-reference còn các kiểu primitive thì là pass-by-value (In Java, Objects are passed by reference, and primitives are passed by value.)
Mệnh đề này chỉ đúng một nửa. Object không phải được pass-by-reference
mà là object reference được pass-by-value. Chúng ta sẽ hiểu rõ ở câu
trả lời:
Câu trả lời cho tất cả các sự kỳ quặc trên ở Java đó chính
là Java đã “làm sạch” cú pháp pointer trong C. Java có pointer nhưng
pointer được khai báo và sử dụng một cách rất clean. Và tất nhiên nó
tuy không mạnh bằng pointer trong C nhưng nó cũng “fix” tất cả những
lỗi tiềm tàng và nguy hiểm (casting, releasing pointer hay pointer
arithmetic) của pointer trong C.
Trong Java,
Object a;

giống như trong C/C++
Object* a;

Do đó khi
Object b = a;

có nghĩa trong C/C++
Object* b = a; // b và a đều là pointer

và
b.setName("Object B");

tương đương với
b->setName("Object B");

Thế nên b.setName(”Object B”) cũng đặt object “trỏ” bởi a có tên là “Object B” vì a và b trỏ cùng vào một object.
Và
private void swap(Object a, Object b)
{
Object temp = a;
a = b;
b = temp;
}

tương ứng với
void swap(Object* a, Object* b)
{
Object* temp = a;
a = b;
b = temp;
}

Rõ ràng hàm này trong C không hoạt động trừ phi thay đổi thế này:
void swap(Object* a, Object* b)
{
Object temp = *a;
*a = *b;
*b = temp;
}

“Con trỏ” a và b được truyền theo kiểu pass-by-value (có thể hiểu
rằng Java giống như C, tất cả các tham số được truyền theo kiểu
pass-by-value) nên sau khi hàm swap trả về thì a, b không bị thay đổi
hay phép gán a = b không có ý nghĩa. Thế nhưng a.setValue(”…”) thì đã
thay đổi object trỏ bởi con trỏ.
Tham khảo

Tóm lại 1 VD để sử dụng swap như sau:

Code:: public class Test
{
public Test()
{
number m,n;
m = new number(1);
n = new number(2);
System.out.println("m = " + m.get());
System.out.println("n = " + n.get());
swap(m,n);
System.out.println("m = " + m.get());
System.out.println("n = " + n.get());
}

private void swap(number m, number n)
{
int temp;
temp = m.get();
m.set(n.get());
n.set(temp);
}

public static void main(String[] args)
{
new Test();
}
}

class number
{
private int a;
public number(int p)
{
a = p;
}
public int get()
{
return a;
}
public void set(int p)
{
a = p;
}
}

Tiêu đề: Re: Thảo luận bài toán sắp xếp 17/7/2009, 10:25 am

dohoangdat90 đã viết:: her, bài bạn nó có sắp xếp đâu.

Co bao nhieu so?: 6
So thu 1: 3
So thu 2: 6
So thu 3: 4
So thu 4: 1
So thu 5: 7
So thu 6: 4
So thu 1 la: 3
So thu 2 la: 6
So thu 3 la: 4
So thu 4 la: 1
So thu 5 la: 7
So thu 6 la: 4

Thui chết, mình nhầm với bài của mình, gắn nó vào mà chưa sử lý hàm xuât nên nó vẫn in ra đúng và không gọi tới hàm swap().
Sory bạn Very Happy

.

Tiêu đề: Re: Thảo luận bài toán sắp xếp 23/7/2009, 12:46 pm

Sáng nay ngồi đang ngồi đọc phần arraylist thì thấy cái này .
Share cho mọi người :
// ham swap
void swap(int []A,int i,int j)
{ int t=A[i];
A[i]=A[j];
A[j]=t;
}
// cach goi ham swap
void sapxep(){
for()
for()
if(A[i]>A[j])
swap(A,i,j);
}

Tớ đã test thử rồi ,successful.

» đáp án bài tập 3<đây là cách làm của mình có gì thắc mắc comment cùng thảo luận nhá>....<ai có giải thuật nào hay thì cùng commẻnt và share cho mọi người cùng học hỏi nhá>