主題

ZeroJudge - f423: 高雄市109年資訊競賽國中組第一題 解題心得

Not In My Back Yard | 2020-11-20 00:00:05

題目連結:


題目大意:
給定一正整數 N (1 ≦ N ≦ 10000),求 1(含)~ N(含)之間所有奇數之和。



範例輸入:
範例輸入一:
5

範例輸入二:
123

範例輸入三:
10000


範例輸出:
範例輸出一:
9

範例輸出二:
3844

範例輸出三:
25000000


解題思維:
此題為一道數學題(當然,用迴圈暴力直接求總和也是可以的)。

可以看到 1 ~ N 之間有 ceil(N ÷ 2) 個奇數(以下以 X 代稱),其中 ceil() 代表上高斯,對於正數來說即是無條件進位。

而套入國中可能就上過的等差級數之公式:
(2a + nd - d) × n ÷ 2
其中 a 代表首項(在這題是 1)、 n 表有幾個項次(此即 X)、d 代表公差(此為 2)。

因此,我們的上式套入此題的數字並化簡會變為
X ^ 2
即前 X 奇數加起來之總和恰好為 X 平方之值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
56 巴幣: 12
愛香
咦?現在國中就開始教程式語言了嗎?而且還是C語言。
2020-11-20 04:17:45

更多創作