Các bài toán phân tích số

Cao Minh Anh

Trong quá trình học chắc các bạn sẽ gặp rất nhiều các bài toán về phân tích số. Các bài này có rất nhiều dạng khác nhau. Sau đây tôi xin đề cập đến một số bài toán để cùng trao đổi với các bạn.

Bài 1: Cho số nguyên dương M(M<=232),tìm cách phân tích M ra các số nguyên dương khác nhau có tổng bằng M sao cho tích của chúng là lớn nhất.

Mart.inp

M

Mart.out

a1 a2 a3 … ak

Ví dụ:

Mart.inp

11

Mart.out

2 4 5

Với bài toán trên thì có nhiều cách giải khác nhau,sau đây tôi xin trình bày với các bạn một thuật toán để giải bài này có tính mô phỏng. Đó là “thuật toán rải đậu”.

Sau đây tôi xin trình bầy tư tưởng thuật toán như sau:

Thuật toán:

+Xây dựng mảng a với a[1]=2;

a[I]=a[I-1]+1;(I>=2)

Tìm k lớn nhất sau cho a[1]+a[2]+..+a[k]<=M;

+ Xét d:=M-(a[1]+a[2]+..+a[k]);

+ Bây giờ ta tưởng tượng ta đang có d hạt đậu, chúng ta bắt đầu rải từng hạt đậu vào các a[I](1<=I<=k) theo chiều từ k1. Nếu rải đến 1 mà vẫn còn thì ta vẫn rải lại bắt đầu từ k lại,cứ như thế cho đến khi không còn hạt đậu nào. Khi rải đậu đến ô nào thì tăng giá trị của ô đó lên.

Sau đó xuất mảng a[i] ra là giải quyết xong bài toán.

Xong trên chỉ là tư tưởng của thuật toán trên, nếu làm theo cách đó thì ta sẽ tốn nhiều thời gian và dữ liệu. Sau đây tôi xin giới thiệu một cách cài đặt giúp tăng thời gian và giảm dử liệu:

Ở bước một ta tìm K lớn nhất cho a[1]+a[2]+..+a[k]<=M

+ Giải phương trình:2+3+4+..+(k-1)<=M

<-> k(k-1)/2 <=M-1.

Giải phương trình trên tìm nghiệm k nguyên trong khoảng nghiệm là được.

Bước hai: Thay vì mỗi lần ta rãi 1 hạt, mà ta rải (d div k) hạt đậu từ a[k]àa[1] (Với d là số hạt đậu còn lại, k là số ô để ta bỏ đậu vào), sau đó sẽ còn dư (d mod k) ta lại rải lại từ cuối đến đầu. Như vậy chỉ mất 2 lần

rải.

Một điểm nữa là kết quả xuất ra là một dãy liên tiếp đức đoạn, có nghĩa là nó mất một số trên đoạn tăng đó.

Ví dụ: 22 à 2 3 4 6 7 (Mất 5)

40 à 2 3 5 6 7 8 9 (Mất 4)

Như vậy ta cũng không cần mảng để lưu nữa, ta sẽ tính xem những số từ đâu đến đâu tăng M div n,những số từ đâu đến đâu tăng (M div n) + 1.

Sau đây là bài giải hoàn chỉnh:

uses crt;

const fi='RAIDAU.inp';

go='RAIDAU.out';

var m,r,sp,cs,k,du,delta :longint;

k1,k2 :real;

f,g :text;

procedure openf;

begin

assign(f,fi);

reset(f);

assign(g,go);

rewrite(g);

end;

procedure closef;

begin

close(f);

close(g);

end;

procedure Init;

begin

readln(f,m);

end;

procedure Timk;

begin

delta:=1+8*(M+1);

k1:=((-1)-sqrt(delta))/2;

k2:=((-1)+sqrt(delta))/2;

k:=trunc(k2);

du:=M+1-(k*(k+1) div 2);

end;

procedure Print;

var i:longint;

begin

k:=k-1;

cs:=du div k;

sp:=du mod k;

r:=2;

for i:=1 to k-sp do

begin

write(g,r+cs,' ');

r:=r+1;

if i mod 100=0 then writeln(g);

end;

for i:=k-sp+1 to k do

begin

write(g,r+cs+1,' ');

r:=r+1;

if i mod 100=0 then writeln(g);

end;

end;

Begin

Openf;

Init;

Timk;

Print;

Closef;

End.

Với cách làm trên ta có thể xử lý rất nhanh,vừa đỡ dữ liệu.Sau đây là một bài khác.

Bài 2: Phân tích số đòi hỏi đưa ra tất cả các cách có thể có.

+Với những bài như trên thì dữ liệu vào sẽ nhỏ,và phương pháp đơn giản nhất là duyệt.

Ví dụ: Cho một số n.Hãy đưa ra tất cả các cách phân tích n ra các số nguyên tố có thể giống nhau sao cho tổng của chúng bằng n.

Với n=11

Có 6 cách la:

2 2 2 2 3

2 2 2 5

2 2 7

2 3 3 3

3 3 5

11

function Nto(n:longint):boolean;

var i:integer;

begin

Nto:=false;

For i:=2 to round(sqrt(n)) do

If n mod i=0 then exit;

Nto:=true;

End;

Procedure Print;

Var i:integer;

Begin

For i:=1 to dem do write(g,a[i]:4);

Writeln(g);

End;

Procedure Phantich(n,k,d:integer);

Begin

A[d]:=k;

If n=0 then

Begin

Dem:=d;

Print;

End

Else

Begin

For i:=k to n do

If nto(i) then phantich(n-i,i,d+1);

N:=n+k;

End;

End;

Từ bài trên có thể chuyển qua rất nhiều bài như sau:

+Phân tích n ra các số nguyên tố khác nhau.

Chỉ cần sửa một chút là:

Begin

For i:=k+1 to n do

If nto(i) then phantich(n-i,i,d+1);

N:=n+k;

End;

+Nếu bài toán là phân tích ra các số có thể giống nhau thì ta sửa như sau:

Begin

For i:=k to n do phantich(n-i,i,d+1);

N:=n+k;

End;

Còn nếu phân tích ra các số khác nhau để tổng bằng n thì sửa như sau:

Begin

For i:=k+1 to n do phantich(n-i,i,d+1);

N:=n+k;

End;

Với những bài phân tích ra tất cả các cách thì rất đơn giản.Nhưng với các bài toán chỉ yêu cầu đưa ra số cách có thể với n lớn mà đệ quy như trên không thể làm được thì rất khó.Với những bài như thế thì làm bằng phương pháp Quy Hoạch Động rất đơn giản và nhanh chóng.

Bài 3:

+Dạng 1:Các số hạng có thể giống nhau.

Bài toán: Cho một số n<=2000 hãy tìm số cách phân tích n thành các số nguyên tố có thể giống nhau sau cho tổng của chúng bằng n.

Phantich.inp phantich.out

N S(Số cách)

Ví dụ;

N=11 ---------à S=6.

Phương pháp :

F[n]=Tổng các F[n-p] với p:là số nguyên tố.Và F[n-p] là số cách phân tích n ra các số nguyên tố nhỏ hơn hoặc bằng p.

Khởi tạo: Fx[i]=1 nếu i là số nguyên tố.

Khi xét các số nguyên tố p từ 2..n thì ta luôn có:

Fx[j]:=Fx[j]+Fx[j-p];

for i:=2 to n do

if nto(i) then

begin

Fx[i]:=Fx[i]+1;

for j:=i+2 to n do

Fx[j]:=Fx[j]+Fx[j-i];

end;

Đây là chương trình chính:

uses crt;

const fi='Prime.inp';

go='Prime.out';

type arr=array[1..50] of byte;

var n,k,dem :longint;

Fx :array[0..2000] of ^arr;

Donvi :arr;

p :pointer;

f,g :text;

procedure Openf;

begin

assign(f,fi);

reset(f);

assign(g,go);

rewrite(g);

end;

procedure Closef;

begin

close(f);

close(g);

end;

procedure Input;

begin

readln(f,n);

donvi[1]:=1;

end;

function nto(p:longint):boolean;

var k:longint;

begin

Nto:=false;

for k:=2 to round(sqrt(p)) do

if p mod k=0 then exit;

Nto:=true;

end;

procedure Print;

var i:integer;

begin

for i:=k downto 1 do write(g,fx[n]^[i]);

end;

procedure Cong(a,b:arr;var c:arr);

var i,du :integer;

begin

i:=0;

du:=0;

while i<>

begin

inc(i);

c[i] :=(a[i]+b[i]+du) mod 10;

du :=(a[i]+b[i]+du) div 10;

end;

if du<>0 then

begin

i:=i+1;

c[i]:=du;

end;

k:=i;

end;

Procedure Main;

var i,j:integer;

begin

k:=1;

for i:=1 to n do

begin

New(Fx[i]);

fillchar(fx[i]^,sizeof(fx[i]^),0);

end;

for i:=2 to n do

if nto(i) then

begin

Cong(Fx[i]^,donvi,Fx[i]^);

for j:=i+2 to n do

Cong(Fx[j]^,Fx[j-i]^,Fx[j]^);

end;

end;

begin

clrscr;

Mark(p);

openf;

Input;

Main;

Print;

release(p);

Closef;

end.

+ Bài trên còn có thể áp dụng với phân tích n ra các số không cần nguyên tố có thể giống nhau sao cho tổng các số bằng n.Yêu cầu đưa ra số cách.

Chỉ sửa lại một chút như sau;

Procedure Main;

var i,j:integer;

begin

for i:=1 to n do

begin

Fx[i]:=Fx[i]+1;

for j:=i+1 to n do

Fx[j]:=Fx[j]+Fx[j-i];

end;

end;

+Dạng 2: Với lớp bài toán phân tích n ra các số (hay nguyên tố) có thể giống nhau nhưng khác bài trên là:

Ví dụ: Với n=4 có 8 cách

1 1 1 1

1 1 2

1 2 1

2 1 1

1 3

3 1

2 2

4

+Được gọi là một cách phân tích nếu khi sắp các số này lại xít nhau thì tạo thành những số khác nhau:

Ví dụ:

Giả sử n=3

Thì 1 2 và 2 1 là hai cách khác nhau

Nên phân tích 4 sẽ có những cách sau:

1 2

2 1

3

1 1 1

Có thể thấy bài này trên đề ra kỳ này số tháng 8-2004.Bài Bộ Cờ.(Nhưng cách diễn đạt khác nhau).

Bài này dễ vì giả sử được một cách nhưng khi hoán vị cách này lên thì 0 khác với cách ban đầu thì vẫn tính thêm một cách.

Gọi Fx[i] là số cách tạo thành i;

Khởi tạo:Fx[i]=1 với 1<=i<=n.

Vì lặp lại vẫn được nên ta có công thức sau:

For h:=1 to n-i do

Fx[i+h]:=Fx[i+h]+Fx[i];

Tổng quan như sau:

For i:=1 to n do fx[i]:=1;

For i:=1 to n do

Begin

For h:=1 to n-i do Fx[i+h]:=Fx[i+h]+fx[i];

End;

Chỉ chạy h đến n-i để khỏi phải tính những cách tạo thành số lớn hơn n.

Đây là chương trình chính:

uses crt;

const fi='Prime.inp';

go='Prime.out';

type arr=array[1..200] of byte;

var n,k,dem :longint;

Fx :array[0..1000] of ^arr;

p :pointer;

f,g :text;

procedure Openf;

begin

assign(f,fi);

reset(f);

assign(g,go);

rewrite(g);

end;

procedure Closef;

begin

close(f);

close(g);

end;

procedure Input;

begin

readln(f,n);

end;

function nto(p:longint):boolean;

var k:longint;

begin

Nto:=false;

for k:=2 to round(sqrt(p)) do

if p mod k=0 then exit;

Nto:=true;

end;

procedure Cong(a,b:arr;var c:arr);

var i,du :integer;

begin

i:=0;

du:=0;

while i<>

begin

inc(i);

c[i] :=(a[i]+b[i]+du) mod 10;

du :=(a[i]+b[i]+du) div 10;

end;

if du<>0 then

begin

i:=i+1;

c[i]:=du;

end;

k:=i;

end;

procedure Print;

var i:integer;

begin

for i:=k downto 1 do write(g,Fx[n]^[i]);

end;

Procedure Main;

var i,h:integer;

begin

k:=1;

for i:=1 to n do

begin

New(Fx[i]);

fillchar(fx[i]^,sizeof(fx[i]^),0);

Fx[i]^[1]:=1;

end;

for i:=1 to n do

begin

for h:=1 to n-i do

Cong(Fx[i+h]^,Fx[i]^,Fx[i+h]^);

end;

end;

begin

clrscr;

Mark(p);

openf;

Input;

Main;

Print;

release(p);

Closef;

end.

+Với bài như trên nhưng phân tích n ra các số nguyên tố.

Ví dụ:Với n=7 có 6 cách hết.

2 2 3

2 3 2

3 2 2

2 5

5 2

7

Bài này chỉ sửa một chút thôi:

uses crt;

const fi='Prime.inp';

go='Prime.out';

var n,k,dem :longint;

Fx :array[0..1000] of longint;

f,g :text;

procedure Openf;

begin

assign(f,fi);

reset(f);

assign(g,go);

rewrite(g);

end;

procedure Closef;

begin

close(f);

close(g);

end;

procedure Input;

begin

readln(f,n);

end;

function nto(p:longint):boolean;

var k:longint;

begin

Nto:=false;

for k:=2 to round(sqrt(p)) do

if p mod k=0 then exit;

Nto:=true;

end;

procedure Print;

var i:integer;

begin

writeln(g,Fx[n]);

end;

Procedure Main;

var i,h:integer;

begin

for i:=2 to n do if nto(i) then Fx[i]:=1;

for i:=2 to n do

if Fx[i]<>0 then

begin

for h:=2 to n-i do

if nto(h) then Fx[i+h]:=Fx[i+h]+Fx[i];

end;

end;

begin

clrscr;

openf;

Input;

Main;

Print;

Closef;

end.

Bài này các bạn chỉ cần làm thêm chương trình cộng sô lớn là xong.Tuy nhiên vẫn còn 1 dạng nữa mình vẫn chưa làm được đó là:Tính số cách phân tích số n ra các số (hay nguyên tố ) khác nhau.

Ví dụ:

N=5 có 3 cách là:

1 4

2 3

5