时间戳

首页 > 解决方案 > 确定我们是否可以将“+”和“-”放在数字之间，以便结果可以被数字整除：我的错误在哪里？

c - 确定我们是否可以将“+”和“-”放在数字之间，以便结果可以被数字整除：我的错误在哪里？

问题描述

我们有howmanynums数字。我们必须确定是否有一种方法可以将它们放在它们'+'之间'-'，以使结果可以被给定的 number 整除mod。

（最好通过动态编程来完成，但我只是从头开始计算每个序列，因为时间很短，只需要它工作）。


int howmanynums, mod;

int ring(int num) {
    if ((num >= 0) && (num <= mod - 1))
        return num;
    if (num >= mod) {
        while (num >= mod)
            num -= mod;
        return num;
    }
    if (num < 0) {
        while (num < 0)
            num += mod;
        return num;
    }
}

long int p(int n) {
    long int t = 1;

    while (n > 0) {
        t *= 2; 
        n--;
    }
    return t;
}

int sequence[10000][2];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%d%d%d", &howmanynums, &mod, &sequence[0][0]);
    sequence[0][0] = ring(sequence[0][0]);
    int temp;
    int k = 1;
    while (k < howmanynums) {
        scanf("%d", &temp);
        sequence[k][0] = ring(temp);
        sequence[k][1] = ring(-temp);
        k++;
    }

    long int x = (p(howmanynums - 1)); 
    while (x > 0) {
        long int a = sequence[0][0];
        long int permutation = x;
        long int insidePermutation = x % 2;
        int l = 1;
        while (l < howmanynums) { 
            a += sequence[l][insidePermutation]; 
            l++; 
            permutation = permutation / 2; 
            insidePermutation = permutation % 2; 
        }
        if (a % mod == 0) {
            printf("%s", "Divisible");
            goto e;
        }
        x--;
    }
     printf("%s", "Not divisible");

 e:
    return 0;
}

它通过了 20 个测试中的 10 个。我不知道测试。

我还尝试将所有整数替换为长整数，但结果相同。

我的错在哪里？

标签： cdynamic-programming

解决方案

我简化了您的代码，对我来说它看起来不错。它应该完成这项工作。我唯一关心的是效率。对于下一个 30 个数字序列，大约需要 20 秒才能找到答案“不可整除”： 30 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0。每增加一个数字，前一次的数字就会增加一倍。因此，您的代码未通过的测试可能是因为允许的测试时间。

动态编程是通过测试的必要条件。

#include <stdio.h>
#pragma warning(disable : 4996)

int howmanynums, mod, sequence[64];

int main() {
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    scanf("%d%d", &howmanynums, &mod);
    if (howmanynums > 64)
    {
        printf("Too many %d", howmanynums);
    }
    int k = 0;
    while (k < howmanynums)
        scanf("%d", &sequence[k++]);
    int x = (2 << (howmanynums - 2)) - 1;
    bool divisible = false;
    while (!divisible && x >= 0)
    {
        int a = sequence[0], bit = 1;  k = 1;
        while (k < howmanynums)
        {
            a += x & bit ? sequence[k] : -sequence[k];
            k++;
            bit *= 2;
        }
        divisible = a % mod == 0;
        x--;
    }
    printf("%s", divisible ? "Divisible": "Not divisible");
    return 0;
}

推荐阅读