Đúng là mình quên khai báo biến max nhưng tại sao không in ra kết quả nhỉ? Lệnh cuối cùng dùng để in ra a[k] là số xuất hiện nhiều nhất và max là số lần xuất hiện a[k] mà?
Giúp thuật toán tìm số xuất hiện nhiều nhất trong 1 dãy.
- Thread starter chuot0106
- Ngày gửi
chuot0106
Thành viên gắn bó
- Tham gia
- 20/1/13
- Bài viết
- 2,567
- Được thích
- 1,670
Bỏ lệnh exit đi là nó in bạn ạ. Nhưng nó chỉ in số xuất hiện nhiều nhất thôi. Còn số lần xuất hiện thì nó in sai bạn ạ!
Bạn có thể nói qua thuật toán của bạn được không. Để tôi thử sửa lại xem sao?
Chỉnh sửa lần cuối bởi điều hành viên:
Lệnh exit không bỏ được, mục đích của code mình viết là tạo mảng b[1..10] như sau nếu mảng a = 1, 1, 1, 2, 1, 2 thì mảng
b= 1, 2, 3, 1, 4, 2. Khi lặp j từ i-1 đến 1 nếu a=a[j] thì gán b:=b[j]+1 sau đó exit for luôn, nếu không exit thì b sẽ được gán thành b[1]=1. Nếu không dùng exit thì thay bằng goto thoát, nhãn "thoat' này phải đặt ngoài vòng lặp
for j:=i-1 down to 1 để thoát khỏi vòng lặp.
Mã:
Label thoat;
Var i, j, k, max:integer;
a, b: array [1..10] of integer;
Begin
max:=1;
k:=1;
b[1]:=1;
Readln(a[1]);
For i:=2 to 10 do
Begin
Readln(a[i]);
For j:=i-1 downto 1 do
Begin
If a[i]=a[j] then
Begin
b[i]:=b[j]+1;
Goto thoat;
End;
b[i]:=1;
End;
thoat: If b[i]>max then
Begin
max:=b[i];
k:=i;
End;
End;
Writeln(a[k],max);
End.
Lần chỉnh sửa cuối:
chuot0106
Thành viên gắn bó
- Tham gia
- 20/1/13
- Bài viết
- 2,567
- Được thích
- 1,670
Vậy tại sao chương trình lại không in kết quả nhỉ.
Được rồi bạn ạ. Tôi thay lệnh exit; bằng lệnh Break; là OK luôn. Bạn có pascal không thử luôn xem!
Chỉnh sửa lần cuối bởi điều hành viên:
Mình không có Pascal, mà bạn dùng Pascal gì? Mình viết theo cú pháp của Turbo Pascal, ngày xưa học vẫn nhớ lệnh exit. Có thể bạn dùng Pascal khác chăng?
- Tham gia
- 4/11/07
- Bài viết
- 13,902
- Được thích
- 36,465
- Donate (Momo)
- Giới tính
- Nam
- Nghề nghiệp
- Consultant
Gởi chuot,
Bạn không nên viết 1 lần 2, 3 bài liên tục, tôi đã phải gộp 2 thành 1 ít nhất là 4 lần trong topic này, và nhiều lần ở những topic khác. Hãy nghĩ kỹ tất cả những gì cần viết và viết 1 bài, cho xứng đáng 1 bài có ý nghĩa.
Ngoài ra, chỉ cần trích dẫn vừa đủ ý muốn trích, và vừa đủ để biết đang trả lời ai, đừng trích dài thậm thượt rồi viết chỉ 1 câu cụt lủn.
Bạn không nên viết 1 lần 2, 3 bài liên tục, tôi đã phải gộp 2 thành 1 ít nhất là 4 lần trong topic này, và nhiều lần ở những topic khác. Hãy nghĩ kỹ tất cả những gì cần viết và viết 1 bài, cho xứng đáng 1 bài có ý nghĩa.
Ngoài ra, chỉ cần trích dẫn vừa đủ ý muốn trích, và vừa đủ để biết đang trả lời ai, đừng trích dài thậm thượt rồi viết chỉ 1 câu cụt lủn.
Lần chỉnh sửa cuối:
chuot0106
Thành viên gắn bó
- Tham gia
- 20/1/13
- Bài viết
- 2,567
- Được thích
- 1,670
Tôi dùng Free Pascal
Nghe giúp em bạn, vậy thì coi như là VD mẫu cho nó học đi,
Ở đây tôi tạm bỏ qua phần nhập liệu nhé --> em bạn chắc làm tốt (có thể nhập từ bàn phím hay file gì đó, ở đây gán trực tiếp), cơ bản như sau (program sau đảm bảo chạy và đúng thuật toán cơ bản)
Mã:
program VD_day1;
var
i,j,n,maxd,d,id: integer;
a: array[1..10] of integer;
begin
n:=10;
a[1]:=30; a[2]:=4; a[3]:=5; a[4]:=30; a[5]:=7;
a[6]:=4; a[7]:=30; a[8]:=5; a[9]:=7; a[10]:=30;
maxd:=0;
for i:=1 to n-1 do
begin
d:=1;
for j:=i+1 to n do
if a[i]=a[j] then d:=d+1;
if d>maxd then
begin maxd:=d; id:=i; end
end;
writeln('Ket qua la so lap nhieu la ', a[id], ' so lan = ',maxd);
readln;
end.Còn trường hợp liệt kê hết các số có "số lần xuất hiện nhiểu nhất bằng nhau" thì để em bạn tự phát triển xem sao,
Lần chỉnh sửa cuối:
chuot0106
Thành viên gắn bó
- Tham gia
- 20/1/13
- Bài viết
- 2,567
- Được thích
- 1,670
Rất cảm ơn bạn, thuật toán của bạn kết quả cũng chính xác luôn, đặc biệt rất dễ hiểu.
P/s: Một lần nữa cảm ơn tất cả các bạn đã bỏ công sức giúp đỡ tôi!!!
Đừng vội bằng lòng; THI thì cần phải thuật toán tối ưu hơn, tham khảo cái này cho phức tạp hơn chút
Mã:
program VD_day1b;
uses crt;
var
i,j,n,maxd,d,id: integer;
a,b: array[1..10] of integer;
begin
clrscr;
n:=10;
a[1]:=30; a[2]:=4; a[3]:=5; a[4]:=30; a[5]:=7;
a[6]:=4; a[7]:=30; a[8]:=5; a[9]:=7; a[10]:=30;
fillchar(b,sizeof(b),0);
maxd:=0;
for i:=1 to n-1 do
if b[i]=0 then
begin
d:=1;
for j:=i+1 to n do
if a[i]=a[j] then
begin d:=d+1; b[i]:=1 end;
if d>maxd then
begin maxd:=d; id:=i; end
end;
writeln('Ket qua la so lap nhieu la: a[',id,']= ', a[id], ' voi so lan lap= ',maxd);
readln;
end.trường hợp mở rộng liệt kê tất cả , vẫn để cho em ấy tự phát triển
(chú ý là thi thì những bài này thì thuộc loại thường thường vì thi người ta đòi hỏi tư duy thuật toán , nên cần nói em bạn ôn tập kỹ sâu hơn nữa)
Lần chỉnh sửa cuối:
Nếu số của bạn là số nguyên thì theo nghề lập trinh, bài này thuộc loại "mảng tính chỉ số trực tiếp". Tức là bạn tạo một mảng thật lớn, số phần tử lớn hơn hoặc bằng số lớn nhất trong chuỗi số.
Như vậy, mỗi trị số trong chuỗi sẽ ứng với chỉ số của một phần tử trong mảng kia.
Đọc chuỗi, dùng trị để chiếu đến mảng, và tăng số đếm lên 1; đồng thời ghi trị số đếm max là ở chỉ số này. Cứ mỗi trị kế tiếp trong chuỗi thì lại dò lên mảng để cộng 1 và so sánh nó với phần tử đang có số đếm max.
Thuật toán chỉ số trực tiếp là căn bản lập trình. Tại quý vị quen dùng nhiều tiện nghi của vba (như dictionary) nên bỏ qua phần căn bản thôi.
Như vậy, mỗi trị số trong chuỗi sẽ ứng với chỉ số của một phần tử trong mảng kia.
Đọc chuỗi, dùng trị để chiếu đến mảng, và tăng số đếm lên 1; đồng thời ghi trị số đếm max là ở chỉ số này. Cứ mỗi trị kế tiếp trong chuỗi thì lại dò lên mảng để cộng 1 và so sánh nó với phần tử đang có số đếm max.
Thuật toán chỉ số trực tiếp là căn bản lập trình. Tại quý vị quen dùng nhiều tiện nghi của vba (như dictionary) nên bỏ qua phần căn bản thôi.
Đúng thế, rời Dic to Dic nhỏ là chít sặc ngay, bản chất trong Dic cũng xây lên từ những cái cơ bản này, có chăng giờ hiện đại toàn dùng công cụ to, có nhà sản xuất lo.
bài này thuộc thuật toán dò tim, đếm, max cơ bản
@chuot...: xem lại bài #30 có thuật toán tối ưu hơn
Lần chỉnh sửa cuối:
chuot0106
Thành viên gắn bó
- Tham gia
- 20/1/13
- Bài viết
- 2,567
- Được thích
- 1,670
Trời bài này mà bạn vẫn cho là "thường thường" thôi sao? À quên tôi chưa nói rõ, thẳng em của tôi nó thi tin học trẻ không chuyên do bộ công an tổ chức cho con em trong nghành thi với nhau thôi chứ không phải thi "chuyên" nên những bài này mình nghĩ cũng là khó rồi đó!
P/S: Cho tôi hỏi thêm là chương trình sau này dùng thêm mảng b thì có tốt hơn không vậy? Chương trình trước tôi thấy ổn lắm rồi mà. Tôi thấy bạn và bạn Hau151978 có vẻ chắc về pascal thật đấy, nếu các bạn có bài tập Pascal thì gửi tôi xin 1 ít.
Lần chỉnh sửa cuối:
Chắc chắn là tốt hơn và tiết kiệm đi số vòng lặp không đáng có (đối với các số giống nhau đã xét, ví như số 30, chỉ xét lần 1 gặp mà thôi, còn lần sau thì bỏ qua, không cần phải lặp với for j )-- tại sao thế thì nên để cho em bạn tự đọc code và rút ra thì hay hơn.
về bài tập bạn tự tìm trên mạng, các sách nâng cao, sách thuật toán đầy ở thị trường, ở thư viện. Sợ không làm hết được thôi.
Cuộc thi nào thì cũng phải có những bài toán đáng mặt chọn người giỏi, nên những bài thế này e rằng là mức bình bình trong các cuộc thi - tuy vậy cái đó thì em bạn và thầy của em ấy sẽ biết.
Pascal lâu lắm rồi mình không sờ đến nên quên hết rồi, bài tập hay tài liệu cũng không có. Mình thấy bài này về thuật toán là cơ bản, bạn quen VB rồi thì lập trình bằng VB trước sau đó giải thích thuật toán cho cậu em để nó viết bằng Pascal. Code của mình nếu viết bằng VBA sẽ là:
Mã:
Sub main()
Dim a(1 To 10) As Integer, b(1 To 10) As Integer, i As Integer, j As Integer, k As Integer, maxx As Integer
a(1) = Range("a" & 1)
b(1) = 1
maxx = 1
k = 1
For i = 2 To 10
a(i) = Range("a" & i)
b(i) = 1
For j = i - 1 To 1 Step -1
If a(j) = a(i) Then
b(i) = b(j) + 1
Exit For
End If
Next
If b(i) > maxx Then
maxx = b(i)
k = i
End If
Next
[B1] = maxx
[B2] = a(k)
End Sub
Quang_Hải
Thành viên gạo cội
- Tham gia
- 21/2/09
- Bài viết
- 6,053
- Được thích
- 7,968
- Nghề nghiệp
- Làm đủ thứ
Cũng tham gia 2 cái vòng lặp cho chủ thớt tham khảo. Code đơn giản dễ hiểu
Không xài dictionary thì dễ thấy cách vận hành của code. Nhưng mà nếu dữ liệu nhiều thì chắc hơi oải vì cứ For Next hoài
Trước lúc biết Dic mình toàn nhai thế này.
Không xài dictionary thì dễ thấy cách vận hành của code. Nhưng mà nếu dữ liệu nhiều thì chắc hơi oải vì cứ For Next hoài
Trước lúc biết Dic mình toàn nhai thế này.
PHP:
Sub abc()
Dim data(), i, j, n, giatri, solan
data = [A1:A10].Value
For i = 1 To UBound(data)
For j = 1 To UBound(data)
If data(i, 1) = data(j, 1) Then n = n + 1
If n > solan Then
solan = n
giatri = data(i, 1)
Exit For
End If
Next
n = 0
Next
MsgBox giatri & " xuat hien " & solan
End Sub
Lần chỉnh sửa cuối:
Bài này , giờ mới ngó lại, đúng là đêm khuya nhầm lần (tuy kết quả không sai, nhưng số vòng lặp không được giảm)
đoạn này
Mã:
d:=1;
for j:=i+1 to n do
if a[i]=a[j] then
begin d:=d+1; b[[COLOR=#ff0000]i[/COLOR]]:=1 end;thay b[ i ] thành b[ j ] , như sau
Mã:
d:=1;
for j:=i+1 to n do
if a[i]=a[j] then
begin d:=d+1; b[[COLOR=#0000ff]j[/COLOR]]:=1 end;như thế mới đúng ý đồ thuật toán, là cắt bớt vòng "for j ..." lặp các số giống nhau đã xét
sorry về sự nhầm lẫn này, vậy chuot0106 sửa lại nhé
Lần chỉnh sửa cuối:
chuot0106
Thành viên gắn bó
- Tham gia
- 20/1/13
- Bài viết
- 2,567
- Được thích
- 1,670
Đã chuyển thuật toán của anh quanghai1969 sang pascal và đã thành công! Em cảm ơn anh nhiều ạ!
Cho a là mảng chứa các số nguyên dương từ 0 đến N.
Lý thuyết thuật toán:
Lập cnt là mảng N+1 phần tử (0 to N). Trị của phần tử cnt(n) là số lần xuất hiện của n trong a.
Lý thuyết thuật toán:
Lập cnt là mảng N+1 phần tử (0 to N). Trị của phần tử cnt(n) là số lần xuất hiện của n trong a.
Mã:
Option Explicit
Sub t1()
[COLOR=#006400]' hàm tìm số xuất hiện nhiều lần nhất trong một mảng A1:A100
' nếu có nhiều số đồng hạng thì số tiến tới max trước sẽ được ưu tiên[/COLOR]
Dim a As Variant
a = Application.Transpose(Range("a1:a100"))
Dim i As Integer, mde As Integer
Dim cnt(0 To 100000) As Integer
mde = 0
For i = 1 To UBound(a)
cnt(a(i)) = cnt(a(i)) + 1
If cnt(a(i)) > cnt(mde) Then mde = a(i)[COLOR=#006400] ' ghi lại số có số lần nhiều nhất[/COLOR]
Next i
MsgBox "value: " & mde & "; times: " & cnt(mde)
End Sub
Sub t2()
[COLOR=#006400]' hàm tìm số xuất hiện nhiều lần nhất trong một mảng A1:A100
' nếu có nhiều số đồng hạng thì sé được một mảng[/COLOR]
Dim a As Variant
a = Application.Transpose(Range("a1:a100"))
Dim i As Integer, lm As Integer
Dim ans As String
Dim cnt(0 To 100000) As Integer, mde(0 To 100000) As Integer
[COLOR=#006400]' mde là mảng chứa các số có lần xuất hiện nhiều nhất
' lm là phần tử cuối cùng trong mảng mde[/COLOR]
[COLOR=#006400]l[/COLOR]m = 0
mde(lm) = a(LBound(a))
For i = LBound(a) To UBound(a)
[COLOR=#006400] ' nếu số mới nhiều hơn các số trong mảng kết quả thì nó trở thành số độc tôn
' nếu chỉ bằng các số trong mảng kết quả thì nhét thêm nó vào
' nếu ít hơn thì bỏ qua[/COLOR]
If cnt(a(i)) + 1 >= cnt(mde(lm)) Then
If cnt(a(i)) = cnt(mde(lm)) Then
lm = 0
Else
lm = lm + 1
End If
mde(lm) = a(i)
End If
cnt(a(i)) = cnt(a(i)) + 1
Next i
[COLOR=#006400]' đến đây thì mde(0) --> mde(lm) là các trị xuất hiện nhiều nhất
[/COLOR]ans = ""
For i = 0 To lm
ans = ans & vbLf & "value: " & mde(i) & "; times: " & cnt(mde(i))
Next i
MsgBox ans
End SubLong Nguyen ahihi
Thành viên mới
- Tham gia
- 21/10/15
- Bài viết
- 1
- Được thích
- 0
tìm tần suất
var
a,b:array[1..1000000] of longint;
n,i,max: longint;
begin
read(n); // đọc vào số phần tử trong mảng
for i:=1 to n do read(a);
fillchar(b,sizeof(b),0); //tạo mảng b có toàn phần tử có giá trị bằng 0
for i:=1 to n do inc(b[a]);// đếm xem mỗi phần tử trong mảng a xuất hiện bao nhiêu lần
max:=0; // gán giá trị lớn nhất bằng 0 để so sánh
for i:=1 to n do
if b> max then max:=b; // tìm số lần xuất hiện nhiều nhất;
for i:=1 to n do
begin
if b= max then break;// tìm lại xem số xuất hiện nhiều nhất là bao nhiêu tìm được rồi thì dừng lại
end;
write(i,' ',max);
end.
với cách làm này thì ko thể chạy quá thời gian đối vs những test cỡ lớn đc ạ vì e học chuyên tin nên mấy bài này cũng làm rồi nên cũng khá chắc chắn.
var
a,b:array[1..1000000] of longint;
n,i,max: longint;
begin
read(n); // đọc vào số phần tử trong mảng
for i:=1 to n do read(a);
fillchar(b,sizeof(b),0); //tạo mảng b có toàn phần tử có giá trị bằng 0
for i:=1 to n do inc(b[a]);// đếm xem mỗi phần tử trong mảng a xuất hiện bao nhiêu lần
max:=0; // gán giá trị lớn nhất bằng 0 để so sánh
for i:=1 to n do
if b> max then max:=b; // tìm số lần xuất hiện nhiều nhất;
for i:=1 to n do
begin
if b= max then break;// tìm lại xem số xuất hiện nhiều nhất là bao nhiêu tìm được rồi thì dừng lại
end;
write(i,' ',max);
end.
với cách làm này thì ko thể chạy quá thời gian đối vs những test cỡ lớn đc ạ vì e học chuyên tin nên mấy bài này cũng làm rồi nên cũng khá chắc chắn.
Bài viết mới nhất
- Question
