这是一道水题，但给人非常大的感悟和启发，思维瞬间上升到哲学层面。在我们的生活中，正向和逆向思维对于解决一个问题具有不同的复杂度，虽然结果是一样的，但在不同的情景中，这两种思维会有优劣之分。这道题目便体现了正向和逆向思维。
题目描述：将1,2, .. ,9共9个数分成3组，分别组成3个三位数，且使这3个三位数构成1:2:3的比例，试求出所有满足条件的3个三位数。
输入格式：木有输入
输出格式：若干行，每行3个数字。按照每行第1个数字升序排列。
image
方法一：正向思维，首先枚举出把9个数分成3组的所有组合情况，然后对每一种情况去判断能否满足1:2:3的条件，若能则输出。
一个比较蠢的办法是每一位都从1取到9，取下一位之前要判断是否与前一位取的相同，相同则continue跳出本次循环。（有一个数学上的技巧，第一个数肯定小于334，因为按照1:2:3的比例，第一个数不可能比334大，否则会超过999（3位数） ）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stdio.h>
using namespace std;
int main(){
int a[10],i,j,k;
for (a[0] = 1; a[0] <= 3; a[0]++){
for (a[1] = 1; a[1] <= 9; a[1]++){
if (a[1] == a[0]) continue;
for (a[2] = 1; a[2] <= 9; a[2]++){
if (a[2]==a[1] || a[2]==a[0] ) continue;
for (a[3] = 3; a[3] <= 9; a[3]++){
if (a[3] == a[2] || a[3] == a[1] || a[3] == a[0]) continue;
for (a[4] = 1; a[4] <= 9; a[4]++){
if (a[4] == a[3] || a[4] == a[2] || a[4] == a[1] || a[4] == a[0]) continue;
for (a[5] = 1; a[5] <= 9; a[5]++){
if (a[5] == a[4] || a[5] == a[3] || a[5] == a[2] || a[5] == a[1] || a[5] == a[0]) continue;
for (a[6] = 1; a[6] <= 9; a[6]++){
if (a[6] == a[5] || a[6] == a[4] || a[6] == a[3] || a[6] == a[2] || a[6] == a[1] || a[6] == a[0]) continue;
for (a[7] = 1; a[7] <= 9; a[7]++){
if (a[7] == a[6] || a[7] == a[5] || a[7] == a[4] || a[7] == a[3] || a[7] == a[2] || a[7] == a[1] || a[7] == a[0]) continue;
for (a[8] = 1; a[8] <= 9; a[8]++){
if (a[8] == a[7] || a[8] == a[6] || a[8] == a[5] || a[8] == a[4] || a[8] == a[3] || a[8] == a[2] || a[8] == a[1] || a[8] == a[0]) continue;
i = a[0] * 100 + a[1] * 10 + a[2];
j = a[3] * 100 + a[4] * 10 + a[5];
k = a[6] * 100 + a[7] * 10 + a[8];
if (j == 2 * i && k == 3 * i) printf("%d %d %d\n",i,j,k);
}
}
}
}
}
}
}
}
}
//system("pause");//为了看Visual Studio命令框输出加的
return 0;
}
方法二：逆向思维，首先枚举满足1:2:3关系的三位数（a,a×2,a×3)，然后判断它们中的每位数字是否符合不重复地出现1-9（即有1-9这9个数字）。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Judge(int a, int b, int c){
int sum = 0;
int q[15];
memset(q, 0, sizeof(q));//清零
q[a / 100] = q[a / 10 % 10] = q[a % 10] = 1;
q[b / 100] = q[b / 10 % 10] = q[b % 10] = 1;
q[c / 100] = q[c / 10 % 10] = q[c % 10] = 1;
//如果q数组的q[1]--q[9]都是1，说明a，b，c一共包含了1-9的每一个数
for (int i = 1; i <= 9; i++){
sum += q[i];
}
if (sum == 9) return 1;
else return 0;
}
int main(){
int a, b, c;
int flag;
for (a = 123; a <= 334; a++){
b = 2 * a;
c = 3 * a;
flag = Judge(a, b, c);
if (flag == 1) printf("%d %d %d\n", a, b, c);
}
//system("pause");
return 0;
}
首先从123开始枚举到334，因为123是可能出现的最小数，且第一个数不可能比334大，所以可以减少需要for循环的范围。判断1-9是否都出现的方法可以用数组，把各个数的百十个位拆开，用数组对应的那个数的下标的数组元素值置为1表示出现。（如出现了数字3，则令a[3]=1）。
网友评论