组不到的数字

题目描述

##算法设计
**算法关键:**可以穷举，但i需要在哪里停止？

输入处理

很简单

    int a,b;
    scanf("%d%d",&a,&b);

算法逻辑

数i=j*a+k*b,通过循环来模拟数值变化

如果不满足等式，就更新ans

int solve(int a, int b) {
    int ans;
    for (int i = a > b ? a : b; i < a * b; ++i) {//数
        for (int j = 0; j < b; ++j) {//a的系数
            for (int k = 0; k < a; ++k) {//b的系数
                if (i ！= a * j + b * k) {
                    ans = i;
                }
            }
        }
    }
    return ans;
}

输出处理

printf("%d",ans);

测试运行

呃，跟测试数据差了那么一点点

27=5*4+7，说明j有问题

写的时候先入为主认为b是a和b中较小的那个了，修改一下主方法

    int max=a>b?a:b;
    int ans=solve(max,a+b-max);

让max等于a和b中较大的那个，传入max和a+b-max。（a+b）-max就是较小的那个。

再次运行结果没变，因为算法错了，不是但凡不相等就赋值。在i等于一个值时，总会有对应的j、k组合让等式不相等。这时应该使用标志变量

重新写一下

int solve(int a, int b) {
    int ans;
    int isEqual = 0;
    for (int i = a; i < a * b; ++i) {//数
        for (int j = 0; j < b; ++j) {//a的系数
            for (int k = 0; k < a; ++k) {//b的系数
                if (i == a * j + b * k) {
                    isEqual = 1;
                }
            }
        }
        if (!isEqual) {
            ans = i;
        }
        isEqual = 0;
    }
    return ans;
}

这样就是在内层循环结束后，但凡找到了令等式成立的j、k组合就不进行赋值

得到了正确的结果。

开开心心提交

超时了，不过比爆红要好。

该算法对于每一个i都要从头开始算一遍，非常的耗时间

建立一个二维数组dp[a][b],把i*a+j*b存到dp[i][j]中，这样对于下一个i循环是可以直接调取数组中相应位置的内容

int solve(int a, int b) {
    int ans;
    int dp[b+1][a+1];
    dp[0][0] = 0;
    int isEqual = 0;
    for (int i = a; i < a * b; ++i) {//数
        for (int j = 0; j < b+1; ++j) {//a的系数i
            for (int k = 0; k < a+1; ++k) {//b的系数j
                if (j == 0) {
                    if(k==0){
                        k++;
                    }
                    dp[j][k] = dp[j][k - 1] + b;
                }//第一行
                else {
                    dp[j][k] = dp[j - 1][k] + a;//上一行加a
                }
                if (i == dp[j][k]) {
                    isEqual = 1;
                }
            }
        }
        if (!isEqual) {
            ans = i;
        }
        isEqual = 0;
    }
    return ans;
}

再次提交

时间更长了，原来是对于每个i又重新打了一个表，再次更改一下

int solve(int a, int b) {
    int ans;
    int dp[b + 1][a + 1];
    dp[0][0] = 0;
    int isEqual=0;
    for (int j = 0; j < b + 1; ++j) {//a的系数i
        for (int k = 0; k < a + 1; ++k) {//b的系数j
            if (j == 0) {
                if (k == 0) {
                    k++;
                }
                dp[j][k] = dp[j][k - 1] + b;
            }//第一行
            else {
                dp[j][k] = dp[j - 1][k] + a;//上一行加a
            }
        }
    }
    for (int i = a; i < a*b; ++i) {
        for (int j = 0; j < b+1; ++j) {
            for (int k = 0; k <a+1; ++k) {
                if(i==dp[j][k]){
                    isEqual=1;
                }
            }
        }
        if (!isEqual) {
            ans=i;
        }
        isEqual=0;
    }
    return ans;
}