刷题笔记:Division(UVa725)做题心得

Warning: Use of undefined constant avatar - assumed 'avatar' (this will throw an Error in a future version of PHP) in /data/htdocs/codeingboy.host.smartgslb.com/blog/wp-content/themes/rnmaterial-2.0/single.php on line 17
CodeingBoy 2月 27, 2017

题目

输入一个数(N),从 0~9 中选出数字组成 abcde / fghij = N 的组合,每位数字只能使用一次(除了 N)。

UVa 题目链接

版本 1

根据题目,使用穷举法穷举 fghij 即可。因为 N 是给定的,所以可以根据 N * fghij 求得 abcde,然后对这些数字进行判定即可。

代码如下:

// Example 7-1 Division
// UVa 725
// For more information, see problem 725 on UVa Online Judge.
// Language: C++

#include <iostream>

using namespace std;

bool isUnique(int, int);

int main(){
    int input;
    while(cin >> input && input){
        const int N = input;

        for(int f = 0;f < 10;f++){
            for(int g = 0;g < 10;g++){
                for(int h = 0;h < 10;h++){
                    for(int i = 0;i < 10;i++){
                        for(int j = 0;j < 10;j++){
                            int num2 = f*10000+g*1000+h*100+i*10+j;    
                            int num1 = N * num2;
                            if(isUnique(num1, num2)){
                                cout << num1 << " / " << num2 << " = " << N << endl;
                            }
                        }
                    }
                }
            }
        }
    }
}

bool isUnique(int num1, int num2){
    bool nums[10] = {false};

    while(num1){
        int digit = num1 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num1 /= 10;
    }

    while(num2){
        int digit = num2 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num2 /= 10;
    }

    return true;
}

编译跑了一下,发现两个错误:

  1. 直接显示了 num1,若 num1 是 4 位数的情况下,没有显示前导 0
  2. num1 可能为 6 位数,这是不允许的

版本 2 & 版本3

版本 2 对这第二个问题进行修正:

// Example 7-1 Division
// UVa 725
// For more information, see problem 725 on UVa Online Judge.
// Language: C++

#include <iostream>

using namespace std;

bool isUnique(int, int);

int main(){
    int input;
    while(cin >> input && input){
        const int N = input;

        for(int f = 0;f < 10;f++){
            for(int g = 0;g < 10;g++){
                if(g == f)continue;
                for(int h = 0;h < 10;h++){
                    if(h == g)continue;
                    for(int i = 0;i < 10;i++){
                        if(i == h)continue;
                        for(int j = 0;j < 10;j++){
                            if(j == i)continue;
                            int num2 = f*10000+g*1000+h*100+i*10+j;    
                            int num1 = N * num2;
                            if(num1 >= 100000){
                                continue;
                            }
                            if(isUnique(num1, num2)){
                                cout << num1 << " / " << num2 << " = " << N << endl;
                            }
                        }
                    }
                }
            }
        }
    }
}

bool isUnique(int num1, int num2){
    bool nums[10] = {false};

    if(num2 < 10000){
        nums[0] = true;
    }

    while(num1){
        int digit = num1 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num1 /= 10;
    }

    while(num2){
        int digit = num2 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num2 /= 10;
    }

    return true;
}

如果传入的 num2 为4 位,就认定为数字 0 已经存在。同时也在穷举 num2 的时候进行一定程度上的剪枝。

版本 3 对第一个问题进行修正:

// Example 7-1 Division
// UVa 725
// For more information, see problem 725 on UVa Online Judge.
// Language: C++

#include <iostream>

using namespace std;

bool isUnique(int, int);

int main(){
    int input;
    while(cin >> input && input){
        const int N = input;
        int solve = 0;

        for(int f = 0;f < 10;f++){
            for(int g = 0;g < 10;g++){
                if(g == f)continue;
                for(int h = 0;h < 10;h++){
                    if(h == g)continue;
                    for(int i = 0;i < 10;i++){
                        if(i == h)continue;
                        for(int j = 0;j < 10;j++){
                            if(j == i)continue;
                            int num2 = f*10000+g*1000+h*100+i*10+j;    
                            int num1 = N * num2;
                            if(num1 >= 100000){
                                continue;
                            }
                            if(isUnique(num1, num2)){
                                cout << num1 << " / " << (num2 < 10000?"0":"") << num2 << " = " << N << endl;
                                solve++;
                            }
                        }
                    }
                }
            }
        }

        if(solve == 0){
            cout << "There are no solutions for " << N << "." << endl;
        }
    }
}

bool isUnique(int num1, int num2){
    bool nums[10] = {false};

    if(num2 < 10000){
        nums[0] = true;
    }

    while(num1){
        int digit = num1 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num1 /= 10;
    }

    while(num2){
        int digit = num2 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num2 /= 10;
    }

    return true;
}

通过判定数字的大小,输出的时候添加前导 0。

版本 4

然而发现 num1 的位数也可能为 4 位,因此也添加了 num1 为 4 位时的应对措施。

// Example 7-1 Division
// UVa 725
// For more information, see problem 725 on UVa Online Judge.
// Language: C++

#include <iostream>

using namespace std;

bool isUnique(int, int);

int main(){
    int input;
    while(cin >> input && input){
        const int N = input;
        int solve = 0;

        for(int f = 0;f < 10;f++){
            for(int g = 0;g < 10;g++){
                if(g == f)continue;
                for(int h = 0;h < 10;h++){
                    if(h == g)continue;
                    for(int i = 0;i < 10;i++){
                        if(i == h)continue;
                        for(int j = 0;j < 10;j++){
                            if(j == i)continue;
                            int num2 = f*10000+g*1000+h*100+i*10+j;    
                            int num1 = N * num2;
                            if(num1 >= 100000){
                                continue;
                            }
                            if(isUnique(num1, num2)){
                                cout << (num1 < 10000?"0":"") << num1 << " / " << (num2 < 10000?"0":"") << num2 << " = " << N << endl;
                                solve++;
                            }
                        }
                    }
                }
            }
        }

        if(solve == 0){
            cout << "There are no solutions for " << N << "." << endl;
        }
    }
}

bool isUnique(int num1, int num2){
    bool nums[10] = {false};

    if(num1 < 10000){
        nums[0]=true;
    }

    if(num2 < 10000){
        if(nums[0])return false;
        nums[0] = true;
    }

    while(num1){
        int digit = num1 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num1 /= 10;
    }

    while(num2){
        int digit = num2 % 10;
        if(nums[digit]){
            return false;
        }else{
            nums[digit] = true;
        }
        num2 /= 10;
    }

    return true;
}

到了这里,应该就差不多了,然而提交的时候提示 Presentaion Error……

版本 5

看了看题目,原来是说每两个输出之间间隔一行,而不是每个输出后跟一个空行。

Separate the output for two different values of N by a blank line.

因此添加:

if(kase)cout << endl;

添加后再次提交,终于 AC。

本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。
本文链接:https://blog.codeingboy.me/%e5%88%b7%e9%a2%98%e7%ac%94%e8%ae%b0%ef%bc%9adivision%ef%bc%88uva725%ef%bc%89%e5%81%9a%e9%a2%98%e5%bf%83%e5%be%97/

发表评论

电子邮件地址不会被公开。 必填项已用*标注