Cần một giải thuật hay cho bài toán này!

[sonhn]

Mình đang viết một hàm nhằm phát hiện vị trí của tất cả các đoạn chứa giá trị 0 trong một mảng. Ví dụ: có một mảng a chứa n phần tử, mỗi phần từ nằm trong khoảng từ 0 đến 9.

char *a = new char[n];

và mình nhập giá trị cho mảng này đại loại như sau:

a = {0001234586200001265489241000000002156854000000125 64}

trong mảng trên, có thể thấy rằng có nhiều đoạn mang giá trị 0 nằm lẫn lộn (tạm gọi là đoạn 0). Mình muốn in ra tất cả các vị trí trung tâm của mỗi đoạn 0 này trong mảng. Ví dụ, với mảng a trên, ta phải in các vị trí sau (chỉ mũi tên):

a = {0002345862000026548924100000000215685400000012564 }
------^----------^---------------^----------------^---------

Bạn nào có thể đưa ra một giải thuật (bằng mã giả) hoặc C code thì càng hay. Xin cảm ơn.

[Xcross87]

while ( cnt < str.length )
{
       if ( (int)main[cnt] != 0 )  // Nếu là số 0
       {       
               if ( ZeroStr.length != 0 )    // Nếu có chiều dài
                          printMainZero(ZeroStr);   // Viết hàm in kí tự ở giữa
               else
               ZeroStr = NULL;
       }
       else
       {
         ZeroStr += mainStr[cnt++];  // ở đây tôi viết ngắn gọn : khởi tạo biến đếm số phần tử của ZeroStr và tăng biến đếm phần tử trong mainStr
        }

# Ở trên là tớ viết đơn giản cho cậu hiểu chứ không phải code ..
# Thuật toán không có gì khó, nếu gạp số 0 thì bắt đầu đếm qua một mảng trung gian đến khi nào hết thì in ra và khởi tạo lại mảng trung gian đó; quy trình đến khi hết mảng chính.

[kidkid]

Hix Không biết sao kidkid vẫn không hiểu ý của Sonhn nhỉ ?

Mình đang viết một hàm nhằm phát hiện vị trí của tất cả các đoạn chứa giá trị 0 trong một mảng

trong mảng trên, có thể thấy rằng có nhiều đoạn mang giá trị 0 nằm lẫn lộn (tạm gọi là đoạn 0). Mình muốn in ra tất cả các vị trí trung tâm của mỗi đoạn 0 này trong mảng. Ví dụ, với mảng a trên, ta phải in các vị trí sau (chỉ mũi tên):

Không biết từ trên lâp luận thế nào mà lại bảo là in như thế này ?

a = {0002345862000026548924100000000215685400000012564 }
------^----------^---------------^----------------^---------

[sonhn]

Pete 87 hiểu ý mình rồi ấy chứ! Thanks!

[phthinh]

cái này cũng chẳng có gì là khó:
-dùng mảng một chiều khác để lưu các vị trí mà ở đó giá trị bằng 0,và một biến đếm để xác định (tổng số)số phần tử có giá trị bằng 0 trong mảng đó
- sau khi kiểm tra xong mảng a rồi thì ta làm việc với mảng một chiều mà vừa tạo đó:
+ demphu=0;
+ cho i=0-->dem-1(tùy thuộc vào giá trị khởi tạo cho biến đếm (dem=0))
nếu a[i+1] = a[i]+1; thì
demphu++ ;
else
{
k=demphu /2 (lấy nguyên)
k= i-k;( lúc này k là vị trí cần tìm)
xuất k; (còn nếu muốn xem đoạn đó có bao nhiêu phần tử bằng 0 thì chỉ việc xuất giá trị demphu)
}
chú Ý: đây chỉ mới là gợi ý thôi, về làm nhớ chỉnh lại gí trị các biến demphu cho phu hợp là được còn thuật toán thì OK rồi

[sonhn]

Cảm ơn các bạn. 2 bạn có ý tưởng sử dụng mảng trung gian. Bạn phthinh dùng đến 2 vòng lặp thì không tối ưu lắm. Mình đã làm, và chỉ sử dụng 1 vòng lặp, 2 biến cờ (flag) và không dùng mảng trung gian.