Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Phân tích thành một dãy liên tiếp   Thu 18 Mar 2010, 13:18

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.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Phân tích thành một dãy liên tiếp   Thu 18 Mar 2010, 18:41

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.
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Phân tích thành một dãy liên tiếp   Thu 18 Mar 2010, 21:34

[You must be registered and logged in to see this link.] prp thật. Cho tràng vỗ tay nào.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Phân tích thành một dãy liên tiếp   Fri 19 Mar 2010, 14:12

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.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Phân tích thành một dãy liên tiếp   Fri 19 Mar 2010, 14:19

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.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Phân tích thành một dãy liên tiếp   Sun 21 Mar 2010, 15:32

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.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Phân tích thành một dãy liên tiếp   Sun 21 Mar 2010, 18:23

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. ^^
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Phân tích thành một dãy liên tiếp   Today at 18:54

Về Đầu Trang Go down
 
Phân tích thành một dãy liên tiếp
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến