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 :D 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ụ :D

[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.

[chinh_2525]

-----
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.

theo mình nghĩ cách này hay nhưng mà người lập trình hay người sài máy p4, như vậy đọc cả một bài văn bản thì chắc là treo máy luôn.

[saido317]

Ừ 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.
kô phải vấn đề nằm ở đây, ví dụ sâu input là sâu a, bạn cho vòng lặp chạy từ a[0]->a[n-1] với mỗi a[0], a[1], a[2]... a[n-1] bạn phải kiểm tra xem ở mảng thứ 2 đã xuất hiện chưa, nếu chưa thì thêm mới, rồi thì tăng tần xuất đúng kô nào, có nghĩ là bạn phải duyệt mảng 2 đến n lần, nếu sâu input mà là văn bản dài thì....


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?

mình sort cả ký tự khoảng trắng bạn àh, "Bai tap ve xau ky tu" -> " aaaeikttuuvxB". tất nhiên khi đếm tần xuất thì sẽ bỏ wa kí tự "32"


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.
kô dùng Hash là bởi vì 1 lý do đơn giản: mình chưa học tới :D mình mới học năm 1 thôi nên kiến thức có hạn :)

[bomayday123]

Cho em hỏi tí, đề bài là nhập vào 2 xâu và copy xâu 2 vào xâu 1, in ra màn hình xâu ghép đó, mình nên làm như thế nào ạ!

[Tình Lê]

Cho em hỏi tí, đề bài là nhập vào 2 xâu và copy xâu 2 vào xâu 1, in ra màn hình xâu ghép đó, mình nên làm như thế nào ạ!
Theo mình thì làm vầy

#include<conio.h>
#include<stdio.h>
void main()
{
int j=0, i=0;
char s1[100],s2[100];
printf("Nhap mot chuoi 1: ");
gets(s1);
printf("Nhap mot chuoi 2: ");
gets(s2);
while(s1[i])
i++;
while(s1[i++]= s2[j++]);
puts(s1);
}

[tieutu_ht]

anh chị ơi giúp em giải bài này với!viết chương trình nhập vào một xâu kí tự từ bàn phím.tìm và in ra màn hình từ có độ dài nhỏ nhất

[lucky01hiep]

Đầu tiên bạn nên tạo mãng chứa các từ nhập..rồi kiểm tra mảng nào có chiều dài ít nhất là được

[haqtien09590]

Cho em hỏi tí, đề bài là nhập vào 2 xâu và copy xâu 2 vào xâu 1, in ra màn hình xâu ghép đó, mình nên làm như thế nào ạ!

theo mình hiểu thì làm thế này:
#include<iostream.h>
#include<string.h>
void main(){
char s[100],t[200];//khai bao xau s va t
cin.getline(s,100);//nhap vao xau s
cin.getline(t,200);//nhap vao xau t
strcat(s,t);//noi xau t vao cuoi xau s
cout<<s;
}