uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）

本文主要是介绍uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意是

   ?  1  ?  2  ?  ...  ?  n = k

式子中给k，? 处可以填 + 也可以填 - ，问最小满足条件的n。

e.g

k = 12 

- 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12

with n = 7。

先给证明，令 S（n） = 1 + 2 + 3 + 4 + 5 + .... + n

暴搜n，搜出当 S（n） >= k ，的最小n；

若S（n） = k，直接输出就好了，

若S（n） > k， 则在S（n）中，将某个适当的值的 + 号 改成 - 号 可以使S（n） = k， 设被减掉的值为 x；

则S（n） = 1 + 2 + 3 + 4 + 5 + ...+ x  ....+ n

则改过符号的 C（n）= 1 + 2 + 3 + 4 + 5 +... - x ...+ n = k

所以 S（n） - C（n） = S（n） - k = 2 * x（必为偶数）

按上述推导找出n即可，若上式不为偶数，则再加n，继续找。

代码：

#include <stdio.h>int S(int x)
{return ((1 + x) * x) >> 1;
}int main()
{int ncase;scanf("%d", &ncase);while (ncase--){int k;scanf("%d", &k);if (k < 0)k = -k;int n;for (n = 1; ; n++){if (S(n) >= k && !((S(n) - k) & 1)){printf("%d\n", n);break;}}if (ncase)printf("\n");}return 0;
}

有的时候会想，如果这是高考数学的选择填空的最后一题，直接用数学的方法做要麻烦很多。

感觉计算机+数学灰常无敌。

这篇关于uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---