Bài tập về mảng

[CuiBapOnline]

Đề là như thế này:Tìm dãy con tăng dần ko liên tiếp dài nhất trong mảng.
VD: Cho mảng A là : 1 2 3 4 8 9 5 6 7 10.
Ở mảng trên có 2 mảng con tăng dần ko liên tiếp đó là : 1 2 3 4 8 9 10 và 1 2 3 4 5 6 7 10. Kết quả của bài trên là 1 2 3 4 5 6 7 10 vì mảng này có 8 phần tử lớn hơn mảng kia 1 phần tử. Ai biết cách làm xin gợi ý dùm mình bài này. Cám ơn trước.

[hacker_mubaohiem]

- uh, bài này có hai cách để làm :

+ Dùng đệ qui quay lui (back tracking).Tạo mảng mới như là một dãy nhị phân 0 1. giá trị 0 ứng với số đó ko đc chon và 1 là đc chon.Sau khi có dãy nhị phân rồi thì ta dựa vào các giá trị 1 để tính tổng,xét tính tăng,tính đô dài và cập nhật kỉ lục...(duyệt toàn bộ, chạy chậm, ko hay nhưng đc cái dễ cài đặt)

+ dùng kĩ thuật Qui hoạch động là hay nhất (khử đệ quy).

Về quay lui thì bạn tự tìm hiểu nhé!Riêng QHĐ thì sáng mai mình nêu ý tưởng cho bạn nhé, CODE lun cũng đc...Tối nay bận suy nghĩ.

[CuiBapOnline]

Mình hiểu ý của bạn ở cách 1 rồi, thanks bạn nhiều.

[CuiBapOnline]

Mình về thử làm theo cách của bạn rồi nhưng ko ổn bạn ơi, bị trục trặc ở chổ này, khi ta dùng 1 mảng phụ b tương đương để đánh dấu những phần tử được chọn là 1 ở mảng con tăng thứ nhất, sau đó tính tổng các số 1 đó để xem độ dài là bao nhiêu để so sánh, khi ta tiếp tục làm như vậy ở mảng con thứ 2 tăng, thì những số 1 ở mảng con b tương đương ở mảng con tăng 1 một sẽ bị gán 1 giá trị mới ở mảng con tăng thứ 2, nếu mảng 2 lớn hơn 1 thì ko có vấn đề gì nhưng ngược lại nếu mảng con 1 lớn hơn mảng 2 thì sẽ ko thể in ra những phần tử ở mảng con 1 theo mảng b tương đương vì nó đã bị đổi khi tìm các phần tử tăng ở mảng con tăng 2. Mình nói như vậy hơi khó hiểu phải ko ? Ví dụ như thế này, ta có 1 mảng A:
a[0]=1 a[1]=2 a[2]=3 a[3]=4 a[4]=8 a[5]=9 a[6]=5 a[7]=10
b[0]=1 b[1]=1 b[2]=1 b[3]=1 b[4]=1 b[5]=1 b[6]=0 a[7]=1
Như vậy mảng tăng thứ I gồm 7 phần tử : 1 2 3 4 8 9 10
b[0]=1 b[1]=1 b[2]=1 b[3]=1 b[4]=0 b[5]=0 b[6]=1 b[7]=1
Như vậy mảng tăng thứ II gồm 6 phần tử : 1 2 3 4 5 10
Bây giờ ta ko thể xuất theo mảng b để tìm dãy dài nhất đc vì dãy b đã bị thay đổi bởi mảng tăng thứ 2.
Cách QHD là thế nào bạn có thể nói cái ý tưởng của bạn cho mình biết đc ko, mình ko biết QHD là gì cả.

[rox_rook]

Nếu không biết QHD là gì thì down sách giải thuật của tác giả Lê Minh Hoàng về đọc sẽ hiểu -> trong box giải thuật ebook có ebook này, tui vừa up lại, vào đó mà down về.
- Trong box giải thuật cũng có 1 số bài tập về QHD cơ bản, đọc thêm ví dụ rùi sẽ hiểu kĩ hơn.
- Tui nhớ là bài này tui có bàn luận với 1 bạn nào rùi, không nhớ lắm, nếu rảnh thì có thể check cái bài viết của tui.

[hacker_mubaohiem]

- bạn ơi,khi chúng ta giải bằng đệ quy quay lui thì ý tưởng tui từng nêu đó chính là ứng dụng của việc tạo ra dãy nhị phân có độ dài N.Vậy khi mảng có N số thì nó sẽ tạo ra 2^N dãy nhị phân.Dựa vào dãy nhị phân đó mình làm một hàm tính toán và cập nhật kỉ lục riêng.Khi đã có một dãy tối ưu thì mình dùng thêm một mảng btoiuu để lưu lại cấu hình tối ưu của b.Và tiếp tục duyệt để tìm tiếp.Sau cùng thoát ra mình có dãy nhị phân tối ưu đc lưu trong mảng btoiuu dực vào đó mà printf ra....

Cấu trúc chương trình như sau...

void back_tracking(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=1;j++)
		{
			b[i] = j;
			if (i==n)
			{
				// Ham kiem tra ki luc...
			}
			else
			{
				back_tracking(i+1);
			}
		}
		b[i] = 0; //Tra ve cau hinh ban dau cho b[i];
	}
}

- Nói chung thì cái này ban đầu thì khó hiểu lắm.Mình đã chia tay với các giải thuật kiểu này lâu rồi nên ko còn "Pro" để hướng dẫn bạn nhiều hơn đc.Sorry nhé!

- Còn về QHD thì bản chất của nó là "Khử đệ quy" thôi...Ví dụ:
+ Bài toán tính dãy FIBONACCI thì có hai cách làm:
*đệ quy:Fibo[n] = Fibo[n-1] + Fibo[n-2];
*Vòng lặp + mảng F: F[i] = F[i-1] + F[i-2] với F[0]=F[1]=1;

- trong đó thì vòng lặp chính là hình thức QHD đó.Nó nhanh hơn đệ quy nhưng hơi khó hiểu về mặt hình thức ( đối với các bài toán lớn hơn)..

- Còn về chi tiết thì xin mời bạn đọc giải thuật của Lê Minh Hoàng nhé !!Nó sẽ chỉ cho bạn...Một ebook hay đó

[maihung1989dn]

Em còn kém lắm, xin mấy huynh chỉ giáo giúp !!

[hoangnhathuan]

mình có một bài toán thế này: cho n là một số nguyên hay lạp trinh đảo ngược số đó vd n=12345 thì làm thế nào để được 54321

[Forlorn_hope]

mình có một bài toán thế này: cho n là một số nguyên hay lạp trinh đảo ngược số đó vd n=12345 thì làm thế nào để được 54321

Bạn có thể lấy từng số đưa vào mảng, sau đó từ mảng, bạn làm ngược lại

int i=1;int A[20];while(n!=0){    A[i]=n%10;    n=n/10;    i=i+1;}//A[1,2,3,4,5]n=0;for(int j=i-1;j>=1;j--)    n=n*10+A[j];//n=(((((0*10+5)*10+4)*10+3)*10+20)*10+1)

[CuiBapOnline]

mình có một bài toán thế này: cho n là một số nguyên hay lạp trinh đảo ngược số đó vd n=12345 thì làm thế nào để được 54321

int n, rem;while(n>0){ rem=n%10;// Lay so du   n=n/10;   printf("%d",rem); //xuat thang so du ra luon}