1

我是 Python 的初学者，并尝试使用MIT 6.00，提供的页面是作业页面。

我在作业 2中，我必须找到丢番图方程的解，我的数学真的不是很好，所以我试图尽可能多地理解它的作用，并想出一个解决方案。

这就是我要做的：

def test(x):
    for a in range(1,150):
        for b in range(1,150):
            for c in range(1,150):
                y = 6*a+9*b+20*c
                if y == x:
                    print "this --> " , a, b, c
                    break
                else : ##this to see how close i was to the number
                    if y - x < 3: 
                        print a, b, c , y

作业指出有 的解决方案50, 51, 52, 53, 54, and 55，但不幸的是，脚本只能获得 的解决方案50, 53 and 55。

如果有人解释我的代码有什么问题，或者我根本不理解丢番图方程，我将非常感激，请告诉我这是怎么回事以及如何找到解决方案，因为我无法得到作业解释进入我的脑海。

谢谢。

4

9 回答 9

4

作业说：

要确定是否有可能恰好购买 n 个 McNuggets，必须求解丢番图方程：找到a、b 和 c 的非负整数值，使得 6a + 9b + 20c = n。

看来您必须在函数范围内包含零。这样，您就可以找到所需的所有数字的解决方案。

于 2012-09-25T14:32:55.503 回答
3

一个解决方案

6*a+9*b+20*c = 51

对于整数a, b,c必须至少有一个整数 0 或负数。一些解决方案是

6*7 + 9*1 + 20*0 = 51
6*0 + 9*(-1) + 20*3 = 51

根据分配中的约束，您需要在可能的系数中包含 0 甚至负数。

于 2012-09-25T14:27:27.290 回答
2

51 的解决方案是5*9 + 1*6。

提示：在哪里20？这对它的系数意味着什么？

54 的解决方案是3*20 + (-1)*6。剩下的你自己想办法。

于 2012-09-25T14:27:17.070 回答
1

首先，您可以有效地利用边界分析。给定

6a + 9b + 20c = n
0 <= a
0 <= b
0 <= c

我们可以系统地将成对的 {a, b, c} 设置为 0，以推断剩余变量的上限。这给了我们

a <= floor(n / 6)
b <= floor(n / 9)
c <= floor(n / 20)

此外，如果您选择一种策略（例如，分配 c 然后 b 然后 a），您可以进一步收紧上限，例如：

b <= floor((n - 20c) / 9)

此外，要分配的最后一个变量必须是其他变量的函数：您不需要搜索它。

于 2012-09-26T07:04:56.713 回答
1

您可以将 a、b、c 的范围从 0 到 150 开始。

实际上，即使我是初学者，也只是从 MIt 6.00 开始。在阅读他们的问题时，我认为 150 是无法接受的最大数量的限制。

于 2013-06-13T11:36:20.527 回答
0

这是 Perl 中的一个解决方案。而是使用正则表达式来破解。

按照这篇博文使用正则表达式求解代数方程。

我们可以将以下脚本用于 3x + 2y + 5z = 40

#!/usr/bin/perl
$_ = 'o' x 40;
$a = 'o' x 3;
$b = 'o' x 2;
$c = 'o' x 5;
$_ =~ /^((?:$a)+)((?:$b)+)((?:$c)+)$/;
print "x = ", length($1)/length($a), "\n";
print "y = ", length($2)/length($b), "\n";
print "z = ", length($3)/length($c), "\n";

输出：x=11，y = 1，z = 1

著名的最古老的钢琴拼图最终变成了一个 3 变量方程

此方法适用于变量实际为正且常数为正的条件。

于 2013-08-09T01:54:09.530 回答
0

检查这个我改编自你的。它似乎解决了你的问题：

variables=range(0,10)
exams=range(51,56)
for total in exams:
    for a in variables:
        for b in variables:
            for c in variables:
                if total==4*a+6*b+20*c:
                    print a, 'four pieces', b, 'six pieces','and', c ,'twenty pieces', 'for a total of', total
于 2015-01-04T03:45:43.357 回答
0

break 函数只会跳出最近的循环。下面的代码使用一个指标来打破每个循环。

    n = 1     # n starting from 1
    count = 0 # Count + 1 everytime we find a possible value. 
              # Reset = 0 after a non-possible value. 
    notPossibleValue = ()
    while True:
        ind = 0 # become 1 if int solutions were found
        for c in range (0,n/20+1):
            if ind == 1: break 
            for b in range (0,n/9+1):
                if ind == 1: break 
                for a in range (0, n/6+1):
                    if (n-20*c) == (b*9+a*6):
                        count += 1
                        ind = 1                    
                        # print 'n=', n, a,b,c, 'count', count                       
                        break # Break out of "a" loop
        if ind == 0:
            count = 0
            notPossibleValue += (n,)
            # print notPossibleValue, 'count', count
        if count == 6:
            print 'The largest number of McNuggets that cannot be bought in exact quantity is', notPossibleValue[-1]
            break
        n += 1
于 2016-10-25T13:56:56.310 回答
0 
n=1
a=0
b=0
c=0
mcnugget = []
for i in range (n,100):
   for a in range (0,20):
       if  6*a + 9* b +20*c ==i:
           mcnugget.append(i)
           break
       else:
            for b in range (0,12):
                if  6*a + 9* b +20*c ==i:
                    mcnugget.append(i)
                    break
                else:
                    for c in range(0,5):
                        if  6*a + 9* b +20*c ==i:
                            mcnugget.append(i)
                            break
   else:
        if i>8:
            if mcnugget[-1]==mcnugget[-2]+1==mcnugget[-3]+2==mcnugget[-4]+3==mcnugget[-5]+4==mcnugget[-6]+5 and mcnugget[-6]>0 :
                break

mcnugget = set (mcnugget)
mcnugget = list (mcnugget)
count = 0
for z in mcnugget:
   count += 1
   if mcnugget [count]==mcnugget [count-1]+1==mcnugget [count-2]+2==mcnugget [count-3]+3==mcnugget [count-4]+4==mcnugget[count-5]+5:
      biggestN= mcnugget[count-6]
      break
#print (mcnugget)
biggestN = str(biggestN)

print ('Largest number of McNuggets that cannot be bought in exact quantity: <'+ biggestN +'>')
于 2018-07-18T16:12:36.747 回答