P2669 [NOIP2015 普及组] 金币

题目背景

NOIP2015 普及组 T1

题目描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 $n$ 天每天收到 $n$ 枚金币后，骑士会在之后的连续 $n+1$ 天里，每天收到 $n+1$ 枚金币。

请计算在前 $k$ 天里，骑士一共获得了多少金币。

输入格式

一个正整数 $k$，表示发放金币的天数。

输出格式

一个正整数，即骑士收到的金币数。

1.题目分析

该题主要考察的是对循环的使用，一些数学公式：
等差数列求前n项和：n*（a1 + an）/2.
这里还可以考虑使用递归。

2.题目思路

写一个递归函数求n*n的前n项和，用于计算连续n天后发的总金币数。
键入天数d，需要 根据d计算是第n轮发n个金币，可以得到他们之间的关系是：1 + 2 +3 … +n =d.
所以可以根据等差数列的前N项公式求得，得到N的值后，调用递归函数，如果恰好不是n轮结束的天数，则需要减去多余的金币数。如：第4天： 1 +2 + 2 +3 + 3 等于 1 + 2 +2 +3 +3 +3 减去 一个3

3.代码实现

#include <stdio.h>
//写一个函数，表示求n*n的前n项和
int res(int n) {if (n == 1) {return 1;}return n * n + res(n - 1);
}int main() {/*** d,表示天数*/int n, sum, d;n = 0;//re表示计算时超出的金币数int re;scanf("%d", &d);//判断天数d和第n次发n枚金币之间的关系while (true) {if (n * (n + 1) >= d * 2) {break;}n++;}//求总金币数sum = res(n);re = (n * (n + 1) - d * 2) / 2 * n;//总金币数减去超出的printf("%d", sum - re);
}