Cần anh/chị hướng dẫn chèn dấu "." lần lượt vào một chuỗi trong excel (1 người xem)

Liên hệ QC

Người dùng đang xem chủ đề này

Khoan nói chuyện rải mail rác, và bỏ đi chuyện thổi phồng.
Nới trên cương vị giải thuật thì đây là mọt bài toán hóc búa (trừ phi có chỗ nào quá đơn giản mà tôi không thấy nổi). Bạn nào đã thử code chưa?

Trước mắt thì khuynh hướng code là viết 1 hàm rải dẩu chấm lần lượt sau từng ký tự. Hàm này sẽ gọi dệ quy nó để rải chỗ còn lại.
vd chuỗi "quasuchocbua12":
Hàm rải dấu chấm vào sau q, và tự đệ quy nó để tính tiếp "uasuchocbua", cho ra dạng q.xxxxxxxx
Kế đó, nó rài dâu chấm sau u, và tự đệ quy nó để tính tiếp "asuchocbua", cho ra dạng qu.xxxxxxx
Tiếp tục cho đến ký tự cuối là 2

(*) đang suy nghĩ xem có cách nào rải bom (rải tùm lum) dấu cách rồi dùng hàm trim?

à há , lâu rồi chưa có ai đố anh Vetmini phải không ?
mời anh Vetmini cho biết
Đếm tất cả mọi trường hợp chèn dấu chấm vào chuỗi "quasuchocbua12"
từ "q.uasuchocbua12" đến "q.u.a.s.u.c.h.o.c.b.u.a.1.2" sẽ là bao nhiêu trường hợp ? (chỉ hỏi về tổng số) xin mời .
 
à há , lâu rồi chưa có ai đố anh Vetmini phải không ?
mời anh Vetmini cho biết
Đếm tất cả mọi trường hợp chèn dấu chấm vào chuỗi "quasuchocbua12"
từ "q.uasuchocbua12" đến "q.u.a.s.u.c.h.o.c.b.u.a.1.2" sẽ là bao nhiêu trường hợp ? (chỉ hỏi về tổng số) xin mời .
Ké chút cho xôm, kết quả chạy thử là 8191 thì phải.
 
à há , lâu rồi chưa có ai đố anh Vetmini phải không ?
mời anh Vetmini cho biết
Đếm tất cả mọi trường hợp chèn dấu chấm vào chuỗi "quasuchocbua12"
từ "q.uasuchocbua12" đến "q.u.a.s.u.c.h.o.c.b.u.a.1.2" sẽ là bao nhiêu trường hợp ? (chỉ hỏi về tổng số) xin mời .

Cái này thì dễ, chỉ là toán thuần tuý. Cứ giữa 2 ký tự thì có 2 trường hợp, có dấu chấm và không có dấu chấm. Như vậy nếu chuỗi có n ký tự thì có tất cả 2^(n-1) kiểu.

=== đính chính:
Uả quên, theo đúng toán nhị phân, n bit thì trị lớn nhất là 2^n-1, như vậy 2^n kiểu mới đúng chớ.
 
Lần chỉnh sửa cuối:
Sẵn đã gợi ý thì nhắc luôn. Bài này nếu đệ quy thì phải dùng phi tuyến, khó bỏ bố.
Cách dễ hơn là dùng dãy nhị phân, như tôi đã phân tích ở bài #49
 
Sẵn đã gợi ý thì nhắc luôn. Bài này nếu đệ quy thì phải dùng phi tuyến, khó bỏ bố.
Cách dễ hơn là dùng dãy nhị phân, như tôi đã phân tích ở bài #49
Đúng là hiện tại dùng chuỗi nhị phân thì tìm được 8191 mẫu + thêm 1 mẫu gốc không có dấu chấm nào cả thì ra 8192 = 2^(n-1) như bài 49 có nói.
Số lượng kết quả có thể thừa thiếu, nhưng không quan trọng lắm. Việc dùng nhị phân cho bài này có lẽ cũng tàm tạm hiểu được 1 phần.

Nhờ VetMiNi có thể gợi ý cụ thể thêm tí chút về đệ quy phi tuyến để có thể vận dụng cho các trường hợp khác.
Cảm ơn rất nhiều!
---
( Khó cũng được, lâu lâu gặm tí xương cho nó chắc cái răng --=0)
 
Lần chỉnh sửa cuối:
Đúng là hiện tại dùng chuỗi nhị phân thì tìm được 8191 mẫu + thêm 1 mẫu gốc không có dấu chấm nào cả thì ra 8192 = 2^(n-1) như bài 49 có nói.
Số lượng kết quả có thể thừa thiếu, nhưng không quan trọng lắm. Việc dùng nhị phân cho bài này có lẽ cũng tàm tạm hiểu được 1 phần.

Nhờ VetMiNi có thể gợi ý cụ thể thêm tí chút về đệ quy phi tuyến để có thể vận dụng cho các trường hợp khác.
Cảm ơn rất nhiều!
---
( Khó cũng được, lâu lâu gặm tí xương cho nó chắc cái răng --=0)
Anh tham khảo link này xem:
http://vuongwp.blogspot.com/2014/05/code-c-e-quy-phi-tuyen.html
 
Đệ quy: thú thật mình chỉ biết nhìn dạng bài để suy thuật toán thôi. Chứ cái này hướng đi thì dễ, nhưng thực hành thì nó liên quan đến cọng kết quả vào chuỗi nên rất khó. Phải ngồi vẽ đường (trên giấy trắng mực đen đàng hoàng) cả buổi mới hy vọng.

Bài này theo tôi thì các bạn thử dùng dãy nhị phân để giải dễ hơn. Lưu ý: số long chỉ có 32 bits, bỏ đi bit đánh dấu âm, chỉ còn lại 31 bits, tức là chỉ làm được chuỗi 32 ký tự. Muốn làm dài hơn thì phải thêm thuật toán "very long integer", dùng collection hoặc dùng byte array.
 
Vì topic liên quan nhiều vấn đề nhạy cảm , tôi không tổng quát bài toán , chỉ giải quyết chuỗi của anh Vetmini thôi

xét trường hợp cần chèn 2 dấu chấm
Chuỗi "quasuchocbua12" có 14 kí tự , vậy sẽ có 13 khe để dí dấu chấm vào
vị trí của 2 dấu chấm này là 1 con số trong đoạn [1,13] , ta cần tính tất cả mọi bộ 2 số (a,b) mà a và b nằm trong đoạn [1,3]
vậy chả khác nào biểu ta đi tìm số tổ hợp chập 2 của 13
tôi viết 1 thủ tục tạo danh sách các tổ hợp chập k của 13
Mã:
Public Sub createCBlist(maxI As Byte, ByVal i As Byte, ByVal r As Byte, coll As Collection, arr)
If i <= maxI Then
    Dim x As Byte
    For x = r + 1 To 13 Step 1
        arr(i) = x
        createCBlist maxI, i + 1, x, coll, arr
    Next
Else
    coll.Add Join(arr, ";")
End If
End Sub


thủ tục chính
Mã:
Public Sub hello2()
Dim coll As Collection, r As Long, i As Byte, arr, dArr
For i = 1 To 13 Step 1
    ReDim arr(1 To i)
    Set coll = New Collection
    createCBlist i, 1, 0, coll, arr
    ReDim dArr(1 To coll.Count, 1 To 1)
    For r = 1 To coll.Count Step 1
        dArr(r, 1) = coll(r)
    Next
    Sheet1.Range("H1").Offset(, i).Resize(coll.Count).Value = dArr
Next
End Sub

kết quả là ra được 1 mớ tả phí lù nằm rải rác từ cột I tới cột U
muốn có được chuỗi thật thì phải làm công đoạn chuyển đổi cái mớ nhìn thấy thành chuỗi thật
ví dụ "1;3" chuyển thành
q.ua.suchocbua12 , "1;2;3;6" chuyển thành q.u.a.suc.hocbua12 , ......
đấy là ngu kiến của tôi , bạn nào có cách hay hơn để chèn dấu chấm cũng mong nêu ý kiến để tôi học tập . cảm ơn .


 
Như bài 54 có nói, vì đề tài không bình thường nên thử tham gia thuật toán cho vui.
Chuỗi quasuchocbua12 có 14 ký tự, nếu chèn toàn bộ dấu "." sẽ thành "q.u.a.s.u.c.h.o.c.b.u.a.1.2" là 27 ký tự. Nếu tính từ chữ "q", tất cả các dấu "." đều nằm tại các vị trí chẵn.

Tạo một mảng A 1 chiều, có 27 phần tử, các vị trí lẻ là các ký tự của mail trên, chẵn là rỗng.
Tạo một loạt chuỗi nhị phân có độ dài là 13 ký tự, từ 0000000000001 ---> 1111111111111
Quét chuỗi nhị phân, tại vị trí =1 ---> A(vị trí *2)="."
replace() và join() mảng A

Chỉ là một cách xử lý, hy vọng được xem những hướng giải quyết khác.
 
Lần chỉnh sửa cuối:
Như bài 54 có nói, vì đề tài không bình thường nên thử tham gia thuật toán cho vui.
Chuỗi quasuchocbua12 có 14 ký tự, nếu chèn toàn bộ dấu "." sẽ thành "q.u.a.s.u.c.h.o.c.b.u.a.1.2" là 27 ký tự. Nếu tính từ chữ "q", tất cả các dấu "." đều nằm tại các vị trí chẵn.

Tạo một mảng A 1 chiều, có 27 phần tử, các vị trí lẻ là các ký tự của mail trên, chẵn là rỗng.
Tạo một loạt chuỗi nhị phân có độ dài là 13 ký tự, từ 0000000000001 ---> 1111111111111
Quét chuỗi nhị phân, tại vị trí =1 ---> A(vị trí *2)="."
replace() và join() mảng A

Chỉ là một cách xử lý, hy vọng được xem những hướng giải quyết khác.

Theo thuật toán chuỗi nhị phân thì bắt đầu như vậy là gần lắm rồi. Chỉ có điểm: riêng bài này thì không cần phải tạo chuỗi nhị phân riêng? Có thể chèn chuỗi vào thẳng trong chuỗi kia, các vị trí chẵn. Lúc ấy, ta có thể diễn đạt 1 là dấu chấm và 0 là trống.

Tiếp tục thử thuật toán quét chuỗi nhị phân xem.

Chú thích: nếu giới hạn chỉ 32 ký tự thì có thể dùng thuật toán quét theo số nguyên Long. Tạo một biến Long, quét từ 0 đến 2^n. Dùng phép toán tử And để biết bit nào 1 và bit nào 0.
 
Lần chỉnh sửa cuối:
Có bạn nào muốn thử bài toán quét chuỗi nhị phân?

Gợi ý:
Nguyên tắc số nhị phân: 2 ^x là số có bit thứ x+1 là 1, các bit khác là 0
Vì toán tử And trong VBA là toán tử bit And. Suy ra nếu ta And một số với 2 ^ (i-1) thì ta sẽ xét được bit thứ i của số có là 1 hay 0

Ví dụ có n vị trí cần đặt ( n = len(chuỗi) - 1 )

' trong code sau, biến SO tượng trưng cho tất cả các trường hợp dấu chấm
' biến VT dùng đế đọc dọc thoe SO bvaf xét xem bit nào 0 vào bit nào là 1

For SO = 0 to 2 ^ n - 1 ' quét số từ 0 (không có chấm nào) đến 2^n-1 (đủ số chấm)
for VT = 1 to n ' vòng lặp này xét các bits của SO ở vị trí từ 1 đến n
If SO And 2 ^ (VT-1) Then
' bit set, đặt dấu chấm
Else
' bit off, đặt trống
End If
next VT
Next SO
 
Thử làm theo thuật toán đệ quy:
PHP:
Sub Test()
Dim iKQ As Long, KQ(1 To 1048576, 1 To 1)
DeQuy Application.Name, 0, KQ, iKQ
Range("A1:A" & iKQ).Value = KQ
End Sub
PHP:
Private Function DeQuy(ByVal Ch As String, ByVal VTri As Long, ByRef KQ, ByRef iKQ As Long)
Dim i As Long
iKQ = iKQ + 1:  KQ(iKQ, 1) = Ch
For i = VTri + 1 To Len(Ch) - 1
    DeQuy Left(Ch, i) & ChrW(64) & Mid(Ch, i + 1), i + 1, KQ, iKQ
Next
End Function
 
Chuỗi nhị phân. Triong đây có 2 subs. Sub thứ nhất (NhetCham) nhái toán tử tăng 1 của lập trình để thực hiện các mẫu con số. Sub thứ hai (NhetCham2) dùng thẳng số đếm, cộng phép tính xét bit.

Lưu ý: code này tôi viết theo trường phái code của tôi, tách rời thuật toán ra khỏi cách chứa và hiển thị dữ liệu. Nói theo cách khác, bài giải gọi hàm con để chứa kết quả, và gọi hàm con khác để hiển thị kết quả. Kỹ thuật này tách biệt thuậ toán ra khỏi các vấn đề linh tinh.
Lợi điểm trước mắt là khi con số lên rất lớn (2^31 lên đến trên 2 tỷ), ta có thể sửa các hàm con để chứa và hiển thị kết quả theo cách khác mà không hề đụng chạm (hoặc chạm rất ít) vào thuật toán căn bản.

Mã:
' note that this code only demonsatrates the technique
' therefore, it only crunches up the results
' handling of results is left to the three peripheral subs which can be easily modified to suit user's need
' I normally avoid using global variables.
' However, in this case hey present the best way to handle the use of peripheral subs

Private resArr() As String, numEl As Long

Sub NhetCham(ByVal s As String)
Dim sArr() As String
Dim ln As Integer, el As Integer
PrepareResultset
AddToResultset s ' first entry, the string itself, no dots
ln = Len(s)
If ln <= 1 Then GoTo Wrap_Up
ReDim sArr(1 To ln * 2 - 1)
For el = 1 To ln ' copy each character of string to odd position in array
sArr(el * 2 - 1) = Mid(s, el, 1)
Next el
ln = UBound(sArr) - 1 ' ln is now the last even position in array
Do ' start building the rest of the resultset
' the following code simulates the action of adding 1 to an integer
' that is, 1+0 is 1; 1+1 is 0 plus 1 carried to the next digit
' simulation procedure: starting from left most, inspect the element
' if the emement is a dot, turn it to a blank and repeat with the next element
' if the elenemt is a blank, turn it to a dot and exit
    el = 0
    Do
        el = el + 2 ' our values are even-positioned elements of the array
        If el > ln Then Exit Do ' can not carry any further
        If sArr(el) = "" Then
            sArr(el) = "."
            Exit Do
        End If
        sArr(el) = ""
    Loop
    If el > ln Then Exit Do ' no more
    AddToResultset Join(sArr, "") ' add current result
Loop

Wrap_Up:
PresentResultset
End Sub

Sub NhetCham2(ByVal s As String)
Dim sArr() As String
Dim ln As Integer, el As Integer, num As Long
PrepareResultset
ln = Len(s)
If ln < 1 Then GoTo Wrap_Up
ReDim sArr(1 To ln * 2 - 1)
For el = 1 To ln ' copy each character of string to odd position in array
sArr(el * 2 - 1) = Mid(s, el, 1)
Next el
For num = 0 To 2 ^ (ln - 1) - 1
    For el = 0 To ln - 2
        sArr((el + 1) * 2) = IIf(num And 2 ^ el, ".", "")
    Next el
    AddToResultset Join(sArr, "") ' add current result
Next num
Wrap_Up:
PresentResultset
End Sub

Sub PrepareResultset()
numEl = 0
ReDim resArr(1 To 60000)
End Sub

Sub AddToResultset(ByVal s As String)
numEl = numEl + 1
resArr(numEl) = s
End Sub

Sub PresentResultset()
Dim i As Long
For i = 1 To numEl
Range("A" & i) = resArr(i)
Next i
End Sub
 
Web KT

Bài viết mới nhất

Back
Top Bottom