Vijos P1772 巧妙填数【进制+置换】

描述

将1,2,⋯,9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成1:2:3的比例。

试求出所有满足条件的三个三位数。
例如：三个三位数满足以上条件。

格式

输入格式

无输入。

输出格式

需要输出全部结果。每行输出3个数用空格隔开。按照字典序的顺序输出。

来源

NOIP 1998 普及组第一题

问题链接： Vijos P1772 巧妙填数

问题分析：

这个问题是一个计算问题。

由1-9数字构成的3位数最小值是123，最大值是987。所以3个数中最小那个数的最大值小于或等于987/3=329，也就是说满足条件的3个数中，最小那个数值的范围是123-329。

这样，第1个数a就可以在123-329范围试探。另外两个数就应该是a*2和a*3。只要这3个数中不包含0，并且数字不重复，那么就是合适的解。

另外一种做法是利用置换函数来实现，其第1个数的值范围也是123-329，程序显得比较简洁。

程序说明：

函数legalcheck()的功能是判断数的数字是否出现重复。

给出两种不同实现方法的程序，可以比较着看。

题记：

进制是计算中绕不开的话题。

参考链接：（略）

AC的C++程序如下：

#include <iostream>
#include <cstring>

using namespace std;

const int BASE10 = 10;
const int N = 10;
int digit[N];

bool legalcheck(int v)
{
    bool flag;

    flag = true;
    while(v) {
       int d = v % BASE10;
       if(d == 0 || digit[d]) {
           flag = false;
           break;
       }
       digit[d] = 1;

       v /= BASE10;
    }

    return flag;
}

int main()
{
    for(int a=123; a<=329; a++) {
        memset(digit, 0, sizeof(digit));

        if(!legalcheck(a))
            continue;
        if(!legalcheck(a * 2))
            continue;
        if(!legalcheck(a * 3))
            continue;

        cout << a << " " << a * 2 << " " << a * 3 << endl;
    }

    return 0;
}

AC的C++程序如下：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9;

int v[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

int main()
{
    int a, b, c;

    a = v[0] * 100 + v[1] * 10 + v[2];
    for(;;) {
        b = v[3] * 100 + v[4] * 10 + v[5];
        if(a * 2 == b) {
            c = v[6] * 100 + v[7] * 10 + v[8];
            if(a * 3 == c)
                cout << a << " " << b << " " << c << endl;
        }

        next_permutation(v, v + N);
        a = v[0] * 100 + v[1] * 10 + v[2];
        if(a > 329)
            break;
    }

    return 0;
}