Bài tập về xâu kí tự. Giúp em với

[linhberos]

Em có bài này mong các bác hướng dẫn giúp em. Nhập 1 chuỗi từ bàn phím, in ra số lần xuất nhiều nhất của 1 kí tự trong chuỗi.
VD: Nhập chuỗi là: nguyen van thì kí tự "n" xuất hiện nhiều nhất trong chuỗi, in số lần xuất hiện ra và kí tự đó ra.
Mong các bác giúp em

[chinh_2525]

bạn có thể đổi các chuỗi kí tự thành mã assi và đếm số mã này xuất hiện. xong thì bạn chuyển nó thành kí tự. thế là xong rồi.

[shuto_uke]

Gợi ý như bạn chinh là đúng đó. Chuyển kí tự sang mã ASCII cho đỡ code dài

[saido317]

theo mình: bạn nên sắp xếp cái chuỗi đó tăng (hoặc giảm) dần theo mã ASCII (tất nhiên nếu kô mún làm thay đổi chuỗi thì bạn copy wa 1 chuỗi phụ rồi hãy sắp xếp). Sau khi sắp xếp các ký tự giống nhau sẽ nằm gần nhau, và việc đếm là khá dễ dàng

[chinh_2525]

theo mình làm như cách của bạn thì nó hình như dài quá à. vì vừa sắp xếp vừa đếm sau lại sắp xếp thì khá vất vả.

[saido317]

.................................................. ...............................

[mr.tiger]

vừa sắp xếp vừa đếm sau lại sắp xếp là sao bạn nói mình chả hiểu, copy wa thêm 1 chuỗi phụ, sắp xếp và làm việc cần làm thôi.
còn theo như bạn nói ở trên thì bạn sẽ cho vòng lặp chạy từ ký tự A -> Z phải kô nào, như thế thì vòng lặp lúc nào cũng phải chạy đúng 26 lần, nếu so 2 thuật toán thì chi phí cho thuật toán của mình vẫn tốt hơn chứ. lập trình chứ đâu phải toán học đâu bạn, kô phải code ngắn hơn là thuật toán đó hay hơn đâu

Cái này nghe có vẻ ổn, nhưng cũng chưa ổn lắm, vì ký tự gõ trên bàn phím thì không chỉ có đơn thuần A-Z, mà còn có 0-9, các mã khác, chưa kể cách bấm alternate (sử dụng Alt+[numpad]). Ngoài ra cần phải tính độ phức tạp xem thuật toán này có tốt không. Nếu áp dụng cách này vào trường hợp xâu là nội dung một văn bản dài sẽ không khả thi.

chinh_2525
bạn có thể đổi các chuỗi kí tự thành mã assi và đếm số mã này xuất hiện. xong thì bạn chuyển nó thành kí tự. thế là xong rồi.

Cái này vẫn chung chung. Cũng cần mô tả kỹ hơn cách làm thế nào để tính được độ phức tạp của thuật toán.

-----
Nếu làm trên C\C++ mình nghĩ đơn giản như sau:

1. Khai báo 2 mảng m1, m2.
a. Mảng 1 lưu các ký tự xuất hiện trong xâu, bỏ qua ký tự lặp (nếu là ASCII từ bàn phím thì trên lý thuyết mảng chỉ có tối đa 256 phần tử, mặc dầu sẽ không bao giờ tới được).
b. Mảng 2 lưu tần số xuất hiện của ký tự trong xâu được nhập đó.

2. Duyệt xâu từ đầu đến cuối xau[i] i=0,length-1, đồng thời đẩy từng ký tự nếu chưa có vào mảng 1, bằng cách tìm xau[i] trong m1 m1[j]=xau[i], khởi tạo tần số xuất hiện m2[j]=0, nếu có cập nhật tần số xuất hiện m2[j]=m2[j]+1.

3. Một vòng lặp tìm max trong m2 có chỉ số k, in ra kết quả ký tự m1[k] có tần số xuất hiện m2[k] lớn nhất.  Có thể gộp bước này vào bước 2 luôn để xác định max cho tối ưu, nhưng code viết sẽ hơi khó đọc.

[traitb0902]

Mr Tiger làm đúng đó theo minh cách đó là cơ bản nhất và dễ làm , độ chính xác cao

[saido317]

Cái này nghe có vẻ ổn, nhưng cũng chưa ổn lắm, vì ký tự gõ trên bàn phím thì không chỉ có đơn thuần A-Z, mà còn có 0-9, các mã khác, chưa kể cách bấm alternate (sử dụng Alt+[numpad]). Ngoài ra cần phải tính độ phức tạp xem thuật toán này có tốt không. Nếu áp dụng cách này vào trường hợp xâu là nội dung một văn bản dài sẽ không khả thi.

cho dù nó là kí tự gì đi chăng nữa thì trong mã ASCII nó cũng chỉ là 1 con số mà thôi, sắp xếp tăng (giảm) dần là điều dễ dàng (cho dù là văn bảng dài thì cũng đã có quicksort rồi bác àh, sắp xếp sẽ rất nhanh) sau đó các kí lặp sẽ nằm gần nhau chỉ việc chạy vòng lặp từ a[0]->a[n-1] mà thôi sẽ rất đơn giản

còn cách của bác thì em kô dám ý kiến, nó cũng là cách hay nhưng nếu xét trong 1 văn bản dài thì sao? để có đc mảng các ký tự xuất hiện, mỗi lần thêm phần tử mới bác phải duyệt lại toàn bộ mảng này xem nó đã có chưa, nên trong 1 văn bản dài bác sẽ phải duyệt wa mảng này cực kỳ nhìu lần, chưa tính đến là tốn thêm bộ nhớ cho 2 mảng phụ

[mr.tiger]

Ừ há, nhưng hai mảng của tớ có độ dài chỉ tối đa là 256, trường hợp xấu nhất.

Theo mình hiểu bạn phải sort các ký tự trong xâu kiểu
"Bai tap ve xau ky tu" -> "aaaeikttuuvxB" sau đó đếm số lần xuất hiện của các nhóm ký tự đó.
Theo cách sort của bạn không rõ độ dài bao nhiêu, vì nó là sort các ký tự trong xâu đầu vào. Giả dụ xâu có độ dài 2 tỉ thì sao?

Nếu đó không phải là cách của bạn, xin giải thích.

Còn nếu đã thích chơi QuickSort thì sao không mất công dùng Hash luôn, vì đó là cách tối ưu cho bài toán này.