//
you're reading...
Bài tập huấn luyện, Chủ đề Toán học và Tin học

Chia mảng tỉ lệ 1:1


Đề bài


Tìm cách chia dãy số nguyên không âm a1, a2,…,an, n > 1 cho trước thành hai
đoạn có tổng các phần tử trong mỗi đoạn bằng nhau.

Đặc tả

Ta quy ước viết #E là “tồn tại” và #V là “với mọi“. Kí hiệu sum(a[d..c]) là tổng các phần tử liên tiếp nhau từ a[d] đến a[c] của dãy a: sum(a[d..c]) = a[d] + a[d +1]+ … + a[c].
Gọi
t là tổng các phần tử của mảng: t = sum(a[1..n]). Muốn chia a thành hai đoạn a[1..i] và a[i+1..n] có tổng bằng nhau ta phải có:
1.
t là số chẵn (t chia hết cho 2). Đặt t2 = t div 2.
2. (#E
i: 1 <= i <= n): sum(a[1..i]) = t2.

Chương trình


Hàm Chia cho giá trị i nếu mảng a chia được thành a[1..i] a[i+1..n].
Trong trường hợp vô nghiệm
Chia = -1. Ta gọi i là điểm chia và dùng biến tr (tổng riêng) để tích luỹ tổng các phần tử của đoạn đang xét a[1..i]. Khi tr = t2 bài toán có nghiệm i. Ngược lại, khi tr > t2 bài toán vô nghiệm.
Ta khởi trị ngẫu nhiên cho mảng
a. Tuy nhiên ta muốn số lần có nghiệm (mảng a chia được thành hai phần có tổng bằng nhau) xấp xỉ bằng số lần vô nghiệm. Ta sẽ thực hiện mục tiêu đề ra như sau:
Mỗi lần khởi trị ta tung đồng xu hai mặt. Nếu gặp mặt sấp (
random(2)=0), ta sẽ khởi trị tùy ý cho mảng a, ngược lại, nếu gặp mặt ngửa (random(2)=1) ta khởi trị a là mảng có nghiệm.
Để khởi trị sao cho mảng
a có nghiệm ta lại chọn ngẫu nhiên một điểm cắt d trong khoảng 1..(n/2). Sau đó ta khởi trị ngẫu nhiên cho các phần tử a[1..d]. Với các phần tử còn lại ta cũng khởi trị ngẫu nhiên trong khoảng hợp lí sao cho tổng các giá trị của chúng đúng bằng tổng t của đoạn a[1..d]. Bạn đọc xem chi tiết thủ tục Gentrong chương trình.

(* Pascal *)
(*—————————————–
Chia mang nguyen a thanh 2 doan
co tong bang nhau
——————————————- *)
program ChiaTiLe11;
{$B-}
uses crt;
const MN = 500; Esc = #27;
var a: array [1..MN] of integer;
n: integer;
(*——————————————-
Sinh ngau nhien n so nguyen khong am
cho mang a
——————————————- *)
procedure Gen(m: integer);
var i,d,t: integer;
begin
randomize; n := m;
if random(2)=0 then
begin {khoi tri tuy y}
for i := 1 to n do a[i]:=random(m);
exit;
end;
{ Khoi tri mang co tong d phan tu dau
bang tong cac phan tu con lai }
d := random(n div 2)+ 1; { diem chia }
t := 0;
for i := 1 to d do
begin
a[i] := random(n);
t := t + a[i];
end; { t = sum(a[1..d]) }
for i := d+1 to n-1 do
begin { sum(a[d+1..i]) + t = sum(a[1..d]) }
a[i] := random(t);
t := t-a[i];
end;
a[n] := t; { sum(a[1..d]) = sum(a[d+1..n]) }
end;
procedure Xem: Hiển thị mảng a, tự viết
function Chia: integer;
var i, t, t2, tr: integer;
begin
Chia := -1; t := 0;
for i:=1 to n do t:=t+a[i]; {t=sum(a[1..n]}
if Odd(t) then exit; { vo nghiem }
t2 := t div 2; tr := 0;
for i:=1 to n do
begin

tr := tr + a[i];
if tr > t2 then exit; {vo nghiem }
if tr = t2 then { co nghiem i }
begin Chia:= i; exit; end;
end;
end;
procedure Test;
var i: integer;
begin
repeat
Gen(10); Xem; i := Chia;
if i = -1 then writeln(‘Khong chia duoc’)
else
begin
writeln(‘Doan thu nhat: a[1..’,i,’]’);
writeln(‘Doan thu hai: a[‘,i+1,’..’,n,’]’);
end;
until ReadKey=Esc;
end;
BEGIN
Test;
END.
Chú ý
1. Muốn dừng chương trình hãy nhấn phím Esc có mã ASCII là #27.
2. Nếu mảng a có chứa một số giá trị 0 thì bài toán có thể có nhiều nghiệm
(nhiều cách chia).
// C#
using System;
namespace SangTao1
{
class ChiaMangTiLe1_1
{
static void Main()
{
do {
Run(20);
Console.Write(“\n Bam phim ENTER “ +
“de tiep tuc, “);
Console.Write(“\n Bam phim T de thoat: “);
} while (Console.ReadLine() == “”);
}
static public void Run(int n)
{ int[] a = new int[n];
Gen(a, n); // sinh ngau nhien 1 test
Print(a, n);
int t = 0, d = Chia(a, n, ref t);
if (d < 0)
Console.WriteLine(“\n Khong chia duoc”);
else if (KiemTra(a, n, d))
{ Console.WriteLine(“\n Doan thu nhat: 1..{0} “,d);
Console.WriteLine(“\n Doan thu hai: {0}..{1} “,

Sáng tạo trong Thuật toán và Lập trình Tập I 20
d+1, n);
Console.WriteLine(“\n Tong moi doan: ” + t);
}
else Console.WriteLine(“\n Loi giai sai!”);
} // end Run
// Kiem tra sum(a[1..d] == sum(a[d+1..n]) ?
static public bool KiemTra(int[] a, int n, int d)
{ if (d < 0 || d >= n) return false;
int t = 0;
for (int i = 0; i < d; ++i) t += a[i];
for (int i = d; i < n; ++i) t -= a[i];
return (t == 0) ? true : false;
}
static public int Chia(int[] a, int n, ref int t)
{ int sum = 0; // sum = tong(a[1..n])
for (int i = 0; i < n; ++i) sum += a[i];
if (sum % 2 != 0) return -1;
t = sum / 2; // tong moi doan
int tr = 0; // tong rieng
// doan 1: tr = sum a[1..i]
for (int i = 0; i < n; ++i)
{ tr += a[i];
if (tr == t) return i+1;
}
return -1;
}
// sinh ngau nhien n so ghi vao mang a
static public void Gen(int[] a, int n)
{
Random r = new Random();
if (r.Next(2) == 0)
{ // 1/2 so test la vo nghiem
for (int i = 0; i < n; ++i) a[i]=r.Next(n);
return;
}
// sinh mang a: sum(a[0..d-1])=sum(a[d..n-1])
int d = r.Next(n / 2) + 1; // diem chia
int t = 0;
// sinh doan a[0..d-1]
for (int i = 0; i < d; ++i)
{ a[i] = r.Next(n); t += a[i]; }
// sinh tiep doan a[d..n-1]
int n1 = n-1;
for (int i = d; i < n1; ++i)
{ a[i] = r.Next(t); t -= a[i]; }
a[n-1] = t; // phan tu cuoi
}
static public void Print(int[] a, int n): tự viết
} // SoCapNhan
} // SangTao1

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: