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

头像
vicyang
版主
版主
帖子: 47
注册时间: 2016年07月21日 20:35
拥有现金: 锁定
储蓄: 锁定
Has thanked: 7 times
联系:

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

帖子 #1 vicyang » 2016年09月10日 10:24

先发链接:
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
版主
版主
帖子: 47
注册时间: 2016年07月21日 20:35
拥有现金: 锁定
储蓄: 锁定
Has thanked: 7 times
联系:

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

帖子 #2 vicyang » 2016年09月13日 00:52

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

递归低效率版,Perl
Code: [全选] [展开/收缩] [Download] (Untitled.pl)
  1. my  @init = (0, 0, 0, 0, 0, 0);                  #初始值
  2. our @e = (1999, 1299, 1499, 2799, 2499, 3299);  #系数
  3. our @limit = (607, 534, 60, 660, 100, 209);     #范围
  4. our $check = 2328450;                           #校验
  5.  
  6. func( \@init, 0 );
  7.  
  8. sub func
  9. {
  10.     our @e;
  11.     our @limit;
  12.     our $check;
  13.  
  14.     my ($ref, $lv) = (shift, shift);
  15.  
  16.     if ($lv <= $#$ref)
  17.     {
  18.         for my $n ( 0 .. $limit[$lv] )
  19.         {
  20.             $ref->[$lv] = $n;
  21.             func( $ref, $lv+1 );
  22.         }
  23.     }
  24.     else
  25.     {
  26.         my $sum = 0;
  27.         for my $idx ( 0 .. $#$ref )
  28.         {
  29.             $sum += $ref->[$idx] * $e[$idx];
  30.         }
  31.         if ($sum == $check)
  32.         {
  33.             print join(", ", @$ref), "\n";
  34.         }
  35.     }
  36. }


暴力6层循环,C语言版
Code: [全选] [展开/收缩] [Download] (Untitled.c)
  1. #include <stdio.h>
  2.  
  3. int main(int argc, char *argv[])
  4. {
  5.     long a,b,c,d,e,f;
  6.     long limit[6] = {607, 534, 60, 660, 100, 209};
  7.     long coe[] = {1999, 1299, 1499, 2799, 2499, 3299};
  8.     long sum;
  9.  
  10.     for (a = 0; a <= limit[0]; a++ ) {
  11.     for (b = 0; b <= limit[1]; b++ ) {
  12.     for (c = 0; c <= limit[2]; c++ ) {
  13.     for (d = 0; d <= limit[3]; d++ ) {
  14.     for (e = 0; e <= limit[4]; e++ ) {
  15.     for (f = 0; f <= limit[5]; f++ ) {
  16.  
  17.         sum = a*coe[0] + b*coe[1] + c*coe[2] +
  18.               d*coe[3] + e*coe[4] + f*coe[5];
  19.  
  20.         if (sum == 2328450)
  21.         {
  22.             printf("%d %d %d %d %d %d\n", a,b,c,d,e,f);
  23.         }
  24.  
  25.     }}}}}}
  26.     return 0;
  27. }


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版
Code: [全选] [展开/收缩] [Download] (Untitled.pl)
  1. our $check = 2328450;                           #校验
  2. our @limit = (607, 534, 60, 660, 100, 209);     #范围
  3. our @e = (1999, 1299, 1499, 2799, 2499, 3299);  #系数
  4.  
  5. my $sum;
  6. my %hash;
  7.  
  8. print "step1\n";
  9. for my $a ( 0 .. $limit[0] )
  10. {
  11.     for my $b ( 0 .. $limit[1] )
  12.     {
  13.         for my $c ( 0 .. $limit[2] )
  14.         {
  15.             $sum = $a * $e[0] + $b * $e[1] + $c * $e[2];
  16.             $hash{$sum} = [$a, $b, $c];
  17.         }
  18.     }
  19. }
  20.  
  21. print "step2\n";
  22. my $part1;
  23. my $part2;
  24. open $WRT, ">:raw", "D:/Result.txt";
  25. for my $d ( 0 .. $limit[3] )
  26. {
  27.     for my $e ( 0 .. $limit[4] )
  28.     {
  29.         for my $f ( 0 .. $limit[5] )
  30.         {
  31.             $part2 = $d * $e[3] + $e * $e[4] + $f * $e[5];
  32.             $part1 = $check - $part2;
  33.             if ( exists $hash{$part1} )
  34.             {
  35.                 print $WRT join( ", ", @{ $hash{$part1} }, $d, $e, $f );
  36.                 print $WRT "\n";
  37.             }
  38.         }
  39.     }
  40. }
  41. close $WRT;
  42. <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
拥有现金: 锁定
储蓄: 锁定
Has thanked: 14 times
Been thanked: 14 times
联系:

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

帖子 #3 happy886rr » 2016年09月27日 20:19

解六元线性丢番图方程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;
以下为伪码,只示思路。
Code: [全选] [展开/收缩] [Download] (Untitled.c)
  1. 则化为ti型参数方程:
  2. {
  3.     1999a+1299b=t2
  4.     t2+1499c=t3
  5.     t3+2799d=t4
  6.     t4+2499e=t5
  7.     t5+3299f=2328450    //其中t2~t5为参数
  8. }
  9.  
  10. 由于你说a,b,,f∈N自然数,这就好办了,很容易的。从最后一个ti型参数方程“t5+3299f=2328450”入手也就是t5=2328450-3299f,这是标准的二元线性丢番图,先找出其一个解{f=0,t5=2328450},
  11. 直接套公式(易求出)其通解为:
  12. {
  13.     f=0+θ,               //由于题目还给出f<=209,所以θ∈[0,209]闭区
  14.     t5=2328450-3299θ;    //其中θ∈[0,209]
  15. }
  16.  
  17. 这样f的解就都求出来,直接把求得的t5参值代入到倒数第二个ti型参数方程“t4+2499e=t5”中,继续重复调用二元线性丢番图丢番图的求解公式,得到全部e的解和t4参值。
  18.  
  19. 依次类推
  20. {
  21.     倒数第三个ti型参数方程
  22.     倒数第四个ti型参数方程
  23.     倒数第五个ti型参数方程
  24. }

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


回到 “Math”

在线用户

用户浏览此论坛: 没有注册用户 和 0 访客