Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

SINH DỮ LIỆU VÀO VÀ RA

No description
by

Dế Mèn

on 15 March 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of SINH DỮ LIỆU VÀO VÀ RA

Chương 2:

SINH DỮ LIỆU VÀO VÀ RA

Mở đầu
Hầu hết các bài toán tin đều đòi hỏi
dữ liệu vào và ra.
Bài 2.1. Sinh ngẫu nhiên theo khoảng
Sinh ngẫu nhiên cho mảng nguyên a, n phần tử trong khoảng -M..M; M > 0.
(*-----------------------------------------
Sinh ngau nhien n so nguyen trong khoang
d den c va ghi vao mang a
----------------------------------------- *)
Procedure
Gen(n,d,c: integer);
var i,len: integer;
begin
randomize;
len := c-d+1;
for i:=1 to n do a[i]:= d+random(len);
end;

Bài 2.2. Sinh ngẫu nhiên tăng
Sinh ngẫu nhiên n phần tử được sắp không giảm cho mảng nguyên a.
Bài 2.3. Sinh hoán vị ngẫu nhiên
Sinh ngẫu nhiên cho mảng nguyên a một hoán vị của 1..n.

Ba phương thức sinh và nạp dữ liệu sau:
1. Nạp dữ liệu trực tiếp từ bàn phím.
Phương thức này được dùng
khi dữ liệu không nhiều.
Phương thức này dùng khi nào?
2. Sinh dữ liệu nhờ hàm random
Lợi ích:
Phương thức này
nhanh chóng và tiện lợi
, nếu khéo tổ chức có thể sinh ngẫu nhiên được các dữ liệu đáp ứng được một số điều kiện định trước.

Random(N);
{ kết quả sẽ trả về là 1 số nguyên trong đoạn từ [0..N-1] }.
3. Đọc dữ liệu từ một tệp, thường là tệp văn bản.
Phương thức này:
khá tiện lợi
khi phải chuẩn bị trước những tệp dữ liệu phức tạp.
Kết quả thực hiện chương trình
: thông báo trực tiếp trên màn hình hoặc ghi vào một tệp văn bản.
Đặc tả:
Ta viết thủ tục tổng quát
Gen(n,d,c)
- sinh ngẫu nhiên
n số nguyên
trong khoảng từ
d đến c (d < c)
.
Để giải bài 2.1 ta chỉ cần gọi
Gen(n,-M,M)
.

random(n+1)

biến thiên trong khoảng từ

0 đến n

random(c–d+1)
biến thiên trong khoảng từ
0 đến c-d

do đó

d+random(c–d+1)
sẽ biến thiên trong khoảng từ d đến
d+c-d = c
.
Xuất phát từ hoán vị đơn vị a = (1, 2,..., n) ta đổi chỗ a[1] với một phần tử tuỳ ý (được chọn ngẫu nhiên) a[j] sẽ được một hoán vị. Ta có thể thực hiện việc đổi chỗ nhiều lần.
(* Pascal *)
(*-----------------------------------------
Sinh ngau nhien cho mang nguyen a
mot hoan vi cua 1..n
------------------------------------------*)
program GenPer;
const MN = 1000; { so luong toi da }
Esc = #27; { dau thoat }
BL = #32; { dau cach }
var a: array[1..MN] of integer;
(*-----------------------
Sinh du lieu
-----------------------*)
procedure Gen(n: integer);
var i,j,x: integer;
begin
{ Khoi tao hoan vi don vi }
for i:= 1 to n do a[i]:= i;
for i:= 1 to n do
begin
j := random(n)+1;
x := a[1]; a[1] := a[j]; a[j] := x;
end;
end;
procedure Xem(n: integer); tự viết
procedure Test;
var n: integer;
begin
randomize;
repeat {chon ngau nhien kich thuoc n = 10..39}
n := random(30)+10; Gen(n); Xem(n);
until ReadKey = Esc; { Nhan ESC de thoat }
end;
BEGIN
Test;
END.
Bài 2.4. Sinh ngẫu nhiên đều
Sinh ngẫu nhiên
n phần tử
cho mảng nguyên a
thoả điều kiện
n phần tử tạo thành k đoạn liên tiếp

tổng
các phần tử trong
mỗi đoạn bằng nhau

bằng giá trị t
cho trước.

Thuật toán
1. Chọn số lượng các phần tử trong mỗi đoạn là random(n div k) + 1, khi đó số lượng các phần tử được phát sinh ngẫu nhiên sẽ không vượt quá
k*(n div k) ≤ n
Sau đó ta sẽ chỉnh sao cho số lượng các phần tử đúng bằng n.
2. Giả sử a[d..c] là đoạn thứ j cần được sinh ngẫu nhiên sao cho
a[d] + a[d + 1] + ... + a[c] = t
Ta sinh đoạn này như sau:
2.1. Gán tr := t; { tr - giá trị còn lại của tổng }.
2.2. Gán trị ngẫu nhiên 0..tr-1 cho các phần tử a[d..(c - 1)]
(i = d..c ): a[i] := random(tr)
2.3. Đồng thời chỉnh giá trị còn lại của tr:
tr := tr - a[i]
Ta có:
a[d] < t
a[d+1] < t - a[d]
a[d+2] < t - a[d+1] - a[d]
...
a[c - 1] < t - a[d] - a[d + 1] - ... - a[c - 2]
Chuyển vế các phần tử a[*] trong biểu thức cuối cùng, ta thu được
a[d] + a[d + 1] + ... + a[c – 1] < t
2.4. Ta đặt giá trị còn lại của tổng riêng vào phần tử cuối đoạn: a[c] := tr sẽ thu được a[d] + a[d + 1] + ... + a[c] = t.

Bài 2.5 Sinh ngẫu nhiên tệp tăng:
Sinh ngẫu nhiên n số tự nhiên sắp tăng và ghi vào một tệp văn bản có tên cho trước.
Bài 2.6: Đếm tàu
Một tệp văn bản có tên fn có ghi sơ đồ một vùng biển hình chữ nhật chiều ngang 250 kí tự, chiều dọc (số dòng) không hạn chế. Trên biển có các con tàu hình chữ nhật chứa các kí tự 1, vùng nước được biểu thị qua các kí tự 0. Biết rằng các con tàu không dính nhau. Hãy đếm số lượng tàu.
Ví dụ, hình bên có 5 tàu
1 1 1 1 0 0 1 1 1
0 0 0 0 0 0 1 1 1
1 1 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0 1
5 tàu
Full transcript