Thử thách

VetMini · 13/11/21

Có bài toán như vầy:
Ghe đưa lên một cần xé cam và một cần xé quýt. Mướn xe ba gác thồ về miễu. Có người mách lẻo là lúc trên xe có điều ô uế cho nên hai cần xé này không cúng được nữa. Chỉ còn đem ra phát cho chúng sinh đi viếng miễu.
Bây giờ chia ra đĩa. Thầy bói ngồi trước miễu xem xâm và giải quẻ sâm "gia nhất" ra thành:
Miễu này nằm giữa hai hòn. "gia nhất" là thêm một. Thêm một vào giữa hai hòn thành ra ba.
Chủ tin vậy và lập điều kiện mỗi đĩa phải có tối thiểu 2 quả này và một quả kia.
Cho biết làm cách nào để chia được nhiều đĩa nhất.
Nếu muốn viết code VBA càng tốt.

Gợi ý:
Trước mắt tôi có hai giải thuật. Giải thuật thứ nhất giản dị hơn nhưng giải thuật thứ hai thực tế hơn.
Nếu quý vị cho rằng gợi ý này khó hiểu thì cứ việc bỏ qua cái "giải thuật thực tế"

CHAOQUAY · 13/11/21

VetMini đã viết:
Có bài toán như vầy:
Cần xé cam có C quả. Cần xé quýt có Q quả.
Bây giờ chia ra đĩa. Với điều kiện mỗi đĩa phải có tối thiểu 2 quả này và một quả kia.
Cho biết làm cách nào để chia được nhiều đĩa nhất.
Nếu muốn viết code VBA càng tốt.

Gợi ý:
Trước mắt tôi có hai giải thuật. Giải thuật thứ nhất giản dị hơn nhưng giải thuật thứ hai thực tế hơn.
Nếu quý vị cho rằng gợi ý này khó hiểu thì cứ việc bỏ qua cái "giải thuật thực tế"

Max số đĩa là min( Q, C ).
Xếp gạch hóng
---

Xem lại có lẽ chưa chặt. Vẫn hóng

ptm0412 · 13/11/21

Không biết thế này gọi là gì, thực tế hay chết tiệt

- Lấy bên nhiều 2 quả, bên ít 1 quả, sắp từng đĩa cho đến khi số còn lại bằng nhau (hoặc hơn kém 1)
- Bắt đầu lấy 2 này 1 kia, rồi 2 kia 1 này, rồi lại 2 này 1 kia (luân phiên) đến khi hết hoặc còn lẻ không đủ 1 đĩa

ongke0711 · 13/11/21

Thường Quýt nhỏ hơn Cam nên 1 cần xé sẽ nhiều quả hơn, do đó cứ lấy 2 Q + 1 C.

VetMini · 13/11/21

Xin lỗi mọi người. Tôi viết xong đọc lại thì chả thấy gì thực tế để mà nói chuyện thực tế cả.

Xinn đọc lại bài #1 để lấy ý tưởng "thực tế" hơn

ptm0412 · 13/11/21

ongke0711 đã viết:
Thường Quýt nhỏ hơn Cam nên 1 cần xé sẽ nhiều quả hơn, do đó cứ lấy 2 Q + 1 C.

Nhiều hơn thì đúng, nhưng không phải nhiều gấp đôi. Lấy 2Q + 1C thì sẽ đến lúc cam hết quít còn 1 rổ (quít tiều nhỏ xíu), hoặc ngược lại (cam đẹt)

CHAOQUAY · 13/11/21

Số đĩa có lẽ tùy thuộc tỷ số giữa quýt ( Q ) & cam ( C )
Giả sử Q > C:
- Nếu Q>2C số đĩa = C
- Ngược lại Số đĩa = Q/2.

ptm0412 · 13/11/21

CHAOQUAY đã viết:
Số đĩa có lẽ tùy thuộc tỷ số giữa quýt ( Q ) & cam ( C )
Giả sử Q > C:
- Nếu Q>2C số đĩa = C
- Ngược lại Số đĩa = Q/2.

1. Q > 2C
Ví dụ Q = 100, C = 45
Theo bài 3 thì:
- bước 1: 90Q + 45C = 45 đĩa
- không có bước 2
Cộng 45 đĩa ( = C), bạn @CHAOQUAY đúng

2. Q < 2C
Ví dụ Q = 100, C = 55
- bước 1: 90Q + 45C = 45 đĩa. Mỗi loại còn 10
- bước 2: 2Q1C, 2C1Q, 2Q1C, 2C1Q, 2Q1C, 2C1Q = 6 đĩa. Mỗi loại còn 1

Cộng 51 đĩa > Q/2
bạn @CHAOQUAY sai

Nếu Q = 100, C = 60, sau 2 bước tôi sẽ có 53 đĩa

ptm0412 · 13/11/21

Tóm cái thuật toán ct là:
Bước 1:
Gọi y là số đĩa, mỗi đĩa 2Q và 1C cho đến khi số còn lại bằng nhau
q -x = c - y
x = 2y
=> q - 2y = c - y
y = q - c
Thực tế y = min(q - c, c)
Bước 2:
Gọi số còn lại là z (z>0)
z = c - y = c - q + c = 2c - q
Số đĩa của bước 2 (t) là 2/3 của z (t = z * 2 / 3)

Viết hàm:
t = If((c - y) > 0, z * 2 / 3, 0)

Kết quả cuối = y + t = min(q - c, c) + If((2c - q) > 0, RoundDown((2c - q) * 2 / 3,0), 0)

Cái kết quả cuối này đúng hay sai thì chờ lão chủ ra đề

VetMini · 14/11/21

ptm0412 đã viết:
Tóm cái thuật toán ct là:
Bước 1:
Gọi y là số đĩa, mỗi đĩa 2Q và 1C cho đến khi số còn lại bằng nhau
...

Đâu có lý do gì buộc "số còn lại bằng nhau"
Tôi có một chục quýt và 9 cam
6 đĩa: 12 quít + 6 cam.
Còn lại 0 quýt và 3 cam.

Gợi ý: với 3 cam còn lại ở trên, bày ra thêm được 1 đĩa nữa. Kết quả của 12 quýt và 9 cam là 7 đĩa.

Chú thích: toi dùng "chục" chung là 12 nhé. Chớ có bắt bẻ chục ở địa phường đâu đó là 14, hay 16.

Phuocam · 14/11/21

VetMini đã viết:
điều kiện mỗi đĩa phải có tối thiểu 2 quả này và một quả kia.

Số dĩa tối đa là số thấp nhất trong 3 điều kiện sau:

1. Số quýt

2. Số cam

3. Làm tròn =>(Số quýt+Số cam)/3

Công thức: =MIN(Số quýt, Số cam, INT((Số quýt+Số cam)/3)

Số dĩa tối đa của 12 Q+ 9C là: =Min(12,9,int(12+9)/3) = 7

Phuocam · 14/11/21

Dùng vòng lặp liệt kê:

PHP:

Public Function SoDiaCamQuyt(ByVal Cam As Long, ByVal Quyt As Long, ByVal SoLuong1Dia As Long) As Long
'SoLuong1Dia là so luong toi thieu tren 1 dia
Dim SLTD As Long 'so luong toi da tren 1 dia
If SoLuong1Dia < 2 Then Exit Function
SLTD = SoLuong1Dia - 1
Do While Cam + Quyt >= SoLuong1Dia And Cam > 0 And Quyt > 0
    If Cam > Quyt Then
        Cam = Cam - SLTD
        Quyt = Quyt - 1
    Else
        Cam = Cam - 1
        Quyt = Quyt - SLTD
    End If
    SoDiaCamQuyt = SoDiaCamQuyt + 1
Loop

End Function

=SoDiaCamQuyt(12,9,3)

batman1 · 14/11/21

VetMini đã viết:
Tôi có một chục quýt và 9 cam
6 đĩa: 12 quít + 6 cam.
Còn lại 0 quýt và 3 cam.

Gợi ý: với 3 cam còn lại ở trên, bày ra thêm được 1 đĩa nữa. Kết quả của 12 quýt và 9 cam là 7 đĩa.

Từ

mỗi đĩa phải có tối thiểu 2 quả này và một quả kia

suy ra là trên mỗi đĩa phải có cả 2 loại quả. 3 quả cam làm sao xếp được một đĩa vậy?

Đâu có lý do gì buộc "số còn lại bằng nhau"

Nếu điều kiện như tôi trích ở trên thì bài #3 đúng. Chỉ là bài #9 diễn giải bài #3 chưa chặt.

Chính xác phải là: Theo bài 3 thì bước 1 kết thúc khi "bên ít" và "bên nhiều" còn số quả bằng nhau k >= 0 (cùng hết hoặc cùng còn số quả như nhau), hoặc "bên ít" không còn quả nào còn "bên nhiều vẫn còn.

1. q >= 2c -> bước 1: số đĩa = c. Không có bước 2.
2. q < 2c -> bước 1: số đĩa = (q-c). Còn lại quít = q-2*(q-c) = 2*c-q, cam = c-(q-c) = 2*c-q.
Số đĩa trong bước 2 = ((2*c-q) \ 3)*2 + 1 (nếu 2*c-q chia 3 dư 2)

Nếu giả thiết là có thể quít nhiều hơn cam hoặc cam nhiều hơn quít (cam mimi) thì hàm tổng quát

Mã:

Function so_dia(ByVal q As Long, ByVal c As Long) As Long
Dim k As Long
    If q < c Then
        k = q
        q = c
        c = k
    End If
    If q >= 2 * c Then
        so_dia = c
    Else
        so_dia = (q - c) + ((2 * c - q) \ 3) * 2
        If (2 * c - q) Mod 3 = 2 Then so_dia = so_dia + 1
    End If
End Function

ptm0412 · 14/11/21

VetMini đã viết:
Đâu có lý do gì buộc "số còn lại bằng nhau"

Thuật toán 2 bước, và bước 1 làm tới mức đó ấy chứ.

VetMini đã viết:
Gợi ý: với 3 cam còn lại ở trên, bày ra thêm được 1 đĩa nữa. Kết quả của 12 quýt và 9 cam là 7 đĩa.

Điều kiện là ít nhất một nọ hai kia nha bạn già. Nếu 3 cam được, thì 3 quit cũng được, vậy thì số đĩa = (P + Q)/3 (làm tròn), phân bước làm gì cho mệt

Phuocam đã viết:
Số dĩa tối đa của 12 Q+ 9C là: =Min(12,9,int(12+9)/3) = 7

Bạn mô tả từng đĩa của 7 đĩa đó xem có thỏa điều kiện hai này 1 kia không nào?

Bài đã được tự động gộp: 14/11/21

batman1 đã viết:
Số đĩa trong bước 2 = ((2*c-q) \ 3)*2 + 1 (nếu 2*c-q chia 3 dư 2)

Chia 3 dư 2 mà thêm 1 đĩa thì đĩa cuối chỉ có 2 quả, không thỏa điều kiện. Hai quả dư đó phần thưởng cho người chia đó anh

CHAOQUAY · 14/11/21

Thử thêm 1 cách

Mã:

Option Explicit

Public Function SoDiaCamQuyt_(ByVal Cam As Long, ByVal Quyt As Long, ByVal SoLuong1Dia As Long) As Long
Dim Q0, Q1
Dim SLTD As Long 'so luong toi da tren 1 dia
Dim k, t

SLTD = SoLuong1Dia - 1
If Cam > Quyt Then
    Q0 = Cam
    Q1 = Quyt
Else
    Q0 = Quyt
    Q1 = Cam
End If

If Q0 >= SLTD * Q1 Then
    SoDiaCamQuyt_ = Q1
Else
'    k = Q0 / SLTD
'    t = (Q1 - k) \ SoLuong1Dia
'    SoDiaCamQuyt_ = k + t
    SoDiaCamQuyt_ = (Q0 + Q1) \ SoLuong1Dia'<<--
End If
End Function

ptm0412 · 14/11/21

CHAOQUAY đã viết:
Thử thêm 1 cách

Tôi test với 12 và 9 ra 7 đĩa. Bạn cũng thử mô tả từng đĩa xem có thỏa điều kiện ít nhất 2 này 1 kia không?

CHAOQUAY · 14/11/21

ptm0412 đã viết:
Tôi test với 12 và 9 ra 7 đĩa. Bạn cũng thử mô tả từng đĩa xem có thỏa điều kiện ít nhất 2 này 1 kia không?
View attachment 269155

Giả sử Q=12 & C=9, xếp 3 quả, 2 này 1 kia.
Lần 1: Xếp theo Q = 12/2 = 6 đĩa; C dùng hết 6 quả còn lại 3.

Lần 2:
Nhặt 1 quả C, xếp vào 1 đĩa đã xếp, rút 1 quả Q ra. Làm 2 lần sẽ dư 2Q
Lấy 2Q ghép với 1C còn thừa sẽ thêm 1 đĩa.

Vậy là lần 2, với số dư C, mỗi lần dùng 3 quả sẽ được thêm 1 đĩa

ptm0412 · 14/11/21

CHAOQUAY đã viết:
Vậy là lần 2, với số dư C, mỗi lần dùng 3 quả sẽ được thêm 1 đĩa

Nếu vậy là dường như bước 2 bao gồm việc chỉnh sửa bước 1 mặc dù không thay đổi số đĩa bước 1. Quay về "tổng quát" thì tôi đang nghĩ có nên lấy tổng chia 3 phứt cho xong, khỏi phân bước.

CHAOQUAY · 14/11/21

ptm0412 đã viết:
Nếu vậy là dường như bước 2 bao gồm việc chỉnh sửa bước 1 mặc dù không thay đổi số đĩa bước 1. Quay về "tổng quát" thì tôi đang nghĩ có nên lấy tổng chia 3 phứt cho xong, khỏi phân bước.

Tổng chia 3 gặp trường hợp tỷ số Q/C >= 2+3 có thể xảy ra 1 đĩa chỉ có cùng 1 loại.

ptm0412 · 14/11/21

CHAOQUAY đã viết:
Giả sử Q=12 & C=9, xếp 3 quả, 2 này 1 kia.
Lần 1: Xếp theo Q = 12/2 = 6 đĩa; C dùng hết 6 quả còn lại 3.

Tôi lại thử với 13 và 8, Kết quả ra 6. Trong khi dùng công thức của tôi ra 7. Minh họa bằng 2 cột H và I
C2=LET(q,A1,c,A2,MIN(q-c,c)+IF((c*2-q)>0,ROUNDDOWN((c*2-q)*2/3,0),0))

Thử thách

Ăn cùng góc phố

Thành viên gắn bó

Bad Excel Member

Thành viên gắn bó

Ăn cùng góc phố

Bad Excel Member

Thành viên gắn bó

Bad Excel Member

Bad Excel Member

Ăn cùng góc phố

Thành viên mới

Thành viên mới

Thành viên gạo cội

Bad Excel Member

Thành viên gắn bó

Bad Excel Member

Thành viên gắn bó

Bad Excel Member

Thành viên gắn bó

Bad Excel Member

Facebook

Group