题目梗概
约翰需要将三种饲料调配成 a:b:c 的成品的比例，所以他进行了三次购买，每次购买的数量比例为 x:y:z.
是否能够用购买的饲料组成a:b:c的比例，如果可以输出 三种饲料的最小份数和成品的份数
思考
题目可以用暴力枚举过，也可以用列方程组用高斯消元法过。
详细看注释
暴力枚举法-#include <cstdio> #include <cmath> #include <algorithm> #include <iostream> using namespace std; int Aim[4]; struct node{ int x1,x2,x3; }fuck[4]; int used[4][105]; int main(){ scanf("%d%d%d",&Aim[1],&Aim[2],&Aim[3]); for(int i=1;i<=3;i++) scanf("%d%d%d",&fuck[i].x1,&fuck[i].x2,&fuck[i].x3); if(Aim[1]==0 && Aim[2]==0 && Aim[3]==0){ //特判 printf("0 0 0 0"); return 0; } for(int ans=1;ans<=100;ans++){ //这里是把成品的100次情况全部计算出来 为后面节省时间 used[1][ans] = ans * Aim[1]; used[2][ans] = ans * Aim[2]; used[3][ans] = ans * Aim[3]; } for(register int i=0;i<=100;i++) //i分 x1饲料 for(register int j=0;j<=100;j++)//j份 x2饲料 for(register int k=0;k<=100;k++){ //k份 x3饲料 if(i==0 && j==0 && k==0 ) continue; int l1 = (fuck[1].x1*i)+(fuck[2].x1*j)+(fuck[3].x1*k); int l2 = (fuck[1].x2*i)+(fuck[2].x2*j)+(fuck[3].x2*k); int l3 = (fuck[1].x3*i)+(fuck[2].x3*j)+(fuck[3].x3*k); //别问我为什么选100这个数字 你也可以选10 20 30 40 试试看 这些都是会WA的 for(register int ans=1;ans<=100;ans++){ if(used[1][ans]>l1 || used[2][ans]>l2 || used[3][ans]>l3) break; if(used[1][ans]==l1 && used[2][ans]==l2 && used[3][ans]==l3){ printf("%d %d %d %d",i,j,k,ans); return 0; } } } printf("NONE"); //如果最后还是没有结果 那么一定是不能组成的 return 0; } 高斯消元法-
#include <iostream> #include <cmath> #include <cstdio> using namespace std; const int max_n = 5; int equ, var;// 方程数量， var个变元 所以增广矩阵有equ行，var +1 列 （最后一列为你懂的） int a[max_n][max_n], ta[max_n][max_n]; int x[max_n]; //解集 int gcd(int a, int b){return a == 0 ? b : gcd(b % a , a);} int lcm(int a, int b){return a / gcd(a, b) * b;} bool guess() { int row=0, col=0; //行，列 for (; row != equ && col != var; ++ row, ++ col) { int max_row = row; for (int i = row + 1; i != equ; ++ i) if (a[i][col] > a[max_row][col]) max_row = i; if (!a[max_row][col]) return false; for (int i = col; i <= var; ++ i) swap(a[row][i], a[max_row][i]); for (int i = row + 1; i != equ; ++ i) { if (!a[i][col]) continue; int tmp = lcm(abs(a[row][col]), abs(a[i][col])); int ta = tmp / a[row][col]; //正负，为他们自己的符号 int tb = tmp / a[i][col]; for (int j = col; j <= var; ++ j) a[i][j] = a[i][j] * tb - a[row][j] * ta; } } row = equ - 1, col = var - 1; for (;row >= 0; -- row, -- col) { int tmp = a[row][var]; for (int i = col + 1; i != var; ++ i) tmp -= a[row][i] * x[i]; if (tmp % a[row][col]) return false; x[col] = tmp / a[row][col]; if (x[col] < 0) return false; } return true; } void init() { for (int i = 0; i != 3; ++ i) cin >> ta[i][var]; for (int i = 0; i != 3; ++ i) for (int j = 0; j != 3; ++ j) cin >> ta[j][i]; } void doit() { for (int ans = 1; ans <= 100; ++ ans) { for (int i = 0; i != 3; ++ i) for (int j = 0; j != 4; ++ j) a[i][j] = ta[i][j]; for (int i = 0; i != 3; ++ i) a[i][3] *= ans; if (guess()) { for (int i = 0; i != var; ++ i) cout<<x[i]<<" "; cout<<ans<<endl; return; } } cout<<"NONE"<<endl; } int main() { equ = var = 3; init(); doit(); return 0; }
转载于:https://www.cnblogs.com/OIerLYF/p/7055570.html
