Tin học trẻ

Cho một số nguyên n (1<= N<=10[SUP]5[/SUP]). Hãy viết chương trình pascal có tên Bai2.pas tìm các số m (1<= m <= N) sao cho thỏa mãn điều kiện: Dãy số tự nhiên từ 1 đến m được chia thành hai đoạn có tổng các phần tử trong mỗi đoạn bằng nhau.
Dữ liệu: Vào từ file văn bản TIMSO.INP chứa số n
Kết quả: Ghi ra file văn bản TIMSO.OUT:
- Các số m mỗi số cách nhau một dấu trống (nếu tìm được)
- Ghi vào là -1 nếu không tìm được số m
Ví dụ:
TIMSO.INP
TIMSO.OUT
TIMSO.INP
TIMSO.OUT
50
3 20
200
3 20 119
 
T

tengiday

Happy life
Vì đề ko nói rõ 2 đoạn con là thế nào, liên tục hay sao, nên mình assume rằng sum(1..i) = sum(i..k) cho đoạn [1..k]. Như thế, bài này bạn có thể làm như vầy:
- Tạo 1 integral array S với S := S[i - 1] + i;
- Tại mỗi giá trị i thì tìm xem trong mảng S, đoạn 1..i có số S / 2 hay không. Vì mảng S tăng dần nên ta có thể dùng binary search.
Độ phức tạp của thuật toán O(n log n).
- Cheating: Sau khi bạn chạy hết tới 10^5 thì bạn lưu kết quả dưới dạng const array (mảng hằng). Khi nhập n thì tùy theo mà xuất giá trị cho phù hợp. Mình đảm bảo kết quả ko quá nhiều để lưu trữ bằng tay đc. :p

Good luck.
 
T

tuonglong

có nghĩa mình sử dụng một mảng cộng dồn các giá trị lại
s[0]:=0;
for i:= 1 to n do
s:= s[i-1]+i;
xong cái này mình tiến hành tìm hả bạn. Nhưng tại sao pải chia cho 2 vì mảng này miễn sao có hai đoạn là được đâu nhất thiết làm số lượng phần tử bằng nhau
 
T

tengiday

Happy life
tuonglong:
có nghĩa mình sử dụng một mảng cộng dồn các giá trị lại
s[0]:=0;
for i:= 1 to n do
s:= s[i-1]+i;
xong cái này mình tiến hành tìm hả bạn. Nhưng tại sao pải chia cho 2 vì mảng này miễn sao có hai đoạn là được đâu nhất thiết làm số lượng phần tử bằng nhau
Nhấn để mở rộng...

S = 1 + ... + i
Chúng ta cần tìm thằng j sao cho S[j] = S / 2.
Ví dụ: m = 3 thì 1 + 2 + 3 = 6. Sau đó 6/2 = 3 thì 2 đoạn có tổng bằng nhau là 1+2 và 3. Chúng ta cần tìm con số 3 này đã có trong mảng S chưa.

PS: Một kiến nghị nhỏ cũng khá hay là bạn có thể dùng giải pt bậc 2 để tìm số j.
Tổng các số từ 1 tới n đc cho bởi S = n(n+1)/2. Nếu biết S, ta có thể giải pt tìm n. :) Nếu làm cách này thì độ phức tạp sẽ còn O(n), nhưng nó vẫn ko nhanh bằng kiểu dùng mảng hằng, O(1) thôi.
 
T

tuonglong

cách tính thằng s của mình như thế là đk chưa hả bạn..tại nếu theo cái mình ghi thì số 20sex ko có trong mảng
còn tính thằng s[j] tính như thế nào vậy bạn.
nhờ bạn code đoạn xử lí cái ý tưởng của bạn với ak,chứ dốt quá bạn ơi..
 
T

tengiday

Happy life
Code đại khái như sau:
[ah]
Mã: 
procedure timso(n : longint);
var i, left, right, mid, target : longint;
    s : array[0..100000] of longint;
begin
    if (n < 3) then
        begin
            write(-1);
            exit;
        end;
    s[0] := 0;
    for i := 1 to n do
        begin
            s[i] := s[i - 1] + i;
            if ((s[i] and 1) = 0) then
                begin
                    target := s[i] shr 1;
                    left := 1;
                    right := i;
                    while (left <= right) do
                        begin
                            mid := left + ((right - left) shr 1);
                            if (s[mid] = target) then
                                begin
                                    write(i,' ');
                                    break;
                                end;
                            if (s[mid] < target) then
                                left := mid + 1
                            else
                                right := mid - 1;
                        end;
                end;
        end;
end;
[/ah]
Bạn chạy tới 10^5 sẽ thấy chỉ có mấy số sau:
Mã: 
3 20 119 696 4059 23660 93243 96532 98312
Bạn có thể lưu trc kết quả ở const arr rồi output tùy theo n thôi. :)
 
T

tuonglong

chết rồi,cách xử lí theo bit mình chưa từng tìm hiểu...mấy chỗ shr 1 có thể thay đổi bằng cách khác ko bạn
 
T

tengiday

Happy life
- Bạn thay 'shr 1' bằng 'div 2' là xong. Vì 'div' tốn tài nguyên tính toán hơn là di chuyển bit nên mình mới dùng xử lý bit. Trong máy tính, khi bạn di chuyển sang bên phải 1 bit thì tương ứng với chia 2; tương tự khi di chuyển sang bên trái 1 bit thì tương ứng với nhân 2.
- Cái này nó tương tự như hệ cơ số 10 của chúng ta vậy. Di chuyển sang phải 1 số hay sang trái 1 số là chia và nhân lần lượt cho 10.
 
T

tuonglong

Chỗ này nữa bạn ơi if ((s and 1) = 0) then.nhờ bạn thay cái này bằng câu lệnh thông thường cho mình với.chứ ko hiểu cái này nữa thôi
 
T

tengiday

Happy life
tuonglong:
Chỗ này nữa bạn ơi if ((s and 1) = 0) then.nhờ bạn thay cái này bằng câu lệnh thông thường cho mình với.chứ ko hiểu cái này nữa thôi
Nhấn để mở rộng...

'a and 1' = 1 nếu a là lẻ, và = 0 nếu a là chẵn. Câu lệnh đó kiểm tra s có phải là số chẵn hay ko.
 
T

tuonglong

nhưng cho mình hỏi chỗ cuối nữa.vì sao khi s là chẵn thì ta mới tiến hành tìm kiếm hả bạn
 
Sửa lần cuối:
T

tengiday

Happy life
tuonglong:
nhưng cho mình hỏi chỗ cuối nữa.vì sao khi s là chẵn thì ta mới tiến hành tìm kiếm hả bạn
Nhấn để mở rộng...

Chúng ta cần tìm đoạn có thể chia làm 2 phần có tổng bằng nhau, cho nên s phải là số chẵn trước đã.
 
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Bài viết đang hot

Thống kê

Chủ đề
100,579
Bài viết
467,301
Thành viên
339,803
Thành viên mới nhất
Phambeo790

Bài viết được quan tâm nhiều

Top