Có bao nhiêu quà tặng trong 12 ngày giáng sinh nếu chúng tôi kéo dài 12 đến bất kỳ số nào?

Question

Tôi nhận được câu hỏi này hôm nay trong một cuộc phỏng vấn: viết một chức năng để tính toán tổng số quà tặng nhận được cho bất kỳ ngày nào trong 12 ngày của bài hát giáng sinh. Tôi đã viết một hàm đơn giản bằng cách sử dụng vòng lặp for() trong mã ish C# 'đã hoạt động. Sau đó, người phỏng vấn yêu cầu tôi mở rộng nó cho bất kỳ số ngày nào. Cuộc hội thoại sau đó đã chuyển sang cách tối ưu hóa vòng lặp. Rõ ràng có một thủ thuật toán học thú vị sẽ làm điều này trong giới hạn của bất kỳ số nguyên nào của bạn. Bất cứ ai biết nó là gì và nó được gọi là gì? Bất kỳ ngôn ngữ nào là ok và tham chiếu đến thuật toán sẽ là tuyệt vời.

Câu trả lời sử dụng đệ quy KHÔNG phải là những gì tôi đang tìm kiếm.

EDIT: Trả lời cho ngày 2 là tổng số 4 quà tặng, không phải 3 vì tôi sẽ có 2 Cây (1 từ hôm nay, 1 từ hôm qua) và 2 hộp mực. Vào ngày 12, tôi sẽ nhận được tổng cộng 364. Tôi muốn công thức cho phép tôi nhập 12 và nhận được 364.

Answer 1

• Vào ngày đầu tiên, bạn sẽ có được 1.
• Vào ngày thứ hai, bạn sẽ có được 1 + 2.
• Vào ngày thứ ba, bạn sẽ có được 1 + 2 + 3.
• .. .
• Vào ngày n ngày, bạn nhận được 1 + 2 + 3 + ... + n.

Tổng số 1 + 2 + ... + n là n(n+1)/2. Vì vậy, tổng số, T(N) là tổng của n(n+1)/2 cho n trong 1..N, trong đó N là số ngày.

Bây giờ, n(n+1)/2 = n^2/2 + n/2, và tổng của n^2 cho n trong 1..N là N(N+1)(2N+1)/6, vì vậy bạn sẽ có được:

T(N) = N(N+1)(2N+1)/12 + N(N+1)/4 
    = N(N^2 + 3N + 2)/6 

Không vòng. Không có đệ quy.

Answer 2

Ngày n ngày thứ, chúng tôi nhận được 1 + 2 + 3 + ... + n quà tặng.

Hoặc ... (1 + n) + (2 + n-1) + ...

Nói cách khác, (n + 1) * n/2.

Answer 3

Loại $ P $ -th hiện tại (trong đó $ 1 $ st là hộp số, $ 2 $ nd là chim bồ câu, vv) có số lượng $ P = \ sum_ {X = 1}^{P } 1 $.

Vào ngày $ D $, bạn nhận quà từ $ 1 $ đến $ D $, tổng cộng $ \ sum_ {P = 1}^{D} \ sum_ {X = 1}^{P} 1 $ nhiều món quà vào ngày đó.

Và vì vậy, nếu ngày chạy từ $ 1 $ đến $ N $ (theo kinh điển, $ N $ là 12, nhưng hiện tại chúng tôi đang cho phép nó thay đổi), bạn nhận được $ \ sum_ {D = 1}^{N} \ sum_ {P = 1}^{D} \ sum_ {X = 1}^{P} 1 $.

Điều này tính số lượng bộ ba không giảm $ 1 \ leq X \ leq P \ leq D \ leq N $.

Điều này giống với số lượng tăng gấp ba lần $ 1 \ leq X < P + 1 < D + 2 \ leq N + 2 $.

Vì vậy, câu trả lời là $ \ binom {N + 2} {3} = \ frac {(N + 2) (N + 1) N} {6} $.