好库网首页 | 我的好库
好库网 好库网社区
IT社区 » C/C++ » C++论坛 » 一道习题(消元法)
回复 发帖

查看:1401    回复:2 一道习题(消元法)
访问bruceteen的空间
发表于 2011/3/29 14:50:13
1楼
今有5羊4犬3鸡2兔值钱1496,4羊2犬6鸡3兔值钱1175,3羊1犬7鸡5兔值钱958,2羊3犬5鸡1兔值钱861,求羊值多少钱?

#include <cstddef>
#include <cassert>

// 求最大公约数
int gcd( int a, int b )
{
    if(a<0) a = -a;
    if(b<0) b = -b;
    if(a==0) return b;
    if(b==0) return a;
    if(a<b) { int c=a; a=b; b=c; }

    for( int c; (c=a%b)!=0; a=b,b=c );
    return b;
}

// 消元法
template<size_t M> void elimination( int (&buf)[M-1][M] )
{
    size_t N = M-1;

    for( size_t i=4; i!=1; --i )
    {
        if( buf[i-1][i] == 0 )
        {
            size_t j;
            for( j=0; j<i-1 && buf[j][i]==0; ++j );
            if( j != i-1 )
            {
                for( size_t k=0; k<=i; ++k )
                {
                    int tmp = buf[j][k];
                    buf[j][k] = buf[i-1][k];
                    buf[i-1][k] = tmp;
                }
            }
        }

        for( size_t j=0; j<i-1; ++j )
        {
            if( buf[j][i] == 0 )
                continue;

            int gcdn = gcd(buf[j][i],buf[i-1][i]);
            int x = buf[i-1][i]/gcdn;
            int y = buf[j][i]/gcdn;
            for( size_t k=0; k<i; ++k )
            {
                buf[j][k] = buf[j][k]*x - buf[i-1][k]*y;;
            }
        }
    }

    if( buf[0][1] == 0 )
        buf[0][0] = 0; // resultless
    else
    {
        for( size_t i=0; i<N; ++i )
        {
            int sum = buf[i][0];
            for( size_t j=1; j<i+1; ++j )
                sum -= buf[i][j]*buf[0][j];
            buf[0][i+1] = sum/buf[i][i+1];
            assert( sum%buf[i][i+1] == 0 );
        }
        buf[0][0] = 1;
    }
}

#include <iostream>
using namespace std;
int main()
{
    int buf[4][5] = { 1496, 5, 4, 3, 2
                    , 1175, 4, 2, 6, 3
                    , 958 , 3, 1, 7, 5
                    , 861 , 2, 3, 5, 1 };

    elimination( buf );

    if( buf[0][0] == 0 )
        cout << "resultless" << endl;
    else
    {
        for( size_t i=1; i<=sizeof(buf)/sizeof(buf[0]); ++i )
            cout << ' ' << buf[0][i] << ' ';
        cout << endl;
    }

    return 0;
}
访问bruceteen的空间
发表于 2011/3/29 14:51:14
2楼
输出结果是:
羊177  犬121  鸡23  兔29
访问simula的空间
发表于 2011/3/29 14:55:29
3楼
呃.矩阵运算~
您需要登录后才可以回帖 登录 | 注册
回复 发帖