Phân tích thành một dãy liên tiếp

Cho một số, hãy phân tích số vừa cho thành một tổng của nhiều số tự nhiene liên tiếp. Hãy cho biết với số vừa cho, có thể phân tích như trên được không, nếu được thì hãy phân tích ra tất cả các trường hợp khác nhau.

Ví dụ với 8 thì thông báo là không thể. Với 9 thì thông báo có hai cách là 9=4+5 và 9=2+3+4.

k:=trunc(sqrt(n*2))+1
j:=1;
for i:=2 to k do
begin
j:=j+i;
if j>n then break;
if (n-j) mod i =0 then
write('có thể phân tích thành tổng các số bắt đầu từ ', (n-j) div i +1, ' đến ',(n-j) div i +i);
end;

Đoạn code này liệt kê tất cả các cách phân tích có thể được.
N có thể đạt giá trị 10^16 (mười triệu tỷ) mà chương trình vẫn chạy không quá nửa giây.

administrators đã viết:

k:=trunc(sqrt(n*2))+1
j:=1;
for i:=2 to k do
begin
j:=j+i;
if j>n then break;
if (n-j) mod i =0 then
write('có thể phân tích thành tổng các số bắt đầu từ ', (n-j) div i +1, ' đến ',(n-j) div i +i);
end;

Đoạn code này liệt kê tất cả các cách phân tích có thể được.
N có thể đạt giá trị 10^16 (mười triệu tỷ) mà chương trình vẫn chạy không quá nửa giây.

Thuật toán của ad (tên mới nhé, gọi cho nhanh) hay thật. Phải mất một lát mới hiểu ^^.

Tuy nhiên ta có thể lấy k=trunc(sqrt(n*2)) thôi, ko cần cộng 1 đâu. vì nếu coi m là số mà có tổng 1+...+m lớn hơn hoặc bằng n thì ta sẽ có m>sqrt(n*2)-1 . Vì vậy ta lấy m=sqrt(n*2) là vừa đủ.

Mình hồi trước ko làm thế này, làm dài hơn tuy nhiên chạy cũng khá nhanh đối với n=10^16 chẳng hạn. Nếu cách của ad chạy với 0.5 giây cho 10^16 thì cách mình làm bình thường khoảng 2 giây. Cách tính k thì cũng tương tự, cũng suy từ công thức toán học ra.

Bài cụ thẻ theo cách của ad:

Code:

uses crt;
var n,j:longint; i,k,dem:integer;
begin
 clrscr;
 write('nhap so n: ');readln(n);
 k:=trunc(sqrt(n*2));
 j:=1;
 for i:=2 to k do
  begin
  j:=j+i;
  if j>n then break;
  if (n-j) mod i=0 then
    begin
    inc(dem);
    writeln('phan tich tu ',(n-j) div i +1,' den ',(n-j) div i+i);
    end;
  end;
 writeln('co tat ca ',dem,' cach phan tich.');
readln;
end.

Bạn littlelee rất nhạy cảm với toán học. Bạn xuất thân từ chuyên toán à. Vì đoạn mã lệnh trên hàm chứa rất nhiều thứ trong ấy mà bạn vẫn nhìn ra được. Đúng là tuổi trẻ tài cao. Mình đoán là bạn sẽ vô địch về giải thuật lập trình khi bạn ở độ tuổi 18.

administrators đã viết:

Bạn littlelee rất nhạy cảm với toán học. Bạn xuất thân từ chuyên toán à. Vì đoạn mã lệnh trên hàm chứa rất nhiều thứ trong ấy mà bạn vẫn nhìn ra được. Đúng là tuổi trẻ tài cao. Mình đoán là bạn sẽ vô địch về giải thuật lập trình khi bạn ở độ tuổi 18.

Ad quá khen rồi ^^. Đúng là littlelee xuất thân từ toán thật. Thật ra môn toán mới là môn chính của mình, tuy nhiên môn tin là môn rất yêu thích của mình. ^^