xin duoc chi dan ... [Archive] - Diễn Đàn Tin Học

View Full Version : xin duoc chi dan ...

Marina

16-11-2004, 11:07

Em mới học về C , có mấy bài tập , không biết phải xoay sở làm sao , mong các anh chị chỉ giúp
1) có một mảnh đất kích thước (MxN) Xác định số hình vuông nỏ nhất có thể chia ra từ mảnh đất đó (nhập vào M, N)
2)cho n loại tiền a1-an Có số tiền L , tìm số tờ ít nhất có thể đổi ra từ L số tiền đó (thông số nhập là L , n loại tiền , a[n] giá trị loại tiền )

whitepenguin

16-11-2004, 15:33

BÁc ơi Penguin vẫn chưa hiểu rỏ đề bài cho lắm (chắc không được thông minh) ,tại vì penguin nghĩ là cho mãnh đất M*N ,vậy bác nghĩ coi mãnh hình vuông chia từ mảnh đất đó thế nào thì gọi là nhỏ nhất đây ????
Nếu chia như vậy thì penguin nghĩ từ mảnh đó có thể chia làm hàng tỉ tỉ tỉ .... hình vuôing nhỏ nhất .Penguin nghĩ là như vậy !!! Bác có thể nói rõ hơn được hông

Còn bài thứ 2 thì penguin nghĩ bạn nên đổi số tiền L thành ra các tờ tiền an (với an là loại tiền lớn nhất ) như vậy số tờ tiền sẽ ít
bạn làm như sau : L là số tiền
an là một loại tiền co giá trị cao nhất thì "L/an" sẽ ra số tờ tiền đó sau đó lấy L-L/an
thì sẽ ra số tiền còn dư lại ,sp61 tiền còn dư lại này tiếp tục chi cho an(nào đó có giá trị Lớn nhất so với số tiền con dư này) rồi lại lấy dư tiếp tục cho đến khi chia xong
Penguin nghĩ là như vậy ... CÓ gì sai bạn thông củm nhá :d

Marina

17-11-2004, 17:39

không phải chia ra thành hình vuông nhỏ nhất bạn à ! Yêu cầu là chia thành các mảnh hình vuông , và số mảnh hình vuông phải là nhỏ nhất .
Vd mảnh đất 6x9 có thể chia lần đầu một hình vuông 6x6 , còn lại một hình chữ nhật 3x6 thì được chia làm 2 hình vuông 3x3. Vậy số mảnh hình vuông ít nhất là 3 .
Nhưng với mảnh đất 5x6 , nếu ta chia hình vuông lớn trước 5x5 thì ta còn 5 hình vuông nhỏ 1x1=>số mảnh trong cách này là 6 mảnh. còn nếu ta chia làm 2 hình chữ nhật 3x6 và 2x6 , sau đó chia mảnh hcm 3x6 thành 2 hình vuông 3x3, còn mảnh hcm 2x6 thành 3 hv 2x2 thì chỉ có 5 mảnh thui ! Vậy số mảnh ít nhất trong th này là 5
(chính vì mỗi th có một cách chia khác như vậy nên mình không nghĩ đuợc thuật giải chung )

Đối với bài tiền tương tự , vd bạn có 12000 và 3 lọai tiền 5000, 1000,4000néu làm như cách bạn thì phải đởi thành 5000+5000+1000+1000 =.có tất cả 4 tờ , nhưng nếu đổi 12000=3tờ 4000 , số tò sẽ ít hơn

thailehuy

18-11-2004, 10:53

Bài 1 :Mình giả sử hình chữ nhật có kich thước MxN, M < N, và M và N nguyên dương nhá
-Đầu tiên, xét xem M hay N có bằng 1 không, nếu có, số hình vuông ít nhất là M*N (hiển nhiên)
-Nếu M và N đều lớn hơn 1:(2 trở lên)
-Dùng đệ quy:
1. -Đầu tiên xét xem hình chữ nhật đó có thể chia đều thành a hình vuông bằng nhau không (xét vòng lặp: for(i = 2; i< M*N; i = i*i)), nếu được, dừng đệ quy.
Nếu không, chia hình chữ nhật ban đầu thành 2 phần, 1 phần n hình vuông MxM với 1 phần hình chữ nhật (N - nM)xN
2. Nếu hình chữ nhật (N - nM)xN có diện tích lớn hơn 0, lặp lại bước 1 cho hình chữ nhật với kích thước mới
3. Đệ quy kết thúc khi hình chữ nhật còn lại có diện tích là 0;

Dùng 1 biến global để lưu số hình chữ nhật được thêm vào sau mỗi vòng lặp

Bài 2 làm tương tự.

talent computer

18-11-2004, 11:09

mình nghĩ rằng với bài số 2 thì bạn nên dùng phương pháp quy hoạch động.Nếu bạn học qua pascal rồi thì phương pháp này sẽ không khó và bài toán trở nên dễ dàng, đừng làm theo cách ma "whitepenguin " chỉ nhé. Cách đó không đúng đâu. Nếu muốn có bài giải hay cách làm thì hãy gửi mail cho mình qua địa chỉ : thanhtc_qg105@yahoo.com. Mình cũng rất muốn đựoc trao đổi với bạn về những bài toán tin học

Marina

18-11-2004, 17:17

to Thailehuy : bạn có thể nói rõ hơn không , theo như mình hiểu thì giải thuật trên hình như cũng có chỗ chưa đúng lắm

Đầu tiên, xét xem M hay N có bằng 1 không, nếu có, số hình vuông ít nhất là M*N (hiển nhiên)
(vd mảnh đất đó là 1*6 , thì ta có 6 hình vuông 1*1 chứ đâu phải 1 hình vuoông ... khi nào m=n thì mới cói duy nhất 1 hình vuông chứ

1. -Đầu tiên xét xem hình chữ nhật đó có thể chia đều thành a hình vuông bằng nhau không (xét vòng lặp: for(i = 2; i< M*N; i = i*i)), nếu được, dừng đệ quy
nếu bạn chạy vòng lặp từ nhỏ tăng dần lên thì vd mảnh đất là 6*12 , đầu tiên i=2, i<72, i=2*2=4, vậy mảnh đất được chia thành 18 hình vuông kích thước 2*2 , thỏa dk , chương trình sẽ dừng lại , cho đáp số là 18???? trong khi ta có thể chia thành 2 hình vuông 6*6.Nếu sữa lại , cho i chạy từ lớn xuống thì giải thuật của bạn cũng lấy ý tưởng từ việc chia mảnh đất thành hình vuông trước , phần còn lại dùng đệ quy , như vậy bị vướng trường hợp với mảnh đất 5*6 như mình đã vd trên (phải chia thành 2 hình chữ nhật trước )
Mong được đàm luận với các bạn , để tìm, ra cách giải wuyết bài này ...

thailehuy

19-11-2004, 12:25

(vd mảnh đất đó là 1*6 , thì ta có 6 hình vuông 1*1 chứ đâu phải 1 hình vuoông ... khi nào m=n thì mới cói duy nhất 1 hình vuông chứ

Hình như bạn không xem kĩ lắm, mình nói số hình vuông là M*N chứ đâu phải là 1.

nếu bạn chạy vòng lặp từ nhỏ tăng dần lên thì vd mảnh đất là 6*12 , đầu tiên i=2, i<72, i=2*2=4, vậy mảnh đất được chia thành 18 hình vuông kích thước 2*2 , thỏa dk , chương trình sẽ dừng lại , cho đáp số là 18???? trong khi ta có thể chia thành 2 hình vuông 6*6.Nếu sữa lại , cho i chạy từ lớn xuống thì giải thuật của bạn cũng lấy ý tưởng từ việc chia mảnh đất thành hình vuông trước , phần còn lại dùng đệ quy , như vậy bị vướng trường hợp với mảnh đất 5*6 như mình đã vd trên (phải chia thành 2 hình chữ nhật trước )

Chỗ này thì đúng là mình nhầm, phải cho i chạy từ lớn đến nhỏ, nhưng vì mình không biết lớn cỡ nào là vừa(vì không chắc M*N là số chính phương) nên mình nghĩ nên sửa thuật toán lại 1 chút.
Ừm, sau khi phân tích kĩ mình thấy bài còn hơi phụ thuộc vào từng trường hợp. Ví dụ bạn thử hình chữ nhật 4x6 xem. Mình có ý tưởng rồi, nhưng chưa hoàn thiện thuật toán. Chừng nào có thời gian post tiếp !!!

Marina

19-11-2004, 15:34

ah , đúng rùi , xin lỗi bạn , cái đó mình đọc không kĩ
với th cụ thể 5*6, ban đầu Mình nghĩ cho thêm một biến i chạy từ 1 đến N/2 , kiểm tra xem (i)*(N-i) có phải là ước của M , nếu thỏa thì chia mảnh đất M*N thành thành 2 hình chữ nhật i*M và (N-I)*M , còn không thỏa dk trên thì chia theo kiểu hình vuông N*N trước .
Khổ nỗi cũng có th cách chia thành 2 hình chữ nhật lại thu được số mảnh hình vuông nhiều hơn cách chia theo kiểu lấy hình vuông có cạnh là cạnh nhỏ nhất của hcm ban đầu . Do đó , mình nghĩ tới việc cho 2 đoạn code của 2 cách chia này lần lượt chạy , rùi sau đó mới so sánh xem cách nào chia hình vuông nhỏ nhất.Khổ nỗi , nếu chia có một lần thì còn so sánh được , chứ nếu chia nhiều lần thì làm sao so sánh .(Ví như lần đầu thì nên chia thành hình vuông N*N trước , lần 2 với mảnh còn lại thì nên chia thành hình chữ nhật , rùi mảnh còn lại củqa lần 3 ...) Càng nghĩ càng thấy rối rắm , và giải thậut của mình đưa ra không thích hợp !!! chẳng biết có cách nào tổng quát lại không ????

thailehuy

19-11-2004, 19:43

Theo mình nghĩ thì tùy vào hình dạng và kích thước hình chữ nhật, nếu chiều dài lớn hơn chiều rộng rất nhiều, cụ thể từ 2-3 lần trở lên thì có thể dùng cách chia của mình, nếu chiều rộng lớn hơn 1/2 chiều dài thì dùng kiểu chia thành a hình vuông bằng nhau...Thuật toán thì sắp nghĩ ra rồi

hieusua

19-11-2004, 20:15

Hic, ko có thời gian đọc lại mấy bài post trứơc của các bạn, nên nếu ý kiến của mình có trùng thì đừng la nghen :D
Theo tui, hai bài này có chung ý tưởng. Tui trình bày ý tưởng cho bài đầu mới dzô so sánh M dzới N, chọn cái nhỏ hơn. Giả sử N < M, gọi s là tổng các hình vuông, ta lấy s = s + (M div N). Sau đó cho M = N, N thì bằng M mod N. Đến lúc nào số lớn hơn chia hết cho số nhỏ hơn thì dừng được gồi.

whitepenguin

19-11-2004, 21:48

Bác ơi theo penguin bác nên làm đệ quy ca`i bài hình vuông ,
với một biến đếm hình vuông là i=0
M*N,nếu M=N thì i++ ,else thì tìm Max(M,N) và Min(M,N) sau đó lấy Max-Min rồi i++ ,và tiếp tục đệ quy với " (Max-Min) và Min(M,N)" coi như 2 cái đó là M*N "mới"
giài thuật đệ quy chỉ kết thúc khi M=N chú ý bác có thề dùng biến i là toàn cục ,hoặc truyền biến y vào hàm đệ quy theo kiểu reference
Có gì sai sót các bác chỉ em nhá

Để Penguin đóng góp thử 1 giải thuật xem sao ,có gì sai các bác chỉ giúp nhá
int i=0;
void Chiahinhvuong(int M,int N,int &i)
{
if(M==N)
i++;
else
{int minval=Min(M,N);
k=Max(M,N)-minval;
i++;
chiahinhvuong(k,minval,i);
}
}
Penguin mới vừa nghĩ ra tại chỗ thui nên chưa có test thử ,các bác chỉ giúp penguin nếu có gì sai ,và thông cảm nếu hông có đúng yêu cầu bài toán tại vì penguin cũng hông có được sáng suốt cho lắm,cái hàm Max và Min các bác tự thiết kế nhá

Marina

20-11-2004, 12:26

to:ThaiLehuy :cám ơn gợi ý của bạn .để m,ình thử xem sao ...mà trường hợp chiều rộng lớn hơn 1/2 chiều dài ấy , liệu có tổng quát không nhỉ , mà chia thành 2 hình vuông = nhau , hay chia thanh 2 hcnhật ?
to whitepenguin,hieusua : cám ơn các bạn đã nghĩ giúp mình trường hợp chia theo hiònh vuông trước , không biết đối với trường hợp phải chia thành hcn trước nhu mảnh đất 5 *6 các bạn có giải thuật gì không ?

whitepenguin

20-11-2004, 13:16

Marina

22-11-2004, 11:54

chia thành hình chữ nhật trước là sao hả bác??? hình như bài này là chia một mành đất M*N bất kỳ thành các mảnh hình vuông !! tại sao lại phải chia mảnh 5*6 thành hcn trước để làm gì hả bác và tại sao lại chia theo hcn???
mình đã viết phía trên rùi đó :
Nhưng với mảnh đất 5x6 , nếu ta chia hình vuông lớn trước 5x5 thì ta còn 5 hình vuông nhỏ 1x1=>số mảnh trong cách này là 6 mảnh. còn nếu ta chia làm 2 hình chữ nhật 3x6 và 2x6 , sau đó chia mảnh hcm 3x6 thành 2 hình vuông 3x3, còn mảnh hcm 2x6 thành 3 hv 2x2 thì chỉ có 5 mảnh thui ! Vậy số mảnh ít nhất trong th này là 5

talent computer

22-11-2004, 13:16

thailehuy

22-11-2004, 21:16

Ừm, mình không muốn làm mất lòng, nhưng hình như giải thuật thì trên ngôn ngữ nào cũng giống nhau cả, chỉ khác ở phần code thôi.
Hơn nữa, các thuật toán không chính quy như trên đâu có ai nói là hoàn hảo để ứng dụng, mình đưa ra chỉ có tính bàn bạc tham khảo. Nếu bạn có thuật toán hay thì post lên cho mọi ngừơi xem đi (không cần code cũng được)

Marina

23-11-2004, 10:41

may minh ko dang duoc phong tieng viet nen cac ban thong cam nhe
.Cac thuat toan cac ban dua ra o tren (theo 1 so bai minh doc thi van con thieu sot nhieu cho, ma trong tin hoc nguoi ta goi do la phuong phap :"tham lam" hay "an ban",tuc la dung duoc test nao thi dung,dung cang nhieu cang tot)
Doi voi cac test de thi bai cua ban se duoc diem caoo, con doi voi cac test kho thi eeeeeeeeee rang........
Minh koi co nhieu thoi gian tren mang nen minh ko the viet duoc het giai thuat o day,ban nen tim nhung quyen sach ve pascal : tin hoc chon loc cua Thay Nguyen Xuan My, quyen nay ghi rat ro rang ve thuat toan quy hoach dong va nhieu bai toan hay khac.
minh khuyen ban nen tot nhat la di hoc pascal truoc khi hoc C vi giai thuat o nhung bai toan tren pascal se de hieu hon nhieu so voi C.
Ban phai tim hieu truoc khi hoi ai, minh chi co thoi gian tra loi 1 so cau hoi ngan ve giai thuat thoi,ko the o tren mang lau duoc. Sorry
uhm, nam lớp 12 mình cũng học Pascal , năm ngoái học VB và năm nay thì dính C ... Nhưng có lẽ bạn nói đúng , từ truớc đến giờ học tin học nhưng cũng giống như học toán vậy , chỉ thấy bài là lo tìm cách trực tiếp để giải , chưâ bao giờ phải suy nghĩ đến cách giải tổng wát của nó .
Mà hôm trước bạn bảo mình gửi mail , sao chang thấy hồi âm gì cả ? giải thuật mà bạn nói có phải quy họach động không ? Ý tưởng thì mình cũng hiểu đôi chút , nhưng code thì vẫn chưa viết ...:P

bete

23-11-2004, 12:25

Tui có chút thắc mắc:

cho hình chữ nhựt 5x7 => có 1 cách chia như sau:

1111122
1111122
1111133
1111133
1111145

=> chia làm 5 mảnh với 4 lát cắt:
lát thứ 1 tách rời mảnh 1 và phần còn lại (2,3,4,5)
lát thứ 2 tách rời mảnh 2 và phần còn lại (3,4,5)
lát thứ 3 tách rời mảnh 3 và phần còn lại (4,5)
lát thứ 4 tách rời mảnh 4 và phần còn lại (5)

Cũng có 1 cách chia khác:

1112233
1112233
1114555
6677555
6677555

=> chia làm 7 mảnh với 6 lát cắt. Trong cách chia này không thể sắp các lát cắt theo 1 thứ tự nào đó để co được "tách rời ...... khỏi phần còn lại (......)"

Tui để ý các bạn đều giả thiết: các lát cắt đều rơi vào loại 1 (1 lát cắt bất kỳ sẽ chia đôi mảnh con tương ứng). Không biết có cách nào để chứng minh trong rằng: trường hợp tối ưu (số mảnh con là nhỏ nhứt) thì các lát cắt đefu sẽ là loại 1; hoặc tìm được 1 phản thí dụ (trường hợp tối ưu -> có 1 lát cắt nào đó thuộc loại 2).

Nếu tìm được 1 phản thí dụ thì phải tìm hướng mới. Còn nếu chứng minh được "trường hợp tối ưu -> các lát cắt đều là loại 1" thì tui nghĩ có thể làm quy hoạch động như sau:

Cho mảnh con M (dài) x N (rộng): xét tất cả các cách chia đôi mảnh con này thành 2 mảnh. Có 2 hướng chia:

Theo chiều dài: 2 mảnh con là M1xN và M2xN (M1+M2=M)
Theo chiều rộng: 2 mảnh con là MxN1 và MxN2 (N1+N2=N)

Như vậy: đặt R[M,N] là số mảnh con trong trường hợp chia tối ưu mảnh MxN. Khi đó

R[M,N] = R[N,M] = min{min1,min2}
min1 = min{R[M1xN] + R[M2xN] với M1+M2=M}
min2 = min{R[MxN1] + R[MxN2] với N1+N2=N}

Các trường hợp đặc biệt:
R[x,1] = x (x là bất kỳ)
R[1,y] = y (y là bất kỳ)
R[x,x] = 1

-thân

thailehuy

23-11-2004, 20:01

min1 = min{R[M1xN] + R[M2xN] với M1+M2=M}
min2 = min{R[MxN1] + R[MxN2] với N1+N2=N}

Ý bạn là
min1 = min{R[M1xN] , R[M2xN]} với M1+M2=M
min2 = min{R[MxN1] , R[MxN2]} với N1+N2=N
hay sao ?
Thuật toán đó đệ quy rất hay, nhưng làm sao tính được giá trị M1, M2 và N1, N2, tương quan giữa các giá trị đó là gì, hay cho chạy M1 từ 1 và M2 từ M-1 ??
Mình nghĩ vấn đề điên đầu là ở đó, chúng ta không biết phải chia thế nào là hợp lý nhất ở bước đầu tiên

bete

23-11-2004, 20:35

Thân gửi thailehuy:

Không phải là

min1 = min{R[M1xN] , R[M2xN]} với M1+M2=M
min2 = min{R[MxN1] , R[MxN2]} với N1+N2=N

mà là

min1 = min{R[M1xN] + R[M2xN] với M1+M2=M}
min2 = min{R[MxN1] + R[MxN2] với N1+N2=N}

1) min1: chia theo chiều dọc => mỗi cách chia sẽ được 2 mảnh con M1xN và M2xN (với M1+M2=M). Tìm cách chia tối ưu cho mảnh con M1xN. Tương tự tìm cách chia tối ưu cho mảnh con M2xN. Suy ra nếu chia làm 2 mảnh con M1xN và M2xN => cách chia tốt nhứt sẽ được: R[M1xN] + R[M2xN]. min1 là trường hợp chia tốt nhứt nếu chia theo chiều dọc (trong tất cả các cách chia theo chiều dọc: chọn min{R[M1xN] + R[M2xN] với M1+M2=M})

2) min2 là trường hợp chia tốt nhứt nếu chia theo chiều ngang (tương tự min1)

Suy ra min = min{min1,min2}: cách chia tối ưu (nếu chỉ dùng các lát cắt loại 1): so sánh cách chia tốt nhứt theo chiều dọc với cách chia tốt nhứt theo chiều ngang

Vài nhận xét:

a) Tại mỗi bước chia: nếu thử chia mảnh hiện thời theo chiều dọc => được 2 mảnh con => các bước kế mình vẫn xét thử 2 cách chia dọc và ngang (chứ không phải chỉ xét chia theo chiều dọc). Tương tự cho chia theo chiều ngang: nếu thử chia mảnh hiện thời theo chiều ngang => được 2 mảnh con => các bước kế mình vẫn xét thử 2 cách chia dọc và ngang (chứ không phải chỉ xét chia theo chiều ngang)

b) Cho M1 chạy từ 1, M2 = M - M1. Vì tính đối xứng: M1 chạy đến M div 2 là đủ rồi

c) Công thức truy hồi => đệ quy cũng được mà quy hoạch động cũng được

(có gì sai sót các bạn chỉ giùm, cám ơn rất nhiều)

-thân