急求>>容易的多元一次方程题，求任何一组解的算法
急求>>简单的多元一次方程题，求任何一组解的算法
请教大家给个简单的方法或思路，谢谢。
目前有一家自助餐馆的销售数据[每个账单的总钱数“含税”]：20.85 , 11.32 , 8.58 等等。
当前这家餐馆的收费一共有四种：成人(A)8.99/人，孩子(B)4.95/人，饮料(C)1.69/份，茶(D)0.5/份
当前餐馆的税率为：0.06.
问题就是：如何求得A,B,C,D的任意一组正数解？如：
20.85=(8.99*A+4.95*B+1.69*C+0.5*D)*1.06 =(8.99*2+4.95*0+1.69*1+0.5*0)*1.06 即一组解为：A=2，B=0，C=1，D=0
因为数据很多，所以需要写个程序处理一下，请各位指点迷津。谢谢。
------解决方案--------------------
解方程
------解决方案--------------------
可以这样，穷举出所有组合：
请教大家给个简单的方法或思路，谢谢。
目前有一家自助餐馆的销售数据[每个账单的总钱数“含税”]：20.85 , 11.32 , 8.58 等等。
当前这家餐馆的收费一共有四种：成人(A)8.99/人，孩子(B)4.95/人，饮料(C)1.69/份，茶(D)0.5/份
当前餐馆的税率为：0.06.
问题就是：如何求得A,B,C,D的任意一组正数解？如：
20.85=(8.99*A+4.95*B+1.69*C+0.5*D)*1.06 =(8.99*2+4.95*0+1.69*1+0.5*0)*1.06 即一组解为：A=2，B=0，C=1，D=0
因为数据很多，所以需要写个程序处理一下，请各位指点迷津。谢谢。
------解决方案--------------------
解方程
------解决方案--------------------
可以这样，穷举出所有组合：
- C/C++ code
struct int_struct{int i1,i2,i3,i4};
map<float ,int_struct> mymap;
for(int i1 = 0;i1<100;i1++)
for(int i2 = 0;i2<100;i2++)
for(int i3 = 0;i3<100;i3++)
for(int i4 = 0;i4<100;i4++)
float key = (8.99*i1+4.95*i2+1.69*i3+0.5*i4)*1.06;
//将key,i1,i2,i3,i4对应关系保存起来，要用时直接查询即可
int_struct res1(i1,i2,i3,i4);
mymap[key] = res1;
------解决方案--------------------
漏了大括号
- C/C++ code
struct int_struct{int i1,i2,i3,i4};
map<float ,int_struct> mymap;
for(int i1 = 0;i1<100;i1++)
for(int i2 = 0;i2<100;i2++)
for(int i3 = 0;i3<100;i3++)
for(int i4 = 0;i4<100;i4++)
{
float key = (8.99*i1+4.95*i2+1.69*i3+0.5*i4)*1.06;
//将key,i1,i2,i3,i4对应关系保存起来，要用时直接查询即可
int_struct res1(i1,i2,i3,i4);
mymap[key] = res1;
}
------解决方案--------------------
可以根据总和确定每个值大致的范围，份数又都是整数。确定了范围后用四重int循环，乘以系数后相加等于总和的值都是正数解
------解决方案--------------------
完全背包勉强可以解决这个问题
貌似线性规划更好
------解决方案--------------------
------解决方案--------------------
- C/C++ code
#include <stdio.h>
#include <stdlib.h>
/*
*功能:回代求解(针对上三角形矩阵)
*参数:matrix上三角阵,line矩阵行数
*返回值:解
*/
float *substitUpMethod(float **matrix, int line)
{
float *result, tmp;
int i, j;
for(i=0; i<line; ++i)
{
if(matrix[i][i] == 0)
{
printf("方程无解或者解不惟一!\n");
return NULL;
}
}
result = (float*)malloc(sizeof(float)*line);
result[line-1] = 1;
for(i=line-1; i>=0; --i)
{
tmp = 0;
j = line - 1;
while(j > i)
{
tmp += matrix[i][j] * result[j];
--j;
}
result[i] = (matrix[i][line] - tmp) / matrix[i][i];
}
return result;
}
/*
*功能:用列主元消去法将矩阵变为上三角形矩阵
*参数:matrix矩阵, matrixLine矩阵行数
*
*/
void eliminationMain(float **matrix, long matrixLine)
{
long i, j, k, sub, maxSub;
float tmp;
for(i=0; i<matrixLine-1; ++i)//列
{
maxSub = i;
for(sub=i; sub<matrixLine; ++sub)//找主元素
{
if(matrix[maxSub][i] < matrix[sub][i] || -matrix[sub][i] > matrix[maxSub][i])
maxSub = sub;
}
if(maxSub != i)
{
for(sub=0; sub<=matrixLine; ++sub)
{
tmp = matrix[maxSub][sub];
matrix[maxSub][sub] = matrix[i][sub];
matrix[i][sub] = tmp;
}
}
//第j行的数据 - (第i行的数据 / matrix[i][i])*matrix[j][i]
for(j=i+1; j<matrixLine; ++j)
{
for(k=i+1; k<=matrixLine; ++k)
{
matrix[j][k] -= (matrix[i][k]/matrix[i][i])*matrix[j][i];
}
matrix[j][i] = 0;
}
}
//输出上三角形矩阵
printf("\n 上三角形矩阵为:\n");
for(i=0; i<matrixLine; ++i)
{
for(j=0; j<matrixLine+1; ++j)
{
printf("%13f", matrix[i][j]);
}
printf("\n");
}
}
/*
*功能:输出数组matrix
*参数:数组matrix, line矩阵的行数
*
*/
void display(float **matrix, long line, long row)
{
int i, j;
for(i=0; i<line; ++i)
{
for(j=0; j<row; ++j)
{
printf("%13f ", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
/*
*功能:接收数组matrix
*参数:数组matrix, matrixLine矩阵的行数
*
*/
void inputMatrix(float **matrix, long matrixLine, long matrixRow)
{
int i, j;
printf("请输入矩阵元素:\n");
for(i=0; i<matrixLine; ++i)
{
for(j=0; j<matrixRow; ++j)
{
scanf("%f", &matrix[i][j]);
}
}
}
/*
*功能:输出结果
*参数:结果数组,数组长度
*/
void printResult(float *result, long matrixLine)
{
int i;
if(result == NULL)
return;
printf(" 方程组的解为:\n\t");
for(i = 0; i < matrixLine; ++i)
printf("%13f", result[i]);
printf("\n");
}
/*
*功能:获取文件中矩阵的个数
*返回值:文件中矩阵的个数
*
*/
int getMatrixCnt()
{
FILE *fp;
char ch;
int matrixCnt = 0;
fp = fopen("matrix.txt", "r");
if(fp == NULL)
{
printf("cannot open file!\n");
return -1;
}
while(!feof(fp))
{
ch = fgetc(fp);
if(ch == '#')
++matrixCnt;
}
--matrixCnt;//文件以#开始以#结束
fclose(fp);
return matrixCnt;
}
/*
*功能:获取文件中第matrixIndex个矩阵的信息
*参数:矩阵索引
*返回值:矩阵的信息
*matrixInfo[0]第matrixIndex个矩阵在文件中的位置
*matrixInfo[1]第matrixIndex个矩阵的行数
*matrixInfo[2]第matrixIndex个矩阵的列数
*/
long *getMatrixInfo(int matrixIndex)
{
FILE *fp;
char ch;
long *matrixInfo, line = 0, row = 0;
matrixInfo = (long*)malloc(sizeof(long)*3);
fp = fopen("matrix.txt", "r");
while(!feof(fp))
{
ch = fgetc(fp);
if(ch == '#')
{
--matrixIndex;
if(matrixIndex == 0)
{
matrixInfo[0] = ftell(fp);
ch = fgetc(fp);
while(ch != '#')
{
ch = fgetc(fp);
if(ch == 10)
++line;
else if(ch == ' ')
++row;
}
break;
}
}
}
matrixInfo[1] = line;
matrixInfo[2] = (row + line) / line;
fclose(fp);
return matrixInfo;
}
/*
*功能:将文件中position位置处的矩阵存储地数组matrix中
*参数:matrix数组, position矩阵位置, line矩阵行数
*
*/
void getMatrix(float **matrix, long position, long line, long row)
{
FILE *fp;
fp = fopen("matrix.txt", "r");
int i = 0, j = 0;
float tmp;
if(fp == NULL)
{
printf("cannot open file!\n");
return;
}
fseek(fp, position, SEEK_SET);
while(i < line)
{
fscanf(fp, "%f", &tmp);
matrix[i][j++] = tmp;
if(j == row)
{
++i;
j = 0;
}
}
fclose(fp);
}
/*
*功能:给矩阵申请空间
*参数:matrixLine矩阵的行数和列数
*返回值:矩阵的首地址
*/
float** initMatrix(long matrixLine, long matrixRow)
{
float** matrix;
int i;
matrix = (float**)malloc(sizeof(float*)*matrixLine);
for (i=0; i<matrixLine; ++i)
*(matrix+i) = (float*)malloc(sizeof(float)*matrixRow);
return matrix;
}
/*
*功能:释放空间
*参数:矩阵,矩阵的行数
*返回值:NULL
*/
float **freeMatrix(float** matrix, long matrixLine)
{
int i;
for(i = 0; i < matrixLine; ++i)
free(matrix[i]);
free(matrix);
return NULL;
}
int main()
{
int matrixCnt, matrixIndex;
long *matrixInfo = NULL, position, matrixLine, matrixRow;
float **matrix = NULL, *result = NULL;
float **matrixL = NULL, **matrixU = NULL;
//从文件读取矩阵
matrixCnt = getMatrixCnt();
printf("文件中有%d个矩阵,读取第matrixIndex个矩阵: matrixIndex = ", matrixCnt);
scanf("%d", &matrixIndex);
while(matrixIndex > matrixCnt)
{
printf("输入有误,请重新输入: matrixIndex = ");
scanf("%d", &matrixIndex);
fflush(stdin);
}
matrixInfo = getMatrixInfo(matrixIndex);
position = matrixInfo[0];
matrixLine = matrixInfo[1];
matrixRow = matrixInfo[2];
free(matrixInfo);
matrixInfo = NULL;
matrix = initMatrix(matrixLine, matrixRow);
getMatrix(matrix, position, matrixLine, matrixRow);
display(matrix, matrixLine, matrixRow);
//高斯列主元素消去法解方程
eliminationMain(matrix, matrixLine);
result = substitUpMethod(matrix, matrixLine);
printResult(result, matrixLine);
matrix = freeMatrix(matrix, matrixLine);
free(result);
result = NULL;
return 0;
}
从文件读数据
文件名matrix.txt
内容如下
#
1 2 1 -2 -1
2 5 3 -2 3
-2 -2 3 5 15
1 3 2 5 9
#
1 1 0 4 1
-1 1 1 3 -2
1 3 5 -4 -4
0 1 2 -1 -2
#
文件内容所代表的意思
如这一组数据
1 2 1 -2 -1
2 5 3 -2 3
-2 -2 3 5 15
1 3 2 5 9
表示
1*x1 + 2*x2 + 1*x3 + (-2)*x4 = -1
2*x1 + 5*x2 + 3*x3 + (-2)*x4 = 3
.......
运行结果
文件中有2个矩阵,读取第matrixIndex个矩阵: matrixIndex = 1
1.000000 2.000000 1.000000 -2.000000 -1.000000
2.000000 5.000000 3.000000 -2.000000 3.000000
-2.000000 -2.000000 3.000000 5.000000 15.000000
1.000000 3.000000 2.000000 5.000000 9.000000
上三角形矩阵为:
2.000000 5.000000 3.000000 -2.000000 3.000000
0.000000 3.000000 6.000000 3.000000 18.000000
0.000000 0.000000 0.500000 -0.500000 0.500000
0.000000 0.000000 0.000000 5.000000 5.000000
方程组的解为:
-3.000000 1.000000 2.000000 1.000000
Press any key to continue