• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

[Bồi bổ] Tính tổng các số trong dãy số

Đây là nơi để các bạn trao đổi về cấu trúc dữ liệu và giải thuật

Điều hành viên: Điều hành

Hình đại diện của người dùng
dazzlingvit
Guru
Guru
Bài viết: 960
Ngày tham gia: T.Ba 18/01/2011 10:21 am
Đến từ: Sinh ra từ hư vô, sống trong thế giới ảo...
Has thanked: 7 time
Been thanked: 112 time
Liên hệ:

[Bồi bổ] Tính tổng các số trong dãy số

Gửi bàigửi bởi dazzlingvit » T.Sáu 26/10/2012 12:32 am

Mình xin phép được lập sêri "Bồi bổ", cung cấp những bài toán và thuật toán đơn giản nhưng thú vị. Cấu trúc dữ liệu và giải thuật là một trong những vấn đề cơ bản của khoa học máy tính, nên mình nghĩ có một kiến thức cơ bản về cái này sẽ giúp ích rất nhiều cho các bạn.
Kết thúc phần luyên thuyên.
---
Bài toán của chúng ta hôm nay là: tính tổng các số trong dãy số. Nghe tiêu đề có vẻ ngon :D
---
Đề bài:
Cho dãy số gồm N phần tử, ban đầu đều bằng 0. Cho M thao tác với dãy số đó, gồm 2 loại:
- SET i j: gán phần tử thứ i giá trị j.
- SUM i j: tính tổng các số từ phần tử i đến phần tử j.
(Chỉ số tính từ 1)
Dữ liệu vào:
- Dòng 1: 2 số N, M cách nhau 1 khoảng trắng.
- M dòng tiếp theo: các thao tác với dãy số (SET, SUM).
Dữ liệu ra: với mỗi thao tác SUM, ghi ra một dòng là tổng giá trị các số.
Để đơn giản coi như giá trị tổng luôn nằm trong phạm vi kiểu int (-2^31 -> 2^31-1).
Ví dụ:

Mã: Chọn hết

3 6
SET 1 2
SUM 1 2
SET 2 3
SUM 1 3
SET 3 1
SUM 2 3

KQ:

Mã: Chọn hết

2
5
4

Giải tích:

Mã: Chọn hết

SET 1 2 | 2 0 0
SUM 1 2 | 2 + 0 = 2
SET 2 3 | 2 3 0
SUM 1 3 | 2 + 3 + 0 = 5
SET 3 1 | 2 3 1
SUM 2 3 | 3 + 1 = 4

---
Và bây giờ là phần quan trọng nhất: chương trình chỉ tính toán trong 1s.
Có 3 loại giới hạn sau:
1. N <= 100, M <= 100.
2. N <= 1000, M <= 1000.
3. N <= 1000000, M <= 100000.
Mọi người cùng thảo luận đưa ra cách làm nhé. Ban đầu cứ chiến giới hạn nhỏ đã, sau đó tìm cách chơi hàng khủng sau :D


Dazzling V.I.T
Hãy gọi tôi là vịt :)

DoremonA
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 441
Ngày tham gia: T.Sáu 29/07/2011 1:00 pm
Has thanked: 11 time
Been thanked: 145 time

Re: [Bồi bổ] Tính tổng các số trong dãy số

Gửi bàigửi bởi DoremonA » T.Tư 24/04/2013 1:24 pm

Duyệt For i từ 1 đến N-1 =>hàm Sum(i)=((i+1)*(i+2)/2)-1. Còn với i=N => Sum(N)= {7 nếu n>3, 4 nếu n=3}
Theo ví dụ của bạn chỉ đến 3 ( chưa tổng quát lắm ) nên mình hiểu ý của bạn như sau với N=5:
    5 10
    SET 1 2 | 2 0 0 0 0
    SUM 1 2 | 2 + 0 = 2
    SET 2 3 | 2 3 0 0 0
    SUM 1 3 | 2 + 3 + 0 = 5
    SET 3 4 | 2 3 4 0 0
    SUM 1 4 | 2 + 3 + 4 + 0 = 9
    SET 4 5 | 2 3 4 5 0
    SUM 1 5 | 2 + 3 + 4 + 5 + 0 = 14
    SET 5 1 | 2 3 4 5 1
    SUM 2 3 | 3 + 4 = 7

Hình đại diện của người dùng
dazzlingvit
Guru
Guru
Bài viết: 960
Ngày tham gia: T.Ba 18/01/2011 10:21 am
Đến từ: Sinh ra từ hư vô, sống trong thế giới ảo...
Has thanked: 7 time
Been thanked: 112 time
Liên hệ:

Re: [Bồi bổ] Tính tổng các số trong dãy số

Gửi bàigửi bởi dazzlingvit » T.Năm 20/06/2013 7:07 am

Hàm SUM i, j là tính tổng các phần tử từ i đến j nhé. Ví dụ SUM 1 3 có giá trị bằng c[1] + c[2] + c[3] với c là mảng giá trị hiện tại. Chỉ số tính từ 1 (tức là c[1] là phần tử đầu tiên của mảng).
Dazzling V.I.T
Hãy gọi tôi là vịt :)


Quay về “Cấu trúc dữ liệu và giải thuật”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.1 khách