目的:用1-9九个数字组成三个三位数abc, def, ghi,每个数字恰好使用一次,求三个数abc:def:ghi = 1 : 2 : 3的所有可能
要求:
输出:按照“abc def ghi”格式输出所有解
样例输出:192 384 576
思路:用数组元素是否重复判断每个数字是否恰好使用一次,将abcdefghi存入数组,如果重复就说明不是解。那么就有两种思路:第一种是由数组得到匹配比例的数字解,这样就要构造循环对数组的每个位进行判断;第二种是不断对第一个数进行迭代,由比例关系得到第二个和第三个数,最后判断数字是否重复,采用了这种方法。
代码如下:
#includeint bitSize;int main(){ //Function declaration int inBit(int *bit, int num); //Local variables int bit[9]; for(int i = 123; i < 333; i++){ bit[0] = i / 100; bit[1] = (i / 10) % 10; bit[2] = i % 10; int status = 1; bitSize = 3; int j = 2 * i; int k = 3 * i; int temp[6]; temp[0] = j / 100; temp[1] = (j / 10) % 10; temp[2] = j % 10; temp[3] = k / 100; temp[4] = (k / 10) % 10; temp[5] = k % 10; for(int iter = 0; iter < 6; iter++){ if(inBit(bit, temp[iter])){ //If repeated status = 0; break; } else{ bit[bitSize++] = temp[iter]; } } if(status){ printf("%d %d %d\n", i, j, k); } } return 0;}int inBit(int *bit, int num){//If repeated,return 1 for(int i = 0; i < bitSize; i++){ if(num == bit[i]){ return 1; } } return 0;}
优化:在找到对应的三个数之后循环判断是否数字重复的过程中,只要有一个重复即不是解,可以进行下一次猜数。
更新:洛谷OJ的P1008出现同题,有了新的看法。
采用字符串解决,尽量用库函数
#include#include #include #include using namespace std;void solve(){ for(int abc = 123; abc < 333; abc++){ int def = 2 * abc; int ghi = 3 * abc; char s1[4]; char s2[4]; char s3[4]; char res[10] = { '\0'}; sprintf(s1, "%d", abc); sprintf(s2, "%d", def); sprintf(s3, "%d", ghi); strcat(res, s1); strcat(res, s2); strcat(res, s3); sort(res, res + 9); if(!strcmp(res, "123456789")){ cout << abc << ' ' << def << ' ' << ghi << endl; } }}int main(){ solve(); return 0;}
觉得用数位解太麻烦,故用比例直接列举第一个数,那么第二个和第三个数也就得到了,之后将这三个书写入字符串。对字符串排序后如果与“123456789”相同那么说明没有重复数字,符合条件。
Ps:刚开始并没有用sprintf()将整数转字符串, 而是用stdlib里的itoa(),但是stdlib里的函数并非通用,在洛谷里出现compile error。
采用标志数组解决,建立一个九位数组,先初始化每位为零。每当出现一个数字,其对应的数组元素置为一,最后检查数组是否有零,有零则表示重复了。(引自洛谷Kelin)
#include#include int i,j,v;bool a[10];//ai表示第i个数已经用过了int main(){ for(i=192;i<=327;i++)//第一个数最小192,最大327。其实不知道的情况下简单来说是从123-329的但是算出来是最值就稍微改了下下 { memset(a,0,sizeof(a));v=0;//清零 a[i%10]=a[i/10%10]=a[i/100]=a[i*2%10]=a[i*2/10%10]=a[i*2/100]=a[i*3%10]=a[i*3/10%10]=a[i*3/100]=1;//统计数字 for(j=1;j<=9;j++) v+=a[j];//v表示1-9这些数字是否全部齐了 if(v==9) printf("%d %d %d\n",i,i*2,i*3);//如果齐了就输出 }return 0;}