Chuyen de lua bo vao chuong CO BAN
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (65.79 KB, 5 trang )
MỤC LỤC
Thuật tốn lùa bị, đếm phân phối...............................................................................................2
Dạng tốn cơ bản chỉ dùng khi giá trị con bò/phần tử dương..................................................2
Dạng tốn cơ bản chỉ dùng khi giá trị con bị/phần tử có cả âm và dương(nên áp dụng cách
này).......................................................................................................................................... 3
Thuật tốn lùa bị, đếm phân phối
Cac dang toan
/>Dạng tốn cơ bản chỉ dùng khi giá trị con bò/phần tử dương
///BÀI 17 ATUNG
TANSO.INP
8
4 3 7 18 3 4 4 1 4
TANSO.OUT
11
32
43
71
18 1
#include <bits/stdc++.h>
#define N 100
using namespace std;
int a[N+1];
int c[201];/// đây là chuồng tối đa để nhốt số mã bò.
int n;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("TANSO.INP","r",stdin);
freopen ("TANSO.OUT","w",stdout);
cin>>n;/// nhập số con bò
for(int i=1;i<=n;i++)
cin>>a[i]; /// nhập từng mã giống bò
for(int i= 1; i<=n; i++)
c[a[i]]++;/// mảng c sau khi đã tịnh tiến lên 100 đơn vị
for(int i=0;i<=100;i++)
{
if(c[i]>0)/// giá trị phần tử thứ i lớn hơn 0
cout<
return 0;
}
Lùa bò, lùa thỏ...lùa động vật hay đếm phân phối là thuật tốn đưa các con vật có giá trị phần
tử vào chuồng có mã số tương ứng với giá trị phần tử đó. Ví dụ mảng A 34 67 4 89. Đưa phần
tử a1(34) vào đúng chuồng có mã số thứ tự 34. (Chuồng được đánh số thứ tự từ 0 đến giá trị
lớn nhất của dãy A). Ví dụ mảng A trên có Max(89)=> sẽ đánh từ chuồng 0 đến chuồng 89.
Mảng khi dùng lùa bò/đếm phân phối không cần sắp xếp trước.
Xét mảng A(4.2.2.18.3.3.1.2)
i 0 1 2 3
A 4 2 2 1
8
4 5 6 7
3 3 1 2
Tạo mảng C(chuồng) được đánh số từ 0 đến 18. Mỗi phần tử trong mảng c đều có giá trị 0
i
0 1 2 3 4 5 6 7 8 9 1
0
C 0 0 0 0 0 0 0 0 0 0 0
11 1
2
0 0
1
3
0
1
4
0
1
5
0
1
6
0
1
7
0
1
8
0
Xét các phần tử trong mảng A từ phần từ đầu tiên đến phần tử cuối cùng
i
A[i]
0 A
0
1 A
1
2 A
2
3 A
3
4 A
4
5 A
5
6 A
6
7 A
7
C[i]
4
C4
Tăng giá trị số lượng bò trong từng
chuồng
0 C4+1=0+1=1
2
C2
0 C2=0+1=1
2
C2
1 C2=1+1=2
1
8
3
C1
8
C3
0 C18=c18+1=0+1=1
3
C3
1 C3=c3+1=1+1=2
1
C1
0 C1=0+1=1
2
C2
2 C2=2+1=3
0 C3=c3+1=0+1=1
Sau khi thực hiện từ A0-A7, ta có mảng C
i
0 1 2 3 4 5 6 7 8 9 1
0
C 0 1 3 2 1 0 0 0 0 0 0
11 1
2
0 0
1
3
0
1
4
0
1
5
0
1
6
0
1
7
0
18
1
Xét từ vị trí 1 đến 18(giá trị maxA)
Nếu chuồng nào có bị (c[i]>0) thì in giá trị i(giá trị của từng con bò) và c[i](số phần tử/số bị)
có trong chuồng.
Dạng toán cơ bản chỉ dùng khi giá trị con bị/phần tử có cả âm và dương(nên áp dụng
cách này)
Đối với thuật tốn trên chúng ta sẽ ln thực hiện đúng với giá trị >=0. Để có thể xử lý những
“con bị” có giá trị Âm=> chương trình trên sẽ khơng hiển thị ra những giá trị âm
Ví dụ
TANSO.INP
9
-40 200 -40 180 331 910 910 278 -40
TANSO.OUT
-40 3
180 1
200 1
278 1
331 1
910 2
Mảng chuồng được đánh lại như sau
i
40
C
..
.
0 1 2 3 4 5 6 7 8 9 1
0
0 1 3 2 1 0 0 0 0 0 0
11 1
2
0 0
1
3
0
1
4
0
1
5
0
1
6
0
1
7
0
..
.
91
0
1
Cải tiến chương trình
Thêm biến mina để tìm ra giá trị nhỏ nhất
(con bị có giá trị nhỏ nhất) để tạo ra chuồng
có giá trị âm như giá trị của bị đó
#include <bits/stdc++.h>
using namespace std;
int maxa,mina,i,n,a[100001],c[1001];///c
mảng mã số chuồng
int main()
{
freopen("TANSO.INP","r",stdin);
freopen("TANSO.OUT","w",stdout);
cin>>n;
for (i=0;i
maxa=a[0];mina=a[0];
for(i=1;i
if (a[i]>maxa)
maxa=a[i];
if (a[i]
}
for (i=mina;i<=maxa;i++)
c[i]=0;
///Dắt (lùa bò) vào chuồng
for(i=0;i
for (i=mina;i<=maxa;i++)
if(c[i]>0)
cout<
return 0;
}
