[知乎问题]六元一次方程整数解?

回复
头像
vicyang
版主
版主
帖子: 56
注册时间: 2016年07月21日 20:35
联系:

[知乎问题]六元一次方程整数解?

帖子 vicyang »

先发链接:
https://www.zhihu.com/question/50470846/answer/121111464
六元一次方程整数解?
1999a+1299b+1499c+2799d+2499e+3299f=2328450.其中abcdef均为整数(可以为0)。
其中,a小于或等于607,b小于或等于534,c小于或等于60,小于或等于660,e小于或等于100,f小于或等于209。
这个可以通过编程或者其他什么办法求整数解吗
范围:正整数和0,以及问题中限定的范围
头像
vicyang
版主
版主
帖子: 56
注册时间: 2016年07月21日 20:35
联系:

Re: [知乎问题]六元一次方程整数解?

帖子 vicyang »

到知乎上回答了…… 感觉在班门弄斧 :(

递归低效率版,Perl
my  @init = (0, 0, 0, 0, 0, 0);                  #初始值
our @e = (1999, 1299, 1499, 2799, 2499, 3299); #系数
our @limit = (607, 534, 60, 660, 100, 209); #范围
our $check = 2328450; #校验

func( \@init, 0 );

sub func
{
our @e;
our @limit;
our $check;

my ($ref, $lv) = (shift, shift);

if ($lv <= $#$ref)
{
for my $n ( 0 .. $limit[$lv] )
{
$ref->[$lv] = $n;
func( $ref, $lv+1 );
}
}
else
{
my $sum = 0;
for my $idx ( 0 .. $#$ref )
{
$sum += $ref->[$idx] * $e[$idx];
}
if ($sum == $check)
{
print join(", ", @$ref), "\n";
}
}
}
暴力6层循环,C语言版
#include <stdio.h>

int main(int argc, char *argv[])
{
long a,b,c,d,e,f;
long limit[6] = {607, 534, 60, 660, 100, 209};
long coe[] = {1999, 1299, 1499, 2799, 2499, 3299};
long sum;

for (a = 0; a <= limit[0]; a++ ) {
for (b = 0; b <= limit[1]; b++ ) {
for (c = 0; c <= limit[2]; c++ ) {
for (d = 0; d <= limit[3]; d++ ) {
for (e = 0; e <= limit[4]; e++ ) {
for (f = 0; f <= limit[5]; f++ ) {

sum = a*coe[0] + b*coe[1] + c*coe[2] +
d*coe[3] + e*coe[4] + f*coe[5];

if (sum == 2328450)
{
printf("%d %d %d %d %d %d\n", a,b,c,d,e,f);
}

}}}}}}
return 0;
}
6层循环,批处理版

代码: 全选

@echo off &setlocal enabledelayedexpansion

set var=a b c d e f
set /a a=607, b=534, c=60, d=660, e=100, f=209
set /a exp=0, check=2328450

for %%x in ( %var% ) do (
    set fo="for /l %%%%x in (0, 1, !%%x!) do (!fo!"
    set end="!end!)"
    set exp= !exp! + %%%%x
    set echo=!echo! %%%%x
)

%fo:"=%
    set /a sum = %exp%
    if "!sum!" == "%check%" (
        echo %echo%
        )
 
%end:"=%
pause
分而治之,Perl版
our $check = 2328450;                           #校验
our @limit = (607, 534, 60, 660, 100, 209); #范围
our @e = (1999, 1299, 1499, 2799, 2499, 3299); #系数

my $sum;
my %hash;

print "step1\n";
for my $a ( 0 .. $limit[0] )
{
for my $b ( 0 .. $limit[1] )
{
for my $c ( 0 .. $limit[2] )
{
$sum = $a * $e[0] + $b * $e[1] + $c * $e[2];
$hash{$sum} = [$a, $b, $c];
}
}
}

print "step2\n";
my $part1;
my $part2;
open $WRT, ">:raw", "D:/Result.txt";
for my $d ( 0 .. $limit[3] )
{
for my $e ( 0 .. $limit[4] )
{
for my $f ( 0 .. $limit[5] )
{
$part2 = $d * $e[3] + $e * $e[4] + $f * $e[5];
$part1 = $check - $part2;
if ( exists $hash{$part1} )
{
print $WRT join( ", ", @{ $hash{$part1} }, $d, $e, $f );
print $WRT "\n";
}
}
}
}
close $WRT;
<STDIN>;
i7,用时约40秒,输出282,819 KB大小的文件。
这里有一个疏忽,

$sum = $a * $e[0] + $b * $e[1] + $c * $e[2];
$hash{$sum} = [$a, $b, $c];


$sum 可能是相同的值,从而忽略了一些不同情况下的 a b c ,保存所有情况下的a b c,提示 out of memory。虽然可以保存到文件,然后建立索引。。。
happy886rr
渐入佳境
渐入佳境
帖子: 45
注册时间: 2016年09月27日 16:11
联系:

Re: [知乎问题]六元一次方程整数解?

帖子 happy886rr »

解六元线性丢番图方程1999a+1299b+1499c+2799d+2499e+3299f=2328450 (约数条件a,b,…,f∈N)时,可先顺次求出最大公约数(1999,1299)=d2, (d2,1499)=d3, (d3,2799)=d4, (d4,2499)=d5, (d5,3299)=d6;易知d2=d3=d4=d5=d6=1;
以下为伪码,只示思路。
则化为ti型参数方程:
{
1999a+1299b=t2
t2+1499c=t3
t3+2799d=t4
t4+2499e=t5
t5+3299f=2328450 //其中t2~t5为参数
}

由于你说a,b,…,f∈N自然数,这就好办了,很容易的。从最后一个ti型参数方程“t5+3299f=2328450”入手也就是t5=2328450-3299f,这是标准的二元线性丢番图,先找出其一个解{f=0,t5=2328450},
直接套公式(易求出)其通解为:
{
f=0+θ, //由于题目还给出f<=209,所以θ∈[0,209]闭区
t5=2328450-3299θ; //其中θ∈[0,209]
}

这样f的解就都求出来,直接把求得的t5参值代入到倒数第二个ti型参数方程“t4+2499e=t5”中,继续重复调用二元线性丢番图丢番图的求解公式,得到全部e的解和t4参值。

依次类推
{
倒数第三个ti型参数方程
倒数第四个ti型参数方程
倒数第五个ti型参数方程
}
由于纯粹数学原理直接套公式,结合a,b,…,f的取值范围限制,用大量if判断break中断,从而降到极少量的for循环,而且关键是一个解都不漏,还有结合1999a+1299b=t2的特殊性(只有这个才需要打表)。mathematics软件也是用的这方法,解丢番图,就调用丢番图模型去解。
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 0 访客