首页 > 其他 > 详细

UVA10025 The ? 1 ? 2 ? ... ? n = k problem【数学规律】

时间:2019-02-17 18:52:05      阅读:228      评论:0      收藏:0      [点我收藏+]

Given the following formula, one can set operators ‘+’ or ‘-’ instead of each ‘?’, in order to obtain a given k

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

For example: to obtain k = 12, the expression to be used will be:

  • 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12
    with n = 7
    Input
    The first line is the number of test cases, followed by a blank line.
    ????Each test case of the input contains an integer k (0 ≤ |k| ≤ 1000000000).
    ????Each test case will be separated by a single line.
    Output
    For each test case, your program should print the minimal possible n (1 ≤ n) to obtain k with the above formula.
    ????Print a blank line between the outputs for two consecutive test cases.
    Sample Input
    2
    12
    -3646397
    Sample Output
    7
    2701

问题链接UVA10025 The ? 1 ? 2 ? ... ? n = k problem
问题简述:(略)
问题分析
????给定一个整数k,找一个最小的n,使得在1-n(按顺序)这n个数的前面加上-或+,使得表达式的结果值为k。例如:因为0=1+2-3,当k=0时,n为3;因为1=-1+2,当k=1时,n为2;因为2=1-2+3,当k=2时,n=3。当k<0时,n的值与-k的情况是一样的,因为只需要将1-n的各个值取负就得到负数了。
????这个题是一个数学规律题。k=0时,需要特殊考虑,即n=3。k<0时则按-k进行计算即可。对于给定的正整数k,令s=1+2+......+n,那么至少需要保证s>=k。对于满足s>=k的n,若s-k=0则n就是所求的结果;若s-k为偶数则将(s-k)/2之前置为-,其他数之前置为+,则n为所求结果;若s-k为奇数则继续增大n再行判定。
程序说明:(略)
参考链接:(略)
题记:(略)

AC的C++语言程序如下:

/* UVA10025 The ? 1 ? 2 ? ... ? n = k problem */

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &k);
        if(k == 0)
            printf("3\n");
        else {
            if(k < 0) k = -k;
            int sum = 0, n = 0;
            while(sum < k) sum += ++n;      // 必要条件:1-n之和>=k
            while((sum - k) % 2 == 1) sum += ++n;   // 差值为奇数时继续增大n,否则将差值/2变为负即可
            printf("%d\n", n);
        }
        if(t) printf("\n");
    }

    return 0;
}

UVA10025 The ? 1 ? 2 ? ... ? n = k problem【数学规律】

原文:https://www.cnblogs.com/tigerisland45/p/10392182.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!